NDLI: Deriving compact extended formulations via LP-based separation techniques

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

Deriving compact extended formulations via LP-based separation techniques

Content Provider	Springer Nature Link
Author	Lancia, Giuseppe Serafini, Paolo
Copyright Year	2014
Abstract	The best formulations for some combinatorial optimization problems are integer linear programming models with an exponential number of rows and/or columns, which are solved incrementally by generating missing rows and columns only when needed. As an alternative to row generation, some exponential formulations can be rewritten in a compact extended form, which have only a polynomial number of constraints and a polynomial, although larger, number of variables. As an alternative to column generation, there are compact extended formulations for the dual problems, which lead to compact equivalent primal formulations, again with only a polynomial number of constraints and variables. In this this paper we introduce a tool to derive compact extended formulations and survey many combinatorial optimization problems for which it can be applied. The tool is based on the possibility of formulating the separation procedure by an LP model. It can be seen as one further method to generate compact extended formulations besides other tools of geometric and combinatorial nature present in the literature.
Ending Page	234
Page Count	34
Starting Page	201
File Format	PDF
ISSN	16194500
e-ISSN	16142411
Journal	4OR
Issue Number	3
Volume Number	12
Language	English
Publisher	Springer Berlin Heidelberg
Publisher Date	2014-06-24
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Integer programming Operations Research/Decision Theory Industrial and Production Engineering Integer linear programming Branch-and-price Combinatorial optimization Branch-and-cut Compact extended formulations Polyhedral combinatorics, branch-and-bound, branch-and-cut Optimization
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Management Science and Operations Research Management Information Systems Computational Theory and Mathematics

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

Deriving compact extended formulations via LP-based separation techniques

The time dependent traveling salesman problem: polyhedra and algorithm

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

Extended formulations in combinatorial optimization

LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison

Solving network design problems via iterative aggregation

Testing cut generators for mixed-integer linear programming

Extended Formulations in Combinatorial Optimization

Branch-and-cut for complementarity-constrained optimization

Deriving compact extended formulations via LP-based separation techniques

Similar Documents

Deriving compact extended formulations via LP-based separation techniques

The time dependent traveling salesman problem: polyhedra and algorithm

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

Extended formulations in combinatorial optimization

LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison

Solving network design problems via iterative aggregation

Testing cut generators for mixed-integer linear programming

Extended Formulations in Combinatorial Optimization

Branch-and-cut for complementarity-constrained optimization

Deriving compact extended formulations via LP-based separation techniques