Abstract | News | Algorithm | Installation | Example | Compilation | Standalone Solver | Documents | Benchmark | Test | License | References

Abstract

PRINTEMPS is a C++ metaheuristics modeler/solver library for general integer optimization problems. PRINTEMPS emphasizes on the following aspects:

News

Date Update
Jan. 15, 2023 New benchmark results were added.
Jan. 15, 2023 PRINTEMPS v2.1.2 was released.

Algorithm

PRINTEMPS can compute approximate solutions for linear and nonlinear integer optimization problems. It employs Tabu Search [1], a metaheuristics technique, to solve problems. In solving, it replaces constraints with penalty functions which return violations to the corresponding constraints, and the penalty functions multiplied by positive penalty coefficients are added to the objective function. The penalty coefficients are updated iteratively and automatically in a method similar (not exact same) to the one proposed in paper [2]. The figure below shows the flow-chart of the algorithm of PRINTEMPS.

The flow-chart of the optimization algorithm of PRINTEMPS.

Installation

Installation of PRINTEMPS is just completed by cloning the repository (or downloading the latest archive) and then copying the printemps/ directory in the repository to an appropriate location.

Example

Let us consider a simple linear integer optimization problem [3]:

   (P1):  minimize       x_1 + 10 x_2
             x
         subject to   66 x_1 + 14 x_2 >= 1430,
                     -82 x_1 + 28 x_2 >= 1306,
                     x_1 and x_2 are integer.

The following code shows an implementation code to solve the problem (P) using PRINTEMPS.

#include <printemps.h>
int main(void) {
    // (1) Modeling
    printemps::model::IPModel model;

    auto& x = model.create_variables("x", 2);
    auto& g = model.create_constraints("g", 2);

    g(0) =  66 * x(0) + 14 * x(1) >= 1430;
    g(1) = -82 * x(0) + 28 * x(1) >= 1306;
    model.minimize(x(0) + 10 * x(1));

    // (2) Running Solver
    auto result = printemps::solver::solve(&model);

    // (3) Accessing the Result
    std::cout << "objective = " << result.solution.objective() << std::endl;
    std::cout << "x(0) = "      << result.solution.variables("x").values(0) << std::endl;
    std::cout << "x(1) = "      << result.solution.variables("x").values(1) << std::endl;

    return 0;
}

By compiling the code above and then running the generated executable, users will obtain the following result:

objective = 707
x(0) = 7
x(1) = 70

Following additional examples are provided in example/ directory.

Compilation

A C++ program integrating PRINTEMPS can be compiled by C++17 standards compatible compilers with specifying include search path where it is installed. For instance, the example code example/knapsack.cpp can be built by the following command using g++:

$g++ -std=c++17 -O3 -I path/to/printemps [-fopenmp] sample/knapsack.cpp -o knapsack.exe

The option -fopenmp is required to activate parallel computation. See Solver Option Guide for details.

Following combinations of operating systems and compilers are confirmed compilation possible:

Operating System Compiler (version)
macOS 11 gcc (9.5.0, 10.4.0, 11.3.0)
macOS 12 gcc (11.3.0)
Ubuntu 18.04 gcc (9.2.1)
clang (9.0.0)
Ubuntu 20.04 gcc (9.3.0, 10.3.0)
clang (10.0.0, 11.0.0, 12.0.0)
Ubuntu 22.04 gcc (9.4.0, 10.3.0, 11.2.0)
clang (12.0.1, 13.0.1, 14.0.0)

Standalone Solver

A standalone executable solver based on PRINTEMPS is also provided. It approximately solves a pure integer programming problem described as MPS (Mathematical Programming System) format file. The solver can be built by the following command:

$make -f makefile/Makefile.application [CC=gcc CXX=g++]

where the options CC and CXX respectively designate the paths of C and C++ compilers, which should be specified according to the user's development environment. The built solver will be generated at build/application/Release/mps_solver.exe.

The solver can be run by the following command:

$./mps_solver.exe mps_file [-p option_file] [--accept-continuous]

where the argument mps_file is the path of the MPS file. The argument -p option_file is optional and it specifies solver options and parameters via a JSON file. If the optional flag --accept-continuous is activated, the solver accepts an MPS file which includes continuous variables. Then the continuous variables will be regarded as integer variables. An example of solver option JSON file is provided as application/dat/option.json.

Documents

Benchmark

Optimization performance of PRINTEMPS has been evaluated using pure integer instances of MIPLIB 2017. Please refer Benchmark Results for detail.

Test

The test suites for PRINTEMPS are powered by googletest. The command

$make -f makefile/Makefile.external [CC=gcc CXX=g++]

installs googletest into external/ directory. The options CC and CXX respectively designate the paths of C and C++ compilers, which should be specified according to the user's development environment. After the installation of googletest, execute the command

$make -f makefile/Makefile.test

to build and run the test suites.

License

PRINTEMPS is licensed under MIT license.

References