Preprocessing and cutting planes with conflict graphs

DOI10.1016/j.cor.2020.105176OpenAlexW2974558510MaRDI QIDQ2027062

Haroldo Gambini Santos, Samuel Souza Brito

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 planesmixed-integer linear programmingpreprocessingconflict graphsclique inequalitiesodd-cycle inequalities

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Related Items (4)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Integer programming techniques for the nurse rostering problem
• The first international nurse rostering competition 2010
• Progress in computational mixed integer programming -- a look back from the other side of the tipping point
• Revival of the Gomory cuts in the 1990's
• The worst-case time complexity for generating all maximal cliques and computational experiments
• Optimizing over the first Chvátal closure
• Progress in presolving for mixed integer programming
• An algorithmic framework for convex mixed integer nonlinear programs
• Geometric algorithms and combinatorial optimization.
• Advanced preprocessing techniques for linear and quadratic programming
• Efficiently enumerating all maximal cliques with bit-parallelism
• Integer programming techniques for educational timetabling
• 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
• Strong bounds for resource constrained project scheduling: preprocessing and cutting planes
• Improved branch-cut-and-price for capacitated vehicle routing
• A cutting plane algorithm for graph coloring
• The feasibility pump
• Branching and bounds tighteningtechniques for non-convex MINLP
• Analysis of mathematical programming problems prior to applying the simplex algorithm
• Solving Airline Crew Scheduling Problems by Branch-and-Cut
• Preprocessing and Probing Techniques for Mixed Integer Programming Problems
• Solving Mixed Integer Programming Problems Using Automatic Reformulation
• Mixed Integer Programming: Analyzing 12 Years of Progress
• Production Planning by Mixed Integer Programming
• Algorithm 457: finding all cliques of an undirected graph
• The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming

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