Dynamic knapsack sets and capacitated lot-sizing
| Autor: | Laurence A. Wolsey, Hugues Marchand, Marko Loparic |
|---|---|
| Rok vydání: | 2003 |
| Předmět: |
Mathematical optimization
Intersection (set theory) Generalization General Mathematics Continuous knapsack problem MathematicsofComputing_NUMERICALANALYSIS Knapsack sets valid inequalities simultaneous lifting lot-sizing WagnerWhitin costs Cutting stock problem Knapsack problem Combinatorial optimization Change-making problem Relaxation (approximation) Software Mathematics |
| Zdroj: | Mathematical Programming. 95:53-69 |
| ISSN: | 1436-4646 0025-5610 |
| DOI: | 10.1007/s10107-002-0341-y |
| Popis: | A dynamic knapsack set is a natural generalization of the 0-1 knapsack set with a continuous variable studied recently. For dynamic knapsack sets a large family of facet-defining inequalities, called dynamic knapsack inequalities, are derived by fixing variables to one and then lifting. Surprisingly such inequalities have the simultaneous lifting property, and for small instances provide a significant proportion of all the facet-defining inequalities. We then consider single-item capacitated lot-sizing problems, and propose the joint study of three related sets. The first models the discrete lotsizing problem, the second the continuous lot-sizing problem with WagnerWhitin costs, and the third the continuous lot-sizing problem with arbitrary costs. The first set that arises is precisely a dynamic knapsack set, the second an intersection of dynamic knapsack sets, and the unrestricted problem can be viewed as both a relaxation and a restriction of the second. It follows that the dynamic knapsack inequalities and their generalizations provide strong valid inequalities for all three sets. Some limited computation results are reported as an initial test of the effectiveness of these inequalities on capacitated lot-sizing problems. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|