Crate ddo

source ·
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 without 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 structure 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 state-space
    // 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 initial 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, _next: &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, depth: usize, _: &mut dyn Iterator<Item = &Self::State>) -> Option<Variable> {
        let n = self.nb_variables();
        if depth < n {
            Some(Variable(depth))
        } else {
            None
        }
    }
    // 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 preferred over state b. Less means that state b should be 
    // preferred over state a. And Equals means you don't care.
    fn compare(&self, a: &Self::State, b: &Self::State) -> std::cmp::Ordering {
        a.capacity.cmp(&b.capacity)
    }
}

§Instantiate 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. Add a dominance relation checker
let dominance = SimpleDominanceChecker::new(KPDominance, problem.nb_variables());
 
// 6. Decide of a cutoff heuristic (if you don't want to let the solver run for ever)
let cutoff = NoCutoff; // might as well be a TimeBudget (or something else)
 
// 7. Create the solver fringe
let mut fringe = SimpleFringe::new(MaxUB::new(&heuristic));
  
// 8. Instantiate your solver
let mut solver = DefaultSolver::new(
      &problem, 
      &relaxation, 
      &heuristic, 
      &width, 
      &dominance,
      &cutoff, 
      &mut fringe);
 
// 9. 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();

// 10. 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 available and the configuration options you can use when customizing 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§

  • CompareSubProblem
    This is a thin wrapper to convert a SubProblemRanking into a Compare object as is sometimes required (e.g. to configure the order in a binary heap)
  • CompilationInput
    The set of parameters used to tweak the compilation of a MDD
  • Completion
    The outcome of an mdd development
  • Decision
    This denotes a decision that was made during the search. It affects a given value to the specified variable. Any given Decision should be understood as ```[[ variable = value ]]````
  • DivBy
    This strategy acts as a decorator for an other max width heuristic. It divides the maximum width of the strategy it delegates to by a constant (configured) factor. It is typically used in conjunction with NbUnassigned to provide a maximum width that allows a certain number of nodes. Using a constant factor of 1 means that this decorator will have absolutely no impact.
  • DominanceCheckResult
    Helper struct that encapsulates the result of a dominance check
  • DominanceCmpResult
    Helper struct that encapsulates the result of a dominance comparison
  • EmptyCache
    Dummy implementation of Cache with no information stored at all.
  • EmptyDominanceChecker
    Implementation of a dominance checker that never detects any dominance relation
  • FixedWidth
    This strategy specifies a fixed maximum width for all the layers of an approximate MDD. This is a static heuristic as the width will remain fixed regardless of the approximate MDD to generate.
  • MaxUB
    The MaxUB (maximum upper bound) strategy is one that always selects the node having the highest upper bound in the fringe. In case of equalities, the ties are broken using the length of the longest path and eventually a state ranking.
  • Mdd
    The decision diagram in itself. This structure essentially keeps track of the nodes composing the diagram as well as the edges connecting these nodes in two vectors (enabling preallocation and good cache locality). In addition to that, it also keeps track of the path (root_pa) from the problem root to the root of this decision diagram (explores a sub problem). The prev_l comprises information about the nodes that are currently being expanded, next_l stores the information about the nodes from the next layer and cut-set stores an exact cut-set of the DD. Depending on the type of DD compiled, different cutset types will be used:
  • NbUnassignedWidth
    This strategy specifies a variable maximum width for the layers of an approximate MDD. When using this heuristic, each layer of an approximate MDD is allowed to have as many nodes as there are free variables to decide upon.
  • NoCutoff
    This is the default cutoff heuristic. It imposes that the search goes proves optimality before to stop.
  • NoDupFringe
    This is an updatable binary heap backed by a vector which ensures that items remain ordered in the priority queue while guaranteeing that a given state will only ever be present ONCE in the priority queue (the node with the longest path to state is the only kept copy).
  • NodeFlags
    This structure stores a compact set of flags relating to a given node. So far, it maintains the following:
  • ParallelSolver
    This is the structure implementing a multi-threaded MDD solver.
  • Pooled
    The decision diagram in itself. This structure essentially keeps track of the nodes composing the diagram as well as the edges connecting these nodes in two vectors (enabling preallocation and good cache locality). In addition to that, it also keeps track of the path (root_pa) from the problem root to the root of this decision diagram (explores a sub problem). The prev_l comprises information about the nodes that are currently being expanded, next_l stores the information about the nodes from the next layer and cut-set stores an exact cut-set of the DD. Depending on the type of DD compiled, different cut-set types will be used:
  • SequentialSolver
    This is the structure implementing an single-threaded MDD solver.
  • SimpleCache
    Simple implementation of Cache using one hashmap for each layer, each protected with a read-write lock.
  • SimpleDominanceChecker
  • SimpleFringe
    The simplest fringe implementation you can think of: is basically consists of a binary heap that pushes and pops fringe nodes
  • SubProblem
    A subproblem is a residual problem that must be solved in order to complete the resolution of the original problem which had been defined.
  • Threshold
    A threshold is a value that can be stored during the execution of a branch and bound algorithm. It is associated with a single exact state and is used to determine whether a new node with the same state is worth exploring.
  • TimeBudget
    This cutoff allows one to specify a maximum time budget to solve the problem. Once the time budget is elapsed, the optimization stops and the best solution that has been found (so far) is returned.
  • Times
    This strategy acts as a decorator for an other max width heuristic. It multiplies the maximum width of the strategy it delegates to by a constant (configured) factor. It is typically used in conjunction with NbUnassigned to provide a maximum width that allows a certain number of nodes. Using a constant factor of 1 means that this decorator will have absolutely no impact.
  • Variable
    This type denotes a variable from the optimization problem at hand. In this case, each variable is assumed to be identified with an integer ranging from 0 until problem.nb_vars()
  • VizConfig
    This is how you configure the output visualisation e.g. if you want to see the RUB, LocB and the nodes that have been merged
  • VizConfigBuilder
    Builder for VizConfig.

Enums§

Constants§

  • FRONTIER
    enqueue all exact nodes that have at least a relaxed child node
  • LAST_EXACT_LAYER
    enqueue the last layer with only exact nodes

Traits§

  • Cache
    This trait abstracts away the implementation details of the solver cache. That is, a Cache represents the data structure that stores thresholds that condition the re-exploration of nodes with a state already reached previously.
  • Cutoff
    This trait encapsulates a criterion (external to the solver) which imposes to stop searching for a better solution. Typically, this is done to grant a given time budget to the search.
  • DecisionCallback
    This trait basically defines a callback which is passed on to the problem so as to let it efficiently enumerate the domain values of some given variable.
  • DecisionDiagram
    This trait describes the operations that can be expected from an abstract decision diagram regardless of the way it is implemented.
  • Dominance
    This trait abstracts gives the possibility to model dominance relations between the states of a specific problem. The dominance relation is evaluated only for pairs of states that are mapped to the same key. A dominance relation exists if the coordinates of a state are greater or equal than those of another state for all given dimensions. The value obtained by the solver for each state can optionally be used as a coordinate in the comparison.
  • DominanceChecker
  • Fringe
    This trait abstracts away the implementation details of the solver fringe. That is, a Fringe represents the global priority queue which stores all the nodes remaining to explore.
  • Problem
    This trait defines the “contract” of what defines an optimization problem solvable with the branch-and-bound with DD paradigm. An implementation of this trait effectively defines a DP formulation of the problem being solved. That DP model is envisioned as a labeled transition system – which makes it more amenable to DD compilation.
  • Relaxation
    A relaxation encapsulates the relaxation $\Gamma$ and $\oplus$ which are necessary when compiling relaxed DDs. These operators respectively relax the weight of an arc towards a merged node, and merges the staet of two or more nodes so as to create a new inexact node.
  • Solver
    This is the solver abstraction. It is implemented by a structure that implements the branch-and-bound with MDD paradigm (or possibly an other optimization algorithm – currently only branch-and-bound with DD) to find the best possible solution to a given problem.
  • StateRanking
    A state ranking is an heuristic that imposes a partial order on states. This order is used by the framework as a means to discriminate the most promising nodes from the least promising ones when restricting or relaxing a layer from some given DD.
  • SubProblemRanking
    A subproblem ranking is an heuristic that imposes a partial order on sub-problems on the solver fringe. This order is used by the framework as a means to impose a given ordering on the nodes that are popped from the solver fringe.
  • WidthHeuristic
    This trait encapsulates the behavior of the heuristic that determines the maximum permitted width of a decision diagram.

Type Aliases§