ddo 0.1.6

DDO a generic and efficient framework for MDD-based optimization.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

// Copyright 2020 Xavier Gillard
//
// Permission is hereby granted, free of charge, to any person obtaining a copy of
// this software and associated documentation files (the "Software"), to deal in
// the Software without restriction, including without limitation the rights to
// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
// the Software, and to permit persons to whom the Software is furnished to do so,
// subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
// FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
// COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
// IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

//! This module defines the basic abstractions one will manipulate when
//! implementing an MDD optimization-solver for some problem formulated as a
//! dynamic program.
//!
//! The most important abstractions that should be provided by a client are
//! `Problem` and `Relaxation`.
use std::i32;

use crate::core::common::{Decision, Variable, VarSet, Node, NodeInfo, Domain};

/// This is the main abstraction that should be provided by any user of our
/// library. Indeed, it defines the problem to be solved in the form of a dynamic
/// program. Therefore, this trait closely sticks to the formal definition of a
/// dynamic program.
///
/// The type parameter `<T>` denotes the type of the states of the dynamic program.
pub trait Problem<T> {
    /// Returns the number of decision variables that play a role in the problem.
    fn nb_vars(&self) -> usize;
    /// Returns the initial state of the problem (when no decision is taken).
    fn initial_state(&self) -> T;
    /// Returns the initial value of the objective function (when no decision is taken).
    fn initial_value(&self) -> i32;

    /// Returns the domain of variable `var` in the given `state`. These are the
    /// possible values that might possibly be affected to `var` when the system
    /// has taken decisions leading to `state`.
    fn domain_of<'a>(&self, state: &'a T, var: Variable) -> Domain<'a>;
    /// Returns the next state reached by the system if the decision `d` is
    /// taken when the system is in the given `state` and the given set of `vars`
    /// are still free (no value assigned).
    fn transition(&self, state: &T, vars : &VarSet, d: Decision) -> T;
    /// Returns the marginal benefit (in terms of objective function to maximize)
    /// of taking decision `d` is when the system is in the given `state` and
    /// the given set of `vars` are still free (no value assigned).
    fn transition_cost(&self, state: &T, vars : &VarSet, d: Decision) -> i32;

    /// Optional method for the case where you'd want to use a pooled mdd
    /// implementation. This method returns true iff taking a decision on
    /// `variable` might have an impact (state or longest path) on a node having
    /// the given `state`
    #[allow(unused_variables)]
    fn impacted_by(&self, state: &T, variable: Variable) -> bool {
        true
    }

    /// Returns the root node of an exact MDD standing for this problem.
    ///
    /// This method is (trivially) auto-implemented, but re-implementing it
    /// does not make much sense.
    fn root_node(&self) -> Node<T> {
        Node::new(self.initial_state(), self.initial_value(), None, true, false)
    }
    /// Returns a var set with all the variables of this problem.
    ///
    /// This method is (trivially) auto-implemented, but re-implementing it
    /// does not make much sense.
    fn all_vars(&self) -> VarSet {
        VarSet::all(self.nb_vars())
    }
}

/// This is the second most important abstraction that a client should provide
/// when using this library. It defines the relaxation that may be applied to
/// the given problem. In particular, the `merge_nodes` method from this trait
/// defines how the nodes of a layer may be combined to provide an upper bound
/// approximation standing for an arbitrarily selected set of nodes.
///
/// Again, the type parameter `<T>` denotes the type of the states.
pub trait Relaxation<T> {
    /// This method merges the given set of `nodes` into a new _inexact_ node.
    /// The role of this method is really to _only_ provide an inexact
    /// node to use as a replacement for the selected `nodes`. It is the MDD that
    /// takes care of maintaining a cutset.
    fn merge_nodes(&self, nodes: &[Node<T>]) -> Node<T>;
    /// This optional method derives a _rough_ upper bound on the maximum value
    /// reachable by passing through the node characterized by the given `state`
    /// and node `info`.
    fn estimate_ub(&self, _state: &T, _info: &NodeInfo) -> i32 {
        i32::max_value()
    }
}

#[cfg(test)]
mod test_problem_defaults {
    use crate::core::abstraction::dp::{Problem, Relaxation};
    use crate::core::common::{Variable, VarSet, Domain, Decision, Node, NodeInfo};

    struct MockProblem;
    impl Problem<usize> for MockProblem {
        fn nb_vars(&self)       -> usize {  5 }
        fn initial_state(&self) -> usize { 42 }
        fn initial_value(&self) -> i32   { 84 }
        fn domain_of<'a>(&self, _: &'a usize, _: Variable) -> Domain<'a> {
            unimplemented!()
        }
        fn transition(&self, _: &usize, _: &VarSet, _: Decision) -> usize {
            unimplemented!()
        }
        fn transition_cost(&self, _: &usize, _: &VarSet, _: Decision) -> i32 {
            unimplemented!()
        }
    }
    struct MockRelax;
    impl Relaxation<usize> for MockRelax {
        fn merge_nodes(&self, _: &[Node<usize>]) -> Node<usize> {
            unimplemented!()
        }
    }

    #[test]
    fn by_default_all_vars_impact_all_states() {
        assert!(MockProblem.impacted_by(&0, Variable(0)));
        assert!(MockProblem.impacted_by(&4, Variable(10)));
        assert!(MockProblem.impacted_by(&92, Variable(53)));
    }

    #[test]
    fn by_default_all_vars_return_all_possible_variables(){
        assert_eq!(VarSet::all(5), MockProblem.all_vars());
    }

    #[test]
    fn by_default_the_root_node_consitsts_of_the_initial_state_and_value() {
        let node = Node::new(MockProblem.initial_state(), MockProblem.initial_value(), None, true, false);
        assert_eq!(node, MockProblem.root_node());
    }

    #[test]
    fn the_default_rough_upper_bound_is_infinity() {
        let info = NodeInfo::new(12, None, true, false);
        assert_eq!(i32::max_value(), MockRelax.estimate_ub(&12, &info));
    }
}