Home
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.
DIP does not currently have extensive documentation, but the design and implementation of DIP are described in more detail in Chapter 4 of the doctoral dissertation of Matthew Galati (linked below) and the thoery behind DIP is described in both of the following below links.
- M. Galati, Decomposition in Integer Linear Programming, Doctoral Dissertation, Lehigh University, December 2009.
- T.K. Ralphs and M. Galati, Decomposition in Integer Programming, in Integer Programming: Theory and Practice, John Karlof, ed. (2005), 57-110. Furthermore, the basic theory and various aspects of how DIP works are covered in the following presentations:
- Decomposition in Integer Linear Programming (Full tutorial covering many aspects of decomposition-based methods)
- Overview of Decomposition and the DIP Software Framework
- Dip and DipPy: A Decomposition-based Modeling System and Solver
- Generic Decomposition-based Solution Methods
- Automatic Methods for Finding Decompositions
- DIP with CHIPPS: Decomposition Methods in Integer Programming
DIP can be customized and called from the python-based modeling language PuLP through the extension called DipPy.
For more information on supported platforms, links to dependent projects, current version, and more, click here
Note that the DIP project was formerly known as DECOMP.
- The latest stable version of DIP is
.
- The latest release version of DIP is
.
- Click here to see the current change log.
Travis-CI (OS X and Linux)
Appveyor (Windows)
- DIP has been built and tested on all popular platforms.
- GNU/Linux (gcc)
- Microsoft Windows
- CYGWIN (w/ either MINGW or SYGWIN gcc).
- Visual C++ Version 9-11 (and probably more recent version also).
- OS X
- clang
- gcc (Homebrew version tested)
- DIP is most easily used through the Python-based modeling language DipPy, which has also been built and tested on all major platforms.
- DipPy can also be used on Windows directly from Excel using the Solver Studio plug-in. Below are some screen shots that show DipPy being used in Solver Studio.
 |
 |
|---|---|
| = Solver Studio screen shot = | = Choosing algorithm in Solver Studio = |
 |
 |
| = Displaying search tree using GrUMPy = | = Editing DipPy Model with Eclipse and PyDev = |
'''Binaries can be obtained
- Pre-compiled binaries are available on BinTray and as part of the COIN-OR Optimization Suite.
- On Windows, the GUI installer for the COIN-OR Optimization Suite is here.
- DipPy can be installed on some platforms with
easy_install coinor.dippy, installed on Windows alongside GiMPy [https://github.com/coin-or/GiMPy] using an install script, or easily built from source (see here).
Source code can be obtained either by
- Downloading a snapshot of the source code from the DIP source code download page, or
- Checking out the latest stable source using a subversion client.
- Checking out the code from Github
The recommended method is to use subversion because it makes it easier to obtain updates. Below are some quick start guides for building on common platforms.
Quick Start Guide for Unix-like Environments
In a Unix-like environment (such as Linux or CYGWIN), the following commands may be used to obtain and build DIP from source using either SVN or git in most cases. For SVN, do
svn checkout https://projects.coin-or.org/svn/Dip/releases/0.92 Dip-0.92
cd Dip-0.92
For git do
git clone --branch=stable/0.92 https://github.com/coin-or/Dip Dip-0.92
cd Dip-0.92
git clone --branch=stable/0.8 https://github.com/coin-or-tools/BuildTools/
BuildTools/get.dependencies.sh fetch
Finally, do
./configure
make
make install
Optionally, once could also execute make test to run DIP's unit test.
Quick Start Guide for Microsoft Visual C++ Users
DIP Binaries can be obtained using the installer for the COIN Optimization Suite, which can be found here (look for the files ending in .exe.
For Microsoft Visual C++ users, there are project files for MSVC++ Versions 9 and 10 available in the MSVisualStudio directory. First, obtain the source code using either a Windows subversion client (see the COIN-OR FAQ) or download a snapshot. Open the solution file and build the Decomp project. The code should build out of the box with default settings.
Note that one can also build in Windows using the cl compiler with the GNU autotools in either CYGWIN or MSys2. This provides an automated command-line build and more flexibility in specifying configuration options. To use this method, follow the instructions above but add --enable-msvc=MD as an argument to the configure command.
January 15, 2017
- DIP 0.92.3 released.
- Update dependencies
- Minor bug fix
- Add support for Appveyor and Travis
- Install examples with DipPy
- Click here to view change set for this release.
November 12, 2015
- DIP 0.92.2 released.
- Got rid of pesky global variable DecompInf, fixing problem with static builds.
- Fix bugs in wedding planner example
- Fix bugs in DipPy to allow returning no solutions, even when an exact subproblem solver is used and to allow no branching candidates when branching.
- Click here to view change set for this release.
November 12, 2015
- DIP 0.91.6 released.
- Fix bugs in wedding planner example
- Fix bugs in DipPy to allow no branching candidates when branching.
- Click here to view change set for this release.
October 8, 2015
- DIP 0.92.1 released.
- Fixed problem with dependency linking
- Click here to view change set for this release.
October 1, 2015
- DIP 0.92.0 released.
- First release in stable series (see new features below).
- Click here to view change set for this release.
September 26, 2015
- DIP 0.91.5 released.
- Small bug fix when SYMPHONY is used and multiple columns are generated in each iteration.
- Click here to view change set for this release.
September 22, 2015
- DIP new stable version 0.92 released.
- Substantially re-designed internals
- Re-named some classes, functions, and parameters more intuitively.
- Eliminated unnecessary "MILP" parameter section and joined it to "DECOMP", as well as making "DECOMP" the default parameter section name.
- Changed parameter setting mechanism to make it possible to pass parameters directly to solvers using native parameters names.
- Added interface to Gurobi.
- Added ability to select solver at run time rather than compile time.
- In DipPy, the user can now return a status in the subproblem solve to indicate whether the subproblem was solved exactly. Previously, DipPy solved the subproblem to optimality internally whenever no solution was returned, which is unnecessary if the user's subproblem solver is exact. It also means that the user was previously required to provide a full description of the subproblem.
- Click here to view change set for 0.92.
June 2, 2015
- DIP 0.91.4 released.
- Fixed bugs in examples
- Updates to dependencies
- Small bug fixes
- Click here to view change set for this release.
April 4, 2015
- DIP 0.91.3 released.
- Incorporating fixes for Doxygen documentation
- Click here to view change set for this release.
March 11, 2015
- DIP 0.91.2 released.
- Fixed issue with master only variable when solving master as an integer program.
- Added ability to generate multiple columns per iteration with SYMPHONY and Cbc.
- Click here to view change set for this release.
February 11, 2015
- DIP 0.91.1 released.
- Updating dependencies.
- Fix for dependency linking
- Fix to installation with
DESTDIR - Click here to view change set for this release.
January 20, 2015
- DIP 0.91.0 released.
- Multiple parallel modes added
- Solution of individual subproblems can be parallelized
- Multiple subproblems can be solved simultaneously
- Multiple algorithms can be executed in parallel (branch and cut plus one or more decomposition-based algorithms)
- Warm starting for solutions of subproblems is supported when using SYMPHONY as the subproblem solver.
- Unbounded feasible regions now supported.
- Explicit treatment of master-only variables.
- Click here to view change set for this release.
- Multiple parallel modes added
January 4, 2015
- DIP 0.9.12 released.
- Fixed long-standing issues with stand-alone apps
- Small some bug fixes
- Click here to view change set for this release.
July 10, 2014
- DIP 0.9.11 released.
- Added some new DipPy examples
- Small bug fixes
- Click here to view change set for this release.
June 25, 2014
- DIP 0.9.10 released.
- Fixes to stand-alone app examples
- Fixes to Visual studio files for examples to support property pages
- Click here to view change set for this release.
March 7, 2014
- New stable version 0.91
- Changes to the DipPy callback interface to make it more user friendly
- Changes to the application interface
- Planning for other changes to the internal algorithm
December 17, 2013
- DIP 0.9.9 released.
- Fixes to DipPy build and examples
- Fixes to allow CGL cuts to be generated from within DipPy branch and price.
- Click here to view change set for this release.
November 24, 2013
- DIP 0.9.8 released.
- Fixes to DipPy examples
- Support for dependency linking
- Click here to view change set for this release.
November 24, 2013
- DIP 0.9.7 released.
- Fixes to DipPy examples
- Support for dependency linking
- Click here to view change set for this release.
November 3, 2013
- DIP 0.9.6 released.
- Fixes to allow proper installation of DipPy on Mac OS X
- Click here to view change set for this release.
November 2, 2013
October 21, 2013
- DIP 0.9.4 released.
- Fixes to parallel subproblem solution mode with OpenMP
- Click here to view change set for this release.
October 18, 2013
October 16, 2013
October 3, 2013
- DIP 0.9.1 released.
- Fixes to Python installation
- Fix to DipPy
- Click here to view change set for this release.
September 18, 2013
January 23, 2013
- New stable version 0.9.
- Visual Studio 10 project files added
- Python-based modeling language DipPy added to Dip source tree
- DIP can now function as a stand-alone MILP solver with automatic structure detection
- Updates and fixes to core libraries
- Updates to build system
The best way to learn how DIP works is to look at the examples provided here. For DipPy examples, look [here https://projects.coin-or.org/Dip/browser/trunk/Dip/src/dippy/examples]
DIP links to a number of other COIN projects for additional functionality, including:
- Clp (the default solver for LP relaxations)
- Osi (an interface to alternative solvers for solving LP relaxations)
- Cgl (for cut generation)
- CoinUtils (for reading in MPS files and various utilities)
- Cbc (for solving integer subproblems)
- SYMPHONY (for solving integer subproblems with warm-starting)
- CHiPPS (for performing the tree search)
-
To report a bug, please submit a trouble ticket. NOTE: Ticket system is currently disabled due to problems with SPAM. Please post to mailing list (see below). 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.
- OSDip -- A generic block-angular decomposition algorithm is now available as part of the Optimization Services (OS) project. It is based on the Decomposition in Integer Programming (Dip) project jointly with the Optimization Services (OS) project. We call this the OS Dip solver. Users can easily add their own block solver (oracle) without altering the OS Dip Solver code. The user simply creates a separate file containing the oracle class. The user-provided oracle class inherits from the generic OSDipBlockSolver class. The OS Dip solver is part of the ApplicationTemplates subproject of CoinBazaar.
- Dippy -- In the Department of Engineering Science (The University of Auckland, New Zealand) we have combined DIP with PuLP (a Python-based mathematical programming language) to create Dippy. Using Dippy we can easily create mathematical models and send them to DIP, but we can also implement user functions for advanced branching, solving subproblems, generating cuts, using heuristics, etc directly within PuLP. Thus, Dippy provides the advanced MILP methods of DIP with the ease of use of PuLP. We have used Dippy as a teaching tool to get students "playing" with advanced branching, cut generation and column generation. We have prototyped formulation and solution methods for building financial portfolios, cutting steel to order and planning tours for health and disability advocates. We have also been researching approaches for mitigating antisymmetry in MILPs and are using Dippy as our test environment.
- IBM -- At IBM Global Technology Services, Business Process Reengineering Department, DIP is utilized as the optimization framework for the extremely large-scale National Workforce Management, Cross-Training and Scheduling Project. Ongoing performance improvements are being carried out by experimenting on initial dual vector estimation to prevent bad starting lower bounds; intermediary dual vector manipulation to avoid parallel columns, degeneracy and to bring smarter columns; and finally, subproblem selection for acceleration purposes. DIP is planned to be used in the Workcell Determination and Back-up Strategies Project, too. Contact Person: Alper Uygur <alperuygur
@gmail.com>
DIP is written in C++ and is distributed as open source code under the Eclipse Public License (EPL). It is available from the COIN-OR initiative.
The primary authors of the code are:
The conceptual designers and maintainers of the code are Matthew Galati and Ted Ralphs of the COR@L Lab at Lehigh University.