Efficient reformulation for 0-1 programs -- methods and computational results
From MaRDI portal
Two general methods for the reformulation of 0-1 programs are given. The first one is for coefficient reduction and the second for lifting. They are used for classical 0-1 structures: knapsack constraints, pair of \(k\) constraints, clique and cover induced inequalities etc. Computational results are given.
Recommendations
- Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations
- A network approach for specially structured linear programs arising in 0-1 quadratic optimization
- A simple technique to improve linearized reformulations of fractional (hyperbolic) 0-1 programming problems
- Subset Coefficient Reduction Cuts for 0/1 Mixed-Integer Programming
- A note for tightening 0-1 models
Cites work
- 0-1 knapsack problems with a side constraint
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
- A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
- A New Algorithm for the 0-1 Knapsack Problem
- An algorithm for the solution of the 0-1 knapsack problem
- Coefficient reduction for inequalities in 0–1 variables
- Coefficient reduction for knapsack-like constraints in 0-1 programs with variable upper bounds
- Easily Computable Facets of the Knapsack Polytope
- Edmonds polytopes and a hierarchy of combinatorial problems
- Faces for a linear inequality in 0–1 variables
- Facet of regular 0–1 polytopes
- Facets of the knapsack polytope
- Generating cuts in integer programming with families of special ordered sets
- Heuristics and reduction methods for multiple constraints 0-1 linear programming problems
- scientific article; zbMATH DE number 44282 (Why is no real title available?)
- scientific article; zbMATH DE number 3598222 (Why is no real title available?)
- Logical Reduction Methods in Zero-One Programming—Minimal Preferred Variables
- Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
- Obtaining clique, cover and coefficient reduction inequalities as Chvatal-Gomory inequalities and Gomory fractional cuts
- On tightening cover induced inequalities
- Outline of an algorithm for integer solutions to linear programs
- S3 sets. An extension of the Beale-Tomlin special ordered sets
- Solving 0-1 Integer Programming Problems Arising from Large Scale Planning Models
- Solving large-scale mixed-integer programs with fixed charge variables
- Solving Large-Scale Zero-One Linear Programming Problems
- Solving Mixed Integer Programming Problems Using Automatic Reformulation
- Strong formulations for mixed integer programming: A survey
- Stronger Inequalities for 0, 1 Integer Programming Using Knapsack Functions
- Subset Coefficient Reduction Cuts for 0/1 Mixed-Integer Programming
- Technical Note—A Note on Zero-One Programming
- Technical Note—Stronger Inequalities for 0-1 Integer Programming: Computational Refinements
Cited in
(22)- \(O(n \log n)\) procedures for tightening cover inequalities
- Reformulating nonlinear combinatorial optimization problems for higher computational efficiency
- 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
- Obtaining clique, cover and coefficient reduction inequalities as Chvatal-Gomory inequalities and Gomory fractional cuts
- Supernode processing of mixed-integer models
- Some properties of cliques in 0-1 mixed integer programs
- A simple technique to improve linearized reformulations of fractional (hyperbolic) 0-1 programming problems
- \(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
- A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems
- Tightening concise linear reformulations of 0-1 cubic programs
- scientific article; zbMATH DE number 1187159 (Why is no real title available?)
- A framework for tightening 0-1 programs based on extensions of pure 0-1 KP and SS problems
- A new idea on the interval-symbol method with correct zero rewriting for reducing exact computations
- Some of my favorite integer programming applications at IBM
- A note for tightening 0-1 models
- The multidimensional 0-1 knapsack problem -- bounds and computational aspects
- A conditional logic approach for strengthening mixed 0-1 linear programs
- Coefficient strengthening: a tool for reformulating mixed-integer programs
This page was built for publication: Efficient reformulation for 0-1 programs -- methods and computational results
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1803672)
