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

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

Decorators

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

Roadmap: What's next?

• 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.
• Each component (Search algorithm, decorator, ... can produce a JSON object) This JSON object can then be written in a file or combined with others by higher components.
• Use Iterator trait for partial expansion (more idiomatic)
• Performance improvement for the PruningDecorator
• Add Decorator trait and base implementation for unwrap()
• improve LazyComputable usage (trait?)

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:

[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)

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