We present a distributed asynchronous algorithm for solving two-stage stochastic mixed-integer programs (SMIP) using scenario decomposition, aimed at industrial-scale instances of the stochastic unit commitment (SUC) problem. The algorithm is motivated by large differences in run times observed among scenario subproblems of SUC instances, which can result in inefficient use of distributed computing resources by synchronous parallel algorithms. Our algorithm performs dual iterations asynchronously using a block-coordinate subgradient descent method which allows performing block-coordinate updates using delayed information, while candidate primal solutions are recovered from the solutions of scenario subproblems using heuristics. We present a high performance computing implementation of the asynchronous algorithm, detailing the operations performed by each parallel process and the communication mechanisms among them. We conduct numerical experiments using SUC instances of the Western Electricity Coordinating Council system with up to 1000 scenarios and of the Central Western European system with up to 120 scenarios. We also conduct numerical experiments on generic SMIP instances from the SIPLIB library (DCAP and SSLP). The results demonstrate the general applicability of the proposed algorithm and its ability to solve industrial-scale SUC instances within operationally acceptable time frames. Moreover, we find that an equivalent synchronous parallel algorithm would leave cores idle up to 80.4% of the time on our realistic test instances, an observation which underscores the need for designing asynchronous optimization schemes in order to fully exploit distributed computing on real world applications.

The well known 4/3 conjecture states that the integrality ratio of the subtour LP is at most 4/3 for metric Traveling Salesman instances. We present a family of Euclidean Traveling Salesman instances for which we prove that the integrality ratio of the subtour LP converges to 4/3. These instances (using the rounded Euclidean norm) turn out to be hard to solve exactly with Concorde, the fastest existing exact TSP solver. For a 200 vertex instance from our family of Euclidean Traveling Salesman instances Concorde needs several days of CPU time. This is more than 1,000,000 times more runtime than for a TSPLIB instance of similar size. Thus our new family of Euclidean Traveling Salesman instances may serve as new benchmark instances for TSP algorithms.

We consider an extended version of the classical Max-k-Cut problem in which we additionally require that the parts of the graph partition are connected. For this problem we study two alternative mixed-integer linear formulations and review existing as well as develop new branch-and-cut techniques like cuts, branching rules, propagation, primal heuristics, and symmetry breaking. The main focus of this paper is an extensive numerical study in which we analyze the impact of the different techniques for various test sets. It turns out that the techniques from the existing literature are not sufficient to solve an adequate fraction of the test sets. However, our novel techniques significantly outperform the existing ones both in terms of running times and the overall number of instances that can be solved.

This paper introduces MiniCP, a lightweight, open-source solver for constraint programming. MiniCP is motivated by educational purposes and the desire to provide the core implementation of a constraint-programming solver for students in computer science and industrial engineering. The design of MiniCP provides a one-to-one mapping between the theoretical and implementation concepts and its compositional abstractions favor extensibility and flexibility. MiniCP obviously does not support all available constraint-programming features and implementation techniques, but these could be implemented as future extensions or exploratory projects. MiniCP also comes with a full set of exercises, unit tests, and development projects.

We consider a version of the knapsack problem in which an item size is random and revealed only when the decision maker attempts to insert it. After every successful insertion the decision maker can choose the next item dynamically based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We propose an exact algorithm based on a reformulation of the value function linear program, which dynamically prices variables to refine a value function approximation and generates cutting planes to maintain a dual bound. We provide a detailed analysis of the zero-capacity case, in which the knapsack capacity is zero, and all item sizes have positive probability of equaling zero. We also provide theoretical properties of the general algorithm and an extensive computational study. Our main empirical conclusion is that the algorithm is able to significantly reduce the gap when initial bounds and/or heuristic policies perform poorly.