pub struct Times<X>(pub usize, pub X);Expand description
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.
§Note:
This wrapper forces a minimum width of one. So it is never going to return 0 for a value of the max width.
§Example
Here is an example of how to use this strategy to allow 5 times as many nodes as there are nodes unassigned variable in a layer.
In the following example, there are 5 variables. Three of these have already been assigned. Which means there are only two unassigned variables left. Using the Times(5) decorator would mean that the maximum allowed width for a layer is 10 nodes.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct KnapsackState {
// details omitted in this example
}
struct Knapsack {
// details omitted in this example
}
impl Problem for Knapsack {
type State = KnapsackState;
fn nb_variables(&self) -> usize {
5
}
// details omitted in this example
}
let problem = Knapsack {
// details omitted in this example
};
let heuristic = Times(5, NbUnassignedWidth(problem.nb_variables()));
let subproblem= SubProblem {
// three decisions have already been made. There only remain variables 0 and 2
path: vec![
Decision{variable: Variable(1), value: 1},
Decision{variable: Variable(3), value: 1},
Decision{variable: Variable(4), value: 1},
]
};
assert_eq!(10, heuristic.max_width(&subproblem));§Typical usage example
Typically, you will only ever create a Times policy when instantiating your solver. The following example shows how you create a solver that imposes a fixed maximum layer width of five node per unassigned variable.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct KnapsackState {
// details omitted in this example
}
struct Knapsack {
// details omitted in this example
}
impl Problem for Knapsack {
// details omitted in this example
}
struct KPRelax<'a>{pb: &'a Knapsack}
impl Relaxation for KPRelax<'_> {
// details omitted in this example
}
struct KPRanking;
impl StateRanking for KPRanking {
// details omitted in this example
}
pub struct KPDominance;
impl Dominance for KPDominance {
// details omitted in this example
}
let problem = Knapsack {
// details omitted
};
let relaxation = KPRelax{pb: &problem};
let heuristic = KPRanking;
let dominance = SimpleDominanceChecker::new(KPDominance, problem.nb_variables());
let cutoff = NoCutoff; // might as well be a TimeBudget (or something else)
let mut fringe = SimpleFringe::new(MaxUB::new(&heuristic));
let mut solver = DefaultSolver::new(
&problem,
&relaxation,
&heuristic,
&Times(5, NbUnassignedWidth(problem.nb_variables())),
&dominance,
&cutoff,
&mut fringe);Tuple Fields§
§0: usize§1: X