A class of valid inequalities for multilinear 0-1 optimization problems. (English) Zbl 1387.90125

Summary: 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).


90C09 Boolean programming
90C10 Integer programming
90C30 Nonlinear programming


Full Text: DOI


[1] Hammer, P. L.; Rosenberg, I.; Rudeanu, S., On the determination of the minima of pseudo-Boolean functions, Stud. Cerc. Mat., 14, 359-364, (1963), (in Romanian) · Zbl 0131.18503
[2] Hammer, P. L.; Rudeanu, S., Boolean methods in operations research and related areas, (1968), Springer-Verlag Berlin · Zbl 0155.28001
[3] Crama, Y.; Hammer, P. L., Boolean functions: theory, algorithms, and applications, (2011), Cambridge University Press New York, N. Y · Zbl 1237.06001
[4] De Simone, C., The cut polytope and the Boolean quadric polytope, Discrete Math., 79, 1, 71-75, (1990) · Zbl 0683.90068
[5] Boros, E.; Hammer, P. L., Pseudo-Boolean optimization, Discrete Appl. Math., 123, 1, 155-225, (2002) · Zbl 1076.90032
[6] Burer, S.; Letchford, A. N., Non-convex mixed-integer nonlinear programming: a survey, Surv. Oper. Res. Manag. Sci., 17, 2, 97-106, (2012)
[7] D’Ambrosio, C.; Lodi, A., Mixed integer nonlinear programming tools: a practical overview, 4OR, 9, 4, 329-349, (2011) · Zbl 1235.90101
[8] Hansen, P.; Jaumard, B.; Mathon, V., State-of-the-art survey: constrained nonlinear 0-1 programming, ORSA J. Comput., 5, 2, 97-119, (1993) · Zbl 0777.90033
[9] Hemmecke, R.; Köppe, M.; Lee, J.; Weismantel, R., Nonlinear integer programming, (50 Years of Integer Programming 1958-2008, (2010), Springer), 561-618 · Zbl 1187.90270
[10] Fortet, R., L’algèbre de Boole et ses applications en recherche opérationnelle, Cah. Cent. Étud. Rech. Opér., 4, 5-36, (1959) · Zbl 0093.32704
[11] Fortet, R., Applications de l’algèbre de Boole en recherche opérationnelle, Rev. Française Autom., Inform. Rech. Opér., 4, 14, 17-26, (1960) · Zbl 0109.38201
[12] Watters, L. J., Reduction of integer polynomial programming problems to zero-one linear programming problems, Oper. Res., 15, 1171-1174, (1967)
[13] Zangwill, W. I., Media selection by decision programming, J. Adv. Res., 5, 30-36, (1965)
[14] Glover, F.; Woolsey, E., Further reduction of zero-one polynomial programming problems to zero-one linear programming problems, Oper. Res., 21, 1, 156-161, (1973) · Zbl 0261.90045
[15] Glover, F.; Woolsey, E., Technical note: converting the 0-1 polynomial programming problem to a 0-1 linear program, Oper. Res., 22, 1, 180-182, (1974) · Zbl 0272.90049
[16] Buchheim, C.; Rinaldi, G., Efficient reduction of polynomial zero-one optimization to the quadratic case, SIAM J. Optim., 18, 4, 1398-1413, (2007) · Zbl 1165.90685
[17] Djeumou Fomeni, F.; Kaparis, K.; Letchford, A., Cutting planes for RLT relaxations of mixed 0-1 polynomial programs, Math. Program., 151, 2, 639-658, (2015) · Zbl 1328.90111
[18] 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 · Zbl 1364.90225
[19] Conforti, M.; Cornuéjols, G.; Zambelli, G., (Integer Programming, Graduate Texts in Mathematics, vol. 271, (2014), Springer Switzerland) · Zbl 1307.90001
[20] McCormick, G. P., Computability of global solutions to factorable nonconvex programs: part I-convex underestimating problems, Math. Program., 10, 1, 147-175, (1976) · Zbl 0349.90100
[21] Al-Khayyal, F. A.; Falk, J. E., Jointly constrained biconvex programming, Math. Oper. Res., 8, 2, 273-286, (1983) · Zbl 0521.90087
[22] Crama, Y., Concave extensions for nonlinear 0-1 maximization problems, Math. Program., 61, 1, 53-60, (1993) · Zbl 0796.90040
[23] Ryoo, H. S.; Sahinidis, N. V., Analysis of bounds for multilinear functions, J. Global Optim., 19, 4, 403-424, (2001) · Zbl 0982.90054
[24] Luedtke, J.; Namazifar, M.; Linderoth, J., Some results on the strength of relaxations of multilinear functions, Math. Program., 136, 2, 325-351, (2012) · Zbl 1286.90117
[25] 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. · Zbl 1419.90118
[26] 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
[27] Balas, E., Disjunctive programming and a hierarchy of relaxations for discrete optimization problems, SIAM J. Algebr. Discrete Methods, 6, 3, 466-486, (1985) · Zbl 0592.90070
[28] Buchheim, C.; Klein, L., Combinatorial optimization with one quadratic term: spanning trees and forests, Discrete Appl. Math., 177, 34-52, (2014) · Zbl 1303.90086
[29] IBM ILOG CPLEX Optimizer 12.6. http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/.
[30] Kolmogorov, V.; Rother, C., Minimizing nonsubmodular functions with graph cuts-a review, IEEE Trans. Pattern Anal. Mach. Intell., 29, 7, 1274-1279, (2007)
[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)
[32] 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, 1387-1395, (2015)
[33] 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, 155-184, (2015)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.