A study of the lot-sizing polytope
This is an analysis of the convex hull of feasible solutions \(F\) of the lot-sizing problem in bottleneck flow formulation. First, it is shown that the convex hull of \(F\) is full dimensional and trivial facets are given. Then the authors define bottlenecks of sets \(S\) and bottleneck covers to introduce bottleneck cover inequalities (BCI). These inequalities are at least as strong as flow cover inequalities and surrogate flow cover inequalities. It is shown that they are valid and that every fractional extreme point of the linear relaxation is defined by a bottleneck cover: BCI cut off all fractional extreme points. Necessary and sufficient conditions for BCI to be facet defining for conv(\(F\)) are given. Furthermore, lifted bottleneck covers are investigated. It is shown that these inequalities yield a complete description of conv(\(F\)) for the uncpacitated case and a polynomial time separation algorithm is given for the constant capacity case. Finally, numerical experiments show that the cuts are effective in solving lot-sizing problems.
- Lot-sizing polyhedra with a cardinality constraint
- A polyhedral study of the static probabilistic lot-sizing problem
- Lower bounds in lot-sizing models: A polyhedral study
- A polyhedral study of lot-sizing with supplier selection
- Polyhedra for lot-sizing with Wagner-Whitin costs
- A polyhedral study of multiechelon lot sizing with intermediate demands
- scientific article; zbMATH DE number 903952
- Uncapacitated lot-sizing: The convex hull of solutions
- On the Wagner-Whitin lot-sizing polyhedron.
- Lot Sizing with Inventory Bounds and Fixed Costs: Polyhedral Study and Computation
- Uncapacitated lot sizing with backlogging: the convex hull
- Lot-sizing polyhedra with a cardinality constraint
- Partial objective inequalities for the multi-item capacitated lot-sizing problem
- Single-item dynamic lot-sizing problems: an updated survey
- Valid inequalities for separable concave constraints with indicator variables
- Polyhedra for lot-sizing with Wagner-Whitin costs
- Mixed \(n\)-step MIR inequalities: facets for the \(n\)-mixing set
- A computational analysis of lower bounds for big bucket production planning problems
- A branch-and-cut algorithm for an assembly routing problem
- Lot-sizing with fixed charges on stocks: the convex hull
- Optimizing over the split closure
- A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem
- Lower bounds in lot-sizing models: A polyhedral study
- Dynamic programming approximation algorithms for the capacitated lot-sizing problem
- Local cuts and two-period convex hull closures for big-bucket lot-sizing problems
- LS-LIB: a library of tools for solving production planning problems
- DASH: dynamic approach for switching heuristics
- Multiechelon Lot Sizing: New Complexities and Inequalities
- Lifting, superadditivity, mixed integer rounding and single node flow sets revisited
- New valid inequalities and formulations for the static joint chance-constrained lot-sizing problem
- Scenario-dominance to multi-stage stochastic lot-sizing and knapsack problems
- Supermodularity and valid inequalities for quadratic optimization with indicators
- Learning optimal solutions via an LSTM-optimization framework
- On lot sizing with capacity acquisition
- Single item lot-sizing with non-decreasing capacities
- A heuristic approach for big bucket multi-level production planning problems
This page was built for publication: A study of the lot-sizing polytope
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1881043)
