wiki:WikiStart

DisCO Development Page

DisCO (Discrete Conic Optimization) is a solver for Mixed Integer Second Order Conic Optimization problems (MISOCP). It is developed on top of COIN-OR High-Performance Parallel Search (CHiPPS) framework.

DisCO does branch and bound search to solve MISOCP problems. DisCO depends on many other projects. It depends OsiConic on communicating with its relaxation solvers. It depends on CglConic to cut infeasible solutions. DisCO shares some commit history with COIN-OR project CHiPPS-Blis. Current master was re-written from scratch, however, and does not share any commits with BLIS.

DisCO is distributed under the Eclipse Public License and is freely redistributable. All source code and documentation is Copyright 2001-2017 by Lehigh University, Aykut Bulut and Ted Ralphs. This README may be distributed freely.

Master Branch Build Status

Travis-CI (OS X and Linux)

https://travis-ci.org/aykutbulut/DisCO.svg

Master Branch Code Quality Report

https://api.codacy.com/project/badge/Grade/a7c5abda08874549bee0324603ecaca1

Download version 0.95

https://api.bintray.com/packages/coin-or/download/DisCO/images/download.svg

Cite DisCO

https://zenodo.org/badge/36100320.svg

Installation

Basic Installation

DisCO depends on many other projects. You should compile the dependant projects if they are not installed in your system. The easiest way of installing DisCO is using BuildTools fetch and build script. For this you can use the following commands in Linux environment. After cloning DisCO, use

git clone --branch=stable/0.8 https://github.com/coin-or-tools/BuildTools
bash BuildTools/get.dependencies.sh fetch > /dev/null
bash BuildTools/get.dependencies.sh build

This compiles DisCO with Outer Approximation (OA) algorithm. This algorithm relaxes integrality constraints and conic constraints. Performs a branch and bound search to find a solution that satisfy both of these constraints.

There are other algorithms implemented in DisCO. You can use a typical branch and bound algorithm where at each node only integrality constraints are relaxed. For this you need to provide a Second Order Conic Optimization (SOCO) solver. For now DisCO supports 3 solvers, Ipopt, Mosek and Cplex. To use DisCO with Ipopt you need to add --with-soco-solver=ipopt flag to configure script. This can be achieved with the following command.

./configure --with-soco-solver=ipopt

Afterward you can call make install to build and install DisCO.

For advanced users

Make sure all dependencies are accessible through pkg-config. Then DisCO's configure script will find them through pkg-config. Alternatively DisCO configure script can locate other projects if --prefix configure flag is set right. Assume other projects are installed at install_dir. Then use

./configure --prefix=install_dir && make install

Specifying an Algorithm/Solver

DisCO implements an Outer Approximation algorithm and it is the default behavior you will get. If you want to use DisCO with a typical branch and bound algorithm (only integrality constraints are relaxed in nodes and corresponding problems are solved with a SOCO solver) you need to specify this during configure. DisCO depends on OsiConic in communicating with its solver. There are three solvers available, Ipopt, Mosek and Cplex. OsiIpopt, OsiMosek and OsiCplex implement OsiConic interface for the corresponding solvers.

To compile DisCO with Mosek/Cplex you should first compile OSI with Mosek/Cplex. Then you should compile OsiMosek/OsiCplex. Please check OSI and OsiMosek/OsiCplex documentations for details.

Once OsiMosek is compiled and installed, You can configure DisCO as follows.

./configure --with-soco-solver=mosek

For Cplex just replace mosek with cplex. Similarly for Ipopt just use ipopt.

To specify CglConic IPM solver, you need to give --with-ipm-solver flag to configure script. For example, following command configures CglConic to use Mosek in warm starting OA method.

./configure --with-ipm-solver=mosek

Similarly you can use cplex, ipopt or cola instead of mosek. If no IPM solver is specified CglConic will use Ipopt.

1.4 Compiling with MPI

To compile with MPI you need to give the following options to configure for DisCO and dependands projects.

./configure --disable-shared --enable-static --with-mpi-lib=/usr/lib/libmpich.so.3.2 --with-mpi-incdir=/usr/lib/mpich/include MPICC=mpicc.mpich MPICXX=mpic++.mpich"

You should update directory locations and executable names acording to your system and MPI implementation you intend to use. DisCO is tested with and works for both mpich2 and openmpi.

Using DisCO

DisCO can read problems in Mosek's extended MPS format (it can handle CSECTION in mps files, see http://docs.mosek.com/7.1/capi/The_MPS_file_format.html) for SOCO problems. Once you compiled DisCO you can use is as follows.

path_to_disco/disco input.mps

This uses the default parameters (cut generation/branching/search etc.). You can modify its default behavior by specifying parameters. See src/disco.par.in file for available parameters. For example following solves input problem using strong branching with generating gomory cuts (available in OA algorithm only) in the root node.

path_to_disco/disco input.mps Alps_instance input.mps Dco_branchStrategy 3 Dco_cutGomoryStrategy 1

Current Testing Status

  • Operating Systems
    • Linux: Well tested.
    • Mac OS: I did not test DisCO in OS. In theory this should work.
    • Windows: Not tested.
  • Algorithms
    • OA: Well tested and works fine.
    • Ipopt: Works fine. There are missing functions in the [interface][5]. Tested on CBLIB 2014 and random problems. Ipopt fails to converge on some instances. We beleive this is due to nonsmooth formulation of the conic constraints.
    • Cola: Well tested, works fine.
    • Mosek: Works fine. There are missing functions in the interface. It is complete enough to work with DisCO. Well tested on CBLIB 2014 and random problems. Mosek might fail on numerically challanging instances.
    • Cplex: Missing functions in the interface. Interface is complete enough to work with DisCO. Tested on CBLIB 2014 and random problems. Cplex rarely fails on some instances.
  • Branching/Cutting
    • When OA algorithm is used and Ipopt is chosen as an IPM solver in CglConic, Ipopt might fail, on some problems, at the root node. You can use Mosek or Cplex for this if it is available to you.
  • MPI testing,
    • MPICH2: Tested and works fine.
    • OpenMPI: Tested up to 128 processors and works fine. Good parallelization performance when the tree is well balanced.

Documentation

You can refer to documentations of the dependant projects. DisCO uses doxygen for documentation purposes. make doxygen will produce a documentation of DisCO.

SUPPORT

Authors

Aykut Bulut (aykutblt@…), Ted Ralphs (ted@…).

Bug Reports

Bug reports should be reported at the DisCO repository at https://github.com/aykutbulut/DisCO/issues/new

Last modified 2 weeks ago Last modified on May 13, 2018 12:12:02 AM