{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T08:42:37Z","timestamp":1769071357521,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":44,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,7,15]],"date-time":"2023-07-15T00:00:00Z","timestamp":1689379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,7,15]]},"DOI":"10.1145\/3583133.3596394","type":"proceedings-article","created":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T23:30:33Z","timestamp":1690241433000},"page":"2195-2202","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Encoding the At-Most-One Constraint for QUBO and Quantum Annealing: Experiments with the N-Queens problem"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6254-6389","authenticated-orcid":false,"given":"Philippe","family":"Codognet","sequence":"first","affiliation":[{"name":"JFLI - Sorbonne University \/ CNRS, Tokyo, Japan"},{"name":"The University of Tokyo, Tokyo, Japan"}]}],"member":"320","published-online":{"date-parts":[[2023,7,24]]},"reference":[{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1032-4"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.3389\/fphy.2019.00048"},{"key":"e_1_3_2_1_4_1","volume-title":"22th Conference on Evolutionary Computation in Combinatorial Optimization (Lecture Notes in Computer Science","volume":"174","author":"Ayodele Mayowa","year":"2022","unstructured":"Mayowa Ayodele . 2022 . Penalty Weights in QUBO Formulations: Permutation Problems. In EvoCOP 2022 , 22th Conference on Evolutionary Computation in Combinatorial Optimization (Lecture Notes in Computer Science , Vol. 13222), Leslie Perez Caceres and Sebastien Verel (Eds.). Springer, 159-- 174 . Mayowa Ayodele. 2022. Penalty Weights in QUBO Formulations: Permutation Problems. In EvoCOP 2022, 22th Conference on Evolutionary Computation in Combinatorial Optimization (Lecture Notes in Computer Science, Vol. 13222), Leslie Perez Caceres and Sebastien Verel (Eds.). Springer, 159--174."},{"key":"e_1_3_2_1_5_1","volume-title":"Efficient CNF Encoding of Boolean Cardinality Constraints. In CP 2003, 9th international conference on principles and practice of Constraint Programming (Lecture Notes in Computer Science","volume":"122","author":"Bailleux Olivier","year":"2003","unstructured":"Olivier Bailleux and Yacine Boufkhad . 2003 . Efficient CNF Encoding of Boolean Cardinality Constraints. In CP 2003, 9th international conference on principles and practice of Constraint Programming (Lecture Notes in Computer Science , Vol. 2833). Springer, 108-- 122 . Olivier Bailleux and Yacine Boufkhad. 2003. Efficient CNF Encoding of Boolean Cardinality Constraints. In CP 2003, 9th international conference on principles and practice of Constraint Programming (Lecture Notes in Computer Science, Vol. 2833). Springer, 108--122."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.12.043"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-019-00511-0"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-007-9009-3"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASC.2014.2318294"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ab33c2"},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of ModRef10","author":"Chen Jingchao","year":"2010","unstructured":"Jingchao Chen . 2010 . A new SAT encoding of the at-most-one constraint . In Proceedings of ModRef10 , International Workshop on Constraint Reformulation and Modelling. Jingchao Chen. 2010. A new SAT encoding of the at-most-one constraint. In Proceedings of ModRef10, International Workshop on Constraint Reformulation and Modelling."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TQE.2021.3094280"},{"key":"e_1_3_2_1_13_1","volume-title":"Domain-Wall \/ Unary Encoding in QUBO for Permutation Problems. In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). 167--173","author":"Codognet Philippe","year":"2022","unstructured":"Philippe Codognet . 2022 . Domain-Wall \/ Unary Encoding in QUBO for Permutation Problems. In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). 167--173 . Philippe Codognet. 2022. Domain-Wall \/ Unary Encoding in QUBO for Permutation Problems. In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). 167--173."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2019.106027"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.3233\/SAT190014"},{"key":"e_1_3_2_1_16_1","volume-title":"A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem. Science 292, 5516","author":"Farhi Edward","year":"2001","unstructured":"Edward Farhi , Jeffrey Goldstone , Sam Gutmann , Joshua Lapan , Andrew Lundgren , and Daniel Preda . 2001. A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem. Science 292, 5516 ( 2001 ), 472--475. Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda. 2001. A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem. Science 292, 5516 (2001), 472--475."},{"key":"e_1_3_2_1_17_1","volume-title":"Some Slow. In Proceedings of ModRef10","author":"Frisch A.M.","year":"2010","unstructured":"A.M. Frisch and P.A Giannaros . 2010 . SAT Encodings of the At-Most-k Constraint: Some Old, Some New, Some Fast , Some Slow. In Proceedings of ModRef10 , International Workshop on Constraint Reformulation and Modelling. A.M. Frisch and P.A Giannaros. 2010. SAT Encodings of the At-Most-k Constraint: Some Old, Some New, Some Fast, Some Slow. In Proceedings of ModRef10, International Workshop on Constraint Reformulation and Modelling."},{"key":"e_1_3_2_1_18_1","volume-title":"Solving Non-Boolean Satisfiability Problems with Stochastic Local Search: A Comparison of Encodings. Journal of Automated Reasoning 35 (01","author":"Frisch Alan","year":"2005","unstructured":"Alan Frisch , Timothy Peugniez , Anthony Doggett , and Peter Nightingale . 2005. Solving Non-Boolean Satisfiability Problems with Stochastic Local Search: A Comparison of Encodings. Journal of Automated Reasoning 35 (01 2005 ), 143--179. Alan Frisch, Timothy Peugniez, Anthony Doggett, and Peter Nightingale. 2005. Solving Non-Boolean Satisfiability Problems with Stochastic Local Search: A Comparison of Encodings. Journal of Automated Reasoning 35 (01 2005), 143--179."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3176788.3176807"},{"key":"e_1_3_2_1_20_1","volume-title":"Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models. 4OR 17, 4","author":"Glover Fred W.","year":"2019","unstructured":"Fred W. Glover , Gary A. Kochenberger , and Yu Du. 2019. Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models. 4OR 17, 4 ( 2019 ), 335--371. Fred W. Glover, Gary A. Kochenberger, and Yu Du. 2019. Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models. 4OR 17, 4 (2019), 335--371."},{"key":"e_1_3_2_1_21_1","volume-title":"Hammer and Sergiu Rudeanu","author":"Peter","year":"1968","unstructured":"Peter L. Hammer and Sergiu Rudeanu . 1968 . Boolean Methods in Operations Research and Related Areas. Springer . Peter L. Hammer and Sergiu Rudeanu. 1968. Boolean Methods in Operations Research and Related Areas. Springer."},{"key":"e_1_3_2_1_23_1","volume-title":"Panigrahi","author":"Jha Rounak","year":"2018","unstructured":"Rounak Jha , Debaiudh Das , Avinash Dash , Sandhya Jayaraman , Bikash K. Behera , and Prasanta K . Panigrahi . 2018 . A Novel Quantum N-Queens Solver Algorithm and its Simulation and Application to Satellite Communication Using IBM Quantum Experience . arXiv:1806.10221 [quant-ph] Rounak Jha, Debaiudh Das, Avinash Dash, Sandhya Jayaraman, Bikash K. Behera, and Prasanta K. Panigrahi. 2018. A Novel Quantum N-Queens Solver Algorithm and its Simulation and Application to Satellite Communication Using IBM Quantum Experience. arXiv:1806.10221 [quant-ph]"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.58.5355"},{"key":"e_1_3_2_1_25_1","volume-title":"Proceedings of CFV07","author":"Klieber W.","unstructured":"W. Klieber and G. Kwon . 2007. Efficient CNF encoding for selecting 1 from n objects . In Proceedings of CFV07 , 4th Workshop on Constraint in Formal Verification. W. Klieber and G. Kwon. 2007. Efficient CNF encoding for selecting 1 from n objects. In Proceedings of CFV07, 4th Workshop on Constraint in Formal Verification."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-014-9734-0"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.09.003"},{"key":"e_1_3_2_1_28_1","volume-title":"Ising formulations of many NP problems. Frontiers in Physics 2","author":"Lucas Andrew","year":"2014","unstructured":"Andrew Lucas . 2014. Ising formulations of many NP problems. Frontiers in Physics 2 ( 2014 ). Andrew Lucas. 2014. Ising formulations of many NP problems. Frontiers in Physics 2 (2014)."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASP-DAC47756.2020.9045100"},{"key":"e_1_3_2_1_30_1","volume-title":"Research and Development of Common Software Platform for Ising Machines. In 2020 IEICE General Conference. https:\/\/amplify.fixstars.com\/docs\/_static\/paper.pdf","author":"Matsuda Yoshiki","year":"2020","unstructured":"Yoshiki Matsuda . 2020 . Research and Development of Common Software Platform for Ising Machines. In 2020 IEICE General Conference. https:\/\/amplify.fixstars.com\/docs\/_static\/paper.pdf Yoshiki Matsuda. 2020. Research and Development of Common Software Platform for Ising Machines. In 2020 IEICE General Conference. https:\/\/amplify.fixstars.com\/docs\/_static\/paper.pdf"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Catherine C. McGeoch. 2014. Adiabatic Quantum Computation and Quantum Annealing: Theory and Practice. Morgan & Claypool.  Catherine C. McGeoch. 2014. Adiabatic Quantum Computation and Quantum Annealing: Theory and Practice. Morgan & Claypool.","DOI":"10.1007\/978-3-031-02518-1"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74970-7_38"},{"key":"e_1_3_2_1_33_1","volume-title":"Empirical Study on SAT-Encodings of the At-Most-One Constraint. In SMA2020","author":"Nguyen Van-Hau","year":"2020","unstructured":"Van-Hau Nguyen , Van-Quyet Nguyen , Kyungbaek Kim , and Pedro Barahona . 2020 . Empirical Study on SAT-Encodings of the At-Most-One Constraint. In SMA2020 , 9th International Conference on Smart Media and Applications (Jeju, Korea). ACM Press, 470--475. Van-Hau Nguyen, Van-Quyet Nguyen, Kyungbaek Kim, and Pedro Barahona. 2020. Empirical Study on SAT-Encodings of the At-Most-One Constraint. In SMA2020, 9th International Conference on Smart Media and Applications (Jeju, Korea). ACM Press, 470--475."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Shuntaro Okada Masayuki Ohzeki and Shinichiro Taguchi. 2019. Efficient partition of integer optimization problems with one-hot encoding.  Shuntaro Okada Masayuki Ohzeki and Shinichiro Taguchi. 2019. Efficient partition of integer optimization problems with one-hot encoding.","DOI":"10.1038\/s41598-019-49539-6"},{"key":"e_1_3_2_1_35_1","volume-title":"Handbook of Satisfiability","author":"Prestwich S.","unstructured":"S. Prestwich . 2009. CNF Encodings . In Handbook of Satisfiability , H. Van Maaren, T. Walsh, A. Biere, and M. Heule (Eds.). IOS Press , 75--98. S. Prestwich. 2009. CNF Encodings. In Handbook of Satisfiability, H. Van Maaren, T. Walsh, A. Biere, and M. Heule (Eds.). IOS Press, 75--98."},{"key":"e_1_3_2_1_36_1","first-page":"2241","article-title":"Quantum annealing: an overview","volume":"381","author":"Rajak Atanu","year":"2022","unstructured":"Atanu Rajak , Sei Suzuki , Amit Dutta , and Bikas K. Chakrabarti . 2022 . Quantum annealing: an overview . Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 381 , 2241 (dec 2022). Atanu Rajak, Sei Suzuki, Amit Dutta, and Bikas K. Chakrabarti. 2022. Quantum annealing: an overview. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 381, 2241 (dec 2022).","journal-title":"Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences"},{"key":"e_1_3_2_1_37_1","volume-title":"Linear and quadratic reformulations of nonlinear optimization problems in binary variables. Ph. D. Dissertation","author":"Rodr\u00edguez-Heck Elisabeth","unstructured":"Elisabeth Rodr\u00edguez-Heck . 2018. Linear and quadratic reformulations of nonlinear optimization problems in binary variables. Ph. D. Dissertation . University of Li\u00e8ge , Belgium. Elisabeth Rodr\u00edguez-Heck. 2018. Linear and quadratic reformulations of nonlinear optimization problems in binary variables. Ph. D. Dissertation. University of Li\u00e8ge, Belgium."},{"key":"e_1_3_2_1_38_1","volume-title":"Reduction of bivalent maximization to the quadratic case. Cahiers du Centre d'Etudes de Recherche Operationnelle 17, 71","author":"Rosenberg I.","year":"1975","unstructured":"I. Rosenberg . 1975. Reduction of bivalent maximization to the quadratic case. Cahiers du Centre d'Etudes de Recherche Operationnelle 17, 71 ( 1975 ). I. Rosenberg. 1975. Reduction of bivalent maximization to the quadratic case. Cahiers du Centre d'Etudes de Recherche Operationnelle 17, 71 (1975)."},{"key":"e_1_3_2_1_39_1","volume-title":"Foundations of Artificial Intelligence","volume":"2","author":"Rossi Francesca","year":"2006","unstructured":"Francesca Rossi , Peter van Beek , and Toby Walsh ( Eds .). 2006 . Handbook of Constraint Programming . Foundations of Artificial Intelligence , Vol. 2 . Elsevier. Francesca Rossi, Peter van Beek, and Toby Walsh (Eds.). 2006. Handbook of Constraint Programming. Foundations of Artificial Intelligence, Vol. 2. Elsevier."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/11564751_73"},{"key":"e_1_3_2_1_41_1","volume-title":"Quantum Technology and Optimization Problems","author":"Stollenwerk Tobias","unstructured":"Tobias Stollenwerk , Elisabeth Lobe , and Martin Jung . 2019. Flight Gate Assignment with a Quantum Annealer . In Quantum Technology and Optimization Problems . Springer , 99--110. Tobias Stollenwerk, Elisabeth Lobe, and Martin Jung. 2019. Flight Gate Assignment with a Quantum Annealer. In Quantum Technology and Optimization Problems. Springer, 99--110."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2021.3081685"},{"key":"e_1_3_2_1_43_1","volume-title":"Chakrabarti","author":"Tanaka Shu","year":"2017","unstructured":"Shu Tanaka , Ryo Tamura , and Bikas K . Chakrabarti . 2017 . Quantum Spin Glasses, Annealing and Computation (1st ed.). Cambridge University Press , USA. Shu Tanaka, Ryo Tamura, and Bikas K. Chakrabarti. 2017. Quantum Spin Glasses, Annealing and Computation (1st ed.). Cambridge University Press, USA."},{"key":"e_1_3_2_1_44_1","volume-title":"A Quantum N-Queens Solver. Quantum 3 (jun","author":"Torggler Valentin","year":"2019","unstructured":"Valentin Torggler , Philipp Aumann , Helmut Ritsch , and Wolfgang Lechner . 2019. A Quantum N-Queens Solver. Quantum 3 (jun 2019 ), 149. Valentin Torggler, Philipp Aumann, Helmut Ritsch, and Wolfgang Lechner. 2019. A Quantum N-Queens Solver. Quantum 3 (jun 2019), 149."},{"key":"e_1_3_2_1_45_1","volume-title":"Djidjev","author":"Vyskocil Tomas","year":"2019","unstructured":"Tomas Vyskocil , Scott Pakin , and Hristo N . Djidjev . 2019 . Embedding Inequality Constraints for Quantum Annealing Optimization. In Quantum Technology and Optimization Problems, Sebastian Feld and Claudia Linnhoff-Popien (Eds.). Springer , 11--22. Tomas Vyskocil, Scott Pakin, and Hristo N. Djidjev. 2019. Embedding Inequality Constraints for Quantum Annealing Optimization. In Quantum Technology and Optimization Problems, Sebastian Feld and Claudia Linnhoff-Popien (Eds.). Springer, 11--22."},{"key":"e_1_3_2_1_46_1","unstructured":"Sheir Yarkoni Elena Raponi Sebastian Schmitt and Thomas B\u00e4ck. 2021. Quantum Annealing for Industry Applications: Introduction and Review. arXiv:2112.07491v2 (quant-ph).  Sheir Yarkoni Elena Raponi Sebastian Schmitt and Thomas B\u00e4ck. 2021. Quantum Annealing for Industry Applications: Introduction and Review. arXiv:2112.07491v2 (quant-ph)."}],"event":{"name":"GECCO '23 Companion: Companion Conference on Genetic and Evolutionary Computation","location":"Lisbon Portugal","acronym":"GECCO '23 Companion","sponsor":["SIGEVO ACM Special Interest Group on Genetic and Evolutionary Computation"]},"container-title":["Proceedings of the Companion Conference on Genetic and Evolutionary Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583133.3596394","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3583133.3596394","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:55Z","timestamp":1750182535000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583133.3596394"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,15]]},"references-count":44,"alternative-id":["10.1145\/3583133.3596394","10.1145\/3583133"],"URL":"https:\/\/doi.org\/10.1145\/3583133.3596394","relation":{},"subject":[],"published":{"date-parts":[[2023,7,15]]},"assertion":[{"value":"2023-07-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}