Solving Sparse Separable Bilinear Programs Using Lifted Bilinear Cover Inequalities

References

• Balas E (1975) Facets of the knapsack polytope. Math. Programming 8(1):146–164.Crossref, Google Scholar
• Balas E, Zemel E (1978) Facets of the knapsack polytope from minimal covers. SIAM J. Appl. Math. 34(1):119–148.Crossref, Google Scholar
• Bixby R, Rothberg E (2007) Progress in computational mixed integer programming—A look back from the other side of the tipping point. Ann. Oper. Res. 149(1):37–41.Crossref, Google Scholar
• Bodur M, Del Pia A, Dey SS, Molinaro M, Pokutta S (2018) Aggregation-based cutting-planes for packing and covering integer programs. Math. Programming 171(1):331–359.Crossref, Google Scholar
• Burer S (2015) A gentle, geometric introduction to copositive optimization. Math. Programming 151(1):89–116.Crossref, Google Scholar
• Burer S, Kilinç-Karzan F (2017) How to convexify the intersection of a second order cone and a nonconvex quadratic. Math. Programming 162(1):393–429.Crossref, Google Scholar
• Crowder H, Johnson EL, Padberg M (1983) Solving large-scale zero-one linear programming problems. Oper. Res. 31(5):803–834.Link, Google Scholar
• Dey SS, Molinaro M, Wang Q (2015) Approximating polyhedra with sparse inequalities. Math. Programming 154(1):329–352.Crossref, Google Scholar
• Dey SS, Molinaro M, Wang Q (2018) Analysis of sparse cutting planes for sparse MILPs with applications to stochastic MILPs. Math. Oper. Res. 43(1):304–332.Link, Google Scholar
• Dey SS, Munoz G, Serrano F (2022) On obtaining the convex hull of quadratic inequalities via aggregations. SIAM J. Optim. 32(2):659–686.Crossref, Google Scholar
• Dey SS, Santana A, Wang Y (2019) New SOCP relaxation and branching rule for bipartite bilinear programs. Optim. Engrg. 20(2):307–336.Crossref, Google Scholar
• Gu X, Dey SS, Richard JPP (2023) Lifting convex inequalities for bipartite bilinear programs. Math. Programming 197(2):587–619.Crossref, Google Scholar
• Gu Z, Nemhauser GL, Savelsbergh MWP (1999) Lifted flow cover inequalities for mixed 0-1 integer programs. Math. Programming 85(3):439–467.Crossref, Google Scholar
• Gu Z, Nemhauser GL, Savelsbergh MWP (2000) Sequence independent lifting in mixed integer programming. J. Combin. Optim. 4(1):109–129.Crossref, Google Scholar
• Hammer PL, Johnson EL, Peled UN (1975) Facet of regular 0–1 polytopes. Math. Programming 8(1):179–206.Crossref, Google Scholar
• Horn RA, Johnson CR (2012) Matrix Analysis (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Marchand H, Wolsey LA (2001) Aggregation and mixed integer rounding to solve MIPs. Oper. Res. 49(3):363–371.Link, Google Scholar
• Modaresi S, Vielma JP (2017) Convex hull of two quadratic or a conic quadratic and a quadratic inequality. Math. Programming 164(1):383–409.Crossref, Google Scholar
• Padberg MW (1975) A note on zero-one programming. Oper. Res. 23(4):833–837.Link, Google Scholar
• Richard JPP (2010) Lifting techniques for mixed integer programming. Cochran JJ, Cox LA Jr, Keskinocak P, Kharoufeh JP, Smith JC, eds. Wiley Encyclopedia of Operations Research and Management Science (John Wiley & Sons, Inc., Hoboken, NJ).Google Scholar
• Santana A, Dey SS (2020) The convex hull of a quadratic constraint over a polytope. SIAM J. Optim. 30(4):2983–2997.Crossref, Google Scholar
• Schoning T (1999) A probabilistic algorithm for k-SAT and constraint satisfaction problems. 40th Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 410–414.Google Scholar
• Tawarmalani M, Richard JPP, Chung K (2010) Strong valid inequalities for orthogonal disjunctions and bilinear covering sets. Math. Programming 124(1–2):481–512.Crossref, Google Scholar
• Wolsey LA (1975) Faces for a linear inequality in 0–1 variables. Math. Programming 8(1):165–178.Crossref, Google Scholar
• Wolsey LA (1976) Facets and strong valid inequalities for integer programs. Oper. Res. 24(2):367–372.Link, Google Scholar
• Wolsey LA (1977) Valid inequalities and superadditivity for 0–1 integer programs. Math. Oper. Res. 2(1):66–77.Link, Google Scholar
• Yildiran U (2009) Convex hull of two quadratic constraints is an LMI set. IMA J. Math. Control Inform. 26(4):417–450.Crossref, Google Scholar
• Zemel E (1978) Lifting the facets of zero–one polytopes. Math. Programming 15(1):268–277.Crossref, Google Scholar