Dip

Projects such as this one are maintained by a small group of volunteers under the auspices of the non-profit COIN-OR Foundation and we need your help! Please consider sponsoring our activities or volunteering to help!

This file is auto-generated from config.yml using the generate_readme script. To make changes, please edit config.yml or the generation scripts here and here.

DIP (Decomposition in Integer Programming) is a framework for implementing a wide variety of decomposition-based algorithms for solving integer programs, including full generic column generation in which the user need only indicate whic constraints to relax and the framework takes care of all other aspects of the column-generation. The problem can be specified using DiPPy, an extension of the Python-based modeling language PuLP (see examples). If desired, custom subroutines for solving the subproblem, branching, heuristics, etc. can be implemented in pure Python and called automatically from C++ during execution of the algorithm.

Dip makes it easy to implement and compare different variety of decomposition-based algorithm while keeping as many details of the algorithmic implem,entation constant as possible, allowing for rigorous empirical comparisons.

Using DiPPy, one can even implement a full column-generation algorithm within an Excel spreadsheet using Solver Studio. See screen shots below.

Dip is written in C++ and is released as open source under the Eclipse Public License 2.0.

It is distributed under the auspices of the COIN-OR Foundation.

The Dip development site is https://github.com/coin-or/Dip.

CITE

Code:

Paper: http://dx.doi.org/10.1007/s10107-005-0606-3

CURRENT BUILD STATUS

DOWNLOAD

What follows is a quick start guide for obtaining or building Dip on common platforms. More detailed information is available here.

Docker image

There is a Docker image that provides Dip, as well as other projects in the COIN-OR Optimization Suite here

Binaries

For newer releases, binaries will be made available as assets attached to releases in Github here. Older binaries are archived as part of Dip here.

Due to license incompatibilities, pre-compiled binaries lack some functionality. If binaries are not available for your platform for the latest version and you would like to request them to be built and posted, feel free to let us know on the mailing list.

Source

Source code can be obtained either by

• Downloading a snapshot of the source code for the latest release version of Dip from the releases page,
• Cloning this repository from Github, or
• Using the coinbrew script to get the project and all dependencies (recommended, see below).

Dependencies

Dip has a number of dependencies, which are detailed in config.yml. Dependencies on other COIN-OR projects are automatically downloaded when obtaining the source with coinbrew. For some of the remaining third-party dependencies, automatic download scripts and build wrappers are provided (and will also be automatically run for required and recommended dependencies), while other libraries that are aeasy to obtain must be installed using an appropriate package manager (or may come with your OS by default).

BUILDING from source

These quick start instructions assume you are in a bash shell.

Using coinbrew

To download and build Dip from source, execute the following on the command line.

wget https://raw.githubusercontent.com/coin-or/coinbrew/master/coinbrew
chmod u+x coinbrew
./coinbrew fetch Dip@master
./coinbrew build Dip

For more detailed instructions on coinbrew, see https://coin-or.github.io/coinbrew. The coinbrew script will fetch the additional projects specified in the Dependencies section of config.yml.

Without coinbrew (Expert users)

• Download the source code, e.g., by cloning the git repo https://github.com/coin-or/Dip
• Download and install the source code for the dependencies listed in config.yml
• Build the code as follows (make sure to set PKG_CONFIG_PTH to install directory for dependencies).

./configure -C
make
make test
make install

Quickstart with DIP/DipPy

If you are on Linux or OS X, DIP can be installed from source using coinbrew (see below). In Windows, there are pre-built binary wheels for DipPy. After build and install of DIP, if you are installing DipPy, make sure to set PKG_CONFIG_PATH to point to the directory where the .pc files are installed (by default, this is in the lib/pkgconfig directory in the installation directory). You may also need to set either LD_LIBRARY_PATH (Linux) or DYLD_LIBRARY_PATH (OS X) to point to the directory where the libraries are installed. Then simply do

pip install coinor.dippy

After installation, you can try running the examples to see if trhings are working. These should all work out of the box. For a listing of examples and some brief instructions, do

python -m coinor.dippy.examples

To get help for an example, do, e.g.,

python -m coinor.dippy.example.cflp --help

or just run

python -m coinor.dippy.examples.cflp

Screen Shots

Using DiPPy in Solver Studio

Choosing algorithm in Solver Studio

Displaying search tree using GrUMPy

Editing DipPy Model with Eclipse and PyDev

Doxygen Documentation

If you have Doxygen available, you can build a HTML documentation by typing

make doxydoc

in the build directory. If Dip was built via coinbrew, then the build directory will be ./build/Dip/master by default. The doxygen documentation main file is found at <build-dir>/doxydoc/html/index.html.

If you don't have doxygen installed locally, you can use also find the documentation here.

Additional Documentation

• C++ examples
• DiPPy (Python) examples
• Slides providing a brief introduction are here
• Slides providing a much longer introduction are here
• For the methodological basis, see
  • This paper (pre-print here); or
  • This more detailed paper; or
  • This dissertation (much more detailed)
• http://coral.ie.lehigh.edu/~ted/files/papers/MatthewGalatiDissertation09.pdf

Project Links

• Code of Conduct
• COIN-OR Web Site
• COIN-OR general discussion forum
• Dip Discussion forum
• Report a bug
• Doxygen generated documentation

CHANGELOG

Release 0.95.0

• Python 3 support added

Release 0.92.4

• Update dependencies
• Minor bug fixes for DipPy

Release 0.92.3

• Update dependencies
• Minor bug fix
• Add support for Appveyor and Travis
• Install examples with DipPy

Release 0.92.2

• Get rid of pesky global variable DecompInf
• 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.

Release 0.91.6

• Fixed bugs in Wedding Planner example.
• Fixed bug in DipPy having to do with branching.

Release