On the relationship between standard intersection cuts, lift-and-project cuts, and generalized intersection cuts

Balas, Egon and Kis, Tamás (2016) On the relationship between standard intersection cuts, lift-and-project cuts, and generalized intersection cuts. MATHEMATICAL PROGRAMMING, 160. pp. 85-114. ISSN 0025-5610

Preview

Text EBalas - TKis On the relationship latex 12 11 15-tks.pdf Download (365kB) | Preview

Abstract

We examine the connections between the classes of cuts in the title. We show that lift-and-project (L&P) cuts from a given disjunction are equivalent to generalized intersection cuts (GICs) from the family of polyhedra obtained by taking positive com- binations of the complements of the inequalities of each term of the disjunction. While L&P cuts from split disjunctions are known to be equivalent to standard intersection cuts (SICs) from the strip obtained by complementing the terms of the split, we show that L&P cuts from more general disjunctions may not be equivalent to any SIC. In particular, we give easily verifiable necessary and sufficient conditions for a L&P cut from a given disjunction D to be equivalent to a SIC from the polyhedral counterpart of D. Irregular L&P cuts, i.e. those that violate these conditions, have interesting properties. For instance, unlike the regular ones, they may cut off part of the corner polyhedron associated with the LP solution from which they are derived. Furthermore, they are not exceptional: their frequency exceeds that of regular cuts. A numerical example illustrates some of the above properties.

Item Type:	Article
Subjects:	Q Science / természettudomány > QA Mathematics / matematika
Depositing User:	Dr. Tamás Kis
Date Deposited:	26 Oct 2016 08:04
Last Modified:	04 Apr 2023 11:49
URI:	http://real.mtak.hu/id/eprint/42010

Available Versions of this Item

• On the relationship between standard intersection cuts, lift-and-project cuts, and generalized intersection cuts. (deposited 09 Sep 2015 08:46)
  • On the relationship between standard intersection cuts, lift-and-project cuts, and generalized intersection cuts. (deposited 26 Dec 2015 08:49)
    • On the relationship between standard intersection cuts, lift-and-project cuts, and generalized intersection cuts. (deposited 15 Jan 2016 12:13)
      • On the relationship between standard intersection cuts, lift-and-project cuts, and generalized intersection cuts. (deposited 26 Oct 2016 08:04) [Currently Displayed]

Actions (login required)

Edit Item