Free Access

Technical Note—A Note on Zero-One Programming

Manfred W. Padberg
Manfred W. Padberg
New York University, New York, New York
Search for more papers by this author

Manfred W. Padberg

New York University, New York, New York

Search for more papers by this author

Published Online:1 Aug 1975https://doi.org/10.1287/opre.23.4.833

Cited by
- Computational aspects of lifted cover inequalities for knapsacks with few different weights
  Discrete Optimization, Vol. 58
- Valid inequalities for the $$\beta $$-edge disruptor problem
  2 November 2025 | Journal of Combinatorial Optimization, Vol. 50, No. 4
- Reformulation Techniques for Chance-Constrained Combinatorial Optimization Problems
  23 February 2025
- Two-set inequalities for the binary knapsack polyhedra
  Discrete Optimization, Vol. 54
- On the complexity of separating cutting planes for the knapsack polytope
  4 May 2023 | Mathematical Programming, Vol. 206, No. 1-2
- 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
- Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation
  9 May 2022 | Mathematical Programming, Vol. 197, No. 2
- Lifting convex inequalities for bipartite bilinear programs
  24 January 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
- On the Complexity of Separation from the Knapsack Polytope
  27 May 2022
- Valid inequalities for quadratic optimisation with domain constraints
  Discrete Optimization, Vol. 41
- Polyhedral properties of the induced cluster subgraphs
  Discrete Applied Mathematics, Vol. 297
- Lifting Convex Inequalities for Bipartite Bilinear Programs
  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
- Valid inequalities for mixed-integer programmes with fixed charges on sets of variables
  Operations Research Letters, Vol. 48, No. 3
- A new lifting theorem for vertex packing
  18 August 2018 | Optimization Letters, Vol. 13, No. 6
- Path planning for unmanned vehicles with localization constraints
  24 May 2019 | Optimization Letters, Vol. 13, No. 5
- Adding incompatibilities to the Simple Plant Location Problem: Formulation, facets and computational experience
  Computers & Operations Research, Vol. 104
- On lifted cover inequalities: A new lifting procedure with unusual properties
  Operations Research Letters, Vol. 47, No. 2
- Lifting and separation of robust cover inequalities
  19 June 2018 | Networks, Vol. 72, No. 2
- Lexicographical Order in Integer Programming
  27 July 2016 | Vietnam Journal of Mathematics, Vol. 45, No. 3
- Known Concepts and Solution Techniques
  9 November 2016
- Risk-Averse Shortest Path Interdiction
  Yongjia Song,
  Siqian Shen
  16 June 2016 | INFORMS Journal on Computing, Vol. 28, No. 3
- Generalized multiple depot traveling salesmen problem—Polyhedral study and exact algorithm
  Computers & Operations Research, Vol. 70
- Chance-Constrained Binary Packing Problems
  Yongjia Song,
  James R. Luedtke,
  Simge Küçükyavuz
  19 May 2014 | INFORMS Journal on Computing, Vol. 26, No. 4
- Linear Inequalities and Polyhedra
  26 September 2014
- Semidefinite Bounds
  26 September 2014
- Getting Started
  26 September 2014
- Enumeration
  26 September 2014
- Reformulations and Relaxations
  26 September 2014
- Valid Inequalities for Structured Integer Programs
  26 September 2014
- Integer and Combinatorial Optimization
  23 January 2016
- Lifting Techniques For Mixed Integer Programming
  15 February 2011
- Lifting for conic mixed-integer programming
  19 May 2009 | Mathematical Programming, Vol. 126, No. 2
- Fifty Years of Integer Programming: A Review of the Solution Approaches
  1 July 2010 | Asia Pacific Business Review, Vol. 6, No. 3
- A theoretical study of continuous counter-current chromatography for adsorption isotherms with inflection points
  Computers & Chemical Engineering, Vol. 34, No. 4
- Generalized cover facet inequalities for the generalized assignment problem
  Optimization, Vol. 59, No. 2
- Mixed Integer Programming Computation
  6 November 2009
- New facets for the two-stage uncapacitated facility location polytope
  23 January 2008 | Computational Optimization and Applications, Vol. 44, No. 3
- Solving a school bus scheduling problem with integer programming
  European Journal of Operational Research, Vol. 193, No. 3
- 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
- Global analysis of combined reaction distillation processes
  Computers & Chemical Engineering, Vol. 32, No. 1-2
- Network design arc set with variable upper bounds
  1 January 2007 | Networks, Vol. 50, No. 1
- The quadratic knapsack problem—a survey
  Discrete Applied Mathematics, Vol. 155, No. 5
- Solving the asymmetric traveling purchaser problem
  24 May 2006 | Annals of Operations Research, Vol. 144, No. 1
- A Branch-and-Cut Algorithm for the Median-Path Problem
  Computational Optimization and Applications, Vol. 32, No. 3
- Airline Crew Scheduling: State-of-the-Art
  Annals of Operations Research, Vol. 140, No. 1
- 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
- Computational Integer Programming and Cutting Planes
- On Identifying Maximal Covers
  SIAM Journal on Discrete Mathematics, Vol. 18, No. 4
- Bidirected and unidirected capacity installation in telecommunication networks
  Discrete Applied Mathematics, Vol. 133, No. 1-3
- Operations Research Letters, Vol. 31, No. 3
- On the facets of the simple plant location packing polytope
  Discrete Applied Mathematics, Vol. 124, No. 1-3
- Cutting planes in integer and mixed integer programming
  Discrete Applied Mathematics, Vol. 123, No. 1-3
- A concurrent processing framework for the set partitioning problem
  Computers & Operations Research, Vol. 29, No. 10
- Shortest‐path network interdiction
  5 August 2002 | Networks, Vol. 40, No. 2
- A Polyhedral Study of the Cardinality Constrained Knapsack Problem
  21 May 2002
- Facet Obtaining Procedures for Set Packing Problems
  SIAM Journal on Discrete Mathematics, Vol. 16, No. 1
- General Mixed Integer Programming: Computational Issues for Branch-and-Cut Algorithms
  19 November 2001
- TSP Cuts Which Do Not Conform to the Template Paradigm
  19 November 2001
- New facets for the set packing polytope
  Operations Research Letters, Vol. 27, No. 4
- A note on the generalized steiner tree polytope
  Discrete Applied Mathematics, Vol. 100, No. 1-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
- On tightening 0-1 programs based on extensions ofpure 0-1 knapsack and subset-sum problems
  Annals of Operations Research, Vol. 81, No. 0
- The Sequential Knapsack Polytope
  SIAM Journal on Optimization, Vol. 8, No. 1
- The Intersection of Knapsack Polyhedra and Extensions
  18 June 1998
- Knapsack Problems
- On the 0/1 knapsack polytope
  Mathematical Programming, Vol. 77, No. 3
- Solving Multiple Knapsack Problems by Cutting Planes
  SIAM Journal on Optimization, Vol. 6, No. 3
- The symmetric generalized traveling salesman polytope
  11 October 2006 | Networks, Vol. 26, No. 2
- The prize collecting traveling salesman problem: II. Polyhedral results
  11 October 2006 | Networks, Vol. 25, No. 4
- Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems
  Annals of Operations Research, Vol. 58, No. 2
- Sequential and Simultaneous Liftings of Minimal Cover Inequalities for Generalized Upper Bound Constrained Knapsack Polytopes
  SIAM Journal on Discrete Mathematics, Vol. 8, No. 1
- A framework for tightening 0–1 programs based on extensions of pure 0–1 KP and SS problems
  1 June 2005
- Bestimmung optimaler Einsatzpläne für Flugpersonal
- The project scheduling polyhedron: Dimension, facets and lifting theorems
  European Journal of Operational Research, Vol. 67, No. 2
- Efficient reformulation for 0–1 programs — methods and computational results
  Discrete Applied Mathematics, Vol. 42, No. 2-3
- Polyhedral results for the precedence-constrained knapsack problem
  Discrete Applied Mathematics, Vol. 41, No. 3
- The complexity of lifted inequalities for the knapsack problem
  Discrete Applied Mathematics, Vol. 39, No. 2
- On tightening cover induced inequalities
  European Journal of Operational Research, Vol. 60, No. 3
- Auswahl von theoriebezogenen Veröffentlichungen
- A hybrid algorithm for the generalized assignment problem
  27 June 2007 | Optimization, Vol. 22, No. 2
- Lagrangean relaxation and constraint generation procedures for capacitated plant location problems with single sourcing
  OR Spektrum, Vol. 12, No. 2
- The generalized assignment problem: Valid inequalities and facets
  Mathematical Programming, Vol. 46, No. 1-3
- (1,k)-configuration facets for the generalized assignment problem
  Mathematical Programming, Vol. 46, No. 1-3
- Facet defining inequalities for the dichotomous knapsack problem
  Operations Research Letters, Vol. 9, No. 1
- On ternary problems
  Mathematical Programming, Vol. 45, No. 1-3
- A generalization of antiwebs to independence systems and their canonical facets
  Mathematical Programming, Vol. 45, No. 1-3
- The boolean quadric polytope: Some characteristics, facets and relatives
  Mathematical Programming, Vol. 45, No. 1-3
- On cutting-plane proofs in combinatorial optimization
  Linear Algebra and its Applications, Vol. 114-115
- References
  22 August 2014
- Facets of the knapsack polytope derived from disjoint and overlapping index configurations
  Operations Research Letters, Vol. 7, No. 2
- References
- Lp-based combinatorial problem solving
  Annals of Operations Research, Vol. 4, No. 1
- LP-Based Combinatorial Problem Solving
- Minimal covers, minimal sets and canonical facets of the posynomial knapsack polytope
  Discrete Applied Mathematics, Vol. 9, No. 2
- A note on node packing polytopes on hypergraphs
  Operations Research Letters, Vol. 2, No. 5
- Computing low-capacity 0–1 knapsack polytopes
  Zeitschrift für Operations Research, Vol. 26, No. 1
- A note of the knapsack problem with special ordered sets
  Operations Research Letters, Vol. 1, No. 1
- (1,k)-configurations and facets for packing problems
  Mathematical Programming, Vol. 18, No. 1
- Report of the Session on Polyhedral Aspects of Discrete Optimization
- Covering, Packing and Knapsack Problems
- Lifting the facets of zero–one polytopes
  Mathematical Programming, Vol. 15, No. 1
- Facets of the Knapsack Polytope From Minimal Covers
  SIAM Journal on Applied Mathematics, Vol. 34, No. 1
- The Role of Master Polytopes in the Unit Cube
  SIAM Journal on Applied Mathematics, Vol. 32, No. 4
- Lineare Charakterisierungen von Travelling Salesman Problemen
  Zeitschrift für Operations Research, Vol. 21, No. 1
- On the Complexity of Set Packing Polyhedra
- Set Partitioning: A survey
  SIAM Review, Vol. 18, No. 4

Volume 23, Issue 4

July-August 1975

Pages 603-840

Article Information

Metrics

Information

Published Online:August 01, 1975

Cite as

Manfred W. Padberg, (1975) Technical Note—A Note on Zero-One Programming. Operations Research 23(4):833-837.

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

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Technical Note—A Note on Zero-One Programming

Volume 23, Issue 4

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News