Facets of the knapsack polytope derived from disjoint and overlapping index configurations
From MaRDI portal
Necessary and sufficient easily verifiable conditions for a class of facets of the knapsack polytope based on two overlapping minimal covers are derived. The conditions are specialized for the case where the minimal covers are disjoint. These conditions may be extended to an arbitrary number of disjoint knapsack constraints. Conditions for facets based on two disjoint (1,k)-configurations are also derived.
Recommendations
- scientific article; zbMATH DE number 4087427
- Minimal covers, minimal sets and canonical facets of the posynomial knapsack polytope
- (1,k)-configuration facets for the generalized assignment problem
- A characterization of lifted-cover facets of knapsack polytope with GUP constraints
- Lifted cover facets of the 0-1 knapsack polytope with GUB constraints
Cites work
- (1,k)-configurations and facets for packing problems
- Covering, Packing and Knapsack Problems
- Faces for a linear inequality in O-1 variables
- Facet of regular O-1 polytopes
- Facets of the knapsack polytope
- Facets of the Knapsack Polytope From Minimal Covers
- scientific article; zbMATH DE number 3566549 (Why is no real title available?)
- Lifting the facets of zero-one polytopes
- Technical Note—A Note on Zero-One Programming
Cited in
(12)- Facets and lifting procedures for the set covering polytope
- A characterization of knapsacks with the max-flow--min-cut property
- On the facets of the mixed-integer knapsack polyhedron
- A concise characterization of strong knapsack facets
- scientific article; zbMATH DE number 4087427 (Why is no real title available?)
- The intersection of knapsack polyhedra and extensions
- Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1
- Computational aspects of lifted cover inequalities for knapsacks with few different weights
- Minimal covers, minimal sets and canonical facets of the posynomial knapsack polytope
- Knapsack polytopes: a survey
- (1,k)-configuration facets for the generalized assignment problem
- Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes
This page was built for publication: Facets of the knapsack polytope derived from disjoint and overlapping index configurations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1103523)