Alternating Criteria Search: A Parallel Large Neighborhood Search Algorithm for Mixed Integer Programs

We present a parallel large neighborhood search framework for finding high quality primal solutions for generic Mixed Integer Programs (MIPs). The approach simultaneously solves a large number of sub-MIPs with the dual objective of reducing infeasibility and optimizing with respect to the original objective. Both goals are achieved by solving restricted versions of two auxiliary … Read more

What Could a Million Cores Do To Solve Integer Programs?

Given the steady increase in cores per CPU, it is only a matter of time until supercomputers will have a million or more cores. In this article, we investigate the opportunities and challenges that will arise when trying to utilize this vast computing power to solve a single integer linear optimization problem. We also raise … Read more

Application of a smoothing technique to decomposition in convex optimization

Dual decomposition is a powerful technique for deriving decomposition schemes for convex optimization problems with specific structure. Although the Augmented Lagrangian is computationally more stable than the ordinary Lagrangian, the \textit{prox-term} destroys the separability of the given problem. In this paper we use another approach to obtain a smooth Lagrangian, based on a smoothing technique … Read more

Decomposition Algorithms for Stochastic Programming on a Computational Grid

We describe algorithms for two-stage stochastic linear programming with recourse and their implementation on a grid computing platform. In particular, we examine serial and asynchronous versions of the L-shaped method and a trust-region method. The parallel platform of choice is the dynamic, heterogeneous, opportunistic platform provided by the Condor system. The algorithms are of master-worker … Read more