[gecode-users] Gecode BAB Questions
Christian Schulte
cschulte at kth.se
Wed Apr 3 09:52:50 CEST 2013
Hi Dean,
I tried to understand what you are doing but failed. This is not really a
Gecode issue but an issue how you model your problem. In particular your
statement that only six solutions are found while there are ten is a little
strange. What you could try, though, is: take the values for the variables
you believe are solutions which are missing and constrain your variables by
hand to these values to verify whether they are solutions according to your
model. Then try to remove some constraints to see which of the constraints
rule out your intended solutions.
Sorry for not being more helpful
Christian
--
Christian Schulte, Professor of Computer Science, KTH,
www.ict.kth.se/~cschulte/
-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Dean Hiller
Sent: Thursday, March 28, 2013 5:19 PM
To: users at gecode.org
Subject: [gecode-users] Gecode BAB Questions
I am very new to constraint programming, but by using the MPG have been able
to develop a fairly large Gecode application in a relatively short period of
time. Due to my lack of constraint programming knowledge, I may not have
selected the best methods for solving my particular problem, but what I have
done appears to work with two exceptions which are shown in the attached
program.
This program is the minimum program I could generate to show what I am doing
and to replicate my two problems.
In the attached program, I have an IntVar X which is to receive ordered
values from Y0, Y1, and Y2 along with an indication of from which Y the
value came.
The first problem I am having is that the program stops after finding 6 of
the 10 possible solutions and I don't understand how to debug this problem.
The second problem I am having is that the program fails to find any
solutions if the constraints on one of the Y variables results in it not
having any solutions even though there are other solutions for X.
I have this problem with both the 3.7.3 release and the
4.0.0 release.
I would appreciate any assistance you can provide.
Thanks,
Dean
#include <gecode/int.hh>
#include <gecode/search.hh>
#include <gecode/minimodel.hh>
using namespace Gecode;
typedef struct Y_s
{
IntVar nY;
} Y;
class GecodeTest3 : public Space {
protected:
int m_nMin;
int m_nMax;
int m_nNumY;
IntVar m_nX;
IntVarArray m_naX;
BoolVarArray m_baX;
int m_nYIndex;
IntVar m_nY0;
IntVar m_nY1;
IntVar m_nY2;
IntVar *m_vY[3];
IntVar m_nCost;
IntVarArray m_nValue;
IntArgs m_nC;
public:
void AddY(int* naY, int nSize)
{
m_nYIndex++;
*m_vY[m_nYIndex] = IntVar(*this, m_nMin, m_nMax);
ConstrainY(naY, nSize);
rel(*this, m_naX[m_nYIndex] == *m_vY[m_nYIndex]);
rel(*this, m_baX[m_nYIndex] == (m_naX[m_nYIndex] == m_nX));
branch(*this, *m_vY[m_nYIndex], INT_VAL_MIN());
}
void ConstrainY(int *naY, int nSize)
{
IntArgs nTemp;
for (int i = 0; i < nSize; i++)
{
nTemp << naY[i];
}
IntSet nsTemp(nTemp);
dom(*this, *m_vY[m_nYIndex], nsTemp);
}
int GetX(void)
{
return m_nX.val();
}
int GetWhichY(void)
{
return m_nValue[0].val();
}
int GetCost(void)
{
return m_nCost.val();
}
GecodeTest3(int nMin, int nMax, int nNumY) :
m_nMin(nMin), m_nMax(nMax), m_nNumY(nNumY), m_nYIndex(-1)
{
if (m_nMin < 0)
{
std::cout << "m_nMin must not be negative" <<
std::endl;
}
m_vY[0] = &m_nY0;
m_vY[1] = &m_nY1;
m_vY[2] = &m_nY2;
m_nX = IntVar(*this, m_nMin, m_nMax);
m_naX = IntVarArray(*this, m_nNumY, m_nMin, m_nMax);
m_baX = BoolVarArray(*this, m_nNumY, 0, 1);
m_nC << 1;
m_nC << m_nNumY;
int nTemp = m_nNumY * m_nMax + m_nNumY;
m_nCost = IntVar(*this, 0, nTemp);
nTemp = m_nMax > nNumY ? m_nMax : nNumY;
m_nValue = IntVarArray(*this, 2, 0, nTemp);
rel(*this, m_nX == min(m_naX));
element(*this, m_baX, m_nValue[0], 1);
rel(*this, m_nValue[1] == m_nX);
linear(*this, m_nC, m_nValue, IRT_EQ, m_nCost);
branch(*this, m_naX, INT_VAR_MIN_MIN(), INT_VAL_MIN());
branch(*this, m_nX, INT_VAL_MIN());
branch(*this, m_nValue[0], INT_VAL_MIN());
}
// search support
GecodeTest3(bool share, GecodeTest3& s) : Space(share, s) {
// s.print(std::cout);
m_vY[0] = &m_nY0;
m_vY[1] = &m_nY1;
m_vY[2] = &m_nY2;
m_nX.update(*this, share, s.m_nX);
m_naX.update(*this, share, s.m_naX);
m_baX.update(*this, share, s.m_baX);
m_nCost.update(*this, share, s.m_nCost);
m_nY0.update(*this, share, s.m_nY0);
m_nY1.update(*this, share, s.m_nY1);
m_nY2.update(*this, share, s.m_nY2);
m_nValue.update(*this, share, s.m_nValue);
for (int i = 0; i < 2; i++)
{
m_nC << s.m_nC[i];
}
}
virtual Space* copy(bool share) {
return new GecodeTest3(share,*this);
}
virtual void constrain(const Space& _b)
{
const GecodeTest3& b = static_cast<const GecodeTest3&>(_b);
rel(*this, m_nCost > b.m_nCost);
}
// print solution
void print(std::ostream& os) const {
os << "m_nX: " << m_nX << std::endl;
for (int i = 0; i < m_naX.size(); i++)
{
os << "m_naX[" << i << "]: " << m_naX[i] << " ";
os << "m_baX[" << i << "]: " << m_baX[i] << " ";
os << std::endl;
}
for (int i = 0; i < m_nC.size(); i++)
{
os << "m_nC[" << i << "]: " << m_nC[i] <<
std::endl;
}
for (int i = 0; i < m_nValue.size(); i++)
{
os << "m_nValue[" << i << "]: " << m_nValue[i] <<
std::endl;
}
os << "m_nCost: " << m_nCost << std::endl;
}
};
void BuildAndSolve(bool b2Y1)
{
int Y0[3] = {1, 3, 7};
int Y1[3] = {2, 4, 5};
int Y2[4] = {4, 6, 8, 9};
int Y1a[3] = {1, 3, 8};
// create model and search engine
GecodeTest3 *m = new GecodeTest3(0, 20, 3);
m->AddY(Y0, sizeof(Y0)/sizeof(int));
m->AddY(Y1, sizeof(Y1)/sizeof(int));
if (b2Y1)
{
m->ConstrainY(Y1a, sizeof(Y1a)/sizeof(int));
}
m->AddY(Y2, sizeof(Y2)/sizeof(int));
// m->print(std::cout);
bool bFailed = true;
BAB<GecodeTest3> e(m);
GecodeTest3 *s;
while (((s = e.next()) != 0))
{
bFailed = false;
// s->print(std::cout);
int X = s->GetX();
int whichY = s->GetWhichY();
int nCost = s->GetCost();
std::cout << "X=" << X << " from Y" << whichY << ". Cost="
<< nCost << std::endl;
// std::cout << std::endl;
delete s;
}
if (bFailed)
{
std::cout << "Model failed" << std::endl;
}
Search::Statistics stat = e.statistics();
std::cout << "Search Statistics" << std::endl;
std::cout << " Propagations: " << stat.propagate << std::endl;
std::cout << " Nodes: " << stat.node << std::endl;
std::cout << " Failures: " << stat.fail << std::endl;
std::cout << " Depth: " << stat.depth << std::endl;
int nPeakMemoryKB = static_cast<int>((stat.memory+1023) / 1024);
std::cout << " Peak Memory " << nPeakMemoryKB << "KB" <<
std::endl;
std::cout << std::endl;
delete m;
return;
}
int GecodeTest3Main(int argc, char* argv[]) {
std::cout << "One Y1 constraint" << std::endl;
BuildAndSolve(false);
std::cout << "Two Y1 constraints" << std::endl;
BuildAndSolve(true);
return 0;
}
Sample output:
One Y1 constraint
X=1 from Y0. Cost=3
X=2 from Y1. Cost=7
X=3 from Y0. Cost=9
X=4 from Y1. Cost=13
X=4 from Y2. Cost=14
X=5 from Y1. Cost=16
Search Statistics
Propagations: 149
Nodes: 21
Failures: 5
Depth: 3
Peak Memory 8KB
Two Y1 constraints
Model failed
Search Statistics
Propagations: 0
Nodes: 0
Failures: 1
Depth: 0
Peak Memory 4KB
_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
More information about the users
mailing list