TreeSearchSolver

A solver based on heuristic tree search.

image source

Description

The goal of this repository is to provide a simple framework to quickly implement algorithms based on heuristic tree search.

Solving a problem only requires a couple hundred lines of code (see examples).

Algorithms:

• Greedy greedy
• Depth first search depth-first-search
• Best first search best-first-search
• Iterative beam search iterative-beam-search
• Iterative beam search 2 iterative-beam-search-2
• Iterative memory bounded best first search iterative-memory-bounded-best-first-search
• Anytime column search anytime-column-search

Examples

Data can be downloaded from fontanf/orproblems

Sequential ordering problem

• The branching scheme is taken from "Tree search for the sequential ordering problem" (Libralesso et al., 2020) PDF.
• It is a forward branching scheme.
• The guide of a node is its bound.
• This implementation returns state-of-the-art results on the instances of the scientific literature with a dense precedence graph.

Permutation flow shop scheduling problem, makespan and Permutation flow shop scheduling problem, total completion time

• The branching schemes are taken from "Iterative beam search algorithms for the permutation flowshop" (Libralesso et al., 2022) DOI.
• For the makespan variant, it is a bidirectional branching scheme.
• For the total completion time variant, it is a forward branching scheme.
• These implementations return state-of-the-art results on the instances of the scientific literature.

1D packing, 2D rectangle packing, 2D rectangle guillotine packing, 2D irregular packing and 3D box-stacks packing problems from fontanf/packingsolver

• These are all forward branching schemes.
• These implementations have been used in the winning algorithm of the Challenge ROADEF/EURO 2022 : Trucks Loading Problem.

Travelling thief problem and thief orienteering problem from fontanf/travellingthiefsolver

• Here, the library is used to implement an exact dynamic programming algorithm implemented as a tree search

Knapsack problem with conflicts

Simple assembly line balancing problem of type 1 (SALBP-1)

Usage, running examples from command line

Compile:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --config Release --parallel
cmake --install build --config Release --prefix install

Download data:

python3 scripts/download_data.py

Then, examples can be executed as follows:

./install/bin/treesearchsolver_sequential_ordering --verbosity-level 1 --input "./data/sequential_ordering/soplib/R.700.1000.60.sop" --format soplib --algorithm iterative-beam-search --certificate solution.txt

======================================
           TreeSearchSolver           
======================================

Instance
--------
Number of locations:  700

Algorithm
---------
Iterative beam search

Parameters
----------
Time limit:                         inf
Messages
    Verbosity level:                1
    Standard output:                1
    File path:                      
    # streams:                      0
Logger
    Has logger:                     0
    Standard error:                 0
    File path:                      
Maximum size of the solution pool:  1
Maximum number of nodes:            -1
Growth factor:                      2
Minimum size of the queue:          1
Maximum size of the queue:          100000000

       Time                           Value                         Comment
       ----                           -----                         -------
      0.000                                                             q 1
      0.017                          277615                             q 2
      0.035                          253795                             q 4
      0.074                          246649                             q 8
      0.138                          245634                            q 16
      0.219                          245589                            q 32

Final statistics
----------------
Value:                      245589
Time:                       0.302434
Number of nodes:            17144
Maximum size of the queue:  64

Solution
--------
Length:  245589

Checker
-------
Number of Vertices:               700 / 700
Number of duplicates:             0
Number of precedence violations:  0
Feasible:                         1
Total distance:                   245589

Usage, C++ library

See examples.