NDLI: A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming

Content Provider	Springer Nature Link
Author	Balas, Egon Perregaard, Michael
Copyright Year	2002
Abstract	We establish a precise correspondence between lift-and-project cuts for mixed 0-1 programs, simple disjunctive cuts (intersection cuts) and mixed-integer Gomory cuts. The correspondence maps members of one family onto members of the others. It also maps bases of the higher-dimensional cut generating linear program (CGLP) into bases of the linear programming relaxation. It provides new bounds on the number of facets of the elementary closure, and on the rank, of the standard linear programming relaxation of the mixed 0-1 polyhedron with respect to the above families of cutting planes. Based on the above correspondence, we develop an algorithm that solves (CGLP) without explicitly constructing it, by mimicking the pivoting steps of the higher dimensional (CGLP) simplex tableau by certain pivoting steps in the lower dimensional (LP) simplex tableau. In particular, we show how to calculate the reduced costs of the big tableau from the entries of the small tableau and based on this, how to identify a pivot in the small tableau that corresponds to one or several improving pivots in the big tableau. The overall effect is a much improved lift-and-project cut generating procedure, which can also be interpreted as an algorithm for a systematic improvement of mixed integer Gomory cuts from the small tableau.
Starting Page	221
Ending Page	245
Page Count	25
File Format	PDF
ISSN	00255610
Journal	Mathematical Programming
Volume Number	94
Issue Number	2-3
e-ISSN	14364646
Language	English
Publisher	Springer-Verlag
Publisher Date	2003-01-01
Publisher Place	Berlin Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Computations with disjunctive cuts for two-stage stochastic mixed 0-1 integer programs

Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants

Lift-and-project cuts for convex mixed integer nonlinear programs : Linear programming based separation and extended formulations

Computing deep facet-defining disjunctive cuts for mixed-integer programming

A convex-analysis perspective on disjunctive cuts

A relax-and-cut framework for Gomory mixed-integer cuts

Intersection cuts from multiple rows: a disjunctive programming approach

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

Lifted inequalities for 0-1 mixed integer programming: Superlinear lifting

A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming

Similar Documents

Computations with disjunctive cuts for two-stage stochastic mixed 0-1 integer programs

Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants

Lift-and-project cuts for convex mixed integer nonlinear programs : Linear programming based separation and extended formulations

Computing deep facet-defining disjunctive cuts for mixed-integer programming

A convex-analysis perspective on disjunctive cuts

A relax-and-cut framework for Gomory mixed-integer cuts

Intersection cuts from multiple rows: a disjunctive programming approach

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

Lifted inequalities for 0-1 mixed integer programming: Superlinear lifting

A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming