Lifted Cover Inequalities for 0-1 Integer Programs: Complexity
From MaRDI portal
Publication:4427368
DOI10.1287/ijoc.11.1.117zbMath1092.90527OpenAlexW2022398556MaRDI QIDQ4427368
Zonghao Gu, Savelsbergh, Martin W. P., Nemhauser, George I.
Publication date: 16 December 2003
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/168be4006c795e6df46402539d8681c71ed60372
Abstract computational complexity for mathematical programming problems (90C60) Boolean programming (90C09)
Related Items (27)
The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design ⋮ Knapsack polytopes: a survey ⋮ On the complexity of sequentially lifting cover inequalities for the knapsack polytope ⋮ Cover inequalities for robust knapsack sets-Application to the robust bandwidth packing problem ⋮ A new class of hard problem instances for the 0-1 knapsack problem ⋮ A branch-cut-and-price algorithm for the piecewise linear transportation problem ⋮ Separation algorithms for 0-1 knapsack polytopes ⋮ On the complexity of separation from the knapsack polytope ⋮ Chance-Constrained Binary Packing Problems ⋮ A cut-and-solve based algorithm for the single-source capacitated facility location problem ⋮ Sequence independent lifting of cover inequalities ⋮ Scheduling of waterways with tide and passing box ⋮ A Repeated Route-then-Schedule Approach to Coordinated Vehicle Platooning: Algorithms, Valid Inequalities and Computation ⋮ New classes of facets for complementarity knapsack problems ⋮ Features for the 0-1 knapsack problem based on inclusionwise maximal solutions ⋮ Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation ⋮ Safe and Verified Gomory Mixed-Integer Cuts in a Rational Mixed-Integer Program Framework ⋮ Optimal Network Design with End-to-End Service Requirements ⋮ An effective hybrid approach to the two-stage capacitated facility location problem ⋮ Yet harder knapsack problems ⋮ Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem ⋮ On the minimum cost multiple-source unsplittable flow problem ⋮ Cutting plane algorithms for \(0-1\) programming based on cardinality cuts ⋮ Risk-Averse Shortest Path Interdiction ⋮ A combinatorial cut-and-lift procedure with an application to 0-1 second-order conic programming ⋮ Simple lifted cover inequalities and hard knapsack problems ⋮ Cover and pack inequalities for (mixed) integer programming
Uses Software
This page was built for publication: Lifted Cover Inequalities for 0-1 Integer Programs: Complexity
