Deriving compact extended formulations via LP-based separation techniques

DOI10.1007/S10288-014-0262-7MaRDI QIDQ5892024zbMATH OpenOpenAlexFDO

Authors Giuseppe Lancia, Paolo Serafini

Publication date 17 December 2014

Published in 4OR (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10288-014-0262-7

zbMATH Keywords

branch-and-cutbranch-and-pricecompact extended formulationsinteger linear programming

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Deriving compact extended formulations via LP-based separation techniques
• Extended formulations in combinatorial optimization
• Extended formulations in combinatorial optimization
• Compact extended linear programming models
• Compact vs. exponential-size LP relaxations

Cites work

• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A Linear Programming Approach to the Cutting Stock Problem—Part II
• A Linear Programming Approach to the Cutting-Stock Problem
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• A time-indexed LP-based approach for min-sum job-shop problems
• An effective compact formulation of the max cut problem on sparse graphs
• Branch-and-price: Column generation for solving huge integer programs
• Compact optimization can outperform separation: a case study in structural proteomics
• Compact vs. exponential-size LP relaxations
• Constructing extended formulations from reflection relations
• Cutting plane versus compact formulations for uncertain (integer) linear programs
• Exact algorithms for minimum routing cost trees
• Exact solution of bin-packing problems using column generation and branch-and-bound
• Exact solution of the robust knapsack problem
• Experiments in quadratic 0-1 programming
• Extended formulations in combinatorial optimization
• scientific article; zbMATH DE number 1102774 (Why is no real title available?)
• Linear vs. semidefinite extended formulations
• LP models for bin packing and cutting stock problems
• Matrices with the Edmonds-Johnson property
• On certain polytopes associated with graphs
• On cuts and matchings in planar graphs
• On the robust knapsack problem
• Optimum Communication Spanning Trees
• Packing cycles in undirected graphs
• Robust discrete optimization and network flows
• Solution of a Large-Scale Traveling-Salesman Problem
• Solution of large-scale symmetric travelling salesman problems
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Sorting permutations by reversals through branch-and-price
• The Price of Robustness
• Using separation algorithms to generate mixed integer model reformulations

Cited in

(13)

• Integer-friendly formulations for the \(r\)-separation problem
• Compact vs. exponential-size LP relaxations
• Compact extended linear programming models
• Surveys in operations research
• Compact optimization can outperform separation: a case study in structural proteomics
• Arc flow formulations based on dynamic programming: theoretical foundations and applications
• Twelve surveys in operations research
• Strong and compact relaxations in the original space using a compact extended formulation
• Extended formulations in combinatorial optimization
• Extended formulations in combinatorial optimization
• Deriving compact extended formulations via LP-based separation techniques
• An extended formulation for the 1‐wheel inequalities of the stable set polytope
• Still more surveys in operations research\dots

This page was built for publication: Deriving compact extended formulations via LP-based separation techniques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5892024)