Higher-order cover cuts from zero-one knapsack constraints augmented by two-sided bounding inequalities

DOI10.1016/J.DISOPT.2007.02.002MaRDI QIDQ951101zbMATH OpenOpenAlexFDO

Authors Hanif D. Sherali, Fred Glover

Publication date 29 October 2008

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2007.02.002

zbMATH Keywords

separation problemssurrogate constraintsknapsack cover inequalitieslifting procedures

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Boolean programming (90C09)

Recommendations

• Second-order cover inequalities
• Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation
• Multi-cover inequalities for totally-ordered multiple knapsack sets
• \(O(n \log n)\) procedures for tightening cover inequalities
• Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes

Cites work

• scientific article; zbMATH DE number 2132174 (Why is no real title available?)
• scientific article; zbMATH DE number 3699703 (Why is no real title available?)
• scientific article; zbMATH DE number 1416629 (Why is no real title available?)
• A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
• A generalization of antiwebs to independence systems and their canonical facets
• A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique
• A note on the knapsack problem with special ordered sets
• An Improved Implicit Enumeration Approach for Integer Programming
• Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions
• Easily Computable Facets of the Knapsack Polytope
• Exploiting nested inequalities and surrogate constraints
• Faces for a linear inequality in 0–1 variables
• Facet of regular 0–1 polytopes
• Facets of the Knapsack Polytope From Minimal Covers
• Facets of the knapsack polytope
• Flows in Arborescences
• Generating cuts from surrogate constraint analysis for zero-one and multiple choice programming
• Improved results on the 0--1 multidimensional knapsack problem
• Lifted cover facets of the 0-1 knapsack polytope with GUB constraints
• MINTO, a Mixed INTeger Optimizer
• Network flows. Theory, algorithms, and applications.
• Nonlinear Programming
• On the 0,1 facets of the set covering polytope
• Preprocessing and Probing Techniques for Mixed Integer Programming Problems
• Rank inequalities and separation algorithms for packing designs and sparse triple systems.
• Second-order cover inequalities
• Sequence independent lifting in mixed integer programming
• Sequential and Simultaneous Liftings of Minimal Cover Inequalities for Generalized Upper Bound Constrained Knapsack Polytopes
• Solving Large-Scale Zero-One Linear Programming Problems
• Some classes of valid inequalities and convex hull characterizations for dynamic fixed-charge problems under nested constraints

Cited in

(7)

• Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation
• Knapsack polytopes: a survey
• Valid inequalities for the multi-dimensional multiple-choice 0-1 knapsack problem
• 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
• Second-order cover inequalities
• Multi-cover inequalities for totally-ordered multiple knapsack sets

Describes a project that uses

Uses Software

• MINTO

This page was built for publication: Higher-order cover cuts from zero-one knapsack constraints augmented by two-sided bounding inequalities

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