A solver based on heuristic tree search.

image source

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

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

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

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 

See examples.