DOGS (Discrete Optimization Global Search) framework

Implements various search algorithms within a unified paradigm (so far, mostly anytime tree search algorithms). See this thesis for more information about anytime tree search algorithms.

Implemented components

Tree search algorithms

Combinators

Bounding combinator: measures dual bounds
LDS combinator: limits the exploration of the tree to the nodes with few discrepancies
G-cost dominance combinator: implements g-cost dominance
Pruning combinator: prunes nodes that are dominated by the best-known solution
Statistics combinator: reports various statistics of the search
Tabu combinator: forbids decisions taken before in the search

Roadmap: What's next?

core:

refactor neighbors with an iterator

combinators:

combinator that stores node information (bound, guide, depth)
StatsCombinator, mark opened nodes (better accuracy)

local search:

Reactive tabu management

tree search:

Possible bug in "is_optimal" if the time limit is exceeded before the search makes some heuristic fathoming. In this case, the algorithm will report "optimal" while it is not.

examples

Some examples are available for various problems. For some of them, the DOGS implementation is state-of-the-art.

The sequential ordering problem (SOP) git repository, reference paper
The permutation flowshop (makespan and flowtime minimization) git repository, reference paper

Some general helpful tips

Install rust

See rust getting started page.

Flamegraph profiling (Linux)

Install requirements sudo apt install -y linux-tools-common linux-tools-generic
Install flamegraph via cargo cargo install flamegraph
Disable the sudo requirement for perf: echo -1 | sudo tee /proc/sys/kernel/perf_event_paranoid. Possibly, sudo sh -c 'echo kernel.perf_event_paranoid=1 > /etc/sysctl.d/local.conf' may allow you to do not use the previous command in every terminal.
Add the following in the Cargo.toml:

[profile.release]
debug = true

cargo flamegraph ARGUMENTS. For instance (SOP): cargo flamegraph insts/R.700.1000.15.sop 30
Visualize the flamegraph (here by using Firefox): firefox flamegraph.svg.
Possibly, use hotspot for the visualization

Heap profiling (Linux)

We recommend using use heaptrack.

Call heaptrack PROG
Analyze data heaptrack_gui DATA.gz

Cache performance

We recommend using Valgrind

valgrind --tool=callgrind --dump-instr=yes --collect-jumps=yes --simulate-cache=yes [PROGRAM] [ARGS]

librallu/dogs