ddo/abstraction/
solver.rs

1// Copyright 2020 Xavier Gillard
2//
3// Permission is hereby granted, free of charge, to any person obtaining a copy of
4// this software and associated documentation files (the "Software"), to deal in
5// the Software without restriction, including without limitation the rights to
6// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
7// the Software, and to permit persons to whom the Software is furnished to do so,
8// subject to the following conditions:
9//
10// The above copyright notice and this permission notice shall be included in all
11// copies or substantial portions of the Software.
12//
13// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
15// FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
16// COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
17// IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
18// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
19
20//! This module defines the `Solver` trait.
21
22use crate::{Decision, Completion};
23
24/// A decision is nothing but a sequence of decision covering all problem
25/// variables.
26pub type Solution = Vec<Decision>;
27
28/// This is the solver abstraction. It is implemented by a structure that 
29/// implements the branch-and-bound with MDD paradigm (or possibly an other
30/// optimization algorithm -- currently only branch-and-bound with DD) to
31/// find the best possible solution to a given problem.
32pub trait Solver {
33    /// This method orders the solver to search for the optimal solution among
34    /// all possibilities. It returns a structure standing for the outcome of
35    /// the attempted maximization. Such a `Completion` may either be marked 
36    /// **exact** if the maximization has been carried out until optimality was 
37    /// proved. Or it can be inexact, in which case it means that the 
38    /// maximization process was stopped because of the satisfaction of some 
39    /// cutoff criterion.
40    ///
41    /// Along with the `is_exact` exact flag, the completion provides an 
42    /// optional `best_value` of the maximization problem. Four cases are thus
43    /// to be distinguished:
44    ///
45    /// * When the `is_exact` flag is true, and a `best_value` is present: the
46    ///   `best_value` is the maximum value of the objective function.
47    /// * When the `is_exact` flag is false and a `best_value` is present, it
48    ///   is the best value of the objective function that was known at the time
49    ///   of cutoff.
50    /// * When the `is_exact` flag is true, and no `best_value` is present: it
51    ///   means that the problem admits no feasible solution (UNSAT).
52    /// * When the `is_exact` flag is false and no `best_value` is present: it
53    ///   simply means that no feasible solution has been found before the 
54    ///   cutoff occurred.
55    ///
56    fn maximize(&mut self) -> Completion;
57    /// This method returns the value of the objective function for the best
58    /// solution that has been found. It returns `None` when no solution exists
59    /// to the problem.
60    fn best_value(&self) -> Option<isize>;
61    /// This method returns the best solution to the optimization problem.
62    /// That is, it returns the vector of decision which maximizes the value 
63    /// of the objective function (sum of transition costs + initial value).
64    /// It returns `None` when the problem admits no feasible solution.
65    fn best_solution(&self) -> Option<Solution>;
66
67    /// Returns the best lower bound that has been identified so far.
68    /// In case where no solution has been found, it should return the minimum
69    /// value that fits within an isize (-inf).
70    fn best_lower_bound(&self) -> isize;
71    /// Returns the tightest upper bound that can be guaranteed so far.
72    /// In case where no upper bound has been computed, it should return the
73    /// maximum value that fits within an isize (+inf).
74    fn best_upper_bound(&self) -> isize;
75
76    /// Sets a primal (best known value and solution) of the problem.
77    fn set_primal(&mut self, value: isize, solution: Solution);
78
79    /// Computes the optimality gap
80    fn gap(&self) -> f32 {
81        let ub = self.best_upper_bound();
82        let lb = self.best_lower_bound();
83        if ub == isize::MAX || lb == isize::MIN {
84            1.0
85        } else {
86            let aub = ub.abs();
87            let alb = lb.abs();
88            let u = aub.max(alb);
89            let l = aub.min(alb);
90        
91            (u - l) as f32 / u as f32
92        }
93    }    
94}
ddo/abstraction/solver.rs

ddo/abstraction/
solver.rs
