High performance computing algorithms for discrete optimization

Abstract

This thesis concerns the application of High Performance Computing to Discrete Optimization, and the development of massively parallel algorithms designed to accelerate the solving process of Mixed-Integer Programs (MIPs). We begin by presenting a portfolio of scalable parallel primal heuristics, which focus on providing the end-user with high quality feasible solutions to any MIP program quickly. In some cases, we show our algorithms to be several orders of magnitude more effective than current state-of-the-art approaches. The first of the contributions in this category is a specialized primal heuristic for the Fixed Charge Multicommodity Network Flow problem. The presented computational experiments back the superior effectiveness of our method at finding substantially better primal solutions when compared to state-of-the-art commercial MIP solvers, even when the latter are allowed five times as much time. We further generalize the introduced notions and develop Parallel Alternating Criteria Search: a general-purpose parallel primal method prepared for handling any unstructured MIP. We show how the combination of parallelism and simple large neighborhood search schemes can provide a powerful tool for generating high quality solutions for any given problem. Our parallel method is able to produce competitive or better and faster results for more than 90% of the tested instances against CPLEX. Parallel Alternating Criteria Search becomes especially useful in the context of large instances and time-sensitive optimization problems, where traditional branch-and-bound methods may not be able to provide competitive upper bounds and attaining feasibility may be challenging. The modular nature of Parallel Alternating Criteria Search can provide an excellent platform for rapid prototyping parallel domain-specific heuristics. We show this particular achievement on the Maritime Inventory Routing Problem, a complex optimization problem that combines network flows with inventory management. In the presented results, tailored versions of our parallel algorithm are able to significantly outperform domain-specific state-of-the-art heuristics and parallel MIP solvers alike. The second half of this thesis is dedicated to the introduction of PIPS-SBB, a parallel distributed-memory solver for deterministic equivalent two-stage stochastic MIPs (sMIPs). The newly introduced solver features multiple levels of nested parallelism. It is also designed with data parallelism in mind, allowing the problem data to be partitioned across multiple distributed-memory machines. We then present two Branch-and-Bound parallelizations extending the already parallel solver. We investigate the effects of leveraging multiple levels of parallelism and their part in improving the scaling performance beyond thousands of cores. We also compare our algorithms against a distributed-memory implementation of a commercial MIP solver. The latter proves to be the best performer at small problem scales. However, the specialized nature of the methods present in PIPS-SBB-based solvers allow them to be the best performers in large SMIP instances. The direct product of this thesis is a set of algorithms ready to be used in massively parallel systems to quickly find high quality solutions to any MIP problem. The presented works ultimately increase our understanding of the use of parallelism in the context of Discrete Optimization and its important part in improving the effectiveness and performance of its algorithms.