Preprocessing and cutting planes with conflict graphs

DOI10.1016/J.COR.2020.105176OpenAlexW2974558510MaRDI QIDQ2027062FDOQ2027062

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

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

zbMATH Keywords

cutting planespreprocessingmixed-integer linear programmingconflict graphsclique inequalitiesodd-cycle inequalities

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Cites Work

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

Cited In (7)

• Preprocessing and Cutting Planes with Conflict Graphs
• 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
• Fair allocation of indivisible items with conflict graphs
• Worst-case analysis of clique MIPs
• On recognizing staircase compatibility

Uses Software

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

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)