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.

The dual decomposition of stochastic mixed-integer programming (SMIP) has been instrumental for providing a scalable solution of SMIP with integer variables and large scenarios by taking the Lagrangian relaxation of the original problem with respect to the nonanticipativity constraints. The Lagrangian relaxation results in the master problem of solving the Lagrangian dual problem and the subproblems that are defined for each scenario and can be solved in parallel. While the bundle method and its variants have been successfully used to solve the master problem, the master problem steps can significantly degrade the parallel efficiency as is typically solved in serial. We present a novel algorithm for solving the master problem in parallel by adopting the alternating direction method of multiplier algorithm. We implement the algorithm and present the numerical results from various test instances.

This talk considers a waste collection problem with intermediate disposal facilities to accommodate the usage of smaller, but more sustainable vehicles, with less capacity than the traditional waste collection trucks. The optimization problem consists in determining the locations to place the collection points and the routes of a capacitated collection vehicle that visits these locations. We first present a mixed-integer linear programming formulation that exploits the sparsity of the road network. To efficiently solve practical instances, we propose a solution method that decomposes the problem into a set covering problem to select the locations and a capacitated vehicle routing problem with intermediate facilities to determine the routes and price the set covering solution. We apply column generation to solve this routing problem and present a novel approach for the set covering problem that exploits the properties of the problem to efficiently find a set cover by using a graph theoretical approach. We compare our method with the set construction method and the heuristic Benders decomposition approach presented in a previous work. Computational experiments on instances derived from real-life data confirm the difficulty of our problem and show the superior performance of the developed decomposition method with respect to the number of best solutions and the average gaps to the best solution.

Large-neighbourhood search (LNS) heuristics are important mathematical programming techniques that search for primal feasible solutions by solving an auxiliary problem with a restricted feasible region. Extending such powerful generic LNS heuristics to the branch-and-price context is inherently challenging. The most prominent challenges arise from the fact that in branch-and-price algorithms, columns are generated with the sole aim to solve linear programming relaxations. Hence, the ability to form integer feasible solutions is not considered during the generation of columns. Without any changes to the standard pricing schemes, the potential of deploying generic LNS heuristics within a branch-and-price procedure is severely limited.

We propose a matheuristic, based on an LNS heuristic framework, where the novelty is a customised pricing scheme for generating columns to solve an auxiliary problem. The theoretical foundation for this pricing scheme is a set of optimality conditions for integer programs. From this foundation, a column generation strategy is developed for finding columns that are likely to be of use in high-quality primal feasible solutions for the original problem. The proposed matheuristic is implemented in the generic branch-price-and-cut solver GCG. On a broad test set comprising classical block diagonal structured instances and general instances from the MIPLIB 2017 Collection, the computational results show a significant improvement to the solving performance of GCG.