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

Please wait, while we are loading the content...

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

Content Provider	Springer Nature Link
Author	Kılınç, Mustafa R. Linderoth, Jeff Luedtke, James
Copyright Year	2017
Abstract	We describe a computationally effective method for generating lift-and-project cuts for convex mixed-integer nonlinear programs (MINLPs). The method relies on solving a sequence of cut-generating linear programs and in the limit generates an inequality as strong as the lift-and-project cut that can be obtained from solving a cut-generating nonlinear program. Using this procedure, we are able to approximately optimize over the rank one lift-and-project closure for a variety of convex MINLP instances. The results indicate that lift-and-project cuts have the potential to close a significant portion of the integrality gap for convex MINLPs. In addition, we find that using this procedure within a branch-and-cut solver for convex MINLPs significantly reduces the total solution time for many instances. We also demonstrate that combining lift-and-project cuts with an extended formulation that exploits separability of convex functions yields significant improvements in both relaxation bounds and the time to calculate the relaxation. Overall, these results suggest that with an effective separation routine, like the one proposed here, lift-and-project cuts may be as effective for solving convex MINLPs as they have been for solving mixed-integer linear programs.
Starting Page	499
Ending Page	526
Page Count	28
File Format	PDF
ISSN	18672949
Journal	Mathematical Programming Computation
Volume Number	9
Issue Number	4
e-ISSN	18672957
Language	English
Publisher	Springer Berlin Heidelberg
Publisher Date	2017-01-25
Publisher Institution	Mathematical Optimization Society
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Lift-and-project cuts Extended formulations Mixed-integer nonlinear programming Mixed integer programming Nonlinear programming Polyhedral combinatorics, branch-and-bound, branch-and-cut Optimization Operations Research/Decision Theory Theory of Computation Mathematics of Computing
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science 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

Local cuts for mixed-integer programming

A hybrid branch-and-bound approach for exact rational mixed-integer programming

Practical strategies for generating rank-1 split cuts in mixed-integer linear programming

Testing cut generators for mixed-integer linear programming

Deriving compact extended formulations via LP-based separation techniques

On optimizing over lift-and-project closures

Classical Cuts for Mixed-Integer Programming and Branch-and-Cut

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

Valid inequalities for mixed integer linear programs

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

Similar Documents

Local cuts for mixed-integer programming

A hybrid branch-and-bound approach for exact rational mixed-integer programming

Practical strategies for generating rank-1 split cuts in mixed-integer linear programming

Testing cut generators for mixed-integer linear programming

Deriving compact extended formulations via LP-based separation techniques

On optimizing over lift-and-project closures

Classical Cuts for Mixed-Integer Programming and Branch-and-Cut

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

Valid inequalities for mixed integer linear programs

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