Optimization Online


Decomposition of loosely coupled integer programs: A multiobjective perspective

Merve Bodur(merve.bodur***at***gatech.edu)
Shabbir Ahmed(sahmed***at***isye.gatech.edu)
Natashia Boland(natashia.boland***at***isye.gatech.edu)
George L. Nemhauser(george.nemhauser***at***isye.gatech.edu)

Abstract: We consider integer programming (IP) problems consisting of (possibly a large number of) subsystems and a small number of coupling constraints that link variables from different subsystems. Such problems are called loosely coupled or nearly decomposable. Motivated by recent developments in multiobjective programming (MOP), we develop a MOP-based decomposition algorithm to solve loosely coupled IPs. More specifically, we reformulate the problem so that it can be decomposed into a (resource-directive) master problem and a set of MOP subproblems. The proposed algorithm iteratively generates columns for the master problem. However, unlike traditional column generation methods, the master problem is an IP and considers a differently structured (and usually smaller) set of columns. Columns are added to the master problem IP until its solution provides an optimal solution to the original problem. One advantage of the approach is that the solution of the master problem and subproblems can be done with standard IP solvers, exploiting the sophisticated techniques they embed; there is no need for a tailored branch-and-price. We provide preliminary computational results, demonstrating the potential benefits of our approach.

Keywords: Integer programming, resource-directive decomposition, multiobjective integer programming, column generation

Category 1: Integer Programming

Category 2: Other Topics (Multi-Criteria Optimization )


Download: [PDF]

Entry Submitted: 08/23/2016
Entry Accepted: 08/23/2016
Entry Last Modified: 08/23/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society