Efficient reformulation for 0-1 programs -- methods and computational results
From MaRDI portal
Publication:1803672
DOI10.1016/0166-218X(93)90044-OzbMath0776.90056MaRDI QIDQ1803672
F. Chance, Brenda L. Dietrich, Laureano Fernando Escudero Bueno
Publication date: 29 June 1993
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
cutting planesmaximal cliquesknapsackcapacity expansionminimal coversvariable upper bounding constraintscoefficient reductionclique and cover induced inequalities
Related Items
Obtaining clique, cover and coefficient reduction inequalities as Chvatal-Gomory inequalities and Gomory fractional cuts, Supernode processing of mixed-integer models, Coefficient strengthening: a tool for reformulating mixed-integer programs, Some properties of cliques in 0-1 mixed integer programs, \(O(n \log n)\) procedures for tightening cover inequalities, A framework for tightening 0–1 programs based on extensions of pure 0–1 KP and SS problems, Some of my favorite integer programming applications at IBM, A note for tightening 0-1 models, \(O(n)\) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates, On identifying dominant cliques., On using clique overlapping for detecting knapsack constraint redundancy and infeasibility in 0-1 mixed integer programs, On using an automatic scheme for obtaining the convex hull defining inequalities of a Weismantel 0-1 knapsack constraint, On surrogating 0-1 knapsack constraints, Order selection on a single machine with high set-up costs, A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems, The multidimensional 0-1 knapsack problem -- bounds and computational aspects, A conditional logic approach for strengthening mixed 0-1 linear programs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Coefficient reduction for knapsack-like constraints in 0-1 programs with variable upper bounds
- Generating cuts in integer programming with families of special ordered sets
- Heuristics and reduction methods for multiple constraints 0-1 linear programming problems
- S3 sets. An extension of the Beale-Tomlin special ordered sets
- Strong formulations for mixed integer programming: A survey
- An algorithm for the solution of the 0-1 knapsack problem
- On tightening cover induced inequalities
- Obtaining clique, cover and coefficient reduction inequalities as Chvatal-Gomory inequalities and Gomory fractional cuts
- Edmonds polytopes and a hierarchy of combinatorial problems
- Easily Computable Facets of the Knapsack Polytope
- A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
- Outline of an algorithm for integer solutions to linear programs
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
- Solving large-scale mixed-integer programs with fixed charge variables
- Solving 0-1 Integer Programming Problems Arising from Large Scale Planning Models
- Solving Large-Scale Zero-One Linear Programming Problems
- Subset Coefficient Reduction Cuts for 0/1 Mixed-Integer Programming
- A New Algorithm for the 0-1 Knapsack Problem
- Logical Reduction Methods in Zero-One Programming—Minimal Preferred Variables
- Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
- Coefficient reduction for inequalities in 0–1 variables
- Technical Note—A Note on Zero-One Programming
- Faces for a linear inequality in 0–1 variables
- Facet of regular 0–1 polytopes
- Facets of the knapsack polytope
- Technical Note—Stronger Inequalities for 0-1 Integer Programming: Computational Refinements
- Solving Mixed Integer Programming Problems Using Automatic Reformulation
- Stronger Inequalities for 0, 1 Integer Programming Using Knapsack Functions
