Deriving compact extended formulations via LP-based separation techniques

DOI10.1007/s10479-015-2012-4zbMath1342.90165OpenAlexW1977974598MaRDI QIDQ5925168

Paolo Serafini, Giuseppe Lancia

Publication date: 22 July 2016

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-015-2012-4

zbMATH Keywords

integer linear programmingbranch-and-cutbranch-and-pricecompact extended formulations

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Exact solution of the robust knapsack problem
• A time-indexed LP-based approach for min-sum job-shop problems
• On cuts and matchings in planar graphs
• Solution of large-scale symmetric travelling salesman problems
• On compact formulations for integer programs solved by column generation
• Matrices with the Edmonds-Johnson property
• Experiments in quadratic 0-1 programming
• The ellipsoid method and its consequences in combinatorial optimization
• Using separation algorithms to generate mixed integer model reformulations
• Expressing combinatorial optimization problems by linear programs
• Geometric algorithms and combinatorial optimization
• Exact solution of bin-packing problems using column generation and branch-and-bound
• On certain polytopes associated with graphs
• Robust discrete optimization and network flows
• Compact vs. exponential-size LP relaxations
• Compact optimization can outperform separation: a case study in structural proteomics
• LP models for bin packing and cutting stock problems
• Cutting plane versus compact formulations for uncertain (integer) linear programs
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• An effective compact formulation of the max cut problem on sparse graphs
• Sorting Permutations by Reversals Through Branch-and-Price
• Constructing Extended Formulations from Reflection Relations
• Optimum Communication Spanning Trees
• A Linear Programming Approach to the Cutting-Stock Problem
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• The Price of Robustness
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Packing cycles in undirected graphs
• Exact algorithms for minimum routing cost trees
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• A Linear Programming Approach to the Cutting Stock Problem—Part II
• Solution of a Large-Scale Traveling-Salesman Problem
• On the Robust Knapsack Problem
• Linear vs. semidefinite extended formulations
• Deriving compact extended formulations via LP-based separation techniques
• Extended formulations in combinatorial optimization

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