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

• Greedy algorithm
• Partial Expansion Greedy algorithm
• Beam Search
• Best First Search
• Depth first Search
• Iterative Beam Search
• Limited Discrepancy Search
• Partial Expansion (Iterative) Beam Search

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)

1. Install requirements sudo apt install -y linux-tools-common linux-tools-generic
2. Install flamegraph via cargo cargo install flamegraph
3. 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.
4. Add the following in the Cargo.toml:

[profile.release]
debug = true

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

Heap profiling (Linux)

We recommend using use heaptrack.

1. Call heaptrack PROG
2. Analyze data heaptrack_gui DATA.gz

Cache performance

We recommend using Valgrind

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