A note on the knapsack problem with special ordered sets

DOI10.1016/0167-6377(81)90019-5zbMath0493.90062OpenAlexW2001472819MaRDI QIDQ1168894

Ellis L. Johnson, Manfred W. Padberg

Publication date: 1981

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(81)90019-5

zbMATH Keywords

algorithmconvex hullknapsack problemlinear programming relaxationfacetsspecial ordered setsgeneralized upper boundsarbitrarily signed coefficientsassociated zero-one polytopeDantzig method

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Boolean programming (90C09)

Related Items (28)

Solving binary cutting stock problems by column generation and branch- and-bound ⋮ Selecting hierarchical facilities in a service-operations environment ⋮ Knapsack polytopes: a survey ⋮ Exact methods for the knapsack problem and its generalizations ⋮ A new Lagrangian relaxation approach to the generalized assignment problem ⋮ Solving the linear multiple choice knapsack problem with two objectives: Profit and equity ⋮ Optimal multicast route packing ⋮ Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: Properties and algorithms ⋮ A versatile algorithm for assembly line balancing ⋮ Maximizing revenue of end of life items in retail stores ⋮ Exact approaches for the knapsack problem with setups ⋮ Multiple-choice knapsack constraint in graphical models ⋮ The knapsack problem with generalized upper bounds ⋮ Sequence independent lifting for mixed knapsack problems with GUB constraints ⋮ A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: strong valid inequalities by sequence-independent lifting ⋮ A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting ⋮ The capacitated maximal covering location problem with backup service ⋮ A branch \& bound algorithm for the 0-1 mixed integer knapsack problem with linear multiple choice constraints ⋮ Higher-order cover cuts from zero-one knapsack constraints augmented by two-sided bounding inequalities ⋮ Valid inequalities for the multi-dimensional multiple-choice 0-1 knapsack problem ⋮ Capacitated emergency facility siting with multiple levels of backup ⋮ Minmax linear knapsack problem with grouped variables and gub ⋮ Continuous maximin knapsack problems with GLB constraints ⋮ Computational comparison on the partitioning strategies in multiple choice integer programming ⋮ Cutting planes for mixed-integer knapsack polyhedra ⋮ Knapsack problems with setups ⋮ A fast algorithm for the linear multiple-choice knapsack problem ⋮ Cover and pack inequalities for (mixed) integer programming

Cites Work

• Unnamed Item
• Solving Large-Scale Zero-One Linear Programming Problems
• (1,k)-configurations and facets for packing problems
• The Linear Multiple Choice Knapsack Problem
• Technical Note—A Note on Zero-One Programming
• Facet of regular 0–1 polytopes

This page was built for publication: A note on the knapsack problem with special ordered sets