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#pragma once
14
15#include <minizinc/solvers/gecode_solverinstance.hh>
16
17/**
18 * \brief Branching on the introduced variables
19 *
20 * This brancher makes sure that when a solution is found for the model
21 * variables, all introduced variables are either assigned, or the solution
22 * can be extended to a solution of the introduced variables.
23 *
24 * The advantage over simply branching over the introduced variables is that
25 * only one such extension will be searched for, instead of enumerating all
26 * possible (equivalent) extensions.
27 *
28 */
29namespace MiniZinc {
30
31class AuxVarBrancher : public Gecode::Brancher {
32protected:
33 /// Flag whether brancher is done
34 bool done;
35 /// Construct brancher
36 AuxVarBrancher(Gecode::Home home, const Gecode::TieBreak<Gecode::IntVarBranch>& int_varsel0,
37 const Gecode::IntValBranch& int_valsel0,
38 const Gecode::TieBreak<Gecode::BoolVarBranch>& bool_varsel0,
39 const Gecode::BoolValBranch& bool_valsel0
40#ifdef GECODE_HAS_SET_VARS
41 ,
42 const Gecode::SetVarBranch& set_varsel0, const Gecode::SetValBranch& set_valsel0
43#endif
44#ifdef GECODE_HAS_FLOAT_VARS
45 ,
46 const Gecode::TieBreak<Gecode::FloatVarBranch>& float_varsel0,
47 const Gecode::FloatValBranch& float_valsel0
48#endif
49 )
50 : Brancher(home),
51 done(false),
52 int_varsel(int_varsel0),
53 int_valsel(int_valsel0),
54 bool_varsel(bool_varsel0),
55 bool_valsel(bool_valsel0)
56#ifdef GECODE_HAS_SET_VARS
57 ,
58 set_varsel(set_varsel0),
59 set_valsel(set_valsel0)
60#endif
61#ifdef GECODE_HAS_FLOAT_VARS
62 ,
63 float_varsel(float_varsel0),
64 float_valsel(float_valsel0)
65#endif
66 {
67 }
68 /// Copy constructor
69 AuxVarBrancher(Gecode::Space& home, AuxVarBrancher& b) : Brancher(home, b), done(b.done) {}
70
71 /// %Choice that only signals failure or success
72 class Choice : public Gecode::Choice {
73 public:
74 /// Whether brancher should fail
75 bool fail;
76 /// Initialize choice for brancher \a b
77 Choice(const Brancher& b, bool fail0) : Gecode::Choice(b, 1), fail(fail0) {}
78 /// Report size occupied
79 virtual size_t size() const { return sizeof(Choice); }
80 /// Archive into \a e
81 virtual void archive(Gecode::Archive& e) const {
82 Gecode::Choice::archive(e);
83 e.put(fail);
84 }
85 };
86
87 Gecode::TieBreak<Gecode::IntVarBranch> int_varsel;
88 Gecode::IntValBranch int_valsel;
89 Gecode::TieBreak<Gecode::BoolVarBranch> bool_varsel;
90 Gecode::BoolValBranch bool_valsel;
91#ifdef GECODE_HAS_SET_VARS
92 Gecode::SetVarBranch set_varsel;
93 Gecode::SetValBranch set_valsel;
94#endif
95#ifdef GECODE_HAS_FLOAT_VARS
96 Gecode::TieBreak<Gecode::FloatVarBranch> float_varsel;
97 Gecode::FloatValBranch float_valsel;
98#endif
99
100public:
101 /// Check status of brancher, return true if alternatives left.
102 virtual bool status(const Gecode::Space& _home) const {
103 if (done) return false;
104 const MiniZinc::FznSpace& home = static_cast<const MiniZinc::FznSpace&>(_home);
105 for (int i = 0; i < home.ivAux.size(); i++)
106 if (!home.ivAux[i].assigned()) return true;
107 for (int i = 0; i < home.bvAux.size(); i++)
108 if (!home.bvAux[i].assigned()) return true;
109#ifdef GECODE_HAS_SET_VARS
110 for (int i = 0; i < home.svAux.size(); i++)
111 if (!home.svAux[i].assigned()) return true;
112#endif
113#ifdef GECODE_HAS_FLOAT_VARS
114 for (int i = 0; i < home.fvAux.size(); i++)
115 if (!home.fvAux[i].assigned()) return true;
116#endif
117 // No non-assigned variables left
118 return false;
119 }
120 /// Return choice
121 virtual Choice* choice(Gecode::Space& home) {
122 done = true;
123 MiniZinc::FznSpace& fzs = static_cast<MiniZinc::FznSpace&>(*home.clone());
124 fzs.copyAuxVars = false;
125 Gecode::branch(fzs, fzs.ivAux, int_varsel, int_valsel);
126 Gecode::branch(fzs, fzs.bvAux, bool_varsel, bool_valsel);
127#ifdef GECODE_HAS_SET_VARS
128 Gecode::branch(fzs, fzs.svAux, set_varsel, set_valsel);
129#endif
130#ifdef GECODE_HAS_FLOAT_VARS
131 Gecode::branch(fzs, fzs.fvAux, float_varsel, float_valsel);
132#endif
133 Gecode::Search::Options opt;
134 opt.clone = false;
135 MiniZinc::FznSpace* sol = Gecode::dfs(&fzs, opt);
136 if (sol) {
137 delete sol;
138 return new Choice(*this, false);
139 } else {
140 return new Choice(*this, true);
141 }
142 }
143 /// Return choice
144 virtual Choice* choice(const Gecode::Space&, Gecode::Archive& e) {
145 bool fail;
146 e >> fail;
147 return new Choice(*this, fail);
148 }
149 /// Perform commit for choice \a c
150 virtual Gecode::ExecStatus commit(Gecode::Space&, const Gecode::Choice& c, unsigned int) {
151 return static_cast<const Choice&>(c).fail ? Gecode::ES_FAILED : Gecode::ES_OK;
152 }
153 /// Print explanation
154 virtual void print(const Gecode::Space&, const Gecode::Choice& c, unsigned int,
155 std::ostream& o) const {
156 o << "FlatZinc(" << (static_cast<const Choice&>(c).fail ? "fail" : "ok") << ")";
157 }
158 /// Copy brancher
159 virtual Actor* copy(Gecode::Space& home) { return new (home) AuxVarBrancher(home, *this); }
160 /// Post brancher
161 static void post(Gecode::Home home, const Gecode::TieBreak<Gecode::IntVarBranch>& int_varsel,
162 const Gecode::IntValBranch& int_valsel,
163 const Gecode::TieBreak<Gecode::BoolVarBranch>& bool_varsel,
164 const Gecode::BoolValBranch& bool_valsel
165#ifdef GECODE_HAS_SET_VARS
166 ,
167 const Gecode::SetVarBranch& set_varsel, const Gecode::SetValBranch& set_valsel
168#endif
169#ifdef GECODE_HAS_FLOAT_VARS
170 ,
171 const Gecode::TieBreak<Gecode::FloatVarBranch>& float_varsel,
172 const Gecode::FloatValBranch& float_valsel
173#endif
174 ) {
175 (void)new (home) AuxVarBrancher(home, int_varsel, int_valsel, bool_varsel, bool_valsel
176#ifdef GECODE_HAS_SET_VARS
177 ,
178 set_varsel, set_valsel
179#endif
180#ifdef GECODE_HAS_FLOAT_VARS
181 ,
182 float_varsel, float_valsel
183#endif
184 );
185 }
186 /// Delete brancher and return its size
187 virtual size_t dispose(Gecode::Space&) { return sizeof(*this); }
188};
189
190} // namespace MiniZinc