Approximate extended formulations

DOI10.1007/s10107-005-0663-7zbMath1085.90051OpenAlexW2091565303MaRDI QIDQ2583138

Laurence A. Wolsey, Mathieu Van Vyve

Publication date: 13 January 2006

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-005-0663-7

zbMATH Keywords

Traveling salesman problemApproximationConvex hullMixed integer programmingExtended formulationLot-sizing

Mathematics Subject Classification ID

Mixed integer programming (90C11) Combinatorial optimization (90C27)

Related Items (36)

Knapsack polytopes: a survey ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ Efficient reformulations for dynamic lot-sizing problems with product substitution ⋮ Period Decompositions for the Capacitated Lot Sizing Problem with Setup Times ⋮ Stochastic lot sizing problem with nervousness considerations ⋮ Extended formulation and valid inequalities for the multi-item inventory lot-sizing problem with supplier selection ⋮ New valid inequalities and formulations for the static joint chance-constrained lot-sizing problem ⋮ Relaxations for two-level multi-item lot-sizing problems ⋮ Combined ship routing and inventory management in the salmon farming industry ⋮ Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems ⋮ Tightening simple mixed-integer sets with guaranteed bounds ⋮ Fixed-charge transportation on a path: optimization, LP formulations and separation ⋮ LS-LIB: A Library of Tools for Solving Production Planning Problems ⋮ Column generation for extended formulations ⋮ Compact formulations as a union of polyhedra ⋮ Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem ⋮ Natural and extended formulations for the time-dependent traveling salesman problem ⋮ Approximate formulations for 0-1 knapsack sets ⋮ Fixed-Charge Transportation on a Path: Linear Programming Formulations ⋮ Valid inequalities, preprocessing, and an effective heuristic for the uncapacitated three-level lot-sizing and replenishment problem with a distribution structure ⋮ Extended formulations in combinatorial optimization ⋮ A heuristic approach for big bucket multi-level production planning problems ⋮ Valid inequalities for two-period relaxations of big-bucket lot-sizing problems: zero setup case ⋮ MIP formulations and heuristics for two-level production-transportation problems ⋮ Extended formulations in combinatorial optimization ⋮ On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space ⋮ Uncapacitated two-level lot-sizing ⋮ Robust formulations for economic lot-sizing problem with remanufacturing ⋮ Polyhedral and Lagrangian approaches for lot sizing with production time windows and setup times ⋮ Mixed Integer Linear Programming Formulation Techniques ⋮ Balas formulation for the union of polytopes is optimal ⋮ Multi-item lot-sizing with joint set-up costs ⋮ Uncapacitated lot sizing with backlogging: the convex hull ⋮ A Horizon Decomposition Approach for the Capacitated Lot-Sizing Problem with Setup Times ⋮ Column Generation for Extended Formulations ⋮ Lower bound on size of branch-and-bound trees for solving lot-sizing problem

Uses Software

• TSPLIB
• bc-prod

Cites Work

• Unnamed Item
• An analytical comparison of different formulations of the travelling salesman problem
• Reformulations of the shortest route model for dynamic multi-item multi-level capacitated lotsizing
• Strong formulations for mixed integer programs: valid inequalities and extended formulations
• Improved lower bounds for the capacitated lot sizing problem with setup times.
• A primal all-integer algorithm based on irreducible solutions
• Polyhedra for lot-sizing with Wagner-Whitin costs
• A solution approach of production planning problems based on compact formulations for single-item lot-sizing models. (Abstract of thesis)
• Linear-programming extended formulations for the single-item lot-sizing problem with backlogging and constant capacity
• Solving Multi-Item Lot-Sizing Problems with an MIP Solver Using Classification and Reformulation
• bc — prod: A Specialized Branch-and-Cut System for Lot-Sizing Problems
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Integer Programming Formulation of Traveling Salesman Problems
• Uncapacitated lot-sizing: The convex hull of solutions
• Tight Mip Formulation for Multi-Item Discrete Lot-Sizing Problems
• Solving Multi-Item Capacitated Lot-Sizing Problems Using Variable Redefinition
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Disjunctive Programming

This page was built for publication: Approximate extended formulations