argmax.hpp
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, 2015
*
* 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/rel.hh>
namespace Gecode { namespace Int { namespace Arithmetic {
template<class VA, class VB, bool tiebreak>
forceinline
ArgMax<VA,VB,tiebreak>::ArgMax(Home home, IdxViewArray<VA>& x0, VB y0)
: Propagator(home), x(x0), y(y0) {
x.subscribe(home,*this,PC_INT_BND);
y.subscribe(home,*this,PC_INT_DOM);
}
template<class VA, class VB, bool tiebreak>
ExecStatus
ArgMax<VA,VB,tiebreak>::post(Home home, IdxViewArray<VA>& x, VB y) {
assert(x.size() > 0);
if (x.size() == 1) {
GECODE_ME_CHECK(y.eq(home,x[0].idx));
} else if (y.assigned()) {
int max=0;
while (x[max].idx < y.val())
max++;
assert(x[max].idx == y.val());
if (tiebreak)
for (int i=0; i<max; i++)
GECODE_ES_CHECK((Rel::Le<VA,VA>::post(home,
x[i].view,x[max].view)));
else
for (int i=0; i<max; i++)
GECODE_ES_CHECK((Rel::Lq<VA,VA>::post(home,
x[i].view,x[max].view)));
for (int i=max+1; i<x.size(); i++)
GECODE_ES_CHECK((Rel::Lq<VA,VA>::post(home,
x[i].view,x[max].view)));
} else {
(void) new (home) ArgMax<VA,VB,tiebreak>(home,x,y);
}
return ES_OK;
}
template<class VA, class VB, bool tiebreak>
forceinline
ArgMax<VA,VB,tiebreak>::ArgMax(Space& home, ArgMax<VA,VB,tiebreak>& p)
: Propagator(home,p) {
x.update(home,p.x);
y.update(home,p.y);
}
template<class VA, class VB, bool tiebreak>
Actor*
ArgMax<VA,VB,tiebreak>::copy(Space& home) {
return new (home) ArgMax<VA,VB,tiebreak>(home,*this);
}
template<class VA, class VB, bool tiebreak>
PropCost
ArgMax<VA,VB,tiebreak>::cost(const Space&, const ModEventDelta&) const {
return PropCost::linear(PropCost::LO,x.size()+1);
}
template<class VA, class VB, bool tiebreak>
void
ArgMax<VA,VB,tiebreak>::reschedule(Space& home) {
x.reschedule(home,*this,PC_INT_BND);
y.reschedule(home,*this,PC_INT_DOM);
}
template<class VA, class VB, bool tiebreak>
ExecStatus
ArgMax<VA,VB,tiebreak>::propagate(Space& home, const ModEventDelta&) {
/*
* A key invariant is as follows: for each value i in the domain
* of y there is an index-value pair with index i in x.
*/
// Compute lower and upper bounds for the maximum and its first position.
int p = x[0].idx;
int l = x[0].view.min();
int u = x[0].view.max();
for (int i=1; i<x.size(); i++) {
if (l < x[i].view.min()) {
p = x[i].idx; l = x[i].view.min();
}
if (u < x[i].view.max())
u = x[i].view.max();
}
// Eliminate elements from x and y that are too small
{
Region r;
// Values to delete from y
int* d=r.alloc<int>(y.size());
// Number of values to delete
int n = 0;
int i=0, j=0;
ViewValues<VB> iy(y);
while ((i < x.size()) && iy()) {
if (x[i].idx == iy.val()) {
if (x[i].view.max() < l) {
x[i].view.cancel(home,*this,PC_INT_BND);
d[n++]=x[i].idx;
} else {
x[j++]=x[i];
}
++iy;
} else {
assert(x[i].idx < iy.val());
if (x[i].view.max() < l) {
x[i].view.cancel(home,*this,PC_INT_BND);
} else {
x[j++]=x[i];
}
}
i++;
}
while (i < x.size())
if (x[i].view.max() < l) {
x[i].view.cancel(home,*this,PC_INT_BND); i++;
} else {
x[j++]=x[i++];
}
x.size(j);
if (static_cast<unsigned int>(n) == y.size())
return ES_FAILED;
Iter::Values::Array id(d,n);
GECODE_ME_CHECK(y.minus_v(home,id,false));
}
/*
* Now the following invariant holds:
* - for all q in y: u >= x(q).max() >= l
* - if l==u, then exists q in y: x(q).max = u
*/
if (tiebreak && (l == u))
GECODE_ME_CHECK(y.lq(home,p));
if (y.assigned()) {
int max=0;
while (x[max].idx < y.val())
max++;
assert(x[max].idx == y.val());
if (tiebreak)
for (int i=0; i<max; i++)
GECODE_ES_CHECK((Rel::Le<VA,VA>::post(home(*this),
x[i].view,x[max].view)));
else
for (int i=0; i<max; i++)
GECODE_ES_CHECK((Rel::Lq<VA,VA>::post(home(*this),
x[i].view,x[max].view)));
for (int i=max+1; i<x.size(); i++)
GECODE_ES_CHECK((Rel::Lq<VA,VA>::post(home(*this),
x[i].view,x[max].view)));
return home.ES_SUBSUMED(*this);
}
// Recompute the upper bound for elements in y
{
ViewValues<VB> iy(y);
int i=0;
// Skip smaller elements
while (x[i].idx < y.min())
i++;
u=x[i].view.max();
// Skip the minimal element
i++; ++iy;
while (iy()) {
if (x[i].idx == iy.val()) {
u = std::max(u,x[i].view.max());
++iy;
} else {
assert(x[i].idx < iy.val());
}
i++;
}
}
// Constrain elements in x but not in y
{
int i = 0;
// Elements which must be smaller (for tiebreaking)
if (tiebreak)
while ((i < x.size()) && (x[i].idx < y.min())) {
GECODE_ME_CHECK(x[i].view.le(home,u));
i++;
}
else
while ((i < x.size()) && (x[i].idx < y.min())) {
GECODE_ME_CHECK(x[i].view.lq(home,u));
i++;
}
assert(x[i].idx == y.min());
// Elements which cannot be larger
ViewValues<VB> iy(y);
// Skip the minimal element
i++; ++iy;
while ((i < x.size()) && iy()) {
if (x[i].idx == iy.val()) {
++iy;
} else {
assert(x[i].idx < iy.val());
GECODE_ME_CHECK(x[i].view.lq(home,u));
}
i++;
}
while (i < x.size()) {
assert(x[i].idx > y.max());
GECODE_ME_CHECK(x[i].view.lq(home,u));
i++;
}
}
return tiebreak ? ES_NOFIX : ES_FIX;
}
template<class VA, class VB, bool tiebreak>
forceinline size_t
ArgMax<VA,VB,tiebreak>::dispose(Space& home) {
x.cancel(home,*this,PC_INT_BND);
y.cancel(home,*this,PC_INT_DOM);
(void) Propagator::dispose(home);
return sizeof(*this);
}
}}}
// STATISTICS: int-prop
Gecode::Actor
Base-class for both propagators and branchers.
Definition core.hpp:628
Gecode::Actor::dispose
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3252
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Int::Arithmetic::ArgMax::x
IdxViewArray< VA > x
Map of index and views.
Definition arithmetic.hh:263
Gecode::Int::Arithmetic::ArgMax::y
VB y
Position of maximum view (maximal argument).
Definition arithmetic.hh:265
Gecode::Int::Arithmetic::ArgMax::ArgMax
ArgMax(Space &home, ArgMax &p)
Constructor for cloning p.
Definition argmax.hpp:76
Gecode::Int::Arithmetic::ArgMax::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition argmax.hpp:103
Gecode::Int::Arithmetic::ArgMax::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition argmax.hpp:84
Gecode::Int::Arithmetic::ArgMax::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition argmax.hpp:90
Gecode::Int::Arithmetic::ArgMax::post
static ExecStatus post(Home home, IdxViewArray< VA > &x, VB y)
Post propagator .
Definition argmax.hpp:48
Gecode::Int::Arithmetic::ArgMax::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition argmax.hpp:255
Gecode::Int::Arithmetic::ArgMax::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition argmax.hpp:96
Gecode::Int::IdxViewArray
An array of IdxView pairs.
Definition idx-view.hh:67
Gecode::Int::Rel::Le::post
static ExecStatus post(Home home, V0 x0, V1 x1)
Post propagator .
Definition lq-le.hpp:91
Gecode::Int::Rel::Lq::post
static ExecStatus post(Home home, V0 x0, V1 x1)
Post propagator .
Definition lq-le.hpp:50
Gecode::Int::ViewValues
Value iterator for integer views.
Definition view.hpp:94
Gecode::Iter::Ranges::ToValues::val
int val(void) const
Return current value.
Definition ranges-values.hpp:129
Gecode::Iter::Values::Array
Value iterator for array of integers
Definition values-array.hpp:46
Gecode::PropCost
Propagation cost.
Definition core.hpp:486
Gecode::PropCost::linear
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:4796
Gecode::PropCost::LO
@ LO
Cheap.
Definition core.hpp:513
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::id
unsigned int id(void) const
Return propagator id.
Definition core.hpp:3542
Gecode::Propagator::Propagator
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3498
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Space::ES_SUBSUMED
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
GECODE_ES_CHECK
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
rel.hh
Gecode::Int::Arithmetic
Numerical (arithmetic) propagators.
Gecode::Int
Finite domain integers.
Gecode::Int::PC_INT_BND
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:91
Gecode::Int::PC_INT_DOM
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
Gecode
Gecode toplevel namespace
Gecode::tiebreak
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
Definition tiebreak.hpp:80
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
Gecode::ES_FIX
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
Gecode::ES_FAILED
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
Gecode::ES_NOFIX
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49
forceinline
#define forceinline
Definition config.hpp:187