this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
3/*
4 * Main authors:
5 * Pierre WILKE (wilke.pierre@gmail.com)
6 * Andrea Rendl (andrea.rendl@nicta.com.au)
7 */
8
9/* This Source Code Form is subject to the terms of the Mozilla Public
10 * License, v. 2.0. If a copy of the MPL was not distributed with this
11 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
12
13#ifndef __GECODE_AUX_BRANCHER_HH__
14#define __GECODE_AUX_BRANCHER_HH__
15
16#include <gecode/int.hh>
17#include <gecode/kernel.hh>
18#include <gecode/search.hh>
19#ifdef GECODE_HAS_SET_VARS
20#include <gecode/set.hh>
21#endif
22
23#ifdef GECODE_HAS_FLOAT_VARS
24#include <gecode/float.hh>
25#endif
26
27#include <minizinc/solvers/gecode_solverinstance.hh>
28
29#include <gecode/driver.hh>
30
31/**
32 * \brief Branching on the introduced variables
33 *
34 * This brancher makes sure that when a solution is found for the model
35 * variables, all introduced variables are either assigned, or the solution
36 * can be extended to a solution of the introduced variables.
37 *
38 * The advantage over simply branching over the introduced variables is that
39 * only one such extension will be searched for, instead of enumerating all
40 * possible (equivalent) extensions.
41 *
42 */
43namespace MiniZinc {
44
45class AuxVarBrancher : public Gecode::Brancher {
46protected:
47 /// Flag whether brancher is done
48 bool done;
49 /// Construct brancher
50 AuxVarBrancher(Gecode::Home home, Gecode::TieBreak<Gecode::IntVarBranch> int_varsel0,
51 Gecode::IntValBranch int_valsel0,
52 Gecode::TieBreak<Gecode::BoolVarBranch> bool_varsel0,
53 Gecode::BoolValBranch bool_valsel0
54#ifdef GECODE_HAS_SET_VARS
55 ,
56 Gecode::SetVarBranch set_varsel0, Gecode::SetValBranch set_valsel0
57#endif
58#ifdef GECODE_HAS_FLOAT_VARS
59 ,
60 Gecode::TieBreak<Gecode::FloatVarBranch> float_varsel0,
61 Gecode::FloatValBranch float_valsel0
62#endif
63 )
64 : Brancher(home),
65 done(false),
66 int_varsel(int_varsel0),
67 int_valsel(int_valsel0),
68 bool_varsel(bool_varsel0),
69 bool_valsel(bool_valsel0)
70#ifdef GECODE_HAS_SET_VARS
71 ,
72 set_varsel(set_varsel0),
73 set_valsel(set_valsel0)
74#endif
75#ifdef GECODE_HAS_FLOAT_VARS
76 ,
77 float_varsel(float_varsel0),
78 float_valsel(float_valsel0)
79#endif
80 {
81 }
82 /// Copy constructor
83 AuxVarBrancher(Gecode::Space& home, AuxVarBrancher& b) : Brancher(home, b), done(b.done) {}
84
85 /// %Choice that only signals failure or success
86 class Choice : public Gecode::Choice {
87 public:
88 /// Whether brancher should fail
89 bool fail;
90 /// Initialize choice for brancher \a b
91 Choice(const Brancher& b, bool fail0) : Gecode::Choice(b, 1), fail(fail0) {}
92 /// Report size occupied
93 virtual size_t size(void) const { return sizeof(Choice); }
94 /// Archive into \a e
95 virtual void archive(Gecode::Archive& e) const {
96 Gecode::Choice::archive(e);
97 e.put(fail);
98 }
99 };
100
101 Gecode::TieBreak<Gecode::IntVarBranch> int_varsel;
102 Gecode::IntValBranch int_valsel;
103 Gecode::TieBreak<Gecode::BoolVarBranch> bool_varsel;
104 Gecode::BoolValBranch bool_valsel;
105#ifdef GECODE_HAS_SET_VARS
106 Gecode::SetVarBranch set_varsel;
107 Gecode::SetValBranch set_valsel;
108#endif
109#ifdef GECODE_HAS_FLOAT_VARS
110 Gecode::TieBreak<Gecode::FloatVarBranch> float_varsel;
111 Gecode::FloatValBranch float_valsel;
112#endif
113
114public:
115 /// Check status of brancher, return true if alternatives left.
116 virtual bool status(const Gecode::Space& _home) const {
117 if (done) return false;
118 const MiniZinc::FznSpace& home = static_cast<const MiniZinc::FznSpace&>(_home);
119 for (int i = 0; i < home.iv_aux.size(); i++)
120 if (!home.iv_aux[i].assigned()) return true;
121 for (int i = 0; i < home.bv_aux.size(); i++)
122 if (!home.bv_aux[i].assigned()) return true;
123#ifdef GECODE_HAS_SET_VARS
124 for (int i = 0; i < home.sv_aux.size(); i++)
125 if (!home.sv_aux[i].assigned()) return true;
126#endif
127#ifdef GECODE_HAS_FLOAT_VARS
128 for (int i = 0; i < home.fv_aux.size(); i++)
129 if (!home.fv_aux[i].assigned()) return true;
130#endif
131 // No non-assigned variables left
132 return false;
133 }
134 /// Return choice
135 virtual Choice* choice(Gecode::Space& home) {
136 done = true;
137 MiniZinc::FznSpace& fzs = static_cast<MiniZinc::FznSpace&>(*home.clone());
138 fzs._copyAuxVars = false;
139 Gecode::branch(fzs, fzs.iv_aux, int_varsel, int_valsel);
140 Gecode::branch(fzs, fzs.bv_aux, bool_varsel, bool_valsel);
141#ifdef GECODE_HAS_SET_VARS
142 Gecode::branch(fzs, fzs.sv_aux, set_varsel, set_valsel);
143#endif
144#ifdef GECODE_HAS_FLOAT_VARS
145 Gecode::branch(fzs, fzs.fv_aux, float_varsel, float_valsel);
146#endif
147 Gecode::Search::Options opt;
148 opt.clone = false;
149 MiniZinc::FznSpace* sol = Gecode::dfs(&fzs, opt);
150 if (sol) {
151 delete sol;
152 return new Choice(*this, false);
153 } else {
154 return new Choice(*this, true);
155 }
156 }
157 /// Return choice
158 virtual Choice* choice(const Gecode::Space&, Gecode::Archive& e) {
159 bool fail;
160 e >> fail;
161 return new Choice(*this, fail);
162 }
163 /// Perform commit for choice \a c
164 virtual Gecode::ExecStatus commit(Gecode::Space&, const Gecode::Choice& c, unsigned int) {
165 return static_cast<const Choice&>(c).fail ? Gecode::ES_FAILED : Gecode::ES_OK;
166 }
167 /// Print explanation
168 virtual void print(const Gecode::Space&, const Gecode::Choice& c, unsigned int,
169 std::ostream& o) const {
170 o << "FlatZinc(" << (static_cast<const Choice&>(c).fail ? "fail" : "ok") << ")";
171 }
172 /// Copy brancher
173 virtual Actor* copy(Gecode::Space& home) { return new (home) AuxVarBrancher(home, *this); }
174 /// Post brancher
175 static void post(Gecode::Home home, Gecode::TieBreak<Gecode::IntVarBranch> int_varsel,
176 Gecode::IntValBranch int_valsel,
177 Gecode::TieBreak<Gecode::BoolVarBranch> bool_varsel,
178 Gecode::BoolValBranch bool_valsel
179#ifdef GECODE_HAS_SET_VARS
180 ,
181 Gecode::SetVarBranch set_varsel, Gecode::SetValBranch set_valsel
182#endif
183#ifdef GECODE_HAS_FLOAT_VARS
184 ,
185 Gecode::TieBreak<Gecode::FloatVarBranch> float_varsel,
186 Gecode::FloatValBranch float_valsel
187#endif
188 ) {
189 (void)new (home) AuxVarBrancher(home, int_varsel, int_valsel, bool_varsel, bool_valsel
190#ifdef GECODE_HAS_SET_VARS
191 ,
192 set_varsel, set_valsel
193#endif
194#ifdef GECODE_HAS_FLOAT_VARS
195 ,
196 float_varsel, float_valsel
197#endif
198 );
199 }
200 /// Delete brancher and return its size
201 virtual size_t dispose(Gecode::Space&) { return sizeof(*this); }
202};
203
204} // namespace MiniZinc
205#endif