Chvátal closures for mixed integer programming problems

DOI10.1007/BF01580858zbMath0711.90057WikidataQ101511298 ScholiaQ101511298MaRDI QIDQ922950

William Cook, Ravindran Kannan

Publication date: 1990

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

lot-sizingcutting-planeplant locationfixed-charge

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Mixed integer programming (90C11) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items (only showing first 100 items - show all)

Rank of random half-integral polytopes — extended abstract — ⋮ Convex hull of two quadratic or a conic quadratic and a quadratic inequality ⋮ Intersection cuts for single row corner relaxations ⋮ Column basis reduction and decomposable knapsack problems ⋮ Disjunctive Cuts for Nonconvex MINLP ⋮ MIPping closures: An instant survey ⋮ MIR closures of polyhedral sets ⋮ Characterization of the split closure via geometric lifting ⋮ Two row mixed-integer cuts via lifting ⋮ Strong valid inequalities for orthogonal disjunctions and bilinear covering sets ⋮ Mixed-integer sets from two rows of two adjacent simplex bases ⋮ On Approximation Algorithms for Concave Mixed-Integer Quadratic Programming ⋮ Binary extended formulations of polyhedral mixed-integer sets ⋮ Theoretical challenges towards cutting-plane selection ⋮ A constructive characterization of the split closure of a mixed integer linear program ⋮ On the facets of mixed integer programs with two integer variables and two constraints ⋮ On optimizing over lift-and-project closures ⋮ On the polyhedrality of cross and quadrilateral closures ⋮ Sparse multi-term disjunctive cuts for the epigraph of a function of binary variables ⋮ On cutting-plane proofs in combinatorial optimization ⋮ Computational Experiments with Cross and Crooked Cross Cuts ⋮ On \(t\)-branch split cuts for mixed-integer programs ⋮ On the enumerative nature of Gomory's dual cutting plane method ⋮ DRL\(^*\): A hierarchy of strong block-decomposable linear relaxations for 0-1 mips ⋮ Practical strategies for generating rank-1 split cuts in mixed-integer linear programming ⋮ On finitely generated closures in the theory of cutting planes ⋮ On a class of mixed-integer sets with a single integer variable ⋮ When the Gomory-chvátal closure coincides with the integer hull ⋮ Lattice closures of polyhedra ⋮ On the NP-hardness of deciding emptiness of the split closure of a rational polytope in the 0,1 hypercube ⋮ Bilevel programming and the separation problem ⋮ Computing with Multi-row Gomory Cuts ⋮ Lifting Integer Variables in Minimal Inequalities Corresponding to Lattice-Free Triangles ⋮ On mixed-integer sets with two integer variables ⋮ On the relative strength of split, triangle and quadrilateral cuts ⋮ Cut generation through binarization ⋮ Reverse split rank ⋮ Split cuts from sparse disjunctions ⋮ Generalized intersection cuts and a new cut generating paradigm ⋮ The rank of (mixed-) integer polyhedra ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization ⋮ On the Practical Strength of Two-Row Tableau Cuts ⋮ Two-halfspace closure ⋮ A note on the MIR closure and basic relaxations of polyhedra ⋮ Random half-integral polytopes ⋮ A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts ⋮ A 3-slope theorem for the infinite relaxation in the plane ⋮ Unbounded convex sets for non-convex mixed-integer quadratic programming ⋮ Split cuts for robust mixed-integer optimization ⋮ How tight is the corner relaxation? Insights gained from the stable set problem ⋮ A note on the split rank of intersection cuts ⋮ Intersection cuts from multiple rows: a disjunctive programming approach ⋮ On the facet defining inequalities of the mixed-integer bilinear covering set ⋮ A note on the MIR closure ⋮ The splittable flow arc set with capacity and minimum load constraints ⋮ The mixing-MIR set with divisible capacities ⋮ Scenario-based cuts for structured two-stage stochastic and distributionally robust \(p\)-order conic mixed integer programs ⋮ Split Cuts in the Plane ⋮ A note on the Chvátal-rank of clique family inequalities ⋮ Generalized Chvátal-Gomory closures for integer programs with bounds on variables ⋮ Design and Verify: A New Scheme for Generating Cutting-Planes ⋮ Cutting planes from extended LP formulations ⋮ The stable set polytope of quasi-line graphs ⋮ Lower Bounds on the Lattice-Free Rank for Packing and Covering Integer Programs ⋮ Sequential pairing of mixed integer inequalities ⋮ Mixed-integer quadratic programming is in NP ⋮ On the relative strength of different generalizations of split cuts ⋮ Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning ⋮ Cook, Kannan and Schrijver's example revisited ⋮ The triangle closure is a polyhedron ⋮ Design and verify: a new scheme for generating cutting-planes ⋮ Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming ⋮ A new lift-and-project operator ⋮ Lattice Reformulation Cuts ⋮ Optimizing over the split closure ⋮ Projected Chvátal-Gomory cuts for mixed integer linear programs ⋮ Mingling: mixed-integer rounding with bounds ⋮ Cutting planes in integer and mixed integer programming ⋮ On the complexity of cutting-plane proofs using split cuts ⋮ Computing with multi-row gomory cuts ⋮ On the exact separation of mixed integer knapsack cuts ⋮ On the separation of disjunctive cuts ⋮ Branching on general disjunctions ⋮ Equivalence between intersection cuts and the corner polyhedron ⋮ A convex-analysis perspective on disjunctive cuts ⋮ Split closure and intersection cuts ⋮ On convergence in mixed integer programming ⋮ Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra ⋮ The split closure of a strictly convex body ⋮ Pivot-and-reduce cuts: an approach for improving Gomory mixed-integer cuts ⋮ Split cuts and extended formulations for mixed integer conic quadratic programming ⋮ Note on the complexity of the mixed-integer hull of a polyhedron ⋮ Valid inequalities for mixed integer linear programs ⋮ The Cutting Plane Method is Polynomial for Perfect Matchings ⋮ A note on the continuous mixing set ⋮ On approximation algorithms for concave mixed-integer quadratic programming ⋮ Using cutting planes in an interactive reference point approach for multiobjective integer linear programming problems ⋮ On the Polyhedrality of Closures of Multibranch Split Sets and Other Polyhedra with Bounded Max-Facet-Width ⋮ The aggregation closure is polyhedral for packing and covering integer programs ⋮ On a generalization of the Chvátal-Gomory closure

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constructive characterizations of the value-function of a mixed-integer program. I
• Constructive characterizations of the value function of a mixed-integer program. II
• Cutting planes in combinatorics
• A recursive procedure to generate all cuts for 0-1 mixed integer programs
• Edmonds polytopes and a hierarchy of combinatorial problems
• Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
• On the symmetric travelling salesman problem I: Inequalities
• On the Uncapacitated Plant Location Problem. I: Valid Inequalities and Facets
• Uncapacitated lot-sizing: The convex hull of solutions
• Facets of the Bipartite Subgraph Polytope
• Valid Linear Inequalities for Fixed Charge Problems
• On Cutting Planes
• Cyclic Scheduling via Integer Programs with Circular Ones
• Disjunctive Programming
• Edmonds polytopes and weakly hamiltonian graphs

This page was built for publication: Chvátal closures for mixed integer programming problems