Free Access

Technical Note—Facets and Strong Valid Inequalities for Integer Programs

Laurence A. Wolsey
Laurence A. Wolsey
Center for Operations Research and Econometrics, Louvain, Belgium
Search for more papers by this author

Laurence A. Wolsey

Center for Operations Research and Econometrics, Louvain, Belgium

Search for more papers by this author

Published Online:1 Apr 1976https://doi.org/10.1287/opre.24.2.367

Cited by
- An efficient branch-and-cut approach for large-scale competitive facility location problems with limited choice rule
  European Journal of Operational Research, Vol. 333, No. 2
- 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
- Recycling valid inequalities for robust combinatorial optimization with budgeted uncertainty
  29 August 2024 | Mathematical Programming, Vol. 210, No. 1-2
- Reformulation–Linearization Techniques for Mixed-Discrete Optimization Problems
  6 March 2025
- Two-set inequalities for the binary knapsack polyhedra
  Discrete Optimization, Vol. 54
- Tilted inequalities and facets of the set covering polytope: A theoretical analysis
  Discrete Applied Mathematics, Vol. 357
- Joint optimization of product service system configuration and delivery with learning-based valid cut selection and a tailored heuristic
  Transportation Research Part E: Logistics and Transportation Review, Vol. 187
- Solving Sparse Separable Bilinear Programs Using Lifted Bilinear Cover Inequalities
  Xiaoyi Gu,
  Santanu S. Dey,
  Jean-Philippe P. Richard
  10 January 2024 | INFORMS Journal on Computing, Vol. 36, No. 3
- Improving the scheduling of railway maintenance projects by minimizing passenger delays subject to event requests of railway operators
  Computers & Operations Research, Vol. 165
- Lifting for the integer knapsack cover polyhedron
  7 December 2022 | Journal of Global Optimization, Vol. 86, No. 1
- Conflict hypergraphs to define new families of facets for the independence system polytope
  10 April 2023 | RAIRO - Operations Research, Vol. 57, No. 2
- Lifting convex inequalities for bipartite bilinear programs
  24 January 2022 | Mathematical Programming, Vol. 197, No. 2
- Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation
  9 May 2022 | Mathematical Programming, Vol. 197, No. 2
- 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
- Polyhedral properties of the induced cluster subgraphs
  Discrete Applied Mathematics, Vol. 297
- Lifting Convex Inequalities for Bipartite Bilinear Programs
  5 May 2021
- Multi-cover Inequalities for Totally-Ordered Multiple Knapsack Sets
  5 May 2021
- References
  19 September 2020
- 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
- Valid inequalities for mixed-integer programmes with fixed charges on sets of variables
  Operations Research Letters, Vol. 48, No. 3
- Analysis of Mixed-Integer Linear Programming Formulations for a Fuel-Constrained Multiple Vehicle Routing Problem
  1 November 2017 | Unmanned Systems, Vol. 05, No. 04
- Formulations and algorithms for the multiple depot, fuel-constrained, multiple vehicle routing problem
- The precedence constrained knapsack problem: Separating maximally violated inequalities
  Discrete Applied Mathematics, Vol. 194
- On Merging Cover Inequalities for Multiple Knapsack Problems
  Open Journal of Optimization, Vol. 04, No. 04
- General Bibliography
  8 August 2014
- A Comparison of Some Valid Inequality Generation Methods for General 0–1 Problems
  8 August 2014
- Lifted inequalities for $$0\mathord {-}1$$ mixed-integer bilinear covering sets
  17 April 2013 | Mathematical Programming, Vol. 145, No. 1-2
- A Comparison of Some Valid Inequality Generation Methods for General 0–1 Problems
  13 February 2013
- Integer and Combinatorial Optimization
  23 January 2016
- Reformulation–Linearization Techniques for Discrete Optimization Problems
  26 July 2013
- A Branch-and-Cut Algorithm for the Multilevel Generalized Assignment Problem
  IEEE Access, Vol. 1
- Computational Testing of a Separation Procedure for the Knapsack Set with a Single Continuous Variable
  Pasquale Avella,
  Maurizio Boccia,
  Igor Vasilyev,
  10 March 2011 | INFORMS Journal on Computing, Vol. 24, No. 1
- Lifted Tableaux Inequalities for 0–1 Mixed-Integer Programs: A Computational Study
  Amar K. Narisetty,
  Jean-Philippe P. Richard,
  George L. Nemhauser,
  24 September 2010 | INFORMS Journal on Computing, Vol. 23, No. 3
- On the exact separation of mixed integer knapsack cuts
  6 June 2009 | Mathematical Programming, Vol. 128, No. 1-2
- Lifting for conic mixed-integer programming
  19 May 2009 | Mathematical Programming, Vol. 126, No. 2
- Lifting Techniques For Mixed Integer Programming
  15 February 2011
- Lifting, tilting and fractional programming revisited
  Operations Research Letters, Vol. 38, No. 6
- On a generalization of the master cyclic group polyhedron
  21 November 2008 | Mathematical Programming, Vol. 125, No. 1
- A computational study of exact knapsack separation for the generalized assignment problem
  23 May 2008 | Computational Optimization and Applications, Vol. 45, No. 3
- Generalized cover facet inequalities for the generalized assignment problem
  Optimization, Vol. 59, No. 2
- Lifting inequalities: a framework for generating strong cuts for nonlinear programs
  31 May 2008 | Mathematical Programming, Vol. 121, No. 1
- Valid inequalities for MIPs and group polyhedra from approximate liftings
  16 October 2007 | Mathematical Programming, Vol. 118, No. 2
- Linear-Programming-Based Lifting and Its Application to Primal Cutting-Plane Algorithms
  Santanu S. Dey,
  Jean-Philippe Richard,
  15 September 2008 | INFORMS Journal on Computing, Vol. 21, No. 1
- A cutting plane method for knapsack polytope
  20 March 2009 | Journal of Computer and Systems Sciences International, Vol. 48, No. 1
- Generating Facets for the Independence System Polytope
  SIAM Journal on Discrete Mathematics, Vol. 23, No. 3
- Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes
  Discrete Optimization, Vol. 5, No. 2
- Nonconvex, lower semicontinuous piecewise linear optimization
  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
- Network design arc set with variable upper bounds
  16 April 2007 | Networks, Vol. 50, No. 1
- Lifting, superadditivity, mixed integer rounding and single node flow sets revisited
  5 May 2007 | Annals of Operations Research, Vol. 153, No. 1
- On a Generalization of the Master Cyclic Group Polyhedron
- A Framework to Derive Multidimensional Superadditive Lifting Functions and Its Applications
- A note on characterizing canonical cuts using geometry
  International Transactions in Operational Research, Vol. 12, No. 6
- Cover and Pack Inequalities for (Mixed) Integer Programming
  Annals of Operations Research, Vol. 139, No. 1
- Classical Cuts for Mixed-Integer Programming and Branch-and-Cut
  Annals of Operations Research, Vol. 139, No. 1
- Sequence Independent Lifting for Mixed-Integer Programming
  Alper Atamtürk,
  1 June 2004 | Operations Research, Vol. 52, No. 3
- Zero-Lifting for Integer Block Structured Problems
  Journal of Combinatorial Optimization, Vol. 7, No. 2
- Facets of the Complementarity Knapsack Polytope
  I. R. De Farias,
  E. L. Johnson,
  G. L. Nemhauser,
  1 February 2002 | Mathematics of Operations Research, Vol. 27, No. 1
- Lifted Inequalities for 0-1 Mixed Integer Programming: Basic Theory and Algorithms
  21 May 2002
- A Polyhedral Study of the Cardinality Constrained Knapsack Problem
  21 May 2002
- A family of inequalities for the generalized assignment polytope
  Operations Research Letters, Vol. 29, No. 2
- TSP Cuts Which Do Not Conform to the Template Paradigm
  19 November 2001
- Sequence Independent Lifting in Mixed Integer Programming
  Journal of Combinatorial Optimization, Vol. 4, No. 1
- Lifted Cover Inequalities for 0-1 Integer Programs: Computation
  Zonghao Gu,
  George L. Nemhauser,
  Martin W. P. Savelsbergh,
  1 November 1998 | INFORMS Journal on Computing, Vol. 10, No. 4
- Solving a Truck Dispatching Scheduling Problem Using Branch-and-Cut
  Robert E. Bixby,
  Eva K. Lee,
  1 June 1998 | Operations Research, Vol. 46, No. 3
- Cutting planes for integer programs with general integer variables
  Mathematical Programming, Vol. 81, No. 2
- Reformulation-Linearization Techniques for Discrete Optimization Problems
- Sequence independent lifting of cover inequalities
  1 June 2005
- The project scheduling polyhedron: Dimension, facets and lifting theorems
  European Journal of Operational Research, Vol. 67, No. 2
- On tightening cover induced inequalities
  European Journal of Operational Research, Vol. 60, No. 3
- Auswahl von theoriebezogenen Veröffentlichungen
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
  SIAM Journal on Discrete Mathematics, Vol. 3, No. 3
- The generalized assignment problem: Valid inequalities and facets
  Mathematical Programming, Vol. 46, No. 1-3
- References
  22 August 2014
- References
- Future paths for integer programming and links to artificial intelligence
  Computers & Operations Research, Vol. 13, No. 5
- Minimal covers, minimal sets and canonical facets of the posynomial knapsack polytope
  Discrete Applied Mathematics, Vol. 9, No. 2
- Lifting the Facets of Polyhedra
- Lifting the facets of zero–one polytopes
  Mathematical Programming, Vol. 15, No. 1

Volume 24, Issue 2

March-April 1976

Pages 207-385

Article Information

Metrics

Information

Published Online:April 01, 1976

Cite as

Laurence A. Wolsey, (1976) Technical Note—Facets and Strong Valid Inequalities for Integer Programs. Operations Research 24(2):367-372.

https://doi.org/10.1287/opre.24.2.367

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Technical Note—Facets and Strong Valid Inequalities for Integer Programs

Volume 24, Issue 2

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News