×

zbMATH — the first resource for mathematics

Extended formulations for convex hulls of some bilinear functions. (English) Zbl 07225953
Summary: We consider the problem of characterizing the convex hull of the graph of a bilinear function \(f\) on the \(n\)-dimensional unit cube \([0,1]^n\). Extended formulations for this convex hull are obtained by taking subsets of the facets of the Boolean Quadric Polytope (BQP). Extending existing results, we propose a systematic study of properties of \(f\) that guarantee that certain classes of BQP facets are sufficient for an extended formulation. We use a modification of M. Zuckerberg’s geometric method for proving convex hull characterizations [Oper. Res. Lett. 44, No. 5, 625–629 (2016; Zbl 1408.90193)] to prove some initial results in this direction. In particular, we provide small-sized extended formulations for bilinear functions whose corresponding graph is either a cycle with arbitrary edge weights or a clique or an almost clique with unit edge weights.

MSC:
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C26 Nonconvex programming, global optimization
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
Software:
GloMIQO; polymake
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Rikun, Anatoliy D., A convex envelope formula for multilinear functions, J. Global Optim., 10, 4, 425-437 (1997) · Zbl 0881.90099
[2] Sherali, Hanif D., Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets, Acta Math. Vietnam., 22, 1, 245-270 (1997) · Zbl 0914.90205
[3] Locatelli, Marco; Schoen, Fabio, Global Optimization: Theory, Algorithms, and Applications (2013), SIAM · Zbl 1286.90003
[4] Conforti, Michele; Cornuéjols, Gérard; Zambelli, Giacomo, Extended formulations in combinatorial optimization, 4OR, 8, 1, 1-48 (2010) · Zbl 1219.90193
[5] Balas, Egon; Ceria, Sebastián; Cornuéjols, Gérard, A lift-and-project cutting plane algorithm for mixed 0-1 programs, Math. Program., 58, 1, 295-324 (1993) · Zbl 0796.90041
[6] Sherali, Hanif D.; Adams, Warren P., A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3, 3, 411-430 (1990) · Zbl 0712.90050
[7] Dey, Santanu S.; Gupte, Akshay, Analysis of MILP techniques for the pooling problem, Oper. Res., 63, 2, 412-427 (2015) · Zbl 1327.90351
[8] Gupte, Akshay; Ahmed, Shabbir; Dey, Santanu S.; Cheon, Myun Seok, Relaxations and discretizations for the pooling problem, J. Global Optim., 67, 3, 631-669 (2017) · Zbl 1392.90117
[9] Gupte, Akshay; Ahmed, Shabbir; Cheon, Myun S.; Dey, Santanu S., Solving mixed integer bilinear problems using MILP formulations, SIAM J. Control Optim., 23, 2, 721-744 (2013) · Zbl 1300.90021
[10] McCormick, Garth P., Computability of global solutions to factorable nonconvex programs: Part I - Convex underestimating problems, Math. Program., 10, 1, 147-175 (1976) · Zbl 0349.90100
[11] Misener, Ruth; Smadbeck, James B.; Floudas, Christodoulos A., Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2, Optim. Methods Softw., 30, 1, 215-249 (2015) · Zbl 1325.90071
[12] Boland, Natashia; Dey, Santanu S.; Kalinowski, Thomas; Molinaro, Marco; Rigterink, Fabian, Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions, Math. Program., 162, 523-535 (2017) · Zbl 1384.90073
[13] Luedtke, James; Namazifar, Mahdi; Linderoth, Jeffrey T., Some results on the strength of relaxations of multilinear functions, Math. Program., 136, 2, 325-351 (2012) · Zbl 1286.90117
[14] Ballerstein, Martin; Michaels, Dennis, Extended formulations for convex envelopes, J. Global Optim., 60, 2, 217-238 (2014) · Zbl 1335.90070
[15] Padberg, Manfred W., The Boolean quadric polytope: Some characteristics, facets and relatives, Math. Program., 45, 1-3, 139-172 (1989) · Zbl 0675.90056
[16] Burer, Samuel; Letchford, Adam N., On nonconvex quadratic programming with box constraints, SIAM J. Control Optim., 20, 2, 1073-1089 (2009) · Zbl 1201.90146
[17] Deza, Michel Marie; Laurent, Monique, (Geometry of Cuts and Metrics. Geometry of Cuts and Metrics, Algorithms and Combinatorics, vol. 15 (1997), Springer) · Zbl 0885.52001
[18] Letchford, Adam N.; Sørensen, Michael M., A new separation algorithm for the Boolean quadric and cut polytopes, Discrete Optim., 14, 61-71 (2014) · Zbl 1308.90209
[19] Barahona, Francisco; Mahjoub, Ali Ridha, On the cut polytope, Math. Program., 36, 2, 157-173 (1986) · Zbl 0616.90058
[20] Avis, David; Tiwary, Hans Raj, On the extension complexity of combinatorial polytopes, Math. Program., 153, 1, 95-115 (2015) · Zbl 1336.90095
[21] Simone, Caterina De, The cut polytope and the Boolean quadric polytope, Discrete Math., 79, 1, 71-75 (1990) · Zbl 0683.90068
[22] Michini, Carla, Forbidden minors for tight cycle relaxations (2018), Optimization Online Preprint 5483, optimization-online:5483
[23] Boros, Endre; Crama, Yves; Hammer, Peter L., Chvátal cuts and odd cycle inequalities in quadratic 0-1 optimization, SIAM J. Discrete Math., 5, 2, 163-177 (1992) · Zbl 0761.90069
[24] Bonami, Pierre; Günlük, Oktay; Linderoth, Jeff, Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods, Math. Program. Comput., 10, 3, 333-382 (2018) · Zbl 1400.90239
[25] Tawarmalani, Mohit; Richard, Jean-Philippe P.; Xiong, Chuanhui, Explicit convex and concave envelopes through polyhedral subdivisions, Math. Program., 138, 1, 531-577 (2012) · Zbl 1273.90165
[26] Assarf, Benjamin; Gawrilow, Ewgenij; Herr, Katrin; Joswig, Michael; Lorenz, Benjamin; Paffenholz, Andreas; Rehn, Thomas, Computing convex hulls and counting integer points with polymake, Math. Program. Comput., 9, 1, 1-38 (2017) · Zbl 1370.90009
[27] Zuckerberg, Mark, A Set Theoretic Approach to Lifting Procedures for 0, 1 Integer Programming (2004), Columbia University, (Ph.D. thesis) · Zbl 1077.90041
[28] Zuckerberg, Mark, Geometric proofs for convex hull defining formulations, Oper. Res. Lett., 44, 5, 625-629 (2016) · Zbl 1408.90193
[29] Rudolf Halin, Studies on minimally \(n\)-connected graphs, in: Combinatorial Mathematics and Its Applications (Proc. Conf., Oxford, 1969), 1971, pp. 129-136.
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.