anassmeskini/gph

Heuristics for mixed-integer programming

GPH

General-purpose heuristics for mixed-integer programming

Introduction

GPH implements approximation algorithms for quickly finding feasible solutions to problems of the form:

The algorithms implemented are the heuristics usually embedded in MIP solvers. A description of these algorithms can be found here. The heuristics do not require the problem to have any particular structure.

The code is written in C++17 with a simple object-oriented design and provides data structures that allow for an efficient implementation of the algorithms. Additionally, the code is parallelized using the Thread Building Blocks library.

Design

• The problem data is stored by the class MIP: the constraint matrix is stored in row-major and column-major order as two sparse matrices and the rest of the problem is stored as dense vectors.
• A feasibility heuristic is a class derived from FeasibilityHeuristic and implements the method run. Similarly, an improvement heuristic is a class derived from ImprovementHeuristic that implements the method improve.
• The class Search takes a list of heuristics as input and runs them in parallel. If the feasibility heuristics find a solution, it is passed to the improvement heuristics.

Compilation

GPH depends on an external LP solver and the Thread Building Blocks library and uses CMake for compilation. Three LP solvers are supported: Cplex, SoPlex and GLPK. zlib is an optional dependency to read input in gzip format.

Example: compiling with SoPlex

git clone https://github.com/anassmeskini/GPH
mkdir build
cd build
cmake .. -DSOLVER=soplex -DTBB_ROOT=/path/to/tbb
make

If the LP solver is not installed system-wide, the path needs to be provided to cmake (by adding -DSOPLEX_DIR=/path/to/soplex in the example).

Usage

The executable reads plain text and gzip files in MPS format.

SYNOPSIS
        ./gph <input file> [-l <tlimit>] [-t <nthreads>] [-w] [-s <start_sol>] [-c <config>]

OPTIONS
        <tlimit>    time limit in seconds
        <nthreads>  number of threads to use
        -w          write solution to disk
        <start_sol> path to solution to improve
        <config>    configuration file