#optimization #heuristic #combinatorial #solver

dogs

Discrete Optimization Global Search framework. Implements various search algorithms that can be found in combinatorial optimization or heuristic search.

4 stable releases

1.3.0 Aug 14, 2021
1.2.0 Jul 5, 2021
1.1.0 Feb 7, 2021
1.0.0 Jan 10, 2021

#1762 in Algorithms

MIT license

155KB
3.5K SLoC

Rust 2.5K SLoC // 0.2% comments Julia 1K SLoC // 0.1% comments

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.

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
  1. cargo flamegraph ARGUMENTS. For instance (SOP): cargo flamegraph insts/R.700.1000.15.sop 30
  2. 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

Dependencies

~1.6–2.5MB
~52K SLoC