Covering, Packing and Knapsack Problems

DOI10.1016/S0167-5060(08)70831-8MaRDI QIDQ4194731zbMATH OpenOpenAlexFDO

Authors Manfred Padberg

Publication date 1979

Published in Discrete Optimization I, Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0167-5060(08)70831-8

zbMATH Keywords

CoveringFacial StructuresKnapsack ProblemsLarge Scale Integer Linear ProgrammingPackingSurvey

Mathematics Subject Classification ID

Linear programming (90C05) Boolean programming (90C09) Integer programming (90C10)

Cited in

(29)

• Exact methods for the knapsack problem and its generalizations
• Facets of the knapsack polytope derived from disjoint and overlapping index configurations
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• On the facial structure of the set covering polytope
• Facets and lifting procedures for the set covering polytope
• Conditional clusters, musters, and probability
• A characterization of knapsacks with the max-flow--min-cut property
• Polyhedral results for the precedence-constrained knapsack problem
• The maximum clique problem
• Valid inequalities for a class of assembly system problems
• A concurrent processing framework for the set partitioning problem
• Future paths for integer programming and links to artificial intelligence
• Facets and algorithms for capacitated lot sizing
• Valid inequalities and separation for mixed 0-1 constraints with variable upper bounds
• The simple plant location problem: Survey and synthesis
• Reliability, covering and balanced matrices
• Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems
• A branch and cut algorithm for minimum spanning trees under conflict constraints
• Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
• A Boolean theory of signatures for tonal scales
• Transitive packing
• Classical cuts for mixed-integer programming and branch-and-cut
• A unified approach to approximating partial covering problems
• Interval propagation to reason about sets: Definition and implementation of a practical language
• Large-scale 0-1 linear programming on distributed workstations
• Cover and pack inequalities for (mixed) integer programming
• Integer-programming software systems
• Airline crew scheduling: state-of-the-art
• Facet defining inequalities for the dichotomous knapsack problem

This page was built for publication: Covering, Packing and Knapsack Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4194731)