Skip to main content
SpringerLink
Log in

Quadratic reformulations of nonlinear binary optimization problems

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

Very large nonlinear unconstrained binary optimization problems arise in a broad array of applications. Several exact or heuristic techniques have proved quite successful for solving many of these problems when the objective function is a quadratic polynomial. However, no similarly efficient methods are available for the higher degree case. Since high degree objectives are becoming increasingly important in certain application areas, such as computer vision, various techniques have been recently developed to reduce the general case to the quadratic one, at the cost of increasing the number of variables by introducing additional auxiliary variables. In this paper we initiate a systematic study of these quadratization approaches. We provide tight lower and upper bounds on the number of auxiliary variables needed in the worst-case for general objective functions, for bounded-degree functions, and for a restricted class of quadratizations. Our upper bounds are constructive, thus yielding new quadratization procedures. Finally, we completely characterize all “minimal” quadratizations of negative monomials.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Anthony, M., Boros, E., Crama, Y., Gruber, M.: Quadratization of symmetric pseudo-Boolean functions. Discrete Appl. Math. 203, 1–12 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  2. Billionnet, A., Elloumi, S.: Using a mixed integer quadratic programming solver for the unconstrained quadratic 0–1 problem. Math. Program. 109, 55–68 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  3. Boros, E., Gruber, A.: On quadratization of pseudo-Boolean functions. In: Working paper (2011)

  4. Boros, E., Hammer, P.L.: Pseudo-Boolean optimization. Discrete Appl. Math. 123, 155–225 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  5. Boros, E., Hammer, P.L., Sun, R., Tavares, G.: A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO). Discrete Optim. 5, 501–529 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  6. Boros, E., Hammer, P.L., Tavares, G.: Local search heuristics for quadratic unconstrained binary optimization. J. Heuristics 13, 99–132 (2007)

    Article  Google Scholar 

  7. Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23, 1222–1239 (2001)

    Article  Google Scholar 

  8. Buchheim, Ch., Rinaldi, G.: Efficient reduction of polynomial zero-one optimization to the quadratic case. SIAM J. Optim. 18, 1398–1413 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  9. Buchheim, Ch., Rinaldi, G.: Terse integer linear programs for Boolean optimization. J. Satisf. Boolean Model. Comput. 6, 121–139 (2009)

    MathSciNet  MATH  Google Scholar 

  10. Burer, S., Letchford, A.N.: Non-convex mixed-integer nonlinear programming: a survey. Surv. Oper. Res. Manag. Sci. 17, 97–106 (2012)

    MathSciNet  Google Scholar 

  11. Conforti, M., Cornuéjols, G., Zambelli, G.: Extended formulations in combinatorial optimization. 4OR 4OR(8), 1–48 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  12. Crama, Y., Hammer, P.L.: Pseudo-Boolean optimization. In: Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Applied Optimization, pp. 445–450. Oxford University Press, Oxford (2002)

    Google Scholar 

  13. Crama, Y., Hammer, P.L.: Boolean Functions: Theory, Algorithms, and Applications. Cambridge University Press, New York (2011)

    Book  MATH  Google Scholar 

  14. Crama, Y., Rodríguez-Heck, E.: Short prime quadratizations of cubic negative monomials. Research report, July 2014. http://hdl.handle.net/2268/170649

  15. Ellis, D., Sudakov, B.: Generating all subsets of a finite set with disjoint unions. J. Comb. Theory Ser. A 118, 2319–2345 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  16. Fix, A.: Reductions for rewriting QPBFs with spanning trees. Unpublished notes (2011)

  17. Fix, A., Gruber, A., Boros E., Zabih, R.: A graph cut algorithm for higher-order Markov random fields. In: Proceedings of the 2011 IEEE International Conference on Computer Vision (ICCV), pp. 1020–1027

  18. Fix, A., Gruber, A., Boros, E., Zabih, R.: A hypergraph-based reduction for higher-order Markov random fields. IEEE Trans. Pattern Anal. Mach. Intell. 37, 1387–1395 (2015)

    Article  Google Scholar 

  19. Fortet, R.: L’algèbre de Boole et ses applications en recherche opérationnelle. Cahiers du Centre d’Etudes de Recherche Opérationnelle 1, 5–36 (1959)

    MathSciNet  MATH  Google Scholar 

  20. Fortet, R.: Applications de l’algèbre de Boole en recherche opérationnelle. Revue Française de Recherche Opérationnelle 4, 17–26 (1960)

    MATH  Google Scholar 

  21. Freedman, D., Drineas, P.: Energy minimization via graph cuts: settling what is possible, In: IEEE Conference on Computer Vision and Pattern Recognition (2), pp. 939–946 (2005)

  22. Frein, Y., Lévêque, B., Sebő, A.: Generating all sets with bounded unions. Comb. Probab. Comput. 17, 641–660 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  23. Füredi, Z., Katona, G.O.H.: 2-Bases of quadruples. Comb. Probab. Comput. 15, 131–141 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  24. Glover, F., Alidaee, B., Rego, C., Kochenberger, G.: One-pass heuristics for large-scale unconstrained binary quadratic problems. Eur. J. Oper. Res. 137, 272–287 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  25. Glover, F., Hao, J.-K.: Efficient evaluations for solving large 0–1 unconstrained quadratic optimisation problems. Int. J. Metaheuristics 1, 3–10 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  26. Hammer, P.L., Hansen, P., Simeone, B.: Roof duality, complementation and persistency in quadratic 0–1 optimization. Math. Program. 28, 121–155 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  27. Hammer, P.L., Rudeanu, S.: Boolean Methods in Operations Research and Related Areas. Springer, Berlin (1968)

    Book  MATH  Google Scholar 

  28. Hansen, P., Jaumard, B., Mathon, V.: Constrained nonlinear 0–1 programming. ORSA J. Comput. 5, 97–119 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  29. Hansen, P., Meyer, Ch.: Improved compact linearizations for the unconstrained quadratic 01 minimization problem. Discrete Appl. Math. 157, 1267–1290 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  30. Helmberg, C., Rendl, F.: Solving quadratic (0,1)-problems by semidefinite programs and cutting plane. Math. Program. 82, 291–315 (1998)

    MathSciNet  MATH  Google Scholar 

  31. Ishikawa, H.: Transformation of general binary MRF minimization to the first-order case. IEEE Trans. Pattern Anal. Mach. Intell. 33(6), 1234–1249 (2011)

    Article  Google Scholar 

  32. Kahl, F., Strandmark, P.: Generalized roof duality. Discrete Appl. Math. 160, 2419–2434 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  33. Kappes, J.H., et al.: A comparative study of modern inference techniques for discrete energy minimization problems. In: IEEE Conference on Computer Vision and Pattern Recognition CVPR’13, pp. 1328–1335 (2013)

  34. Kolmogorov, V.: Generalized roof duality and bisubmodular functions. Discrete Appl. Math. 160, 416–426 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  35. Kolmogorov, V., Rother, C.: Minimizing non-submodular functions with graph cuts: a review. IEEE Trans. Pattern Anal. Mach. Intell. 29, 1274–1279 (2007)

    Article  Google Scholar 

  36. Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Anal. Mach. Intell. 26(2), 147–159 (2004)

    Article  MATH  Google Scholar 

  37. Maghout, K.: Sur la détermination des nombres de stabilité et du nombre chromatique d’un graphe. Comptes Rendus de l’Académie des Sci. de Paris 248, 3522–3523 (1959)

    MathSciNet  MATH  Google Scholar 

  38. Maghout, K.: Applications de l’algèbre de Boole à la théorie des graphes et aux programmes linéaires et quadratiques. Cahiers du Centre d’Etudes de Recherche Opérationnelle 5, 21–99 (1963)

    MathSciNet  MATH  Google Scholar 

  39. Merz, P., Freisleben, B.: Greedy and local search heuristics for the unconstrained binary quadratic programming problem. J. Heuristics 8, 197–213 (2002)

    Article  MATH  Google Scholar 

  40. Ramalingam, S., Russell, Ch., Ladický, L. Torr, Ph.H.S.: Efficient minimization of higher order submodular functions using monotonic Boolean functions, (2011) arXiv:1109.2304v1

  41. Rosenberg, I.G.: Reduction of bivalent maximization to the quadratic case. Cahiers du Centre d’Etudes de Recherche Opérationnelle 17, 71–74 (1975)

    MathSciNet  MATH  Google Scholar 

  42. Rother, C., Kohli, P., Feng, W., Jia, J. (2009) Minimizing sparse higher order energy functions of discrete variables. In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 1382–1389

  43. Rother, C., Kolmogorov, V., Lempitsky, V., Szummer, M.: Optimizing binary MRFs via extended roof duality. In: IEEE Conference on Computer Vision and Pattern Recognition (2007)

  44. Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer, Dordrecht (1999)

    Book  MATH  Google Scholar 

  45. Sidorenko, A.: What we know and what we do not know about Turán numbers. Gr. Comb. 11, 179–199 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  46. Živný, S., Cohen, D.A., Jeavons, P.G.: The expressive power of binary submodular functions. Discrete Appl. Math. 157, 3347–3358 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  47. Živný, S., Jeavons, P.G.: Classes of submodular constraints expressible by graph cuts. Constraints 15, 430–452 (2010)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

We are grateful to Zoltán Szigeti and György Turán for pointers on 2-bases and on representations of symmetric functions, and to the reviewers for their valuable comments. The second author thanks the National Science Foundation (Grant IIS-1161476) for partial support. The third author was partially funded by the Interuniversity Attraction Poles Programme initiated by the Belgian Science Policy Office (Grant P7/36) and by a sabbatical grant from FNRS. The fourth author thanks the joint CAPES (Brazil)/Fulbright (USA) fellowship process BEX-2387050/15061676 and the São Paulo Science Foundation (FAPESP) process 2014/23269-8 for partial support.

Author information

Authors and Affiliations

  1. Department of Mathematics, London School of Economics and Political Science, London, UK

    Martin Anthony

  2. MSIS Department and RUTCOR, Rutgers University, New Brunswick, NJ, USA

    Endre Boros

  3. QuantOM, HEC Management School, University of Liège, Liège, Belgium

    Yves Crama

  4. Institute of Mathematics and Statistics, University of São Paulo, São Paulo, Brazil

    Aritanan Gruber

Authors
  1. Martin Anthony
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Endre Boros
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yves Crama
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Aritanan Gruber
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yves Crama.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Anthony, M., Boros, E., Crama, Y. et al. Quadratic reformulations of nonlinear binary optimization problems. Math. Program. 162, 115–144 (2017). https://doi.org/10.1007/s10107-016-1032-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-016-1032-4

Keywords

Mathematics Subject Classification

Search

Navigation