A class of valid inequalities for multilinear 0-1 optimization problems

[en] This paper investigates the polytope associated with the classical standard linearization technique for the unconstrained optimization of multilinear polynomials in 0-1 variables. A new class of valid inequalities, called 2-links, is introduced to strengthen the LP relaxation of the standard linearization. The addition of the 2-links to the standard linearization inequalities provides a complete description of the convex hull of integer solutions for the case of functions consisting of at most two nonlinear monomials. For the general case, various computational experiments show that the 2- links improve both the standard linearization bound and the computational performance of exact branch & cut methods. The improvements are especially significant for a class of instances inspired from the image restoration problem in computer vision. The magnitude of this effect is rather surprising in that the 2-links are in relatively small number (quadratic in the number of terms of the objective function).

Disciplines :

Mathematics
Quantitative methods in economics & management

Author, co-author :

Crama, Yves ; Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production

Rodriguez Heck, Elisabeth ; Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production

Language :

English

Title :

A class of valid inequalities for multilinear 0-1 optimization problems

Publication date :

2017

Journal title :

Discrete Optimization

ISSN :

1572-5286

eISSN :

1873-636X

Publisher :

Elsevier

Volume :

Pages :

28-47

Peer reviewed :

Peer Reviewed verified by ORBi

Name of the research project :

Pôles d'attraction interuniversitaires (PAI) 7/36

Funders :

BELSPO - Politique scientifique fédérale

Available on ORBi :

since 15 May 2016

Statistics

Number of views

240 (42 by ULiège)

Number of downloads

625 (12 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Hammer, P.L., Rosenberg, I., Rudeanu, S., On the determination of the minima of pseudo-Boolean functions. Stud. Cerc. Mat. 14 (1963), 359–364 (in Romanian).
Hammer, P.L., Rudeanu, S., Boolean Methods in Operations Research and Related Areas. 1968, Springer-Verlag, Berlin.
Crama, Y., Hammer, P.L., Boolean Functions: Theory, Algorithms, and Applications. 2011, Cambridge University Press, New York, N. Y.
De Simone, C., The cut polytope and the boolean quadric polytope. Discrete Math. 79:1 (1990), 71–75.
Boros, E., Hammer, P.L., Pseudo-Boolean optimization. Discrete Appl. Math. 123:1 (2002), 155–225.
Burer, S., Letchford, A.N., Non-convex mixed-integer nonlinear programming: a survey. Surv. Oper. Res. Manag. Sci. 17:2 (2012), 97–106.
D'Ambrosio, C., Lodi, A., Mixed integer nonlinear programming tools: a practical overview. 4OR 9:4 (2011), 329–349.
Hansen, P., Jaumard, B., Mathon, V., State-of-the-art survey: constrained nonlinear 0–1 programming. ORSA J. Comput. 5:2 (1993), 97–119.
Hemmecke, R., Köppe, M., Lee, J., Weismantel, R., Nonlinear integer programming. 50 Years of Integer Programming 1958–2008, 2010, Springer, 561–618.
Fortet, R., L'algèbre de Boole et ses applications en recherche opérationnelle. Cah. Cent. Étud. Rech. Opér. 4 (1959), 5–36.
Fortet, R., Applications de l'algèbre de Boole en recherche opérationnelle. Rev. Française Autom., Inform. Rech. Opér. 4:14 (1960), 17–26.
Watters, L.J., Reduction of integer polynomial programming problems to zero–one linear programming problems. Oper. Res. 15 (1967), 1171–1174.
Zangwill, W.I., Media selection by decision programming. J. Adv. Res. 5 (1965), 30–36.
Glover, F., Woolsey, E., Further reduction of zero–one polynomial programming problems to zero–one linear programming problems. Oper. Res. 21:1 (1973), 156–161.
Glover, F., Woolsey, E., Technical note: converting the 0-1 polynomial programming problem to a 0–1 linear program. Oper. Res. 22:1 (1974), 180–182.
Buchheim, C., Rinaldi, G., Efficient reduction of polynomial zero–one optimization to the quadratic case. SIAM J. Optim. 18:4 (2007), 1398–1413.
Djeumou Fomeni, F., Kaparis, K., Letchford, A., Cutting planes for RLT relaxations of mixed 0–1 polynomial programs. Math. Program. 151:2 (2015), 639–658.
Del Pia, A., Khajavirad, A., A polyhedral study of binary polynomial programs. Math. Oper. Res., 2016 Published online, http://dx.doi.org/10.1287/moor.2016.0804.
Conforti, M., Cornuéjols, G., Zambelli, G., Integer Programming Graduate Texts in Mathematics, vol. 271, 2014, Springer, Switzerland.
McCormick, G.P., Computability of global solutions to factorable nonconvex programs: Part I–convex underestimating problems. Math. Program. 10:1 (1976), 147–175.
Al-Khayyal, F.A., Falk, J.E., Jointly constrained biconvex programming. Math. Oper. Res. 8:2 (1983), 273–286.
Crama, Y., Concave extensions for nonlinear 0–1 maximization problems. Math. Program. 61:1 (1993), 53–60.
Ryoo, H.S., Sahinidis, N.V., Analysis of bounds for multilinear functions. J. Global Optim. 19:4 (2001), 403–424.
Luedtke, J., Namazifar, M., Linderoth, J., Some results on the strength of relaxations of multilinear functions. Math. Program. 136:2 (2012), 325–351.
A. Fischer, F. Fischer, S.T. McCormick, Matroid optimisation problems with nested non-linear monomials in the objective function. NAM Preprint 2016-2, Institute for Numerical and Applied Mathematics, University of Goettingen, March 2016.
Balas, E., Disjunctive programming: properties of the convex hull of feasible points, GSIA Management Science Research Report MSRR 348., 1974, Carnegie Mellon University Published as invited paper in Discrete Applied Mathematics 89 (1998) 3–44.
Balas, E., Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM J. Algebr. Discrete Methods 6:3 (1985), 466–486.
Buchheim, C., Klein, L., Combinatorial optimization with one quadratic term: spanning trees and forests. Discrete Appl. Math. 177 (2014), 34–52.
IBM ILOG CPLEX Optimizer 12.6. http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/.
Kolmogorov, V., Rother, C., Minimizing nonsubmodular functions with graph cuts–a review. IEEE Trans. Pattern Anal. Mach. Intell. 29:7 (2007), 1274–1279.
Ishikawa, H., Transformation of general binary MRF minimization to the first-order case. IEEE Trans. Pattern Anal. Mach. Intell. 33:6 (2011), 1234–1249.
Fix, A., Gruber, A., Boros, E., Zabih, R., A hypergraph-based reduction for higher-order binary Markov random fields. IEEE Trans. Pattern Anal. Mach. Intell. 37:7 (2015), 1387–1395.
Kappes, J.H., Andres, B., Hamprecht, F.A., Schnörr, C., Nowozin, S., Batra, D., Kim, S., Kausler, B.X., Kröger, T., Lellmann, J., Komodakis, N., Savchynskyy, B., Rother, C., A comparative study of modern inference techniques for structured discrete energy minimization problems. Int. J. Comput. Vis. 115:2 (2015), 155–184.