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-boun...@gecode.org [mailto:users-boun...@gecode.org] On Behalf Of Dean Hiller Sent: Thursday, March 28, 2013 5:19 PM To: users@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@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users _______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
