ldsb.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christopher Mears <chris.mears@monash.edu>
*
* Copyright:
* Christopher Mears, 2012
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <gecode/int/ldsb.hh>
#include <gecode/int/branch.hh>
#include <map>
namespace Gecode { namespace Int { namespace LDSB {
std::pair<int,int>
findVar(int *indices, unsigned int n_values, unsigned int seq_size, int index) {
unsigned int seq = 0;
unsigned int pos = 0;
for (unsigned int i=0U ; i<n_values ; i++) {
if (indices[i] == index)
return std::pair<int,int>(seq,pos);
pos++;
if (pos == seq_size) {
pos = 0;
seq++;
}
}
return std::pair<int,int>(-1,-1);
}
}}}
namespace Gecode {
using namespace Int::LDSB;
SymmetryHandle VariableSymmetry(const IntVarArgs& vars) {
ArgArray<VarImpBase*> a(vars.size());
for (int i = 0 ; i < vars.size() ; i++)
a[i] = vars[i].varimp();
return SymmetryHandle(new VariableSymmetryObject(a));
}
SymmetryHandle VariableSymmetry(const BoolVarArgs& vars) {
ArgArray<VarImpBase*> a(vars.size());
for (int i = 0 ; i < vars.size() ; i++)
a[i] = vars[i].varimp();
return SymmetryHandle(new VariableSymmetryObject(a));
}
SymmetryHandle VariableSymmetry(const IntVarArgs& x,
const IntArgs& indices) {
IntVarArgs xs(indices.size());
for (int i = 0 ; i < indices.size() ; i++)
xs[i] = x[indices[i]];
return VariableSymmetry(xs);
}
SymmetryHandle ValueSymmetry(const IntArgs& vs) {
return SymmetryHandle(new ValueSymmetryObject(IntSet(vs)));
}
SymmetryHandle ValueSymmetry(const IntSet& vs) {
return SymmetryHandle(new ValueSymmetryObject(vs));
}
SymmetryHandle ValueSymmetry(IntVar x) {
return ValueSymmetry(IntSet(x.min(), x.max()));
}
SymmetryHandle VariableSequenceSymmetry(const IntVarArgs& vars, int ss) {
ArgArray<VarImpBase*> a(vars.size());
for (int i = 0 ; i < vars.size() ; i++)
a[i] = vars[i].varimp();
return SymmetryHandle(new VariableSequenceSymmetryObject(a, ss));
}
SymmetryHandle VariableSequenceSymmetry(const BoolVarArgs& vars, int ss) {
ArgArray<VarImpBase*> a(vars.size());
for (int i = 0 ; i < vars.size() ; i++)
a[i] = vars[i].varimp();
return SymmetryHandle(new VariableSequenceSymmetryObject(a, ss));
}
SymmetryHandle ValueSequenceSymmetry(const IntArgs& vs, int ss) {
return SymmetryHandle(new ValueSequenceSymmetryObject(vs, ss));
}
SymmetryHandle values_reflect(int lower, int upper) {
int n = (upper-lower+1)/2;
IntArgs a(n*2);
int i = lower;
int j = upper;
int k = 0;
while (i < j) {
a[k] = j;
a[n+k] = i;
i++;
j--;
k++;
}
return ValueSequenceSymmetry(a,n);
}
SymmetryHandle values_reflect(const IntVar& x) {
return values_reflect(x.min(), x.max());
}
}
namespace Gecode { namespace Int { namespace LDSB {
class VariableMap : public std::map<VarImpBase*,int> {};
/*
* The duplication in createIntSym/createBoolSym is undesirable,
* and so is the use of dynamic_cast to tell the symmetries
* apart.
*/
SymmetryImp<IntView>*
createIntSym(Space& home, const SymmetryHandle& s,
VariableMap variableMap) {
VariableSymmetryObject* varref =
dynamic_cast<VariableSymmetryObject*>(s.ref);
ValueSymmetryObject* valref =
dynamic_cast<ValueSymmetryObject*>(s.ref);
VariableSequenceSymmetryObject* varseqref =
dynamic_cast<VariableSequenceSymmetryObject*>(s.ref);
ValueSequenceSymmetryObject* valseqref =
dynamic_cast<ValueSequenceSymmetryObject*>(s.ref);
if (varref) {
int n = varref->nxs;
int* indices = home.alloc<int>(n);
for (int i = 0 ; i < n ; i++) {
VariableMap::const_iterator index = variableMap.find(varref->xs[i]);
if (index == variableMap.end())
throw LDSBUnbranchedVariable("VariableSymmetryObject::createInt");
indices[i] = index->second;
}
return new (home) VariableSymmetryImp<IntView>(home, indices, n);
}
if (valref) {
int n = valref->values.size();
int *vs = home.alloc<int>(n);
int i = 0;
for (IntSetValues v(valref->values) ; v() ; ++v) {
vs[i] = v.val();
i++;
}
return new (home) ValueSymmetryImp<IntView>(home, vs, n);
}
if (varseqref) {
int n = varseqref->nxs;
int* indices = home.alloc<int>(n);
for (int i = 0 ; i < n ; i++) {
VariableMap::const_iterator index =
variableMap.find(varseqref->xs[i]);
if (index == variableMap.end())
throw LDSBUnbranchedVariable("VariableSequenceSymmetryObject::createInt");
indices[i] = index->second;
}
return new (home) VariableSequenceSymmetryImp<IntView>(home, indices, n,
varseqref->seq_size);
}
if (valseqref) {
unsigned int n = valseqref->values.size();
int *vs = home.alloc<int>(n);
for (unsigned int i = 0 ; i < n ; i++)
vs[i] = valseqref->values[i];
return new (home) ValueSequenceSymmetryImp<IntView>(home, vs, n,
valseqref->seq_size);
}
GECODE_NEVER;
return NULL;
}
SymmetryImp<BoolView>* createBoolSym(Space& home, const SymmetryHandle& s,
VariableMap variableMap) {
VariableSymmetryObject* varref =
dynamic_cast<VariableSymmetryObject*>(s.ref);
ValueSymmetryObject* valref =
dynamic_cast<ValueSymmetryObject*>(s.ref);
VariableSequenceSymmetryObject* varseqref =
dynamic_cast<VariableSequenceSymmetryObject*>(s.ref);
ValueSequenceSymmetryObject* valseqref =
dynamic_cast<ValueSequenceSymmetryObject*>(s.ref);
if (varref) {
int n = varref->nxs;
int* indices = home.alloc<int>(n);
for (int i = 0 ; i < n ; i++) {
VariableMap::const_iterator index = variableMap.find(varref->xs[i]);
if (index == variableMap.end())
throw LDSBUnbranchedVariable("VariableSymmetryObject::createBool");
indices[i] = index->second;
}
return new (home) VariableSymmetryImp<BoolView>(home, indices, n);
}
if (valref) {
int n = valref->values.size();
int *vs = home.alloc<int>(n);
int i = 0;
for (IntSetValues v(valref->values) ; v() ; ++v) {
vs[i] = v.val();
i++;
}
return new (home) ValueSymmetryImp<BoolView>(home, vs, n);
}
if (varseqref) {
int n = varseqref->nxs;
int* indices = home.alloc<int>(n);
for (int i = 0 ; i < n ; i++) {
VariableMap::const_iterator index =
variableMap.find(varseqref->xs[i]);
if (index == variableMap.end())
throw LDSBUnbranchedVariable("VariableSequenceSymmetryObject::createBool");
indices[i] = index->second;
}
return new (home) VariableSequenceSymmetryImp<BoolView>(home, indices,
n, varseqref->seq_size);
}
if (valseqref) {
unsigned int n = valseqref->values.size();
int *vs = home.alloc<int>(n);
for (unsigned int i = 0 ; i < n ; i++)
vs[i] = valseqref->values[i];
return new (home) ValueSequenceSymmetryImp<BoolView>(home, vs, n,
valseqref->seq_size);
}
GECODE_NEVER;
return NULL;
}
}}}
namespace Gecode {
using namespace Int::LDSB;
void
branch(Home home, const IntVarArgs& x,
IntVarBranch vars, IntValBranch vals,
const Symmetries& syms,
IntBranchFilter bf,
IntVarValPrint vvp) {
using namespace Int;
if (home.failed()) return;
vars.expand(home,x);
ViewArray<IntView> xv(home,x);
ViewSel<IntView>* vs[1] = {
Branch::viewsel(home,vars)
};
switch (vals.select()) {
case IntValBranch::SEL_SPLIT_MIN:
case IntValBranch::SEL_SPLIT_MAX:
case IntValBranch::SEL_RANGE_MIN:
case IntValBranch::SEL_RANGE_MAX:
case IntValBranch::SEL_VALUES_MIN:
case IntValBranch::SEL_VALUES_MAX:
throw LDSBBadValueSelection("Int::LDSB::branch");
break;
case IntValBranch::SEL_VAL_COMMIT:
if (vals.commit())
throw LDSBBadValueSelection("Int::LDSB::branch");
// If vals.commit() is valid, it means it will commit with
// binary branching, which is OK for LDSB, so we fall through.
default:
// Construct mapping from each variable in the array to its index
// in the array.
VariableMap variableMap;
for (int i = 0 ; i < x.size() ; i++)
variableMap[x[i].varimp()] = i;
// Convert the modelling-level Symmetries object into an array of
// SymmetryImp objects.
int n = syms.size();
SymmetryImp<IntView>** array =
static_cast<Space&>(home).alloc<SymmetryImp<IntView>* >(n);
for (int i = 0 ; i < n ; i++) {
array[i] = createIntSym(home, syms[i], variableMap);
}
postldsbbrancher<IntView,1,int,2>
(home,xv,vs,Branch::valselcommit(home,vals),
array,n,bf,vvp);
}
}
void
branch(Home home, const IntVarArgs& x,
TieBreak<IntVarBranch> vars, IntValBranch vals,
const Symmetries& syms,
IntBranchFilter bf,
IntVarValPrint vvp) {
using namespace Int;
if (home.failed()) return;
vars.a.expand(home,x);
if ((vars.a.select() == IntVarBranch::SEL_NONE) ||
(vars.a.select() == IntVarBranch::SEL_RND))
vars.b = INT_VAR_NONE();
vars.b.expand(home,x);
if ((vars.b.select() == IntVarBranch::SEL_NONE) ||
(vars.b.select() == IntVarBranch::SEL_RND))
vars.c = INT_VAR_NONE();
vars.c.expand(home,x);
if ((vars.c.select() == IntVarBranch::SEL_NONE) ||
(vars.c.select() == IntVarBranch::SEL_RND))
vars.d = INT_VAR_NONE();
vars.d.expand(home,x);
if (vars.b.select() == IntVarBranch::SEL_NONE) {
branch(home,x,vars.a,vals,syms,bf,vvp);
} else {
// Construct mapping from each variable in the array to its index
// in the array.
VariableMap variableMap;
for (int i = 0 ; i < x.size() ; i++)
variableMap[x[i].varimp()] = i;
// Convert the modelling-level Symmetries object into an array of
// SymmetryImp objects.
int n = syms.size();
SymmetryImp<IntView>** array =
static_cast<Space&>(home).alloc<SymmetryImp<IntView>* >(n);
for (int i = 0 ; i < n ; i++) {
array[i] = createIntSym(home, syms[i], variableMap);
}
ViewArray<IntView> xv(home,x);
if (vars.c.select() == IntVarBranch::SEL_NONE) {
ViewSel<IntView>* vs[2] = {
Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
};
switch (vals.select()) {
case IntValBranch::SEL_SPLIT_MIN:
case IntValBranch::SEL_SPLIT_MAX:
case IntValBranch::SEL_RANGE_MIN:
case IntValBranch::SEL_RANGE_MAX:
case IntValBranch::SEL_VALUES_MIN:
case IntValBranch::SEL_VALUES_MAX:
throw LDSBBadValueSelection("Int::LDSB::branch");
break;
case IntValBranch::SEL_VAL_COMMIT:
if (vals.commit())
throw LDSBBadValueSelection("Int::LDSB::branch");
// If vals.commit() is valid, it means it will commit with
// binary branching, which is OK for LDSB, so we fall through.
default:
postldsbbrancher<IntView,2,int,2>
(home,xv,vs,Branch::valselcommit(home,vals),
array,n,bf,vvp);
}
} else if (vars.d.select() == IntVarBranch::SEL_NONE) {
ViewSel<IntView>* vs[3] = {
Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
Branch::viewsel(home,vars.c)
};
switch (vals.select()) {
case IntValBranch::SEL_SPLIT_MIN:
case IntValBranch::SEL_SPLIT_MAX:
case IntValBranch::SEL_RANGE_MIN:
case IntValBranch::SEL_RANGE_MAX:
case IntValBranch::SEL_VALUES_MIN:
case IntValBranch::SEL_VALUES_MAX:
throw LDSBBadValueSelection("Int::LDSB::branch");
break;
case IntValBranch::SEL_VAL_COMMIT:
if (vals.commit())
throw LDSBBadValueSelection("Int::LDSB::branch");
// If vals.commit() is valid, it means it will commit with
// binary branching, which is OK for LDSB, so we fall through.
default:
postldsbbrancher<IntView,3,int,2>
(home,xv,vs,Branch::valselcommit(home,vals),
array,n,bf,vvp);
}
} else {
ViewSel<IntView>* vs[4] = {
Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
};
switch (vals.select()) {
case IntValBranch::SEL_SPLIT_MIN:
case IntValBranch::SEL_SPLIT_MAX:
case IntValBranch::SEL_RANGE_MIN:
case IntValBranch::SEL_RANGE_MAX:
case IntValBranch::SEL_VALUES_MIN:
case IntValBranch::SEL_VALUES_MAX:
throw LDSBBadValueSelection("Int::LDSB::branch");
break;
case IntValBranch::SEL_VAL_COMMIT:
if (vals.commit())
throw LDSBBadValueSelection("Int::LDSB::branch");
// If vals.commit() is valid, it means it will commit with
// binary branching, which is OK for LDSB, so we fall through.
default:
postldsbbrancher<IntView,4,int,2>
(home,xv,vs,Branch::valselcommit(home,vals),
array,n,bf,vvp);
}
}
}
}
void
branch(Home home, const BoolVarArgs& x,
BoolVarBranch vars, BoolValBranch vals,
const Symmetries& syms,
BoolBranchFilter bf,
BoolVarValPrint vvp) {
using namespace Int;
if (home.failed()) return;
vars.expand(home,x);
ViewArray<BoolView> xv(home,x);
ViewSel<BoolView>* vs[1] = {
Branch::viewsel(home,vars)
};
// Construct mapping from each variable in the array to its index
// in the array.
VariableMap variableMap;
for (int i = 0 ; i < x.size() ; i++)
variableMap[x[i].varimp()] = i;
// Convert the modelling-level Symmetries object into an array of
// SymmetryImp objects.
int n = syms.size();
SymmetryImp<BoolView>** array =
static_cast<Space&>(home).alloc<SymmetryImp<BoolView>* >(n);
for (int i = 0 ; i < n ; i++) {
array[i] = createBoolSym(home, syms[i], variableMap);
}
// Technically these "bad" value selection could in fact work with
// LDSB, because they degenerate to binary splitting for
// Booleans. Nonetheless, we explicitly forbid them for
// consistency with the integer version.
switch (vals.select()) {
case BoolValBranch::SEL_VAL_COMMIT:
if (vals.commit())
throw LDSBBadValueSelection("Int::LDSB::branch");
// If vals.commit() is valid, it means it will commit with
// binary branching, which is OK for LDSB, so we fall through.
default:
postldsbbrancher<BoolView,1,int,2>
(home,xv,vs,Branch::valselcommit(home,vals),array,n,bf,vvp);
}
}
void
branch(Home home, const BoolVarArgs& x,
TieBreak<BoolVarBranch> vars, BoolValBranch vals,
const Symmetries& syms,
BoolBranchFilter bf,
BoolVarValPrint vvp) {
using namespace Int;
if (home.failed()) return;
vars.a.expand(home,x);
if ((vars.a.select() == BoolVarBranch::SEL_NONE) ||
(vars.a.select() == BoolVarBranch::SEL_RND))
vars.b = BOOL_VAR_NONE();
vars.b.expand(home,x);
if ((vars.b.select() == BoolVarBranch::SEL_NONE) ||
(vars.b.select() == BoolVarBranch::SEL_RND))
vars.c = BOOL_VAR_NONE();
vars.c.expand(home,x);
if ((vars.c.select() == BoolVarBranch::SEL_NONE) ||
(vars.c.select() == BoolVarBranch::SEL_RND))
vars.d = BOOL_VAR_NONE();
vars.d.expand(home,x);
if (vars.b.select() == BoolVarBranch::SEL_NONE) {
branch(home,x,vars.a,vals,syms,bf,vvp);
} else {
// Construct mapping from each variable in the array to its index
// in the array.
VariableMap variableMap;
for (int i = 0 ; i < x.size() ; i++)
variableMap[x[i].varimp()] = i;
// Convert the modelling-level Symmetries object into an array of
// SymmetryImp objects.
int n = syms.size();
SymmetryImp<BoolView>** array =
static_cast<Space&>(home).alloc<SymmetryImp<BoolView>* >(n);
for (int i = 0 ; i < n ; i++) {
array[i] = createBoolSym(home, syms[i], variableMap);
}
// Technically these "bad" value selection could in fact work with
// LDSB, because they degenerate to binary splitting for
// Booleans. Nonetheless, we explicitly forbid them for
// consistency with the integer version.
switch (vals.select()) {
case BoolValBranch::SEL_VAL_COMMIT:
if (vals.commit())
throw LDSBBadValueSelection("Int::LDSB::branch");
// If vals.commit() is valid, it means it will commit with
// binary branching, which is OK for LDSB, so we fall through.
default:
;
// Do nothing and continue.
}
ViewArray<BoolView> xv(home,x);
ValSelCommitBase<BoolView,int>*
vsc = Branch::valselcommit(home,vals);
if (vars.c.select() == BoolVarBranch::SEL_NONE) {
ViewSel<BoolView>* vs[2] = {
Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
};
postldsbbrancher<BoolView,2,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
} else if (vars.d.select() == BoolVarBranch::SEL_NONE) {
ViewSel<BoolView>* vs[3] = {
Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
Branch::viewsel(home,vars.c)
};
postldsbbrancher<BoolView,3,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
} else {
ViewSel<BoolView>* vs[4] = {
Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
};
postldsbbrancher<BoolView,4,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
}
}
}
}
// STATISTICS: int-branch
Gecode::ArgArrayBase::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1607
Gecode::ArgArray
Argument array for non-primitive types.
Definition array.hpp:691
Gecode::BoolValBranch
Which values to select for branching first.
Definition int.hh:4889
Gecode::BoolValBranch::SEL_VAL_COMMIT
@ SEL_VAL_COMMIT
Select value according to user-defined functions.
Definition int.hh:4896
Gecode::BoolValBranch::select
Select select(void) const
Return selection strategy.
Definition val.hpp:124
Gecode::BoolVarArgs
Passing Boolean variables.
Definition int.hh:712
Gecode::BoolVarBranch
Which Boolean variable to select for branching.
Definition int.hh:4656
Gecode::BoolVarBranch::expand
void expand(Home home, const BoolVarArgs &x)
Expand decay factor into AFC or action.
Definition var.hpp:345
Gecode::BoolVarBranch::SEL_RND
@ SEL_RND
Random (uniform, for tie breaking).
Definition int.hh:4661
Gecode::BoolVarBranch::SEL_NONE
@ SEL_NONE
First unassigned.
Definition int.hh:4660
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Home::failed
bool failed(void) const
Check whether corresponding space is failed.
Definition core.hpp:4048
Gecode::IntArgs
Passing integer arguments.
Definition int.hh:628
Gecode::IntSetValues
Value iterator for integer sets.
Definition int.hh:333
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::IntSet::size
unsigned int size(void) const
Return size (cardinality) of set.
Definition int-set-1.hpp:198
Gecode::IntValBranch
Which values to select for branching first.
Definition int.hh:4854
Gecode::IntValBranch::SEL_VALUES_MIN
@ SEL_VALUES_MIN
Select all values starting from smallest.
Definition int.hh:4867
Gecode::IntValBranch::SEL_SPLIT_MAX
@ SEL_SPLIT_MAX
Select values greater than mean of smallest and largest value.
Definition int.hh:4863
Gecode::IntValBranch::SEL_RANGE_MAX
@ SEL_RANGE_MAX
Select the largest range of the variable domain if it has several ranges, otherwise select values gre...
Definition int.hh:4865
Gecode::IntValBranch::SEL_RANGE_MIN
@ SEL_RANGE_MIN
Select the smallest range of the variable domain if it has several ranges, otherwise select values no...
Definition int.hh:4864
Gecode::IntValBranch::SEL_VALUES_MAX
@ SEL_VALUES_MAX
Select all values starting from largest.
Definition int.hh:4868
Gecode::IntValBranch::SEL_VAL_COMMIT
@ SEL_VAL_COMMIT
Select value according to user-defined functions.
Definition int.hh:4866
Gecode::IntValBranch::SEL_SPLIT_MIN
@ SEL_SPLIT_MIN
Select values not greater than mean of smallest and largest value.
Definition int.hh:4862
Gecode::IntValBranch::select
Select select(void) const
Return selection strategy.
Definition val.hpp:49
Gecode::IntVarArgs
Passing integer variables.
Definition int.hh:656
Gecode::IntVarBranch
Which integer variable to select for branching.
Definition int.hh:4570
Gecode::IntVarBranch::expand
void expand(Home home, const IntVarArgs &x)
Expand AFC, action, and CHB.
Definition var.hpp:74
Gecode::IntVarBranch::SEL_RND
@ SEL_RND
Random (uniform, for tie breaking).
Definition int.hh:4575
Gecode::IntVarBranch::SEL_NONE
@ SEL_NONE
First unassigned.
Definition int.hh:4574
Gecode::IntVar
Integer variables.
Definition int.hh:371
Gecode::IntVar::min
int min(void) const
Return minimum of domain.
Definition int.hpp:62
Gecode::IntVar::max
int max(void) const
Return maximum of domain.
Definition int.hpp:70
Gecode::Int::LDSBBadValueSelection
Exception: Value selection incompatible with LDSB
Definition exception.hpp:157
Gecode::Int::LDSBUnbranchedVariable
Exception: Variable in symmetry not branched on
Definition exception.hpp:150
Gecode::Int::LDSB::SymmetryImp
Implementation of a single symmetry.
Definition ldsb.hh:162
Gecode::Int::LDSB::ValueSequenceSymmetryImp
Implementation of a value sequence symmetry.
Definition ldsb.hh:266
Gecode::Int::LDSB::ValueSequenceSymmetryObject
Implementation of a value sequence symmetry at the modelling level.
Definition ldsb.hh:150
Gecode::Int::LDSB::ValueSequenceSymmetryObject::values
IntArgs values
Array of values in symmetry.
Definition ldsb.hh:153
Gecode::Int::LDSB::ValueSequenceSymmetryObject::seq_size
int seq_size
Size of each sequence in symmetry.
Definition ldsb.hh:155
Gecode::Int::LDSB::ValueSymmetryImp
Implementation of a value symmetry.
Definition ldsb.hh:204
Gecode::Int::LDSB::ValueSymmetryObject
Implementation of a value symmetry at the modelling level.
Definition ldsb.hh:128
Gecode::Int::LDSB::ValueSymmetryObject::values
IntSet values
Set of symmetric values.
Definition ldsb.hh:131
Gecode::Int::LDSB::VariableMap
Map from variable implementation to index.
Definition ldsb.cpp:130
Gecode::Int::LDSB::VariableSequenceSymmetryImp
Implementation of a variable sequence symmetry.
Definition ldsb.hh:224
Gecode::Int::LDSB::VariableSequenceSymmetryObject
Implementation of a variable sequence symmetry at the modelling level.
Definition ldsb.hh:136
Gecode::Int::LDSB::VariableSequenceSymmetryObject::seq_size
int seq_size
Size of each sequence in symmetry.
Definition ldsb.hh:143
Gecode::Int::LDSB::VariableSequenceSymmetryObject::nxs
int nxs
Number of variables in symmetry.
Definition ldsb.hh:141
Gecode::Int::LDSB::VariableSequenceSymmetryObject::xs
VarImpBase ** xs
Array of variables in symmetry.
Definition ldsb.hh:139
Gecode::Int::LDSB::VariableSymmetryImp
Implementation of a variable symmetry.
Definition ldsb.hh:183
Gecode::Int::LDSB::VariableSymmetryObject
Implementation of a variable symmetry at the modelling level.
Definition ldsb.hh:116
Gecode::Int::LDSB::VariableSymmetryObject::nxs
int nxs
Number of variables in symmetry.
Definition ldsb.hh:121
Gecode::Int::LDSB::VariableSymmetryObject::xs
VarImpBase ** xs
Array of variables in symmetry.
Definition ldsb.hh:119
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Space::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2837
Gecode::Symmetries
Collection of symmetries.
Definition int.hh:5292
Gecode::SymmetryHandle
A reference-counted pointer to a SymmetryObject.
Definition int.hh:5255
Gecode::SymmetryHandle::ref
Int::LDSB::SymmetryObject * ref
Symmetry object that this handle refers to.
Definition int.hh:5258
Gecode::TieBreak
Combine variable selection criteria for tie-breaking.
Definition tiebreak.hpp:38
Gecode::TieBreak::b
VarBranch b
Definition tiebreak.hpp:41
Gecode::TieBreak::a
VarBranch a
Branching criteria to try in order.
Definition tiebreak.hpp:41
Gecode::TieBreak::c
VarBranch c
Definition tiebreak.hpp:41
Gecode::TieBreak::d
VarBranch d
Definition tiebreak.hpp:41
Gecode::ValBranch::commit
BranchCommit commit(void) const
Return commit function.
Definition val.hpp:102
Gecode::ValSelCommitBase
Base class for value selection and commit.
Definition val-sel-commit.hpp:44
Gecode::ViewArray
View arrays.
Definition array.hpp:253
Gecode::ViewSel
Abstract class for view selection.
Definition view-sel.hpp:44
branch.hh
Gecode::branch
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
Gecode::IntBranchFilter
std::function< bool(const Space &home, IntVar x, int i)> IntBranchFilter
Branch filter function type for integer variables.
Definition int.hh:4176
Gecode::BoolBranchFilter
std::function< bool(const Space &home, BoolVar x, int i)> BoolBranchFilter
Branch filter function type for Boolean variables.
Definition int.hh:4186
ldsb.hh
Gecode::Int::Branch::viewsel
ViewSel< IntView > * viewsel(Space &home, const IntVarBranch &ivb)
Return view selectors for integer views.
Definition view-sel.cpp:39
Gecode::Int::Branch::valselcommit
ValSelCommitBase< IntView, int > * valselcommit(Space &home, const IntValBranch &ivb)
Return value and commit for integer views.
Definition val-sel-commit.cpp:39
Gecode::Int::LDSB
Symmetry breaking for integer variables.
Definition int.hh:5246
Gecode::Int::LDSB::findVar
std::pair< int, int > findVar(int *indices, unsigned int n_values, unsigned int seq_size, int index)
Find the location of an integer in a collection of sequences.
Definition ldsb.cpp:42
Gecode::Int::LDSB::createBoolSym
SymmetryImp< BoolView > * createBoolSym(Space &home, const SymmetryHandle &s, VariableMap variableMap)
Create a boolean symmetry implementation from a symmetry handle.
Definition ldsb.cpp:197
Gecode::Int::LDSB::postldsbbrancher
void postldsbbrancher(Home home, ViewArray< View > &x, ViewSel< View > *vs[n], ValSelCommitBase< View, Val > *vsc, SymmetryImp< View > **syms, int nsyms, BranchFilter< typename View::VarType > bf, VarValPrint< typename View::VarType, Val > vvp)
Post LDSB brancher.
Definition brancher.hpp:275
Gecode::Int::LDSB::createIntSym
SymmetryImp< IntView > * createIntSym(Space &home, const SymmetryHandle &s, VariableMap variableMap)
Create an integer symmetry implementation from a symmetry handle.
Definition ldsb.cpp:140
Gecode::Int
Finite domain integers.
Gecode
Gecode toplevel namespace
Gecode::ValueSymmetry
SymmetryHandle ValueSymmetry(const IntArgs &v)
Values in v are interchangeable.
Definition ldsb.cpp:81
Gecode::ValueSequenceSymmetry
SymmetryHandle ValueSequenceSymmetry(const IntArgs &v, int ss)
Value sequences in v of size ss are interchangeable.
Definition ldsb.cpp:102
Gecode::values_reflect
SymmetryHandle values_reflect(int lower, int upper)
The values from lower to upper (inclusive) can be reflected.
Definition ldsb.cpp:106
Gecode::INT_VAR_NONE
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
Gecode::BOOL_VAR_NONE
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:364
Gecode::IntVarValPrint
std::function< void(const Space &home, const Brancher &b, unsigned int a, IntVar x, int i, const int &n, std::ostream &o)> IntVarValPrint
Function type for printing branching alternatives for integer variables.
Definition int.hh:4552
Gecode::VariableSymmetry
SymmetryHandle VariableSymmetry(const IntVarArgs &x)
Variables in x are interchangeable.
Definition ldsb.cpp:62
Gecode::VariableSequenceSymmetry
SymmetryHandle VariableSequenceSymmetry(const IntVarArgs &x, int ss)
Variable sequences in x of size ss are interchangeable.
Definition ldsb.cpp:90
Gecode::BoolVarValPrint
std::function< void(const Space &home, const Brancher &b, unsigned int a, BoolVar x, int i, const int &n, std::ostream &o)> BoolVarValPrint
Function type for printing branching alternatives for Boolean variables.
Definition int.hh:4559
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56