|Version 18 (modified by mjs, 4 years ago) (diff)|
Welcome to the DIP home page
DIP (Decomposition for Integer Programming) is an open-source extensible software framework for implementing decomposition-based bounding algorithms for use in solving large-scale discrete optimization problems. The framework provides a simple API for experimenting with various decomposition-based algorithms, such as Dantzig-Wolfe decomposition, Lagrangian relaxation, and various cutting plane methods. Given a compact formulation and a relaxation, the framework takes care of all algorithmic details associated with implementing any of a wide range of decomposition-based algorithms, such as branch and cut, branch and price, branch and cut and price, subgradient-based Lagrangian relaxation, branch and relax and cut, and decompose and cut. The user can specify customizations, such as methods for generating valid inequalities and branching, in terms of the variables of the compact formulation, without having to worry about the details of any required reformulations. DIP is used in combination with CHiPPS, which provides the underlying tree search methodology. All of these methods and how they are related are briefly described in the following:
- M. Galati and T.K. Ralphs, A Framework for Decomposition in Integer Programming, INFORMS 2009
- T.K. Ralphs and M. Galati, Decomposition in Integer Programming, in Integer Programming: Theory and Practice, John Karlof, ed. (2005), 57-110.
The design and implementation of DIP are described in more detail in Chapter 4 of the doctoral dissertation of Matthew Galati:
- M. Galati, Decomposition in Integer Linear Programming, Doctoral Dissertation, Lehigh University, December 2009.
Note that the DIP project was formerly known as DECOMP.
Note that these project webpages are based on Wiki, which allows webusers to modify the content to correct typos, add information, or share their experience and tips with other users. You are welcome to contribute to these project webpages. To edit these pages or submit a ticket you must first register and login.
February 17, 2010
- New stable release version 0.8.1.
January 29, 2010
- First stable release, version 0.8.0.
October 17, 2009
- The initial trunk import of DIP.
DIP should work on most platforms. But the following is the list of platforms it has been tested on.
- GNU/Linux (gcc)
- Microsoft Windows
- CYGWIN (w/ gcc)
- Visual C++ Version 9 (Limited testing and support).
There are currently no releases of DIP. The code is only available from the trunk development branch. This means that the code might change periodically. Once we have our first stable release, we will announce it on coin-announce.
In a Unix-like environment (such as Linux or CYGWIN), the following commands may be used to obtain and build DIP from source using SVN in most cases.
cd svn checkout https://projects.coin-or.org/svn/Dip/trunk coin-Dip cd coin-Dip mkdir build cd build ../configure make make install
The best way to learn how DIP works is to look at the examples provided here.
Getting More Help
- To report a bug, please submit a trouble ticket. Note that to edit these pages or submit a trouble ticket, you must first register and login.
- There is a DIP user's mailing list for discussion. Please visit the mailing list home to join or view the archives.
Licensing and Authors
The primary authors of the code are: