Skip to content

Latest commit

 

History

History
93 lines (65 loc) · 3.72 KB

README.md

File metadata and controls

93 lines (65 loc) · 3.72 KB
Raw

Handling Sub-symmetry in Integer Programming using Activation Handlers

This repository contains the experiments setup for testing the activation handler approach for sub-symmetry handling in the Multiple Knapsack Problem, Min-up/min-down Unit Commitment Problem and the Max-k Colorable Subgraph Problem.

Installation

The following may be used as a reference to completely install a working environment. It assumes GCC, CMake and Python version (at least) 3.10 are already installed. It has been tested and known to work with GCC version 9.2.0 and CMake version 3.18.4. Note: change /path/to to a path of your liking.

# Install 3rd party dependencies

# Boost
wget https://boostorg.jfrog.io/artifactory/main/release/1.74.0/source/boost_1_74_0.tar.gz
tar -xf boost_1_74_0.tar.gz
rm boost_1_74_0.tar.gz

cd boost_1_74_0 || exit

./bootstrap.sh --prefix=../boost
./b2 install --prefix=../boost --with=all -j5

cd - || exit

# Bliss (for symmetry detection)
git clone --depth 1 --branch v0.73.3 [email protected]:ds4dm/Bliss.git

cd Bliss || exit
cmake .
cmake --build .

cd - || exit

# Soplex
git clone --depth 1 --branch release-600 [email protected]:scipopt/soplex.git

cd soplex || exit

cmake -DBOOST_INCLUDEDIR=../boost/include -DBOOST_LIBRARYDIR=../boost/lib -DBoost_NO_SYSTEM_PATHS=ON -DBOOST_ROOT=../boost -DCMAKE_BUILD_TYPE=Release -DCMAKE_INSTALL_PREFIX=./install-release -DPAPILO=off -B ./cmake-build-release
cmake --build ./cmake-build-release --clean-first --target install -- -j 5

cd - || exit

# SCIP
cd scip || exit

cmake -DCMAKE_BUILD_TYPE=Release -DPAPILO=off -DSOPLEX_DIR=../soplex/cmake-build-release -DZIMPL=off -DIPOPT=off -DBLISS_DIR=../Bliss -DCMAKE_INSTALL_PREFIX=./install-release -B ./cmake-build-release
cmake --build ./cmake-build-release --clean-first --target install -- -j 5

cd - || exit

# Create venv
python3.10 -m venv venv
source ./venv/bin/activate

pip install -r experiments/requirements.txt

# Install pyscipopt
export SCIPOPTDIR="/path/to/scip/install-release"
pushd pyscipopt || exit
ln -s src/pyscipopt pyscipopt
pip install -e .
popd

How to navigate this repository

The experiments directory contains Python code that sets up the MKP, MUCP and MKCS models in SCIP, and can be used to evaluate the performance of the different models.

The scip directory contains the source code of SCIP, modified with the implementation of the activation handlers. Files of interest fit the pattern scip/src/scip/*activation*. In particular, the files activation_makespan.h/c, activation_suborbitope.h/c, and activation_colorcomp.h/c implement the specific activation handlers used for the MKP, MUCP and MKCS sub-symmetries, respectively.

The pyscipopt directory contains the Python interface for SCIP, modified from the original repository to support the activation handler API endpoints.

Instances

Instances for the MKP are included in the experiments/tests/data directory. The Color02 instances for the MKCS problem can be found here. The MUCP instances are available here.

Running the experiments

Tests can be run in the experiments/tests directory, by running

export SCIPOPTDIR="/path/to/scip/install-release"
export PYTHONPATH="../src"
python runner_{mkp,mucp,mkcs_orig}.py <id>

where <id> is substituted by the index of the instance to solve (see experiments/tests/index/{mkp,mucp,mkcs}). Make sure the Python virtual environment is 'activated'.

Licensing

The SCIP version used is licenced under the ZIB Academic License. All code in the scip directory is published under this license.

PySCIPOpt and the experiments source code is licensed under the MIT license.