pcp/search/
branch_and_bound.rs

1// Copyright 2016 Pierre Talbot (IRCAM)
2
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6
7//     http://www.apache.org/licenses/LICENSE-2.0
8
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use kernel::*;
16use search::space::*;
17use search::search_tree_visitor::*;
18use search::search_tree_visitor::Status::*;
19use term::*;
20use propagators::cmp::*;
21use gcollections::*;
22use concept::*;
23
24pub enum Mode {
25  Minimize,
26  Maximize
27}
28
29pub struct BranchAndBound<VStore, C> where
30 VStore: VStoreConcept,
31 VStore::Item: Collection
32{
33  pub mode: Mode,
34  pub var: Var<VStore>,
35  pub value: Option<<VStore::Item as Collection>::Item>,
36  pub child: C
37}
38
39impl<VStore, C> BranchAndBound<VStore, C> where
40  VStore: VStoreConcept,
41  VStore::Item: Collection
42{
43  pub fn new(mode: Mode, var: Var<VStore>, child: C) -> Self {
44    BranchAndBound {
45      mode: mode,
46      var: var,
47      value: None,
48      child: child,
49    }
50  }
51}
52
53impl<C, Bound, Dom, VStore, CStore, R> SearchTreeVisitor<Space<VStore, CStore, R>> for
54  BranchAndBound<VStore, C> where
55 VStore: VStoreConcept<Item=Dom> + 'static,
56 CStore: IntCStore<VStore>,
57 Dom: IntDomain<Item=Bound> + 'static,
58 Bound: IntBound + 'static,
59 C: SearchTreeVisitor<Space<VStore, CStore, R>>,
60 R: FreezeSpace<VStore, CStore> + Snapshot<State=Space<VStore, CStore, R>>
61{
62  fn start(&mut self, root: &Space<VStore, CStore, R>) {
63    self.child.start(root);
64  }
65
66  fn enter(&mut self, mut current: Space<VStore, CStore, R>)
67    -> (<Space<VStore, CStore, R> as Freeze>::FrozenState, Status<Space<VStore, CStore, R>>)
68  {
69    if let Some(bound) = self.value.clone() {
70      let bound = Box::new(Constant::new(bound)) as Var<VStore>;
71      match self.mode {
72        Mode::Minimize => current.cstore.alloc(Box::new(XLessY::new(self.var.bclone(), bound.bclone()))),
73        Mode::Maximize => current.cstore.alloc(Box::new(x_greater_y(self.var.bclone(), bound.bclone()))),
74      };
75    }
76    let (mut immutable_state, status) = self.child.enter(current);
77    if status == Satisfiable {
78      let space = immutable_state.unfreeze();
79      self.value = Some(self.var.read(&space.vstore).lower());
80      immutable_state = space.freeze();
81    }
82    (immutable_state, status)
83  }
84}
85
86#[cfg(test)]
87mod test {
88  use super::*;
89  use search::test::*;
90  use search::engine::all_solution::*;
91  use search::engine::one_solution::*;
92  use search::propagation::*;
93  use search::branching::binary_split::*;
94  use search::branching::brancher::*;
95  use search::branching::first_smallest_var::*;
96  use search::branching::middle_val::*;
97  use interval::interval_set::*;
98  use gcollections::VectorStack;
99  use gcollections::ops::*;
100
101  #[test]
102  fn simple_maximize_test() {
103    simple_optimization_test(Mode::Maximize, 9);
104  }
105
106  #[test]
107  fn simple_minimize_test() {
108    simple_optimization_test(Mode::Minimize, 0);
109  }
110
111  fn simple_optimization_test(mode: Mode, expect: i32) {
112    let mut space = FDSpace::empty();
113    let x = Box::new(space.vstore.alloc((0,10).to_interval_set())) as Var<VStore>;
114    let y = Box::new(space.vstore.alloc((0,10).to_interval_set())) as Var<VStore>;
115    space.cstore.alloc(Box::new(XLessY::new(x.bclone(), y)));
116
117    let mut search: AllSolution<OneSolution<_, VectorStack<_>, FDSpace>>
118      = AllSolution::new(
119          OneSolution::new(
120            BranchAndBound::new(mode, x.bclone(),
121              Propagation::new(Brancher::new(FirstSmallestVar, MiddleVal, BinarySplit)))));
122    search.start(&space);
123    let (_, status) = search.enter(space);
124    assert_eq!(status, EndOfSearch);
125    assert_eq!(search.child.child.value, Some(expect));
126  }
127}
128
pcp/search/branch_and_bound.rs

pcp/search/
branch_and_bound.rs
