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

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

Decorators

• [X] Bounding decorator: measures dual bounds
• [X] LDS decorator: limits the exploration of the tree to the nodes with few discrepancies
• [X] G-cost dominance decorator: implements g-cost dominance
• [X] Pruning decorator: prunes nodes that are dominated by the best-known solution
• [X] Statistics decorator: reports various statistics of the search

Roadmap: What's next?

• [ ] Replace display statistics by a function that displays statistics from export stats (JSON format)
• [ ] Use Iterator trait for partial expansion (more idiomatic)
• [ ] Performance improvement for the PruningDecorator
• [ ] Add Decorator trait and base implementation for unwrap()

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 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: rust [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.

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]

Iterating over files (Linux)

bash for f in `ls DIRNAME/*`; do COMMAND "${f}"; done

Benchmarking

This project uses cargo-criterion.

While cargo-criterion is installed, you can just call it by: cargo criterion