Compact formulations and valid inequalities for parallel machine scheduling with conflicts

DOI10.1016/J.EJOR.2025.04.006MaRDI QIDQ6931779zbMATH OpenFDO

Authors Phablo F. S. Moura, Roel Leus, Hande Yaman

Publication date 10 September 2025

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.EJOR.2025.04.006

zbMATH Keywords

branch and cutinteger programmingschedulingvalid inequalities

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Integer programming (90C10)

Cites work

• A branch and cut solver for the maximum stable set problem
• A branch-and-cut algorithm for graph coloring
• A class of facet producing graphs for vertex packing polyhedra
• A cutting plane algorithm for graph coloring
• A stand-alone branch-and-price algorithm for identical parallel machine scheduling with conflicts
• A survey on vertex coloring problems
• A tutorial on branch and cut algorithms for the maximum stable set problem
• An exact algorithm for parallel machine scheduling with conflicts
• Antiweb-wheel inequalities and their separation problems over the stable set polytopes
• Approximation algorithms for job scheduling with block-type conflict graphs
• Clique-circulants and the stable set polytope of fuzzy circular interval graphs
• Cliques, holes and the vertex coloring polytope
• Graph colorings with local constraints -- a survey
• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 16720 (Why is no real title available?)
• Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope
• Matrices with the Edmonds-Johnson property
• New symmetry-less ILP formulation for the classical one dimensional bin-packing problem
• On Bin Packing with Conflicts
• On certain polytopes associated with graphs
• On optimal \(k\)-fold colorings of webs and antiwebs
• On stable set polyhedra for K//(1,3)free graphs
• On the asymmetric representatives formulation for the vertex coloring problem
• On the Facet-Inducing Antiweb-Wheel Inequalities for Stable Set Polytopes
• On the facial structure of set packing polyhedra
• Scheduling identical jobs on uniform machines with a conflict graph
• Scheduling on uniform machines with a conflict graph: complexity and resolution
• Scheduling with incompatible jobs
• Simple ingredients leading to very efficient heuristics for the maximum clique problem
• The rank facets of the stable set polytope for claw-free graphs
• The stable set polytope of quasi-line graphs
• The strong perfect graph theorem

This page was built for publication: Compact formulations and valid inequalities for parallel machine scheduling with conflicts

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