Methods for Solving Mixed Integer and Stochastic Optimization Problems in Parallel
Abstract
Methods for Solving Mixed Integer and Stochastic Optimization Problems in Parallel Abstract Our prior research on mixed integer optimization has developed a framework for branch- ing on hyperplane algorithms to allow branching in the original space using the concept of adjoint lattices. We explored the use of approximate adjoint lattices to improve on the performance of branch-and-bound algorithms for mixed integer convex programming. In particular, we showed that the number of nodes in the branch-and-bound tree can be improved by a significant factor for several classes of difficult to solve mixed integer pro- grams. In a second line of research we developed and studied the empirical performance of walk-and-round heuristics for mixed integer linear and convex programs. We found that mixed integer solutions can be generated more efficiently if interior points generating from random walk are combined with the feasibility pump heuristic on a single processor machine for mixed integer linear and convex programs, in comparison to running the feasibility pump from the optimal vertex generated from the simplex method. We are cur- rently in the process of obtaining results on the parallel implementaton of walk-and-round heuristics. This proposal requests support for our ongoing research on algorithms and compu- tational methods for mixed integer and two-stage stochastic mixed integer optimization problems that model parameter uncertainty. The overarching goal of the proposed re- search is to develop algorithms for solving these problems in the emerging high per- formance computing environments. During the next three years we propose to further develop our algorithmic ideas for solving large scale mixed integer programs, particu- larly with emphasis on parallel computing. More specifically, we intend to develop (i) a primal-decomposition framework for solving two-stage stochastic mixed integer linear programs where the first stage variables are mixed integer and the second stage variables are continuous; (ii) study two-stage problems where the second stage can be convexified due to its structure; (iii) study two-stage stochastic linear mixed integer programs where both stages have mixed integer variables; (iv) study an approach for finding high quality solutions in two-stage stochastic linear mixed programs in parallel using walk-and-round heuristics; (v) study approaches for finding high quality disjunctions for branching for two-stage stochastic linear mixed integer programs. We intend to study our algorithmic developments on shared as well as distributed memory computing environments.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 12, 2016
- Source ID
- N000141512226
Entities
People
- Sanjay Mehrotra
Organizations
- Northwestern University
- Office of Naval Research
- United States Navy