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
- Beam Search
- Best First Search
- DFS
- Iterative Beam Search
- LDS
- PartialChildrenExpansion (Iterative) Beam Search
combinators
- Bounding combinator
- LDS combinator
- PrefixEquivalence dominance combinator
- Pruning combinator
- Statistics combinator
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
profiling rust applications (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 - add the following in the
Cargo.toml:
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