Skip to main content
Springer Nature Link
Log in

A Constraint Composite Graph-Based ILP Encoding of the Boolean Weighted CSP

  • Conference paper
  • First Online:
Principles and Practice of Constraint Programming (CP 2017)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 10416))

Abstract

The weighted constraint satisfaction problem (WCSP) occurs in the crux of many real-world applications of operations research, artificial intelligence, bioinformatics, etc. Despite its importance as a combinatorial substrate, many attempts for building an efficient WCSP solver have been largely unsatisfactory. In this paper, we introduce a new method for encoding a (Boolean) WCSP instance as an integer linear program (ILP). This encoding is based on the idea of the constraint composite graph (CCG) associated with a WCSP instance. We show that our CCG-based ILP encoding of the Boolean WCSP is significantly more efficient than previously known ILP encodings. Theoretically, we show that the CCG-based ILP encoding has a number of interesting properties. Empirically, we show that it allows us to solve many hard Boolean WCSP instances that cannot be solved by ILP solvers with previously known ILP encodings.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+
from €39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Chapter
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 42.79
Price includes VAT (Germany)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 53.49
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

') var buybox = document.querySelector("[data-id=id_"+ timestamp +"]").parentNode var buyingOptions = buybox.querySelectorAll(".buying-option") ;[].slice.call(buyingOptions).forEach(initCollapsibles) var buyboxMaxSingleColumnWidth = 480 function initCollapsibles(subscription, index) { var toggle = subscription.querySelector(".buying-option-price") subscription.classList.remove("expanded") var form = subscription.querySelector(".buying-option-form") var priceInfo = subscription.querySelector(".price-info") var buyingOption = toggle.parentElement if (toggle && form && priceInfo) { toggle.setAttribute("role", "button") toggle.setAttribute("tabindex", "0") toggle.addEventListener("click", function (event) { var expandedBuyingOptions = buybox.querySelectorAll(".buying-option.expanded") var buyboxWidth = buybox.offsetWidth ;[].slice.call(expandedBuyingOptions).forEach(function(option) { if (buyboxWidth buyboxMaxSingleColumnWidth) { toggle.click() } else { if (index === 0) { toggle.click() } else { toggle.setAttribute("aria-expanded", "false") form.hidden = "hidden" priceInfo.hidden = "hidden" } } }) } initialStateOpen() if (window.buyboxInitialised) return window.buyboxInitialised = true initKeyControls() })()

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    A MAP problem instance on a probabilistic graphic model, such as a Belief Network, can be formulated as a WCSP instance by taking the negative logarithm on the individual probabilities.

  2. 2.

    As shown in [8], our techniques can also be generalized to the WCSP with variables of domain sizes larger than 2. However, for a proof of concept, this paper focuses on the Boolean WCSP.

  3. 3.

    http://www.hlt.utdallas.edu/~vgogate/uai14-competition/index.html.

References

  1. Berkelaar, M., Eikland, K., Notebaert, P.: lp_solve 5.5 open source (mixed integer) linear programming software (2004). http://lpsolve.sourceforge.net/5.5/

  2. Bistarelli, S., Montanari, U., Rossi, F., Schiex, T., Verfaillie, G., Fargier, H.: Semiring-based CSPs and valued CSPs: frameworks, properties, and comparison. Constraints 4(3), 199–240 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  3. Gurobi Optimization Inc.: Gurobi optimizer reference manual (2017) http://www.gurobi.com

  4. Hurley, B., O’Sullivan, B., Allouche, D., Katsirelos, G., Schiex, T., Zytnicki, M., de Givry, S.: Multi-language evaluation of exact solvers in graphical model discrete optimization. Constraints 21(3), 413–434 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  5. Koller, D., Friedman, N.: Probabilistic Graphical Models: Principles and Techniques. MIT Press, Cambridge (2009)

    MATH  Google Scholar 

  6. Kumar, T.K.S.: Incremental computation of resource-envelopes in producer-consumer models. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 664–678. Springer, Heidelberg (2003). doi:10.1007/978-3-540-45193-8_45

    Chapter  Google Scholar 

  7. Kumar, T.K.S.: A framework for hybrid tractability results in Boolean weighted constraint satisfaction problems. In: Stuckey, P.J. (ed.) CP 2008. LNCS, vol. 5202, pp. 282–297. Springer, Heidelberg (2008). doi:10.1007/978-3-540-85958-1_19

    Chapter  Google Scholar 

  8. Kumar, T.K.S.: Lifting techniques for weighted constraint satisfaction problems. In: The International Symposium on Artificial Intelligence and Mathematics (2008)

    Google Scholar 

  9. Kumar, T.K.S.: Kernelization, generation of bounds, and the scope of incremental computation for weighted constraint satisfaction problems. In: The International Symposium on Artificial Intelligence and Mathematics (2016)

    Google Scholar 

  10. Marinescu, R., Dechter, R.: Best-first AND/OR search for graphical models. In: The AAAI Conference on Artificial Intelligence, pp. 1171–1176 (2007)

    Google Scholar 

  11. Siek, J., Lee, L.Q., Lumsdain, A.: The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley, Boston (2002)

    Google Scholar 

  12. Sierksma, G.: Linear and Integer Programming: Theory and Practice, 2nd edn. CRC Press, Boca Raton (2001)

    MATH  Google Scholar 

  13. Xu, H., Kumar, T.K.S., Koenig, S.: A new solver for the minimum weighted vertex cover problem. In: Quimper, C.-G. (ed.) CPAIOR 2016. LNCS, vol. 9676, pp. 392–405. Springer, Cham (2016). doi:10.1007/978-3-319-33954-2_28

    Google Scholar 

  14. Xu, H., Kumar, T.K.S., Koenig, S.: The Nemhauser-Trotter reduction and lifted message passing for the weighted CSP. In: Salvagnin, D., Lombardi, M. (eds.) CPAIOR 2017. LNCS, vol. 10335, pp. 387–402. Springer, Cham (2017). doi:10.1007/978-3-319-59776-8_31

    Chapter  Google Scholar 

Download references

Acknowledgment

The research at the University of Southern California was supported by the National Science Foundation (NSF) under grant numbers 1409987 and 1319966. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the sponsoring organizations, agencies or the U.S. government.

Author information

Authors and Affiliations

  1. University of Southern California, Los Angeles, CA, 90089, USA

    Hong Xu, Sven Koenig & T. K. Satish Kumar

Authors
  1. Hong Xu
    View author publications

    Search author on:PubMed Google Scholar

  2. Sven Koenig
    View author publications

    Search author on:PubMed Google Scholar

  3. T. K. Satish Kumar
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Hong Xu .

Editor information

Editors and Affiliations

  1. University of Toronto, Toronto, Ontario, Canada

    J. Christopher Beck

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Xu, H., Koenig, S., Kumar, T.K.S. (2017). A Constraint Composite Graph-Based ILP Encoding of the Boolean Weighted CSP. In: Beck, J. (eds) Principles and Practice of Constraint Programming. CP 2017. Lecture Notes in Computer Science(), vol 10416. Springer, Cham. https://doi.org/10.1007/978-3-319-66158-2_40

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-66158-2_40

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-66157-5

  • Online ISBN: 978-3-319-66158-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics