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

Abstract

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

News

Date Update
Sep 29, 2024 PRINTEMPS v2.5.0 was released.
Feb. 8, 2024 Tabu Search-Based Heuristic Solver for General Integer Linear Programming Problems, a paper on PRINTEMPS, has been published in IEEE Access.

Algorithm

PRINTEMPS can compute approximate solutions for integer linear programming problems by Weighted Tabu Search [1]. For more information on the algorithm, please refer to the literature [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 12 gcc (11.4.0, 12.4.0, 14.1.0_2)
macOS 13 gcc (11.4.0, 12.4.0, 14.1.0_2)
macOS 12 gcc (11.4.0, 12.4.0, 13.3.0, 14.1.0_2)
Ubuntu 22.04 gcc (10.5.0, 11.4.0, 12.3.0)
clang (13.0.1, 14.0.0, 15.0.7)
Ubuntu 24.04 gcc (12.3.0, 13.2.0, 14.0.1)
clang (16.0.6, 17.0.6, 18.1.3)

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

Citation

I would appreciate it if you could cite the following article when referring to PRINTEMPS in your work:

@ARTICLE{10418217,
  author={Koguma, Yuji},
  journal={IEEE Access}, 
  title={Tabu Search-Based Heuristic Solver for General Integer Linear Programming Problems}, 
  year={2024},
  volume={12},
  number={},
  pages={19059-19076},
  doi={10.1109/ACCESS.2024.3361323}}