Gerhard J. Woeginger In recent years, branch-and-cut algorithms have become firmly established as the most effective method for solving generic mixed integer linear programs (MILPs). Methods for automatically generating inequalities valid for the convex hull of solutions to such MILPs are a critical element of branch-and-cut. This paper examines the nature of the so-called separation problem, which is … Read more
We study the minimum spanning tree problem, the maximum matching problem and the shortest path problem subject to binary disjunctive constraints: A negative disjunctive constraint states that a certain pair of edges cannot be contained simultaneously in a feasible solution. It is convenient to represent these negative disjunctive constraints in terms of a so-called conflict … Read more
For the $r$-stage open shop problem with identical parallel machines at each stage and the minimum makespan criterion, an approximation scheme is constructed with running time $O(nrm + C(m,\eps))$ , where $n$ is the number of jobs, $m$ is the total number of machines, and $C(m,\eps)$ is a function independent of $n$. CitationDiscrete Appl. Math. … Read more