IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v227y2013i1p44-54.html
   My bibliography  Save this article

Bose–Einstein condensation in satisfiability problems

Author

Listed:
  • Angione, Claudio
  • Occhipinti, Annalisa
  • Stracquadanio, Giovanni
  • Nicosia, Giuseppe

Abstract

This paper is concerned with the complex behavior arising in satisfiability problems. We present a new statistical physics-based characterization of the satisfiability problem. Specifically, we design an algorithm that is able to produce graphs starting from a k-SAT instance, in order to analyze them and show whether a Bose–Einstein condensation occurs. We observe that, analogously to complex networks, the networks of k-SAT instances follow Bose statistics and can undergo Bose–Einstein condensation. In particular, k-SAT instances move from a fit-get-rich network to a winner-takes-all network as the ratio of clauses to variables decreases, and the phase transition of k-SAT approximates the critical temperature for the Bose–Einstein condensation. Finally, we employ the fitness-based classification to enhance SAT solvers (e.g., ChainSAT) and obtain the consistently highest performing SAT solver for CNF formulas, and therefore a new class of efficient hardware and software verification tools.

Suggested Citation

  • Angione, Claudio & Occhipinti, Annalisa & Stracquadanio, Giovanni & Nicosia, Giuseppe, 2013. "Bose–Einstein condensation in satisfiability problems," European Journal of Operational Research, Elsevier, vol. 227(1), pages 44-54.
    • Handle: RePEc:eee:ejores:v:227:y:2013:i:1:p:44-54
    DOI: 10.1016/j.ejor.2012.11.039
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221712008910
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2012.11.039?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Nonobe, Koji & Ibaraki, Toshihide, 1998. "A tabu search approach to the constraint satisfaction problem as a general problem solver," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 599-623, April.
    2. Mastrolilli, Monaldo & Gambardella, Luca Maria, 2005. "Maximum satisfiability: How good are tabu search and plateau moves in the worst-case?," European Journal of Operational Research, Elsevier, vol. 166(1), pages 63-76, October.
    3. Escoffier, Bruno & Paschos, Vangelis Th., 2007. "Differential approximation of min sat, max sat and related problems," European Journal of Operational Research, Elsevier, vol. 181(2), pages 620-633, September.
    4. Coelho, José & Vanhoucke, Mario, 2011. "Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers," European Journal of Operational Research, Elsevier, vol. 213(1), pages 73-82, August.
    5. Zimmermann, H. J. & Monfroglio, Angelo, 1997. "Linear programs for constraint satisfaction problems," European Journal of Operational Research, Elsevier, vol. 97(1), pages 105-123, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mutsunori Yagiura & Toshihide Ibaraki & Fred Glover, 2004. "An Ejection Chain Approach for the Generalized Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 16(2), pages 133-151, May.
    2. Ilkyeong Moon & Sanghyup Lee & Moonsoo Shin & Kwangyeol Ryu, 2016. "Evolutionary resource assignment for workload-based production scheduling," Journal of Intelligent Manufacturing, Springer, vol. 27(2), pages 375-388, April.
    3. Luis F. Machado-Domínguez & Carlos D. Paternina-Arboleda & Jorge I. Vélez & Agustin Barrios-Sarmiento, 2021. "A memetic algorithm to address the multi-node resource-constrained project scheduling problem," Journal of Scheduling, Springer, vol. 24(4), pages 413-429, August.
    4. E A Silver, 2004. "An overview of heuristic solution methods," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(9), pages 936-956, September.
    5. De Causmaecker, Patrick & Demeester, Peter & Vanden Berghe, Greet, 2009. "A decomposed metaheuristic approach for a real-world university timetabling problem," European Journal of Operational Research, Elsevier, vol. 195(1), pages 307-318, May.
    6. Bruno Vieira & Derya Demirtas & Jeroen B. Kamer & Erwin W. Hans & Louis-Martin Rousseau & Nadia Lahrichi & Wim H. Harten, 2020. "Radiotherapy treatment scheduling considering time window preferences," Health Care Management Science, Springer, vol. 23(4), pages 520-534, December.
    7. R Qu & E K Burke, 2009. "Hybridizations within a graph-based hyper-heuristic framework for university timetabling problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(9), pages 1273-1285, September.
    8. Sadan Kulturel-Konak & Bryan A. Norman & David W. Coit & Alice E. Smith, 2004. "Exploiting Tabu Search Memory in Constrained Problems," INFORMS Journal on Computing, INFORMS, vol. 16(3), pages 241-254, August.
    9. Zahid, Taiba & Kühn, Mathias & Völker, Michael & Schmidt, Thorsten, 2015. "Investigation of Scheduling Techniques for Uncertain Conditions," Chapters from the Proceedings of the Hamburg International Conference of Logistics (HICL), in: Blecker, Thorsten & Kersten, Wolfgang & Ringle, Christian M. (ed.), Operational Excellence in Logistics and Supply Chains: Optimization Methods, Data-driven Approaches and Security Insights. Proceedings of the Hamburg , volume 22, pages 171-202, Hamburg University of Technology (TUHH), Institute of Business Logistics and General Management.
    10. Gutjahr, Walter J., 2015. "Bi-Objective Multi-Mode Project Scheduling Under Risk Aversion," European Journal of Operational Research, Elsevier, vol. 246(2), pages 421-434.
    11. Hadi W. Purnomo & Jonathan F. Bard, 2007. "Cyclic preference scheduling for nurses using branch and price," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(2), pages 200-220, March.
    12. Joni L. Jones & Gary J. Koehler, 2005. "A Heuristic for Winner Determination in Rule-Based Combinatorial Auctions," INFORMS Journal on Computing, INFORMS, vol. 17(4), pages 475-489, November.
    13. Yagiura, Mutsunori & Ibaraki, Toshihide & Glover, Fred, 2006. "A path relinking approach with ejection chains for the generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 169(2), pages 548-569, March.
    14. Van Peteghem, Vincent & Vanhoucke, Mario, 2014. "An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances," European Journal of Operational Research, Elsevier, vol. 235(1), pages 62-72.
    15. Bard, Jonathan F. & Purnomo, Hadi W., 2005. "Preference scheduling for nurses using column generation," European Journal of Operational Research, Elsevier, vol. 164(2), pages 510-534, July.
    16. He, Naihui & Zhang, David Z. & Yuce, Baris, 2022. "Integrated multi-project planning and scheduling - a multiagent approach," European Journal of Operational Research, Elsevier, vol. 302(2), pages 688-699.
    17. Nima Zoraghi & Aria Shahsavar & Babak Abbasi & Vincent Peteghem, 2017. "Multi-mode resource-constrained project scheduling problem with material ordering under bonus–penalty policies," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 25(1), pages 49-79, April.
    18. Gómez Sánchez, Mariam & Lalla-Ruiz, Eduardo & Fernández Gil, Alejandro & Castro, Carlos & Voß, Stefan, 2023. "Resource-constrained multi-project scheduling problem: A survey," European Journal of Operational Research, Elsevier, vol. 309(3), pages 958-976.
    19. Deborah L. Kellogg & Steven Walczak, 2007. "Nurse Scheduling: From Academia to Implementation or Not?," Interfaces, INFORMS, vol. 37(4), pages 355-369, August.
    20. Vanhoucke, Mario & Coelho, José, 2016. "An approach using SAT solvers for the RCPSP with logical constraints," European Journal of Operational Research, Elsevier, vol. 249(2), pages 577-591.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:227:y:2013:i:1:p:44-54. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.