Approximate extended formulations
From MaRDI portal
Publication:2583138
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
Traveling salesman problemApproximationConvex hullMixed integer programmingExtended formulationLot-sizing
Related Items
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
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
