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@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
