/MibS

A solver for mixed integer bilevel programs

Primary LanguageJetBrains MPSEclipse Public License 1.0EPL-1.0

MibS

A COIN-OR Project

Latest Release

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.

MibS is a solver for stochastic mixed integer bilevel linear optimization problems. For an introduction to bilevel optimization, see this slide deck. A somewhat outdated but still useful introduction to MibS is here. A paper that contains a complete technical description of the algorithms in MibS is here. A paper that discusses the cuts employed by MibS is here.

More detailed documentation is available here.

MibS 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 MibS development site is https://github.com/coin-or/MibS.

CITE

Code: DOI

Paper: https://doi.org/10.1007/s12532-020-00183-6

CURRENT BUILD STATUS

Windows Builds

Linux and MacOS Builds

DOWNLOAD

Docker image

There is a Docker image that provides MibS, 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 MibS here.

Due to license incompatibilities, pre-compiled binaries may 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 in the discussion formum.

Source

Source code can be obtained either by

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

Below is a quick start guide for building on common platforms. More detailed build instructions are here.

Dependencies

MibS 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

The quick start assumes you are in a bash shell.

Using coinbrew

To download and build MibS 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 MibS@master
./coinbrew build MibS

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/MibS
  • 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

USING

Modelling Systems

MibS has interfaces to the following modelling systems that allow the user to conveniently build the bilevel model in a high-level modelling language and pass the model to MibS through the interface for solution.

  • Pyomo (Python) through the PAO package, see here
  • JuMP (Julia) through the BilevelJuMP package, see here for an example.

Command Line

To solve a deterministic mixed integer bilevel linear optimization problem, you must provide both an MPS file and an auxiliary information file that specifies which variables and constraints are associated with the each level (see a description of the file format here). Then call mibs like this:

<build_or_install_dir>/bin/mibs -Alps_instance file.mps -MibS_auxiliaryInfoFile aux_file.txt 

It is also possible to specify additional settings in a parameter file with, e.g.,

<build_or_install_dir>/bin/mibs -param <build_or_install_dir>/MibS/src/mibs.par 

MibS has many parameters. See the example parameter file mibs.par and the header file MibParams.hpp for explanations. You can also find a detailed description of MibS here. Furthermore, to conduct the experiments illustrated in this report, see the README file in the directory scripts.

MibS is also capable of solving two-stage mixed integer stochastic bilevel linear optimization problems. To solve these problems, there are two ways:

  • Provide an MPS file, a time file and a stoch file in the same way as the SMPS format. The second-stage objective coefficients should be defined at the end of the time file (see here). Then call mibs like this:

    <build_or_install_dir>/bin/mibs -Alps_instance file.mps -MibS_auxiliaryTimFile file.tim -MibS_auxiliaryStoFile file.sto -MibS_stochasticityType stochasticWithoutSAA -MibS_isSMPSFormat 1 -MibS_isA2Random 1 
    

    The parameter MibS_isA2Random should be set to 0 in case the coefficients of the first-stage variables in the second-stage problem are not random variables.

  • Provide an MPS file and an auxiliary information file in the same way as deterministic bilevel problems. The probability distributions of the random variables also should be specified by setting the values of corresponding parameters (MibS currently supports only the discrete uniform distribution). For a sample parameter file, see [src/mibsStochastic.par.in].

Project Links

ACKNOWLEDGEMENT

MibS was developed with support from

  • Office of Naval Research (Grant N000141912330)
  • National Science Foundation (Grants CMMI-1435453, CMMI-0728011, ACI-0102687)
  • Lehigh University
  • Zuse Institute Berlin
  • Research Campus Modal "Mathematical Optimization and Data Analysis Laboratories" funded by the German Federal Ministry of Education and Research (BMBF Grant 05M14ZAM) and by the DFG SFB/Transregio 154