multilinear binary optimization; pseudo-Boolean optimization; integer nonlinear programming; standard linearization
Abstract :
[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
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
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.
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.
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/.
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.
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
