IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v36y2024i3p884-899.html
   My bibliography  Save this article

Solving Sparse Separable Bilinear Programs Using Lifted Bilinear Cover Inequalities

Author

Listed:
  • Xiaoyi Gu

    (School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • Santanu S. Dey

    (School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • Jean-Philippe P. Richard

    (Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455)

Abstract

Recently a class of second-order cone representable convex inequalities called lifted bilinear cover inequalities were introduced, which are valid for a set described by a separable bilinear constraint together with bounds on variables. In this paper, we study the computational potential of these inequalities for separable bilinear optimization problems. We first prove that the semidefinite programming relaxation provides no benefit over the McCormick relaxation for such problems. We then design a simple randomized separation heuristic for lifted bilinear cover inequalities. In our computational experiments, we separate many rounds of these inequalities starting from McCormick’s relaxation of instances where each constraint is a separable bilinear constraint set. We demonstrate that there is a significant improvement in the performance of a state-of-the-art global solver in terms of gap closed, when these inequalities are added at the root node compared with when they are not.

Suggested Citation

  • Xiaoyi Gu & Santanu S. Dey & Jean-Philippe P. Richard, 2024. "Solving Sparse Separable Bilinear Programs Using Lifted Bilinear Cover Inequalities," INFORMS Journal on Computing, INFORMS, vol. 36(3), pages 884-899, May.
    • Handle: RePEc:inm:orijoc:v:36:y:2024:i:3:p:884-899
    DOI: 10.1287/ijoc.2022.0230
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.0230
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2022.0230?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. WOLSEY, Laurence A., 1977. "Valid inequalities and superadditivity for 0-1 integer programs," LIDAM Reprints CORE 328, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. MARCHAND, Hugues & WOLSEY, Laurence A., 2001. "Aggregation and mixed integer rounding to solve mips," LIDAM Reprints CORE 1513, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. L. A. Wolsey, 1977. "Valid Inequalities and Superadditivity for 0--1 Integer Programs," Mathematics of Operations Research, INFORMS, vol. 2(1), pages 66-77, February.
    4. Laurence A. Wolsey, 1976. "Technical Note—Facets and Strong Valid Inequalities for Integer Programs," Operations Research, INFORMS, vol. 24(2), pages 367-372, April.
    5. Hugues Marchand & Laurence A. Wolsey, 2001. "Aggregation and Mixed Integer Rounding to Solve MIPs," Operations Research, INFORMS, vol. 49(3), pages 363-371, June.
    6. WOLSEY, Laurence A., 1975. "Faces for a linear inequality in 0-1 variables," LIDAM Reprints CORE 218, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. Robert Bixby & Edward Rothberg, 2007. "Progress in computational mixed integer programming—A look back from the other side of the tipping point," Annals of Operations Research, Springer, vol. 149(1), pages 37-41, February.
    8. Zonghao Gu & George L. Nemhauser & Martin W.P. Savelsbergh, 2000. "Sequence Independent Lifting in Mixed Integer Programming," Journal of Combinatorial Optimization, Springer, vol. 4(1), pages 109-129, March.
    9. Harlan Crowder & Ellis L. Johnson & Manfred Padberg, 1983. "Solving Large-Scale Zero-One Linear Programming Problems," Operations Research, INFORMS, vol. 31(5), pages 803-834, October.
    10. WOLSEY, Laurence A., 1976. "Facets and strong valid inequalities for integer programs," LIDAM Reprints CORE 246, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    11. Santanu S. Dey & Marco Molinaro & Qianyi Wang, 2018. "Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs," Mathematics of Operations Research, INFORMS, vol. 43(1), pages 304-332, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Alper Atamtürk, 2004. "Sequence Independent Lifting for Mixed-Integer Programming," Operations Research, INFORMS, vol. 52(3), pages 487-490, June.
    2. Quentin Louveaux & Laurence Wolsey, 2007. "Lifting, superadditivity, mixed integer rounding and single node flow sets revisited," Annals of Operations Research, Springer, vol. 153(1), pages 47-77, September.
    3. Amar K. Narisetty & Jean-Philippe P. Richard & George L. Nemhauser, 2011. "Lifted Tableaux Inequalities for 0--1 Mixed-Integer Programs: A Computational Study," INFORMS Journal on Computing, INFORMS, vol. 23(3), pages 416-424, August.
    4. Alper Atamtürk, 2005. "Cover and Pack Inequalities for (Mixed) Integer Programming," Annals of Operations Research, Springer, vol. 139(1), pages 21-38, October.
    5. Wei-Kun Chen & Liang Chen & Yu-Hong Dai, 2023. "Lifting for the integer knapsack cover polyhedron," Journal of Global Optimization, Springer, vol. 86(1), pages 205-249, May.
    6. Zonghao Gu & George L. Nemhauser & Martin W.P. Savelsbergh, 2000. "Sequence Independent Lifting in Mixed Integer Programming," Journal of Combinatorial Optimization, Springer, vol. 4(1), pages 109-129, March.
    7. Santanu S. Dey & Jean-Philippe Richard, 2009. "Linear-Programming-Based Lifting and Its Application to Primal Cutting-Plane Algorithms," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 137-150, February.
    8. Christopher Hojny & Tristan Gally & Oliver Habeck & Hendrik Lüthen & Frederic Matter & Marc E. Pfetsch & Andreas Schmitt, 2020. "Knapsack polytopes: a survey," Annals of Operations Research, Springer, vol. 292(1), pages 469-517, September.
    9. Aardal, K.I. & van Hoesel, S., 1995. "Polyhedral Techniques in Combinatorial Optimization," Other publications TiSEM ed028a07-eb6a-4c8d-8f21-d, Tilburg University, School of Economics and Management.
    10. Amitabh Basu & Pierre Bonami & Gérard Cornuéjols & François Margot, 2011. "Experiments with Two-Row Cuts from Degenerate Tableaux," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 578-590, November.
    11. Michele Conforti & Gérard Cornuéjols & Giacomo Zambelli, 2011. "A Geometric Perspective on Lifting," Operations Research, INFORMS, vol. 59(3), pages 569-577, June.
    12. Manfred Padberg, 2005. "Classical Cuts for Mixed-Integer Programming and Branch-and-Cut," Annals of Operations Research, Springer, vol. 139(1), pages 321-352, October.
    13. Wei-Kun Chen & Liang Chen & Mu-Ming Yang & Yu-Hong Dai, 2018. "Generalized coefficient strengthening cuts for mixed integer programming," Journal of Global Optimization, Springer, vol. 70(1), pages 289-306, January.
    14. I. R. De Farias & E. L. Johnson & G. L. Nemhauser, 2002. "Facets of the Complementarity Knapsack Polytope," Mathematics of Operations Research, INFORMS, vol. 27(1), pages 210-226, February.
    15. Robert E. Bixby & Eva K. Lee, 1998. "Solving a Truck Dispatching Scheduling Problem Using Branch-and-Cut," Operations Research, INFORMS, vol. 46(3), pages 355-367, June.
    16. Absi, Nabil & Kedad-Sidhoum, Safia, 2008. "The multi-item capacitated lot-sizing problem with setup times and shortage costs," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1351-1374, March.
    17. Pasquale Avella & Maurizio Boccia & Igor Vasilyev, 2012. "Computational Testing of a Separation Procedure for the Knapsack Set with a Single Continuous Variable," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 165-171, February.
    18. Chardy, M. & Costa, M.-C. & Faye, A. & Trampont, M., 2012. "Optimizing splitter and fiber location in a multilevel optical FTTH network," European Journal of Operational Research, Elsevier, vol. 222(3), pages 430-440.
    19. Kaparis, Konstantinos & Letchford, Adam N., 2008. "Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 186(1), pages 91-103, April.
    20. Laszlo Ladanyi & Jon Lee & Robin Lougee-Heimer, 2005. "Rapid Prototyping of Optimization Algorithms Using COIN-OR: A Case Study Involving the Cutting-Stock Problem," Annals of Operations Research, Springer, vol. 139(1), pages 243-265, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:36:y:2024:i:3:p:884-899. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.