Skip to content

Commit c3ece81

Browse files
chschultechschulte
committed
Support variable selection criteria for assigning variables during search
1 parent cbfdc08 commit c3ece81

12 files changed

Lines changed: 20009 additions & 19353 deletions

File tree

‎Makefile.dep‎

Lines changed: 19431 additions & 19323 deletions
Large diffs are not rendered by default.

‎Makefile.in‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -349,7 +349,7 @@ INTHDR0 = \
349349
branch/traits.hpp branch/var.hpp branch/val.hpp branch/assign.hpp \
350350
branch/view-values.hpp branch/merit.hpp \
351351
branch/val-sel.hpp branch/val-commit.hpp branch/ngl.hpp \
352-
branch/cbs.hpp \
352+
branch/cbs.hpp branch.hpp \
353353
count.hh count/rel.hpp \
354354
count/int-base.hpp count/int-eq.hpp \
355355
count/int-gq.hpp count/int-lq.hpp \
@@ -495,7 +495,7 @@ FLOATHDR0 = \
495495
rel.hh rel/eq.hpp rel/lq-le.hpp rel/nq.hpp \
496496
bool.hh bool/ite.hpp \
497497
branch.hh branch/afc.hpp branch/action.hpp branch/chb.hpp \
498-
branch/traits.hpp \
498+
branch/traits.hpp branch.hpp \
499499
branch/var.hpp branch/val.hpp branch/assign.hpp \
500500
branch/val-commit.hpp branch/val-sel.hpp branch/merit.hpp \
501501
num.hpp val.hpp rounding.hpp nextafter.hpp \
@@ -589,7 +589,7 @@ SETHDR0 = \
589589
precede.hh precede/single.hpp \
590590
rel-op.hh \
591591
branch.hh branch/afc.hpp branch/action.hpp branch/chb.hpp \
592-
branch/traits.hpp \
592+
branch/traits.hpp branch.hpp \
593593
branch/var.hpp branch/val.hpp branch/assign.hpp \
594594
branch/merit.hpp branch/val-commit.hpp branch/val-sel.hpp \
595595
branch/ngl.hpp \

‎changelog.in‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -68,6 +68,54 @@ Date: 2019-??-??
6868
[DESCRIPTION]
6969
Let's see.
7070

71+
[ENTRY]
72+
Module: int
73+
What: new
74+
Rank: major
75+
[DESCRIPTION]
76+
Variables to be assigned during search can now be selected with
77+
all available selection criteria available for branching.
78+
79+
[ENTRY]
80+
Module: int
81+
What: new
82+
Rank: minor
83+
[DESCRIPTION]
84+
Omitting the variable selection criterion is equivalent to
85+
INT_VAR_NONE().
86+
87+
[ENTRY]
88+
Module: set
89+
What: new
90+
Rank: major
91+
[DESCRIPTION]
92+
Variables to be assigned during search can now be selected with
93+
all available selection criteria available for branching.
94+
95+
[ENTRY]
96+
Module: set
97+
What: new
98+
Rank: minor
99+
[DESCRIPTION]
100+
Omitting the variable selection criterion is equivalent to
101+
SET_VAR_NONE().
102+
103+
[ENTRY]
104+
Module: float
105+
What: new
106+
Rank: major
107+
[DESCRIPTION]
108+
Variables to be assigned during search can now be selected with
109+
all available selection criteria available for branching.
110+
111+
[ENTRY]
112+
Module: float
113+
What: new
114+
Rank: minor
115+
[DESCRIPTION]
116+
Omitting the variable selection criterion is equivalent to
117+
FLOAT_VAR_NONE().
118+
71119

72120
[RELEASE]
73121
Version: 6.1.1

‎gecode/float.hh‎

Lines changed: 39 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1949,12 +1949,23 @@ namespace Gecode {
19491949
FloatVarValPrint vvp=nullptr);
19501950

19511951
/**
1952-
* \brief Assign all \a x with value selection \a vals
1952+
* \brief Assign all \a x with variable selection \a vars and value selection \a vals
19531953
*
19541954
* \ingroup TaskModelFloatBranch
19551955
*/
19561956
GECODE_FLOAT_EXPORT void
1957-
assign(Home home, const FloatVarArgs& x, FloatAssign vals,
1957+
assign(Home home, const FloatVarArgs& x,
1958+
FloatVarBranch vars, FloatAssign vals,
1959+
FloatBranchFilter bf=nullptr,
1960+
FloatVarValPrint vvp=nullptr);
1961+
/**
1962+
* \brief Assign all \a x with tie-breaking variable selection \a vars and value selection \a vals
1963+
*
1964+
* \ingroup TaskModelFloatBranch
1965+
*/
1966+
GECODE_FLOAT_EXPORT void
1967+
assign(Home home, const FloatVarArgs& x,
1968+
TieBreak<FloatVarBranch> vars, FloatAssign vals,
19581969
FloatBranchFilter bf=nullptr,
19591970
FloatVarValPrint vvp=nullptr);
19601971
/**
@@ -1965,10 +1976,35 @@ namespace Gecode {
19651976
GECODE_FLOAT_EXPORT void
19661977
assign(Home home, FloatVar x, FloatAssign vals,
19671978
FloatVarValPrint vvp=nullptr);
1968-
//@}
19691979

19701980
}
19711981

1982+
namespace Gecode {
1983+
1984+
/**
1985+
* \brief Branch over \a x with value selection \a vals
1986+
*
1987+
* \ingroup TaskModelFloatBranch
1988+
*/
1989+
void
1990+
branch(Home home, const FloatVarArgs& x, FloatValBranch vals,
1991+
FloatBranchFilter bf=nullptr,
1992+
FloatVarValPrint vvp=nullptr);
1993+
1994+
/**
1995+
* \brief Assign all \a x with value selection \a vals
1996+
*
1997+
* \ingroup TaskModelFloatBranch
1998+
*/
1999+
void
2000+
assign(Home home, const FloatVarArgs& x, FloatAssign vals,
2001+
FloatBranchFilter bf=nullptr,
2002+
FloatVarValPrint vvp=nullptr);
2003+
2004+
}
2005+
2006+
#include <gecode/float/branch.hpp>
2007+
19722008
namespace Gecode {
19732009

19742010
/*

‎gecode/float/branch.cpp‎

100644100755
Lines changed: 56 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -108,23 +108,74 @@ namespace Gecode {
108108
}
109109

110110
void
111-
assign(Home home, const FloatVarArgs& x, FloatAssign fa,
111+
assign(Home home, const FloatVarArgs& x,
112+
FloatVarBranch vars, FloatAssign vals,
112113
FloatBranchFilter bf,
113114
FloatVarValPrint vvp) {
114115
using namespace Float;
115116
if (home.failed()) return;
116117
ViewArray<FloatView> xv(home,x);
117118
ViewSel<FloatView>* vs[1] = {
118-
new (home) ViewSelNone<FloatView>(home,FLOAT_VAR_NONE())
119+
new (home) ViewSelNone<FloatView>(home,vars)
119120
};
120121
postviewvalbrancher<FloatView,1,FloatNumBranch,1>
121-
(home,xv,vs,Branch::valselcommit(home,fa),bf,vvp);
122+
(home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
123+
}
124+
125+
void
126+
assign(Home home, const FloatVarArgs& x,
127+
TieBreak<FloatVarBranch> vars, FloatAssign vals,
128+
FloatBranchFilter bf,
129+
FloatVarValPrint vvp) {
130+
using namespace Float;
131+
if (home.failed()) return;
132+
vars.a.expand(home,x);
133+
if ((vars.a.select() == FloatVarBranch::SEL_NONE) ||
134+
(vars.a.select() == FloatVarBranch::SEL_RND))
135+
vars.b = FLOAT_VAR_NONE();
136+
vars.b.expand(home,x);
137+
if ((vars.b.select() == FloatVarBranch::SEL_NONE) ||
138+
(vars.b.select() == FloatVarBranch::SEL_RND))
139+
vars.c = FLOAT_VAR_NONE();
140+
vars.c.expand(home,x);
141+
if ((vars.c.select() == FloatVarBranch::SEL_NONE) ||
142+
(vars.c.select() == FloatVarBranch::SEL_RND))
143+
vars.d = FLOAT_VAR_NONE();
144+
vars.d.expand(home,x);
145+
if (vars.b.select() == FloatVarBranch::SEL_NONE) {
146+
assign(home,x,vars.a,vals,bf,vvp);
147+
} else {
148+
ViewArray<FloatView> xv(home,x);
149+
ValSelCommitBase<FloatView,FloatNumBranch>*
150+
vsc = Branch::valselcommit(home,vals);
151+
if (vars.c.select() == FloatVarBranch::SEL_NONE) {
152+
ViewSel<FloatView>* vs[2] = {
153+
Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
154+
};
155+
postviewvalbrancher<FloatView,2,FloatNumBranch,1>
156+
(home,xv,vs,vsc,bf,vvp);
157+
} else if (vars.d.select() == FloatVarBranch::SEL_NONE) {
158+
ViewSel<FloatView>* vs[3] = {
159+
Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
160+
Branch::viewsel(home,vars.c)
161+
};
162+
postviewvalbrancher<FloatView,3,FloatNumBranch,1>
163+
(home,xv,vs,vsc,bf,vvp);
164+
} else {
165+
ViewSel<FloatView>* vs[4] = {
166+
Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
167+
Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
168+
};
169+
postviewvalbrancher<FloatView,4,FloatNumBranch,1>
170+
(home,xv,vs,vsc,bf,vvp);
171+
}
172+
}
122173
}
123174

124175
void
125-
assign(Home home, FloatVar x, FloatAssign fa, FloatVarValPrint vvp) {
176+
assign(Home home, FloatVar x, FloatAssign vals, FloatVarValPrint vvp) {
126177
FloatVarArgs xv(1); xv[0]=x;
127-
assign(home, xv, fa, nullptr, vvp);
178+
assign(home, xv, FLOAT_VAR_NONE(), vals, nullptr, vvp);
128179
}
129180

130181
}

‎gecode/float/branch.hpp‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2+
/*
3+
* Main authors:
4+
* Christian Schulte <schulte@gecode.org>
5+
*
6+
* Copyright:
7+
* Christian Schulte, 2019
8+
*
9+
* This file is part of Gecode, the generic constraint
10+
* development environment:
11+
* http://www.gecode.org
12+
*
13+
* Permission is hereby granted, free of charge, to any person obtaining
14+
* a copy of this software and associated documentation files (the
15+
* "Software"), to deal in the Software without restriction, including
16+
* without limitation the rights to use, copy, modify, merge, publish,
17+
* distribute, sublicense, and/or sell copies of the Software, and to
18+
* permit persons to whom the Software is furnished to do so, subject to
19+
* the following conditions:
20+
*
21+
* The above copyright notice and this permission notice shall be
22+
* included in all copies or substantial portions of the Software.
23+
*
24+
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25+
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26+
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27+
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28+
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29+
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30+
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31+
*
32+
*/
33+
34+
namespace Gecode {
35+
36+
forceinline void
37+
branch(Home home, const FloatVarArgs& x, FloatValBranch vals,
38+
FloatBranchFilter bf, FloatVarValPrint vvp) {
39+
branch(home, x, FLOAT_VAR_NONE(), vals, bf, vvp);
40+
}
41+
42+
forceinline void
43+
assign(Home home, const FloatVarArgs& x, FloatAssign vals,
44+
FloatBranchFilter bf, FloatVarValPrint vvp) {
45+
assign(home, x, FLOAT_VAR_NONE(), vals, bf, vvp);
46+
}
47+
48+
}
49+
50+
// STATISTICS: float-branch

‎gecode/int.hh‎

Lines changed: 71 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -4999,6 +4999,7 @@ namespace Gecode {
49994999
#include <gecode/int/branch/assign.hpp>
50005000

50015001
namespace Gecode {
5002+
50025003
/**
50035004
* \brief Branch over \a x with variable selection \a vars and value selection \a vals
50045005
*
@@ -5057,12 +5058,23 @@ namespace Gecode {
50575058
BoolVarValPrint vvp=nullptr);
50585059

50595060
/**
5060-
* \brief Assign all \a x with value selection \a vals
5061+
* \brief Assign all \a x with variable selection \a vars with value selection \a vals
50615062
*
50625063
* \ingroup TaskModelIntBranch
50635064
*/
50645065
GECODE_INT_EXPORT void
5065-
assign(Home home, const IntVarArgs& x, IntAssign vals,
5066+
assign(Home home, const IntVarArgs& x,
5067+
IntVarBranch vars, IntAssign vals,
5068+
IntBranchFilter bf=nullptr,
5069+
IntVarValPrint vvp=nullptr);
5070+
/**
5071+
* \brief Assign all \a x with tie-breaking variable selection \a vars and value selection \a vals
5072+
*
5073+
* \ingroup TaskModelIntBranch
5074+
*/
5075+
GECODE_INT_EXPORT void
5076+
assign(Home home, const IntVarArgs& x,
5077+
TieBreak<IntVarBranch> vars, IntAssign vals,
50665078
IntBranchFilter bf=nullptr,
50675079
IntVarValPrint vvp=nullptr);
50685080
/**
@@ -5074,14 +5086,25 @@ namespace Gecode {
50745086
assign(Home home, IntVar x, IntAssign vals,
50755087
IntVarValPrint vvp=nullptr);
50765088
/**
5077-
* \brief Assign all \a x with value selection \a vals
5089+
* \brief Assign all \a x with variable selection \a vars with value selection \a vals
50785090
*
50795091
* \ingroup TaskModelIntBranch
50805092
*/
50815093
GECODE_INT_EXPORT void
5082-
assign(Home home, const BoolVarArgs& x, BoolAssign vals,
5094+
assign(Home home, const BoolVarArgs& x,
5095+
BoolVarBranch vars, BoolAssign vals,
50835096
BoolBranchFilter bf=nullptr,
50845097
BoolVarValPrint vvp=nullptr);
5098+
/**
5099+
* \brief Assign all \a x with tie-breaking variable selection \a vars and value selection \a vals
5100+
*
5101+
* \ingroup TaskModelIntBranch
5102+
*/
5103+
GECODE_INT_EXPORT void
5104+
assign(Home home, const BoolVarArgs& x,
5105+
TieBreak<BoolVarBranch> vars, BoolAssign vals,
5106+
IntBranchFilter bf=nullptr,
5107+
IntVarValPrint vvp=nullptr);
50855108
/**
50865109
* \brief Assign \a x with value selection \a vals
50875110
*
@@ -5093,6 +5116,50 @@ namespace Gecode {
50935116

50945117
}
50955118

5119+
namespace Gecode {
5120+
5121+
/**
5122+
* \brief Branch over \a x with value selection \a vals
5123+
*
5124+
* \ingroup TaskModelIntBranch
5125+
*/
5126+
void
5127+
branch(Home home, const IntVarArgs& x, IntValBranch vals,
5128+
IntBranchFilter bf=nullptr,
5129+
IntVarValPrint vvp=nullptr);
5130+
/**
5131+
* \brief Branch over \a x with value selection \a vals
5132+
*
5133+
* \ingroup TaskModelIntBranch
5134+
*/
5135+
void
5136+
branch(Home home, const BoolVarArgs& x, BoolValBranch vals,
5137+
BoolBranchFilter bf=nullptr,
5138+
BoolVarValPrint vvp=nullptr);
5139+
5140+
/**
5141+
* \brief Assign all \a x with value selection \a vals
5142+
*
5143+
* \ingroup TaskModelIntBranch
5144+
*/
5145+
void
5146+
assign(Home home, const IntVarArgs& x, IntAssign vals,
5147+
IntBranchFilter bf=nullptr,
5148+
IntVarValPrint vvp=nullptr);
5149+
/**
5150+
* \brief Assign all \a x with value selection \a vals
5151+
*
5152+
* \ingroup TaskModelIntBranch
5153+
*/
5154+
void
5155+
assign(Home home, const BoolVarArgs& x, BoolAssign vals,
5156+
BoolBranchFilter bf=nullptr,
5157+
BoolVarValPrint vvp=nullptr);
5158+
5159+
}
5160+
5161+
#include <gecode/int/branch.hpp>
5162+
50965163
namespace Gecode {
50975164

50985165
/** Print DFA \a d

0 commit comments

Comments
 (0)