# [−][src]Crate ddo

# DDO

DDO is a truly generic framework to develop MDD-based combinatorial
optimization solvers in Rust. Its goal is to let you describe your
optimization problem as a dynamic program (see `Problem`

) along with a
`Relaxation`

. When the dynamic program of the problem is considered as a
transition system, the relaxation serves the purpose of merging different
nodes of the transition system into an other node standing for them all.
In that setup, the sole condition to ensure the correctness of the
optimization algorithm is that the replacement node must be an over
approximation of all what is feasible from the merged nodes.

## Side benefit

As a side benefit from using `ddo`

, you will be able to exploit all of your
hardware to solve your optimization in parallel.

## Quick Example

The following presents a minimalistic use of ddo. It implements a solver for the knapsack problem which uses all the available computing resources to complete its task. This example is shown for illustration purpose because it is pretty simple and chances are high anybody is already comfortable with the problem definition.

#### Note:

The `example`

folder of our repository contains many other examples in
addition to this one. So please consider checking them out for further
details.

#### Describe the problem as dynamic program

The first thing to do in this example is to describe the binary knapsack
problem in terms of a dynamic program. Here, the state of a node, is nothing
more than an unsigned integer (usize). That unsigned integer represents the
remaining capacity of our sack. To do so, you define your own structure and
make sure it implements the `Problem<usize>`

trait.

#[derive(Debug, Clone)] struct Knapsack { capacity: usize, profit : Vec<usize>, weight : Vec<usize> } impl Problem<usize> for Knapsack { fn nb_vars(&self) -> usize { self.profit.len() } fn domain_of<'a>(&self, state: &'a usize, var: Variable) ->Domain<'a> { if *state >= self.weight[var.id()] { vec![0, 1].into() } else { vec![0].into() } } fn initial_state(&self) -> usize { self.capacity } fn initial_value(&self) -> isize { 0 } fn transition(&self, state: &usize, _vars: &VarSet, dec: Decision) -> usize { state - (self.weight[dec.variable.id()] * dec.value as usize) } fn transition_cost(&self, _state: &usize, _vars: &VarSet, dec: Decision) -> isize { self.profit[dec.variable.id()] as isize * dec.value } }

#### Define a Relaxation

The relaxation we will define is probably the simplest you can think of. When one needs to define a new state to replace those exceeding the maximum width of the MDD, we will simply keep the state with the maximum capacity as it enables at least all the possibly behaviors feasible with lesser capacities.

Optionally, we could also implement a rough upper bound estimator for our
problem in the relaxation. However, we wont do it in this minimalistic
example since the framework provides you with a default implementation.
If you were to override the default implementation you would need to
implement the `estimate()`

method of the `Relaxation`

trait.

#[derive(Debug, Clone)] struct KPRelax; impl Relaxation<usize> for KPRelax { /// To merge a given selection of states (capacities) we will keep the /// maximum capacity. This is an obvious relaxation as it allows us to /// put more items in the sack. fn merge_states(&self, states: &mut dyn Iterator<Item=&usize>) -> usize { // the selection is guaranteed to have at least one state so using // unwrap after max to get rid of the wrapping 'Option' is perfectly safe. *states.max().unwrap() } /// When relaxing (merging) the states, we did not run into the risk of /// possibly decreasing the maximum objective value reachable from the /// components of the merged node. Hence, we dont need to do anything /// when relaxing the edge. Still, if we wanted to, we could chose to /// return an higher value. fn relax_edge(&self, src: &usize, dst: &usize, relaxed: &usize, d: Decision, cost: isize) -> isize { cost } }

# Instanciate your Solver

As soon as you have defined a problem and relaxation, you are good to go. The only thing you still need to do is to write your main method and spin your solver to solve actual problems. Here is how you would do it.

// 1. Create an instance of our knapsack problem let problem = Knapsack { capacity: 50, profit : vec![60, 100, 120], weight : vec![10, 20, 30] }; // 2. Build an MDD for the given problem and relaxation let mdd = mdd_builder(&problem, KPRelax).into_deep(); // 3. Create a parllel solver on the basis of this MDD (this is how // you can specify the MDD implementation you wish to use to develop // the relaxed and restricted MDDs). let mut solver = ParallelSolver::new(mdd); // 4. Maximize your objective function let (optimal, solution) = solver.maximize(); // 5. Do whatever you like with the optimal solution. assert_eq!(220, optimal); println!("Solution"); for decision in solution.unwrap().iter() { if decision.value == 1 { println!("{}", decision.variable.id()); } }

## Going further / Getting a grasp on the codebase

The easiest way to get your way around with DDO is probably to start
exploring the available APIs and then to move to the exploration of the
examples. (Or the other way around, that's really up to you !).
For the exploration of the APIs, you are encouraged to start with the types
from the modules under `ddo::abstraction`

. In particular, you will want to
have a look at `ddo::abstraction::dp`

which defines the core abstractions
you will need to implement. After that, it is also interesting to have a
look at the `ddo::abstraction::heuristic`

, `ddo::common`

and the
`ddo::implementation::deep::config`

modules. That should get you covered
and you should be able to get a deep understanding of how to use our library.

## Citing DDO

If you use DDO, or find it useful for your purpose (research, teaching, business, ...) please cite:

```
@misc{gillard:20:ddo,
author = {Xavier Gillard, Pierre Schaus, Vianney Coppé},
title = {Ddo, a generic and efficient framework for MDD-based optimization},
howpublished = {IJCAI-20},
year = {2020},
note = {Available from \url{https://github.com/xgillard/ddo}},
}
```

## Modules

abstraction | This module (and its submodule) provide the abstractions for the basic
building blocks of an MDD solvers. A client willing to use our library to
implement a solver for his/her particular problem should look into the |

common | This module defines the most basic data types that are used throughout all the code of our library (both at the abstraction and implementation levels). These are also the types your client library is likely to work with. |

implementation | The submodules from this module provide an implementation for the core
abstractions of the library (those are described in |