Distributed Integer Programming
Abstract
This project will study general purpose decomposition methods for Integer Programs (IP) that can exploit distributed computing environments, and can be executed in a decentralized manner with limited coordination. Traditional decomposition approaches for large-scale IP are based on Lagrangian relaxation or column-generation ideas. These schemes require strong coordination among subproblem solutions and are not well suited for implementations across distributed computing nodes. In this work we will develop new forms of decomposition schemes that require little subproblem coordination. The technical approach is to leverage the recent developments in distributed convex optimization, along with the classical IP techniques. 1. Decomposable extended formulations: The IP of interest may not be explicitly available in a form suitable for distributed optimization. By introducing additional variables, i.e. extending to a higher-dimensional space, we can reformulate such a problem into a form of suitable for distributed optimization. Since the reformulation is not unique there is a need to understand strategies for and properties of valid reformulations. 2. Distributed Decomposition based on Lagrangian relaxation: We will study decomposition methods based on the Augmented Lagrangian Relaxation (ALR) framework . Such schemes are known to have much stronger convergence properties than standard Lagrangian Relaxation approaches for convex problems. This work will investigate these schemes for IPs. One specific research direction is the adaptation of Alternating Direction Method of Multipliers (ADMM) type approaches, (which are based on the Augmented Lagrangian Dual framework and developed for distributed convex optimization), to the IP setting. 3. Distributed Decomposition based on column generation: For mixed integer linear programs we will investigate column-generation approaches where the master problem can be solved using a distributed scheme. In the traditional column-generation scheme, the subproblems naturally decompose but the master problem needs to work with columns collected from subproblems. One possible idea is to use an ADMM type approach to distribute the master problem along with the subproblems across computing nodes. In this setting each node works with only its own columns, and exchange dual-price information. 4. Distributed Implementation: The distributed primal and dual decomposition schemes mentioned above require the solution of a large collection of integer subproblems, and coordination among them by exchanging small amounts of information. We will investigate various issues pertaining to the implementation of such schemes on high performance computing (HPC) architectures. One key issue is the use of integer-programming sensitivity analysis to expedite solutions of similar subproblems. Other issues include convergence, warm-starting, load balancing, and stabilization.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 12, 2016
- Source ID
- N000141512078
Entities
People
- Shabbir Ahmed
Organizations
- Georgia Tech Research Corporation
- Office of Naval Research
- United States Navy