GPH

General-purpose heuristics for mixed-integer programming

Introduction

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

$\begin{aligned} \min \quad & c^Tx\\ \textrm{s.t.} \quad & v \leq Ax \leq w \\ & l \leq x \leq u \\ &x_i \in \mathbb{Z}, \forall i \in I \quad \\ \end{aligned}$

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