branch.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2017
*
* 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/flatzinc/branch.hh>
namespace Gecode { namespace FlatZinc {
void
PosIntChoice::archive(Archive& e) const {
Choice::archive(e);
e << _pos;
e << _val;
}
bool
IntBoolBrancherBase::status(const Space&) const {
if (start < x.size()) {
for (int i=start; i < x.size(); i++)
if (!x[i].assigned()) {
start = i;
return true;
}
start = x.size();
}
for (int i=start-x.size(); i < y.size(); i++)
if (!y[i].assigned()) {
start = x.size() + i;
return true;
}
return false;
}
ExecStatus
IntBoolBrancherBase::commit(Space& home, const Choice& _c,
unsigned int b) {
const PosIntChoice& c
= static_cast<const PosIntChoice&>(_c);
int p=c.pos(); int n=c.val();
if (p < x.size()) {
return me_failed(xvsc->commit(home,b,x[p],p,n)) ?
ES_FAILED : ES_OK;
} else {
p -= x.size();
return me_failed(yvsc->commit(home,b,y[p],p,n)) ?
ES_FAILED : ES_OK;
}
}
NGL*
IntBoolBrancherBase::ngl(Space& home, const Choice& _c,
unsigned int b) const {
const PosIntChoice& c
= static_cast<const PosIntChoice&>(_c);
int p=c.pos(); int n=c.val();
if (p < x.size()) {
return xvsc->ngl(home,b,x[p],n);
} else {
p -= x.size();
return yvsc->ngl(home,b,y[p],n);
}
}
void
IntBoolBrancherBase::print(const Space& home, const Choice& _c,
unsigned int b,
std::ostream& o) const {
const PosIntChoice& c
= static_cast<const PosIntChoice&>(_c);
int p=c.pos(); int n=c.val();
if (p < x.size()) {
xvsc->print(home,b,x[p],p,n,o);
} else {
p -= x.size();
yvsc->print(home,b,y[p],p,n,o);
}
}
const Choice*
IntBoolBrancherBase::choice(const Space& home, Archive& e) {
(void) home;
int p; e >> p;
int v; e >> v;
return new PosIntChoice(*this,2,p,v);
}
void
branch(Home home, const IntVarArgs& x, const BoolVarArgs& y,
IntBoolVarBranch vars, IntValBranch vals) {
if (home.failed()) return;
vars.expand(home,x,y);
ViewArray<Int::IntView> xv(home,x);
ViewArray<Int::BoolView> yv(home,y);
ValSelCommitBase<Int::IntView,int>* xvsc =
Int::Branch::valselcommit(home,vals);
ValSelCommitBase<Int::BoolView,int>* yvsc =
Int::Branch::valselcommit(home,i2b(vals));
switch (vars.select()) {
case IntBoolVarBranch::SEL_AFC_MAX:
{
MeritMaxAFC m(home,vars);
IntBoolBrancher<MeritMaxAFC>::post(home,xv,yv,m,xvsc,yvsc);
}
break;
case IntBoolVarBranch::SEL_ACTION_MAX:
{
MeritMaxAction m(home,vars);
IntBoolBrancher<MeritMaxAction>::post(home,xv,yv,m,xvsc,yvsc);
}
break;
case IntBoolVarBranch::SEL_CHB_MAX:
{
MeritMaxCHB m(home,vars);
IntBoolBrancher<MeritMaxCHB>::post(home,xv,yv,m,xvsc,yvsc);
}
break;
case IntBoolVarBranch::SEL_AFC_SIZE_MAX:
{
MeritMaxAFCSize m(home,vars);
IntBoolBrancher<MeritMaxAFCSize>::post(home,xv,yv,m,xvsc,yvsc);
}
break;
case IntBoolVarBranch::SEL_ACTION_SIZE_MAX:
{
MeritMaxActionSize m(home,vars);
IntBoolBrancher<MeritMaxActionSize>::post(home,xv,yv,m,xvsc,yvsc);
}
break;
case IntBoolVarBranch::SEL_CHB_SIZE_MAX:
{
MeritMaxCHBSize m(home,vars);
IntBoolBrancher<MeritMaxCHBSize>::post(home,xv,yv,m,xvsc,yvsc);
}
break;
default:
GECODE_NEVER;
}
}
}}
// STATISTICS: flatzinc-branch
Gecode::Archive
Archive representation
Definition archive.hpp:42
Gecode::BoolVarArgs
Passing Boolean variables.
Definition int.hh:712
Gecode::Brancher::Space
friend class Space
Definition core.hpp:1444
Gecode::Brancher::Choice
friend class Choice
Definition core.hpp:1445
Gecode::Choice
Choice for performing commit
Definition core.hpp:1412
Gecode::Choice::archive
virtual void archive(Archive &e) const
Archive into e.
Definition core.cpp:891
Gecode::FlatZinc::IntBoolBrancherBase::y
ViewArray< Int::BoolView > y
Boolean views to branch on.
Definition branch.hh:269
Gecode::FlatZinc::IntBoolBrancherBase::x
ViewArray< Int::IntView > x
Integer views to branch on.
Definition branch.hh:267
Gecode::FlatZinc::IntBoolBrancherBase::status
virtual bool status(const Space &home) const
Check status of brancher, return true if alternatives left.
Definition branch.cpp:48
Gecode::FlatZinc::IntBoolBrancherBase::yvsc
ValSelCommitBase< Int::BoolView, int > * yvsc
Boolean value selection and commit object.
Definition branch.hh:275
Gecode::FlatZinc::IntBoolBrancherBase::print
virtual void print(const Space &home, const Choice &c, unsigned int b, std::ostream &o) const
Print branch for choice c and alternative b.
Definition branch.cpp:96
Gecode::FlatZinc::IntBoolBrancherBase::ngl
virtual NGL * ngl(Space &home, const Choice &c, unsigned int b) const
Create no-good literal for choice c and alternative b.
Definition branch.cpp:82
Gecode::FlatZinc::IntBoolBrancherBase::commit
virtual ExecStatus commit(Space &home, const Choice &c, unsigned int b)
Perform commit for choice c and alternative b.
Definition branch.cpp:66
Gecode::FlatZinc::IntBoolBrancherBase::xvsc
ValSelCommitBase< Int::IntView, int > * xvsc
Integer value selection and commit object.
Definition branch.hh:273
Gecode::FlatZinc::IntBoolBrancherBase::choice
virtual const Choice * choice(Space &home)=0
Return choice.
Gecode::FlatZinc::IntBoolBrancherBase::start
int start
Unassigned views start here (might be in x or y).
Definition branch.hh:271
Gecode::FlatZinc::IntBoolBrancher::post
static void post(Home home, ViewArray< Int::IntView > x, ViewArray< Int::BoolView > y, Merit &m, ValSelCommitBase< Int::IntView, int > *xvsc, ValSelCommitBase< Int::BoolView, int > *yvsc)
Post brancher.
Definition branch.hpp:347
Gecode::FlatZinc::IntBoolVarBranch
Which integer or Boolean variable to select for branching.
Definition branch.hh:44
Gecode::FlatZinc::IntBoolVarBranch::expand
void expand(Home home, const IntVarArgs &x, const BoolVarArgs &y)
Expand AFC, action, and CHB.
Definition branch.hpp:84
Gecode::FlatZinc::IntBoolVarBranch::select
Select select(void) const
Return selection strategy.
Definition branch.hpp:53
Gecode::FlatZinc::IntBoolVarBranch::SEL_ACTION_SIZE_MAX
@ SEL_ACTION_SIZE_MAX
With largest action divided by domain size.
Definition branch.hh:52
Gecode::FlatZinc::IntBoolVarBranch::SEL_CHB_SIZE_MAX
@ SEL_CHB_SIZE_MAX
With largest CHB Q-score divided by domain size.
Definition branch.hh:53
Gecode::FlatZinc::IntBoolVarBranch::SEL_ACTION_MAX
@ SEL_ACTION_MAX
With highest action.
Definition branch.hh:49
Gecode::FlatZinc::IntBoolVarBranch::SEL_AFC_MAX
@ SEL_AFC_MAX
With largest accumulated failure count.
Definition branch.hh:48
Gecode::FlatZinc::IntBoolVarBranch::SEL_CHB_MAX
@ SEL_CHB_MAX
With highest CHB Q-score.
Definition branch.hh:50
Gecode::FlatZinc::IntBoolVarBranch::SEL_AFC_SIZE_MAX
@ SEL_AFC_SIZE_MAX
With largest accumulated failure count divided by domain size.
Definition branch.hh:51
Gecode::FlatZinc::MeritMaxAFCSize
Select by maximal AFC over size.
Definition branch.hh:146
Gecode::FlatZinc::MeritMaxAFC
Select by maximal AFC.
Definition branch.hh:126
Gecode::FlatZinc::MeritMaxActionSize
Select by maximal Action over size.
Definition branch.hh:186
Gecode::FlatZinc::MeritMaxAction
Select by maximal Action.
Definition branch.hh:166
Gecode::FlatZinc::MeritMaxCHBSize
Select by maximal CHB over size.
Definition branch.hh:226
Gecode::FlatZinc::MeritMaxCHB
Select by maximal CHB.
Definition branch.hh:206
Gecode::FlatZinc::PosIntChoice
Choice storing position and value
Definition branch.hh:246
Gecode::FlatZinc::PosIntChoice::archive
virtual void archive(Archive &e) const
Archive into e.
Definition branch.cpp:40
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::IntValBranch
Which values to select for branching first.
Definition int.hh:4854
Gecode::IntVarArgs
Passing integer variables.
Definition int.hh:656
Gecode::NGL
No-good literal recorded during search.
Definition core.hpp:1340
Gecode::ValSelCommitBase
Base class for value selection and commit.
Definition val-sel-commit.hpp:44
Gecode::ViewArray
View arrays.
Definition array.hpp:253
branch.hh
Gecode::me_failed
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
Gecode::FlatZinc
Interpreter for the FlatZinc language.
Gecode::FlatZinc::i2b
BoolValBranch i2b(const IntValBranch &ivb)
Map respective integer value selection to Boolean value selection.
Definition branch.hpp:421
Gecode::FlatZinc::branch
void branch(Home home, const IntVarArgs &x, const BoolVarArgs &y, IntBoolVarBranch vars, IntValBranch vals)
Branch function for integer and Boolean variables.
Definition branch.cpp:120
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
Gecode toplevel namespace
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
Gecode::ES_FAILED
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56