An Evaluation Upon Theoretical Background For Using the Principle of Decomposition Methods For Integer Linear Programming

An Analysis of Traditional and Integrated Decomposition Methods for Integer Linear Programming

Abstract

In this paper, we present a theoretical background forusing the principle of decomposition to solve mixed integer linear programs(MILP). We focus on the common threads among three traditional methods forgenerating approximations to the convex hull of feasible solutions to an MILP.These include a method employing an outer approximation, the cutting-planemethod, as well as two related methods employing inner approximations, theDantzig-Wolfe method and the Lagrangian method. We then extend thesetraditional methods by allowing for the use of both outer and innerapproximation simultaneously. This leads to the development of two boundingmethods that generate even stronger bounds, known as price-and-cut andrelax-and-cut. We describe DIP (Decomposition for Integer Programming),a new open-source software framework that provides the algorithmic shell forimplementation of these methods. DIP has been designed with the goal ofproviding a user with the ability to easily utilize various traditional andintegrated decomposition methods while requiring only the provision of minimalproblem-specific algorithmic components.