Lifted Cover Inequalities for 0-1 Integer Programs: Computation

Zonghao Gu
Zonghao Gu
Georgia Institute of Technology, School of Industrial and Systems Engineering, Atlanta, GA 30332-0205
Search for more papers by this author
,
George L. Nemhauser
George L. Nemhauser
Georgia Institute of Technology, School of Industrial and Systems Engineering, Atlanta, GA 30332-0205
Search for more papers by this author
,
Martin W. P. Savelsbergh
Martin W. P. Savelsbergh
Georgia Institute of Technology, School of Industrial and Systems Engineering, Atlanta, GA 30332-0205
Search for more papers by this author

Zonghao Gu

Georgia Institute of Technology, School of Industrial and Systems Engineering, Atlanta, GA 30332-0205

Search for more papers by this author

George L. Nemhauser

Georgia Institute of Technology, School of Industrial and Systems Engineering, Atlanta, GA 30332-0205

Search for more papers by this author

Martin W. P. Savelsbergh

Georgia Institute of Technology, School of Industrial and Systems Engineering, Atlanta, GA 30332-0205

Search for more papers by this author

Published Online:1 Nov 1998https://doi.org/10.1287/ijoc.10.4.427

Abstract

We investigate the algorithmic and implementation issues related to the effective and efficient use of lifted cover inequalities and lifted GUB cover inequalities in a branch and cut algorithm for 0-1 integer programming. We have tried various strategies on several test problems and we identify the best ones for use in practice.

Cited by
- Enhancing the separation of rank-1 Chvátal-Gomory cuts from knapsack sets
  Operations Research Letters, Vol. 67
- Towards Large-Scale Probabilistic Set Covering Problems: An Efficient Benders Decomposition Approach
  Wei Lv,
  Wei-Kun Chen,
  Yi-Long Chen,
  Yu-Hong Dai
  20 May 2026 | INFORMS Journal on Computing, Vol. 0, No. 0
- An overview of mathematical programming solvers: Theory, development, and recent advances
  23 April 2026 | ENGINEERING Management, Vol. 13, No. 1
- Branch-and-cut algorithm for multiband robust discrete optimization problems
  10 December 2025 | Optimization Letters, Vol. 53
- Valid inequalities for the $$\beta $$-edge disruptor problem
  2 November 2025 | Journal of Combinatorial Optimization, Vol. 50, No. 4
- Volume-based branch-and-cut algorithm for large-scale fixed-charge multicommodity network design
  22 October 2024 | Annals of Operations Research, Vol. 351, No. 1
- Lifting cover inequalities for the robust knapsack problem
  Operations Research Letters, Vol. 61
- An efficient solution methodology for the airport slot allocation problem with preprocessing and column-and-row generation
  Computers & Operations Research, Vol. 177
- Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming
  IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 46, No. 12
- Two-set inequalities for the binary knapsack polyhedra
  Discrete Optimization, Vol. 54
- New classes of Facets for complementarity knapsack problems
  Discrete Applied Mathematics, Vol. 356
- On the complexity of separating cutting planes for the knapsack polytope
  4 May 2023 | Mathematical Programming, Vol. 206, No. 1-2
- A new sequential lifting of robust cover inequalities
  26 June 2023 | Optimization Letters, Vol. 18, No. 4
- A cut-and-solve algorithm for virtual machine consolidation problem
  Future Generation Computer Systems, Vol. 154
- Operational Research: methods and applications
  27 December 2023 | Journal of the Operational Research Society, Vol. 75, No. 3
- Enhancing Branch-and-Bound for Multiobjective 0-1 Programming
  Nicolas Forget,
  Sophie N. Parragh
  12 September 2023 | INFORMS Journal on Computing, Vol. 36, No. 1
- Lifting for the integer knapsack cover polyhedron
  7 December 2022 | Journal of Global Optimization, Vol. 86, No. 1
- A branch-and-price-and-cut algorithm for operating room scheduling under human resource constraints
  Computers & Operations Research, Vol. 152
- Conflict hypergraphs to define new families of facets for the independence system polytope
  10 April 2023 | RAIRO - Operations Research, Vol. 57, No. 2
- Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation
  9 May 2022 | Mathematical Programming, Vol. 197, No. 2
- Exact approaches for the Minimum Subgraph Diameter Problem
  Computers & Operations Research, Vol. 150
- A combinatorial cut-and-lift procedure with an application to 0–1 second-order conic programming
  11 August 2021 | Mathematical Programming, Vol. 196, No. 1-2
- The aggregation closure is polyhedral for packing and covering integer programs
  1 November 2021 | Mathematical Programming, Vol. 195, No. 1-2
- A Repeated Route-then-Schedule Approach to Coordinated Vehicle Platooning: Algorithms, Valid Inequalities and Computation
  Fengqiao Luo,
  Jeffrey Larson
  16 August 2021 | Operations Research, Vol. 70, No. 4
- A Solution Approach to Distributionally Robust Joint-Chance-Constrained Assignment Problems
  Shanshan Wang,
  Jinlin Li,
  Sanjay Mehrotra
  3 February 2022 | INFORMS Journal on Optimization, Vol. 4, No. 2
- A column generation approach for the integrated crew re-planning problem
  Omega, Vol. 107
- On the Complexity of Separation from the Knapsack Polytope
  27 May 2022
- New Classes of Facets for Complementarity Knapsack Problems
  21 November 2022
- Cover by disjoint cliques cuts for the knapsack problem with conflicting items
  Operations Research Letters, Vol. 49, No. 6
- Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room Planning
  Shanshan Wang,
  Jinlin Li,
  Sanjay Mehrotra
  9 March 2021 | INFORMS Journal on Computing, Vol. 33, No. 4
- Coupling Feasibility Pump and Large Neighborhood Search to solve the Steiner team orienteering problem
  Computers & Operations Research, Vol. 128
- Exact Methods for Fixed-Charge Network Design
  9 December 2020
- Multi-cover Inequalities for Totally-Ordered Multiple Knapsack Sets
  5 May 2021
- On the complexity of sequentially lifting cover inequalities for the knapsack polytope
  15 April 2020 | Science China Mathematics, Vol. 64, No. 1
- Knapsack polytopes: a survey
  19 September 2019 | Annals of Operations Research, Vol. 292, No. 1
- Lifting the knapsack cover inequalities for the knapsack polytope
  Operations Research Letters, Vol. 48, No. 5
- Parametric convex quadratic relaxation of the quadratic knapsack problem
  European Journal of Operational Research, Vol. 281, No. 1
- A History of Operations Research Optimization in the Petroleum Industry
  23 September 2019
- Cover Inequalities for a Vehicle Routing Problem with Time Windows and Shifts
  Said Dabia,
  Stefan Ropke,
  Tom van Woensel
  27 August 2019 | Transportation Science, Vol. 53, No. 5
- A cutting-plane algorithm for the Steiner team orienteering problem
  Computers & Industrial Engineering, Vol. 135
- New valid inequalities for the fixed-charge and single-node flow polytopes
  Operations Research Letters, Vol. 47, No. 5
- An Exact Algorithm for a Rich Vehicle Routing Problem with Private Fleet and Common Carrier
  Said Dabia,
  David Lai,
  Daniele Vigo
  21 May 2019 | Transportation Science, Vol. 53, No. 4
- A Branch-and-Price-and-Cut Algorithm for Resource-Constrained Pickup and Delivery Problems
  Albert H. Schrotenboer,
  Evrim Ursavas,
  Iris F. A. Vis
  28 June 2019 | Transportation Science, Vol. 53, No. 4
- An effective hybrid approach to the two-stage capacitated facility location problem
  European Journal of Operational Research, Vol. 275, No. 2
- Preprocessing and cut generation techniques for multi-objective binary programming
  European Journal of Operational Research, Vol. 274, No. 3
- On lifted cover inequalities: A new lifting procedure with unusual properties
  Operations Research Letters, Vol. 47, No. 2
- Optimizing resource utilization in NFV dynamic systems: New exact and heuristic approaches
  Computer Networks, Vol. 148
- Disaggregated Benders decomposition and branch-and-cut for solving the budget-constrained dynamic uncapacitated facility location and network design problem
  European Journal of Operational Research, Vol. 270, No. 1
- Lifting and separation of robust cover inequalities
  19 June 2018 | Networks, Vol. 72, No. 2
- The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design
  EURO Journal on Computational Optimization, Vol. 6, No. 2
- Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON
  18 July 2017 | Optimization Methods and Software, Vol. 33, No. 3
- An Exact Algorithm for the Fixed Charge Transportation Problem Based on Matching Source and Sink Patterns
  Aristide Mingozzi,
  Roberto Roberti
  27 April 2017 | Transportation Science, Vol. 52, No. 2
- Optimization algorithms for the disjunctively constrained knapsack problem
  23 December 2016 | Soft Computing, Vol. 22, No. 6
- An improved cut-and-solve algorithm for the single-source capacitated facility location problem
  EURO Journal on Computational Optimization, Vol. 6, No. 1
- Local Cuts for 0–1 Multidimensional Knapsack Problems
  28 July 2017
- Generalized coefficient strengthening cuts for mixed integer programming
  2 September 2017 | Journal of Global Optimization, Vol. 70, No. 1
- A polyhedral study on chance constrained program with random right-hand side
  31 December 2016 | Mathematical Programming, Vol. 166, No. 1-2
- Resource constrained project scheduling with uncertain activity durations
  Computers & Industrial Engineering, Vol. 112
- Lifting of probabilistic cover inequalities
  Operations Research Letters, Vol. 45, No. 5
- Commodity Representations and Cut-Set-Based Inequalities for Multicommodity Capacitated Fixed-Charge Network Design
  Mervat Chouman,
  Teodor Gabriel Crainic,
  Bernard Gendron
  27 July 2016 | Transportation Science, Vol. 51, No. 2
- Petroleum supply planning: reformulations and a novel decomposition algorithm
  16 February 2017 | Optimization and Engineering, Vol. 18, No. 1
- Tighter MIP formulations for the discretised unit commitment problem with min-stop ramping constraints
  EURO Journal on Computational Optimization, Vol. 5, No. 1-2
- A Constraint-Programming-Based Branch-and-Price-and-Cut Approach for Operating Room Planning and Scheduling
  Seyed Hossein Hashemi Doulabi,
  Louis-Martin Rousseau,
  Gilles Pesant
  11 May 2016 | INFORMS Journal on Computing, Vol. 28, No. 3
- Risk-Averse Shortest Path Interdiction
  Yongjia Song,
  Siqian Shen
  16 June 2016 | INFORMS Journal on Computing, Vol. 28, No. 3
- Reformulation and decomposition approaches for traffic routing in optical networks
  4 April 2016 | Networks, Vol. 67, No. 4
- Improving problem reduction for 0–1 Multidimensional Knapsack Problems with valid inequalities
  Computers & Operations Research, Vol. 71
- Implicit cover inequalities
  12 November 2014 | Journal of Combinatorial Optimization, Vol. 31, No. 3
- Optimal response to epidemics and cyber attacks in networks
  25 June 2015 | Networks, Vol. 66, No. 2
- A branch-cut-and-price algorithm for the piecewise linear transportation problem
  European Journal of Operational Research, Vol. 245, No. 3
- Computational Study of Cutting Planes for a Lot-Sizing Problem in Branch-and-Cut Algorithm
  Journal of the Korean Operations Research and Management Science Society, Vol. 40, No. 3
- The Fixed Charge Transportation Problem: An Exact Algorithm Based on a New Integer Programming Formulation
  Roberto Roberti,
  Enrico Bartolini,
  Aristide Mingozzi
  14 August 2014 | Management Science, Vol. 61, No. 6
- Lifting for mixed integer programs with variable upper bounds
  Discrete Applied Mathematics, Vol. 186
- A branch-and-price-and-cut approach for sustainable crop rotation planning
  European Journal of Operational Research, Vol. 241, No. 3
- On Merging Cover Inequalities for Multiple Knapsack Problems
  Open Journal of Optimization, Vol. 04, No. 04
- Branch-and-cut for complementarity-constrained optimization
  22 April 2014 | Mathematical Programming Computation, Vol. 6, No. 4
- Chance-Constrained Binary Packing Problems
  Yongjia Song,
  James R. Luedtke,
  Simge Küçükyavuz
  19 May 2014 | INFORMS Journal on Computing, Vol. 26, No. 4
- A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints
  European Journal of Operational Research, Vol. 235, No. 3
- A Branch-and-Price-and-Cut Approach for Sustainable Crop Rotation Planning
  SSRN Electronic Journal, Vol. 418
- A polyhedral study of the semi-continuous knapsack problem
  8 June 2012 | Mathematical Programming, Vol. 142, No. 1-2
- A computational comparison of flow formulations for the capacitated location-routing problem
  Discrete Optimization, Vol. 10, No. 4
- Separation and Extension of Cover Inequalities for Conic Quadratic Knapsack Constraints with Generalized Upper Bounds
  Alper Atamtürk,
  Laurent Flindt Muller,
  David Pisinger,
  6 June 2012 | INFORMS Journal on Computing, Vol. 25, No. 3
- Scheduling of scientific workflow in non-dedicated heterogeneous multicluster platform
  Journal of Systems and Software, Vol. 86, No. 7
- Mixed integer lifted cover inequalities for knapsack problems with a single continuous variable
- Integer and Combinatorial Optimization
  23 January 2016
- A cut-and-solve based algorithm for the single-source capacitated facility location problem
  European Journal of Operational Research, Vol. 221, No. 3
- Multi-period traffic routing in satellite networks
  European Journal of Operational Research, Vol. 219, No. 3
- Cover inequalities for robust knapsack sets—Application to the robust bandwidth packing problem
  1 December 2011 | Networks, Vol. 59, No. 1
- On the exact separation of mixed integer knapsack cuts
  6 June 2009 | Mathematical Programming, Vol. 128, No. 1-2
- Scheduling mixed-parallel application onto multicluster grid with background workloads
- A polyhedral study on 0–1 knapsack problems with disjoint cardinality constraints: Strong valid inequalities by sequence-independent lifting
  Discrete Optimization, Vol. 8, No. 2
- A polyhedral study on 0–1 knapsack problems with disjoint cardinality constraints: Facet-defining inequalities by sequential lifting
  Discrete Optimization, Vol. 8, No. 2
- Cover Inequalities
  15 February 2011
- Lifting Techniques For Mixed Integer Programming
  15 February 2011
- MILP Software
  14 January 2011
- Lifting, tilting and fractional programming revisited
  Operations Research Letters, Vol. 38, No. 6
- Separation algorithms for 0-1 knapsack polytopes
  8 May 2010 | Mathematical Programming, Vol. 124, No. 1-2
- Combining Exact and Heuristic Approaches for the Capacitated Fixed-Charge Network Flow Problem
  Mike Hewitt,
  George L. Nemhauser,
  Martin W. P. Savelsbergh,
  21 September 2009 | INFORMS Journal on Computing, Vol. 22, No. 2
- References
  13 September 2011
- The submodular knapsack polytope
  Discrete Optimization, Vol. 6, No. 4
- Generating Facets for the Independence System Polytope
  SIAM Journal on Discrete Mathematics, Vol. 23, No. 3
- Second-order cover inequalities
  14 February 2007 | Mathematical Programming, Vol. 114, No. 2
- Higher-order cover cuts from zero–one knapsack constraints augmented by two-sided bounding inequalities
  Discrete Optimization, Vol. 5, No. 2
- Local and global lifted cover inequalities for the 0–1 multidimensional knapsack problem
  European Journal of Operational Research, Vol. 186, No. 1
- Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements
  Discrete Optimization, Vol. 5, No. 1
- A Discrete Optimization Approach to Large Scale Supply Networks Based on Partial Differential Equations
  SIAM Journal on Scientific Computing, Vol. 30, No. 3
- Exact solutions to linear programming problems
  Operations Research Letters, Vol. 35, No. 6
- Network design arc set with variable upper bounds
  16 April 2007 | Networks, Vol. 50, No. 1
- On the minimum cost multiple-source unsplittable flow problem
  21 August 2007 | RAIRO - Operations Research, Vol. 41, No. 3
- Lifting, superadditivity, mixed integer rounding and single node flow sets revisited
  5 May 2007 | Annals of Operations Research, Vol. 153, No. 1
- On separating cover inequalities for the multidimensional knapsack problem
  Computers & Operations Research, Vol. 34, No. 6
- A Framework to Derive Multidimensional Superadditive Lifting Functions and Its Applications
- On the Exact Separation of Mixed Integer Knapsack Cuts
- The Integer Knapsack Cover Polyhedron
  SIAM Journal on Discrete Mathematics, Vol. 21, No. 3
- A Branch-and-Cut Procedure for the Multimode Resource-Constrained Project-Scheduling Problem
  Guidong Zhu,
  Jonathan F. Bard,
  Gang Yu,
  1 August 2006 | INFORMS Journal on Computing, Vol. 18, No. 3
- Polyhedral Analysis for Concentrator Location Problems
  23 March 2006 | Computational Optimization and Applications, Vol. 34, No. 3
- Mapping Task-Graphs on Distributed ECU Networks: Efficient Algorithms for Feasibility and Optimality
- Integer-Programming Software Systems
  Annals of Operations Research, Vol. 140, No. 1
- Cover and Pack Inequalities for (Mixed) Integer Programming
  Annals of Operations Research, Vol. 139, No. 1
- Simple lifted cover inequalities and hard knapsack problems
  Discrete Optimization, Vol. 2, No. 3
- Disruption management for resource-constrained project scheduling
  21 December 2017 | Journal of the Operational Research Society, Vol. 56, No. 4
- A branch and cut algorithm for hub location problems with single assignment
  7 July 2004 | Mathematical Programming, Vol. 102, No. 2
- Computational Integer Programming and Cutting Planes
- Locating median cycles in networks
  European Journal of Operational Research, Vol. 160, No. 2
- Resource Constrained Shortest Path Problems in Path Planning for Fleet Management
  Journal of Mathematical Modelling and Algorithms, Vol. 3, No. 1
- Semi-continuous Cuts for Mixed-Integer Programming
- BIBLIOGRAPHY
- An O(nn) procedure for identifying facets of the knapsack polytope
  Operations Research Letters, Vol. 31, No. 3
- Simulation‐optimization framework for stochastic optimization of R&D pipeline management
  16 April 2004 | AIChE Journal, Vol. 49, No. 1
- Cutting planes in integer and mixed integer programming
  Discrete Applied Mathematics, Vol. 123, No. 1-3
- Lifted Inequalities for 0-1 Mixed Integer Programming: Basic Theory and Algorithms
  21 May 2002
- General Mixed Integer Programming: Computational Issues for Branch-and-Cut Algorithms
  19 November 2001
- FATCOP: A Fault Tolerant Condor-PVM Mixed Integer Programming Solver
  SIAM Journal on Optimization, Vol. 11, No. 4
- A Lagrangean relax-and-cut approach for the two-stage capacitated facility location problem
  European Journal of Operational Research, Vol. 126, No. 2
- Sequence Independent Lifting in Mixed Integer Programming
  Journal of Combinatorial Optimization, Vol. 4, No. 1
- Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition
  Ellis L. Johnson,
  George L. Nemhauser,
  Martin W.P. Savelsbergh,
  1 February 2000 | INFORMS Journal on Computing, Vol. 12, No. 1
- Statistical Analysis of Computational Tests of Algorithms and Heuristics
  Marie Coffin,
  Matthew J. Saltzman,
  1 February 2000 | INFORMS Journal on Computing, Vol. 12, No. 1
- MIP: Theory and Practice — Closing the Gap
- A Computational Study of Search Strategies for Mixed Integer Programming
  J. T. Linderoth,
  M. W. P. Savelsbergh,
  1 May 1999 | INFORMS Journal on Computing, Vol. 11, No. 2
- Lifted Cover Inequalities for 0-1 Integer Programs: Complexity
  Zonghao Gu,
  George L. Nemhauser,
  Martin W. P. Savelsbergh,
  1 February 1999 | INFORMS Journal on Computing, Vol. 11, No. 1

cover image INFORMS Journal on Computing

Volume 10, Issue 4

Fall 1998

Pages 359-460

Article Information

Metrics

Information

Published Online:November 01, 1998

Cite as

Zonghao Gu, George L. Nemhauser, Martin W. P. Savelsbergh, (1998) Lifted Cover Inequalities for 0-1 Integer Programs: Computation. INFORMS Journal on Computing 10(4):427-437.

https://doi.org/10.1287/ijoc.10.4.427

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Lifted Cover Inequalities for 0-1 Integer Programs: Computation

Abstract

Volume 10, Issue 4

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News