IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v257y2017i2p420-428.html
   My bibliography  Save this article

A new lift-and-project operator

Author

Listed:
  • Bodur, Merve
  • Dash, Sanjeeb
  • Günlük, Oktay

Abstract

In this paper, we analyze the strength of split cuts in a lift-and-project framework. We first observe that the Lovász–Schrijver and Sherali–Adams lift-and-project operator hierarchies can be viewed as applying specific 0–1 split cuts to an appropriate extended formulation and demonstrate how to strengthen these hierarchies using additional split cuts. More precisely, we define a new operator that adds all 0–1 split cuts to the extended formulation. For 0–1 mixed-integer sets with k binary variables, this new operator is guaranteed to obtain the integer hull in ⌈k/2⌉ steps compared to k steps for the Lovász–Schrijver or the Sherali–Adams operator. We also present computational results on the stable set problem with our new operator.

Suggested Citation

  • Bodur, Merve & Dash, Sanjeeb & Günlük, Oktay, 2017. "A new lift-and-project operator," European Journal of Operational Research, Elsevier, vol. 257(2), pages 420-428.
    • Handle: RePEc:eee:ejores:v:257:y:2017:i:2:p:420-428
    DOI: 10.1016/j.ejor.2016.07.057
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716306129
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.07.057?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Adams, Warren P. & Guignard, Monique & Hahn, Peter M. & Hightower, William L., 2007. "A level-2 reformulation-linearization technique bound for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 180(3), pages 983-996, August.
    2. Egon Balas, 2005. "Projection, Lifting and Extended Formulation in Integer and Combinatorial Optimization," Annals of Operations Research, Springer, vol. 140(1), pages 125-161, November.
    3. William Cook & Sanjeeb Dash, 2001. "On the Matrix-Cut Rank of Polyhedra," Mathematics of Operations Research, INFORMS, vol. 26(1), pages 19-30, 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. Rostami, Borzou & Malucelli, Federico & Belotti, Pietro & Gualandi, Stefano, 2016. "Lower bounding procedure for the asymmetric quadratic traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 253(3), pages 584-592.
    2. STEPHAN, Rüdiger, 2010. "An extension of disjunctive programming and its impact for compact tree formulations," LIDAM Discussion Papers CORE 2010045, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. Pessoa, Artur Alves & Hahn, Peter M. & Guignard, Monique & Zhu, Yi-Rong, 2010. "Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization Technique," European Journal of Operational Research, Elsevier, vol. 206(1), pages 54-63, October.
    4. Richárd Molnár-Szipai & Anita Varga, 2019. "Integrating combinatorial algorithms into a linear programming solver," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 27(2), pages 475-482, June.
    5. Huizhen Zhang & Cesar Beltran-Royo & Liang Ma, 2013. "Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers," Annals of Operations Research, Springer, vol. 207(1), pages 261-278, August.
    6. Filipa D. Carvalho & Maria Teresa Almeida, 2017. "The triangle k-club problem," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 814-846, April.
    7. Jiming Peng & Tao Zhu & Hezhi Luo & Kim-Chuan Toh, 2015. "Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting," Computational Optimization and Applications, Springer, vol. 60(1), pages 171-198, January.
    8. Hahn, Peter M. & Kim, Bum-Jin & Stutzle, Thomas & Kanthak, Sebastian & Hightower, William L. & Samra, Harvind & Ding, Zhi & Guignard, Monique, 2008. "The quadratic three-dimensional assignment problem: Exact and approximate solution methods," European Journal of Operational Research, Elsevier, vol. 184(2), pages 416-428, January.
    9. Pratik Worah, 2015. "Rank bounds for a hierarchy of Lovász and Schrijver," Journal of Combinatorial Optimization, Springer, vol. 30(3), pages 689-709, October.
    10. Peter Hahn & J. MacGregor Smith & Yi-Rong Zhu, 2010. "The Multi-Story Space Assignment Problem," Annals of Operations Research, Springer, vol. 179(1), pages 77-103, September.
    11. Nyberg, Axel & Westerlund, Tapio, 2012. "A new exact discrete linear reformulation of the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 220(2), pages 314-319.
    12. W. Hager, 2009. "COAP 2008 best paper award: Paper of P.M. Hahn, B.-J. Kim, M. Guignard, J.M. Smith and Y.-R. Zhu," Computational Optimization and Applications, Springer, vol. 44(3), pages 525-530, December.
    13. Alexandre Domingues Gonçalves & Artur Alves Pessoa & Cristiana Bentes & Ricardo Farias & Lúcia Maria de A. Drummond, 2017. "A Graphics Processing Unit Algorithm to Solve the Quadratic Assignment Problem Using Level-2 Reformulation-Linearization Technique," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 676-687, November.
    14. Nihal Berktaş & Hande Yaman, 2021. "A Branch-and-Bound Algorithm for Team Formation on Social Networks," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1162-1176, July.
    15. Monique Laurent, 2003. "A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0--1 Programming," Mathematics of Operations Research, INFORMS, vol. 28(3), pages 470-496, August.
    16. Richard J. Forrester & Lucas A. Waddell, 2022. "Strengthening a linear reformulation of the 0-1 cubic knapsack problem via variable reordering," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 498-517, August.
    17. Lucas A. Waddell & Jerry L. Phillips & Tianzhu Liu & Swarup Dhar, 2023. "An LP-based characterization of solvable QAP instances with chess-board and graded structures," Journal of Combinatorial Optimization, Springer, vol. 45(5), pages 1-23, July.
    18. Peter M. Hahn & Yi-Rong Zhu & Monique Guignard & William L. Hightower & Matthew J. Saltzman, 2012. "A Level-3 Reformulation-Linearization Technique-Based Bound for the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 24(2), pages 202-209, May.
    19. E. de Klerk & R. Sotirov & U. Truetsch, 2015. "A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 378-391, May.
    20. Palubeckis, Gintaras, 2015. "Fast simulated annealing for single-row equidistant facility layout," Applied Mathematics and Computation, Elsevier, vol. 263(C), pages 287-301.

    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:eee:ejores:v:257:y:2017:i:2:p:420-428. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.