Conference Agenda

We study all possible Dantzig-Wolfe reformulations of stable set problems and how they relate to each other. In particular, we show that any two reformulations lead to identical polyhedra if and only if the corresponding decompositions contain the same odd induced cycles. Moreover, for instances on complete graphs, it is shown that any two reformulations are asymptotically almost surely different. One could thus expect to obtain a unique dual bound from each of the many polyhedra. In contrast, we observe only a few different dual bounds in our computational experiments. This agrees with earlier observations by Bastubbe, Lübbecke, and Witt, which remain largely unexplained.

We report on an exact approach to min-sum job-shop scheduling which builds on and combines ingredients that have been around in the literature for some time. The first is the idea of using an extended formulation for the problem, in this case essentially a network flow model on a time-indexed graph. Secondly, such formulations can be decomposed (leading to Lagrangian or Dantzig-Wolfe based approaches), either with so-called job-level or machine-level subproblems, or both, leading to strong dual bounds. We use machine-level subproblems. Thirdly, working with time-indexed models directly is often computationally limited because of their sheer size, and the so-called row-and-column generation paradigm suits this well in order to dynamically generate the network. And this is it (well, with some branching, cutting, and primal heuristics), and it worked for us. For several instances (minimum weighted completion time objective) from the literature we can prove optimality for the first time, or improve the best known dual or the primal bounds, respectively. These computational results are almost ten years old, but we never reported on them. In the end we look at a practical application from scheduling in a health care environment, which we came across only recently.