Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut

DOI10.1287/IJOC.3.2.121zbMATH Open0755.90062OpenAlexW1965772065MaRDI QIDQ4025902FDOQ4025902

Authors: Manfred Padberg, Karla L. Hoffman 

Publication date: 18 February 1993

Published in: ORSA Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.3.2.121

Recommendations

• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Zero-one integer programs with few constraints - Efficient branch and bound algorithms
• An outer approximation based branch and cut algorithm for convex 0-1 MINLP problems
• An improved linearization strategy for zero-one quadratic programming problems
• Branch-and-cut for complementarity and cardinality constrained linear programs
• A branch-and-cut method for 0-1 mixed convex programming
• An improved linearization technique for a class of quadratic 0-1 programming problems
• scientific article; zbMATH DE number 1953196
• Computational aspects of a branch and bound algorithm for quadratic zero- one programming
• Solving linear programs with complementarity constraints using branch-and-cut

zbMATH Keywords

branch-and-cutpreprocessingvariable eliminationzero-one linear programmingdetection of redundant rowsspecial-ordered-set constraints

Mathematics Subject Classification ID

Linear programming (90C05) Large-scale problems in mathematical programming (90C06) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Boolean programming (90C09)

Cited In (47)

• Evolution and state-of-the-art in integer programming
• On using an automatic scheme for obtaining the convex hull defining inequalities of a Weismantel 0-1 knapsack constraint
• Generalized coefficient strengthening cuts for mixed integer programming
• A framework for tightening 0–1 programs based on extensions of pure 0–1 KP and SS problems
• Lifting the knapsack cover inequalities for the knapsack polytope
• Progress in presolving for mixed integer programming
• Two-row and two-column mixed-integer presolve using hashing-based pairing methods
• Coefficient strengthening: a tool for reformulating mixed-integer programs
• Knapsack polytopes: a survey
• Title not available (Why is that?)
• \(O(n \log n)\) procedures for tightening cover inequalities
• Cutting planes for mixed-integer knapsack polyhedra
• Detecting constraint redundancy in 0-1 linear programming problems
• Theoretical challenges towards cutting-plane selection
• Progress in computational mixed integer programming -- a look back from the other side of the tipping point
• On the complexity of sequentially lifting cover inequalities for the knapsack polytope
• On lifted cover inequalities: a new lifting procedure with unusual properties
• A procedure for optimizing tactical response in oil spill clean up operations
• Computational implementation of Fujishige's graph realizability algorithm
• \(O(n)\) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates
• Solving \(0/1\) integer programs with enumeration cutting planes
• Combinatorial optimization: current successes and directions for the future
• Minimum cost capacity installation for multicommodity network flows
• Conflict graphs in solving integer programming problems
• Zero-coefficient cuts
• Binary integer programs with two variables per inequality
• Separation algorithms for 0-1 knapsack polytopes
• Presolve Reductions in Mixed Integer Programming
• Complexity evaluation of benchmark instances for the \(p\)-median problem
• Airline crew scheduling: state-of-the-art
• Optimality-based domain reduction for inequality-constrained NLP and MINLP problems
• Optimizing single-terminal dispatch of large volume trips to trucks
• 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
• Solving Large-Scale Zero-One Linear Programming Problems
• Cut-and-solve: An iterative search strategy for combinatorial optimization problems
• Supernode processing of mixed-integer models
• Two-set inequalities for the binary knapsack polyhedra
• Minimizing makespan on parallel machines subject to release dates and delivery times
• Domain reduction techniques for global NLP and MINLP optimization
• Dominance breaking constraints
• Title not available (Why is that?)
• Air cargo scheduling: integrated models and solution procedures
• Data dependent worst case bound improving techniques in zero-one programming
• A conditional logic approach for strengthening mixed 0-1 linear programs
• Logical processing for integer programming
• Classical cuts for mixed-integer programming and branch-and-cut

Uses Software

• GAMS

This page was built for publication: Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4025902)