Preprocessing and cutting planes with conflict graphs

DOI10.1016/J.COR.2020.105176MaRDI QIDQ2027062zbMATH OpenOpenAlexFDO

Authors Samuel Souza Brito, Haroldo G. Santos

Publication date 21 May 2021

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.07780

zbMATH Keywords

cutting planespreprocessingmixed-integer linear programmingconflict graphsclique inequalitiesodd-cycle inequalities

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Recommendations

• A computational study of conflict graphs and aggressive cut separation in integer programming
• Conflict graphs in solving integer programming problems
• Conflict analysis in mixed integer programming
• MIP: Theory and practice -- closing the gap
• The vertex separator problem: algorithms and computations

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 7124428 (Why is no real title available?)
• A branch-and-cut procedure for the Udine course timetabling problem
• A cutting plane algorithm for graph coloring
• Advanced preprocessing techniques for linear and quadratic programming
• Algorithm 457: finding all cliques of an undirected graph
• An algorithmic framework for convex mixed integer nonlinear programs
• Analysis of mathematical programming problems prior to applying the simplex algorithm
• Branching and bounds tighteningtechniques for non-convex MINLP
• Conflict graphs in solving integer programming problems
• Efficiently enumerating all maximal cliques with bit-parallelism
• Exploring relaxation induced neighborhoods to improve MIP solutions
• Geometric algorithms and combinatorial optimization.
• Improved branch-cut-and-price for capacitated vehicle routing
• Integer programming techniques for educational timetabling
• Integer programming techniques for the nurse rostering problem
• Mixed integer programming: analyzing 12 years of progress
• Optimizing over the first Chvátal closure
• Preprocessing and Probing Techniques for Mixed Integer Programming Problems
• Production Planning by Mixed Integer Programming
• Progress in computational mixed integer programming -- a look back from the other side of the tipping point
• Progress in presolving for mixed integer programming
• Revival of the Gomory cuts in the 1990's
• Solving Airline Crew Scheduling Problems by Branch-and-Cut
• Solving Mixed Integer Programming Problems Using Automatic Reformulation
• Strong bounds for resource constrained project scheduling: preprocessing and cutting planes
• The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming
• The feasibility pump
• The first international nurse rostering competition 2010
• The worst-case time complexity for generating all maximal cliques and computational experiments

Cited in

(7)

• A computational study of conflict graphs and aggressive cut separation in integer programming
• Conflict graphs in solving integer programming problems
• A branch and bound algorithm for robust binary optimization with budget uncertainty
• Preprocessing and Cutting Planes with Conflict Graphs
• Fair allocation of indivisible items with conflict graphs
• Worst-case analysis of clique MIPs
• On recognizing staircase compatibility

Describes a project that uses

Uses Software

• GreedyBB
• Algorithm 457
• SHOT
• RAPTOR
• Bonmin
• MIPLIB
• SNDlib

This page was built for publication: Preprocessing and cutting planes with conflict graphs

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