Expand description
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 a simple structure that comprises the remaining capacity of the sack (usize) and a depth to denote the number of variables that have already been assigned.
/// In our DP model, we consider a state that simply consists of the remaining
/// capacity in the knapsack. Additionally, we also consider the *depth* (number
/// of assigned variables) as part of the state since it useful when it comes to
/// determine the next variable to branch on.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct KnapsackState {
/// the number of variables that have already been decided upon in the complete
/// problem.
depth: usize,
/// the remaining capacity in the knapsack. That is the maximum load the sack
/// can bear withouth cracking **given what is already in the sack**.
capacity: usize
}
Additionally, we also define a Knapsack structure to store the parameters of the instance being solved. Knapsack is the structure that actually implements the dynamic programming model for the problem at hand.
use ddo::*;
/// This structure represents a particular instance of the knapsack problem.
/// This is the sctructure that will implement the knapsack model.
///
/// The problem definition is quite easy to understand: there is a knapsack having
/// a maximum (weight) capacity, and a set of items to chose from. Each of these
/// items having a weight and a profit, the goal is to select the best subset of
/// the items to place them in the sack so as to maximize the profit.
struct Knapsack {
/// The maximum capacity of the sack (when empty)
capacity: usize,
/// the profit of each item
profit: Vec<usize>,
/// the weight of each item.
weight: Vec<usize>,
}
/// For each variable in the decision problem, there are two possible choices:
/// either we take the item in the sack, or we decide to leave it out. This
/// constant is used to indicate that the item is to be taken in the sack.
const TAKE_IT: isize = 1;
/// For each variable in the decision problem, there are two possible choices:
/// either we take the item in the sack, or we decide to leave it out. This
/// constant is used to indicate that the item is to be left out of the sack.
const LEAVE_IT_OUT: isize = 0;
/// This is how you implement the labeled transition system (LTS) semantics of
/// a simple dynamic program solving the knapsack problem. The definition of
/// each of the methods should be pretty clear and easy to grasp. Should you
/// want more details on the role of each of these methods, then you are
/// encouraged to go checking the documentation of the `Problem` trait.
impl Problem for Knapsack {
// This associated type indicates that the type which is used to represent
// a state of the knapsack problem is `KnapsackState`. Hence the statespace
// of the problem consists of the set of KnapsackStates that can be represented
type State = KnapsackState;
// This method is used to tell the number of variables in the knapsack instance
// you are willing to solve. In the literature, it is often referred to as 'N'.
fn nb_variables(&self) -> usize {
self.profit.len()
}
// This method returns the intial state of your DP model. In our case, that
// is nothing but an empty sack.
fn initial_state(&self) -> Self::State {
KnapsackState{ depth: 0, capacity: self.capacity }
}
// This method returns the initial value of the DP. This value accounts for the
// constant factors that have an impact on the final objective. In the case of
// the knapsack, when the sack is empty, the objective value is 0. Hence the
// initial value is zero as well.
fn initial_value(&self) -> isize {
0
}
// This method implements a transition in the DP model. It yields a new sate
// based on a decision (affectation of a value to a variable) which is made from
// a given state.
fn transition(&self, state: &Self::State, dec: Decision) -> Self::State {
let mut ret = state.clone();
ret.depth += 1;
if dec.value == TAKE_IT {
ret.capacity -= self.weight[dec.variable.id()]
}
ret
}
// This method is analogous to the transition function. But instead to returning
// the next state when a decision is made, it returns the "cost", that is the
// impact of making that decision on the objective function.
fn transition_cost(&self, _state: &Self::State, dec: Decision) -> isize {
self.profit[dec.variable.id()] as isize * dec.value
}
// This method is used to determine the order in which the variables will be branched
// on when solving the knapsack. In this case, we implement a basic scheme telling that
// the variables are selected in order (0, 1, 2, ... , N).
fn next_variable(&self, next_layer: &mut dyn Iterator<Item = &Self::State>) -> Option<Variable> {
let n = self.nb_variables();
next_layer.filter(|s| s.depth < n).next().map(|s| Variable(s.depth))
}
// If you followed this example until now, you might be surprised not to have seen
// any mention of the domain of the variables. Search no more. This function is
// designed to perform a call to the callback `f` for each possible decision regarding
// a given state and variable. In other words, it calls the callback `f` for each value
// in the domain of `variable` given that the current state is `state`.
fn for_each_in_domain(&self, variable: Variable, state: &Self::State, f: &mut dyn DecisionCallback)
{
if state.capacity >= self.weight[variable.id()] {
f.apply(Decision { variable, value: TAKE_IT });
f.apply(Decision { variable, value: LEAVE_IT_OUT });
} else {
f.apply(Decision { variable, value: LEAVE_IT_OUT });
}
}
}
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 fast_upper_bound()
method of the Relaxation
trait.
struct KPRelax<'a>{pb: &'a Knapsack}
impl Relaxation for KPRelax<'_> {
// The type of states which this relaxation operates on is KnapsackState.
// Just like the Problem definition which told us that its state spaces
// consisted of all the possible KnapsackStates.
type State = KnapsackState;
// This method creates and returns a new KnapsackState that will stand for
// all the states returned by the 'states' iterator. The newly created state
// will replace all these nodes in a relaxed DD that has too many nodes.
fn merge(&self, states: &mut dyn Iterator<Item = &Self::State>) -> Self::State {
states.max_by_key(|node| node.capacity).copied().unwrap()
}
// This method is used to offset a portion of the cost that would be lost in
// the merge operations towards the edges entering the merged node. It is important
// to know this method exists, even though most of the time, you will simply return
// the cost of the relaxed edge (that is you wont offset any cost on the entering
// edges as that wont be required by your relaxation. But is some -- infrequent -- cases
// your model will require that you do something smart here).
fn relax(&self, _source: &Self::State, _dest: &Self::State, _merged: &Self::State, _decision: Decision, cost: isize) -> isize {
cost
}
}
State Ranking
There is a third piece of information which you will need to pass on to the
solver before being able to use ddo. This third bit of information is called
a StateRanking
and it is an heuristic used to discriminate the most promising
states from the least promising one. That way, the solver isn’t blind when it
needs to decide which nodes to delete or merge as it compiles restricted and
relaxed DDs for you.
For instance, in the case of the knapsack, when all else is equal, you will obviously prefer that the solver leaves the states with a higher remaining capacity untouched and merge or delete the others.
use ddo::*;
struct KPRanking;
impl StateRanking for KPRanking {
// This associated type has the same meaning as in the problem and
// relaxation definitions.
type State = KnapsackState;
// It compares two states and returns an ordering. Greater means that
// state a is prefered over state b. Less means that state b should be
// preferred over state a. And Equals means you dont care.
fn compare(&self, a: &Self::State, b: &Self::State) -> std::cmp::Ordering {
a.capacity.cmp(&b.capacity)
}
}
Instanciate your Solver
As soon as you have defined a problem and relaxation and state ranking, 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. Create a relaxation of the problem
let relaxation = KPRelax{pb: &problem};
// 3. Create a ranking to discriminate the promising and uninteresting states
let heuristic = KPRanking;
// 4. Define the policy you will want to use regarding the maximum width of the DD
let width = FixedWidth(100); // here we mean max 100 nodes per layer
// 5. Decide of a cutoff heuristic (if you dont want to let the solver run for ever)
let cutoff = NoCutoff; // might as well be a TimeBudget (or something else)
// 5. Create the solver frontier
let mut frontier = SimpleFrontier::new(MaxUB::new(&heuristic));
// 6. Instanciate your solver
let mut solver = DefaultSolver::new(
&problem,
&relaxation,
&heuristic,
&width,
&cutoff,
&mut frontier);
// 7. Maximize your objective function
// the outcome provides the value of the best solution that was found for
// the problem (if one was found) along with a flag indicating whether or
// not the solution was proven optimal. Hence an unsatisfiable problem
// would have `outcome.best_value == None` and `outcome.is_exact` true.
// The `is_exact` flag will only be false if you explicitly decide to stop
// searching with an arbitrary cutoff.
let outcome = solver.maximize();
// The best solution (if one exist) is retrieved with
let solution = solver.best_solution();
// 8. Do whatever you like with the optimal solution.
assert_eq!(Some(220), outcome.best_value);
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
ddo::Problem
and ddo::Relaxation
which defines the core abstractions
you will need to implement. After that, it is also interesting to have a
look at the various heuristics availble and the configuration options you
can use when cutomizing the behavior of your solver and mdd. 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}},
}
Structs
Compare
object as is sometimes required (e.g. to configure the order in a binary heap)value
to the specified variable
. Any given Decision
should be
understood as ```[[ variable = value ]]````problem.nb_vars()