Valid inequalities for mixed integer linear programs

DOI10.1007/s10107-006-0086-0zbMath1278.90266OpenAlexW2152088446MaRDI QIDQ995784

Cornuéjols, Gérard

Publication date: 10 September 2007

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

Full work available at URL: https://doi.org/10.1007/s10107-006-0086-0

zbMATH Keywords

Elementary closurePolyhedraGomory cutLift-and-projectMixed integer linear programMixed integer roundingSplit cutUnion of polyhedra

Mathematics Subject Classification ID

Integer programming (90C10) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

Redundant robust topology optimization of truss, Improving branch-and-cut performance by random sampling, Convex hull of two quadratic or a conic quadratic and a quadratic inequality, On the minimum cut separator problem, MIPping closures: An instant survey, Integrality gaps for strengthened linear relaxations of capacitated facility location, MIR closures of polyhedral sets, Computing deep facet-defining disjunctive cuts for mixed-integer programming, Characterization of the split closure via geometric lifting, A note on the selection of Benders' cuts, A Conic Representation of the Convex Hull of Disjunctive Sets and Conic Cuts for Integer Second Order Cone Optimization, Stage- and scenario-wise Fenchel decomposition for stochastic mixed 0-1 programs with special structure, Discrete dynamical system approaches for Boolean polynomial optimization, Strong lift-and-project cutting planes for the stable set problem, Solving discrete linear bilevel optimization problems using the optimal value reformulation, DRL\(^*\): A hierarchy of strong block-decomposable linear relaxations for 0-1 mips, Decomposing the efficient frontier of the DEA production possibility set into a smallest number of convex polyhedrons by mixed integer programming, Integer programming solution approach for inventory‐production–distribution problems with direct shipments, Continuous cutting plane algorithms in integer programming, Exact methods for discrete \({\varGamma}\)-robust interdiction problems with an application to the bilevel knapsack problem, A note on the implications of approximate submodularity in discrete optimization, Decision Diagrams for Discrete Optimization: A Survey of Recent Advances, On the membership problem for the \({0, 1/2}\)-closure, Bi-objective optimization problems with two decision makers: refining Pareto-optimal front for equilibrium solution, Lift-and-project cuts for convex mixed integer nonlinear programs, On mixing sets arising in chance-constrained programming, Random half-integral polytopes, The dynamic bowser routing problem, On the facet defining inequalities of the mixed-integer bilinear covering set, Compact formulations as a union of polyhedra, Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning, A complete characterization of disjunctive conic cuts for mixed integer second order cone optimization, General cut-generating procedures for the stable set polytope, Lattice Reformulation Cuts, Preprocessing and cut generation techniques for multi-objective binary programming, A relax-and-cut framework for Gomory mixed-integer cuts, The Gomory-Chvátal Closure of a Non-Rational Polytope is a Rational Polytope, A short proof for the polyhedrality of the Chvátal-Gomory closure of a compact convex set, Intersection cuts for nonlinear integer programming: convexification techniques for structured sets, On Minimal Valid Inequalities for Mixed Integer Conic Programs, On the polyhedral lift-and-project methods and the fractional stable set polytope, Computational aspects of infeasibility analysis in mixed integer programming, The impact of distribution system characteristics on computational tractability, Optimizing drinking water distribution system operations, A novel dynamic generalized opposition-based grey wolf optimization algorithm, An iterative graph expansion approach for the scheduling and routing of airplanes, A framework for generalized Benders' decomposition and its application to multilevel optimization

Uses Software

• MIPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chvátal closures for mixed integer programming problems
• A note on the MIR closure
• Compact formulations as a union of polyhedra
• Intermediate integer programming representations using value disjunctions
• Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation
• On cutting-plane proofs in combinatorial optimization
• On the membership problem for the elementary closure of a polyhedron
• Strengthening cuts for mixed integer programs
• Factoring polynomials with rational coefficients
• A reformulation-linearization technique for solving discrete and continuous nonconvex problems
• Disjunctive programming: Properties of the convex hull of feasible points
• A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming
• On the separation of split cuts and related inequalities
• Tight formulations for some simple mixed integer programs and convex objective integer programs
• Cutting planes from a mixed integer Farkas lemma.
• Split closure and intersection cuts
• A recursive procedure to generate all cuts for 0-1 mixed integer programs
• A connection between cutting plane theory and the geometry of numbers
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Optimizing over the split closure
• Projected Chvátal-Gomory cuts for mixed integer linear programs
• Strong formulations of robust mixed 0-1 programming
• Some polyhedra related to combinatorial problems
• Edmonds polytopes and a hierarchy of combinatorial problems
• Gomory cuts revisited
• On the Matrix-Cut Rank of Polyhedra
• Reduce-and-Split Cuts: Improving the Performance of Mixed-Integer Gomory Cuts
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Optimizing over the First Chvàtal Closure
• Aggregation and Mixed Integer Rounding to Solve MIPs
• On the Value of Binary Expansions for General Mixed-Integer Linear Programs
• Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
• On Cutting Planes
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Lectures on Polytopes
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Subset Algebra Lift Operators for 0-1 Integer Programming
• Solving Lift-and-Project Relaxations of Binary Integer Programs
• Intersection Cuts—A New Type of Cutting Planes for Integer Programming
• Some continuous functions related to corner polyhedra
• When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
• The Continuous Mixing Polyhedron
• Elementary closures for integer programs.
• Mixing mixed-integer inequalities
• On the rank of mixed 0,1 polyhedra.