Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem

DOI10.1016/J.EJOR.2007.01.032zbMath1138.90016DBLPjournals/eor/KaparisL08OpenAlexW2094886241WikidataQ57702253 ScholiaQ57702253MaRDI QIDQ2462108

Adam N. Letchford, Konstantinos Kaparis

Publication date: 23 November 2007

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2007.01.032

zbMATH Keywords

integer programmingcombinatorial optimization

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Related Items (23)

Implicit cover inequalities ⋮ Knapsack polytopes: a survey ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Separation algorithms for 0-1 knapsack polytopes ⋮ Improving problem reduction for 0-1 multidimensional knapsack problems with valid inequalities ⋮ Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room Planning ⋮ Chance-Constrained Binary Packing Problems ⋮ Valid inequalities for mixed-integer programmes with fixed charges on sets of variables ⋮ Generalized laminar matroids ⋮ Sequence independent lifting for mixed knapsack problems with GUB constraints ⋮ Mixed-integer linear optimization for optimal lift-gas allocation with well-separator routing ⋮ A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem ⋮ Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms ⋮ Laminar matroids ⋮ Coupling feasibility pump and large neighborhood search to solve the Steiner team orienteering problem ⋮ Optimization algorithms for the disjunctively constrained knapsack problem ⋮ Lifting convex inequalities for bipartite bilinear programs ⋮ Lifting convex inequalities for bipartite bilinear programs ⋮ CORAL: An Exact Algorithm for the Multidimensional Knapsack Problem ⋮ Mathematical Models and Search Algorithms for the Capacitated p-Center Problem ⋮ Optimum Solution of the Closest String Problem via Rank Distance ⋮ Formulations and algorithms for the recoverable \({\varGamma}\)-robust knapsack problem ⋮ Revisiting surrogate relaxation for the multidimensional knapsack problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cover and pack inequalities for (mixed) integer programming
• The multidimensional 0-1 knapsack problem -- bounds and computational aspects
• On separating cover inequalities for the multidimensional knapsack problem
• A genetic algorithm for the multidimensional knapsack problem
• The complexity of cover inequality separation
• The multidimensional 0-1 knapsack problem: an overview.
• Strengthening Chvátal-Gomory cuts and Gomory fractional cuts
• A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems
• Sequence independent lifting in mixed integer programming
• Edmonds polytopes and a hierarchy of combinatorial problems
• Easily Computable Facets of the Knapsack Polytope
• Solving Large-Scale Zero-One Linear Programming Problems
• Lagrangean decomposition: A model yielding stronger lagrangean bounds
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Faces for a linear inequality in 0–1 variables
• Facets of the knapsack polytope
• Technical Note—Facets and Strong Valid Inequalities for Integer Programs
• Facets of the Knapsack Polytope From Minimal Covers
• Generating Fenchel Cutting Planes for Knapsack Polyhedra
• Lifted Cover Inequalities for 0-1 Integer Programs: Complexity
• Solving Multiple Knapsack Problems by Cutting Planes

This page was built for publication: Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem