[gecode-users] Gecode BAB Questions

[Dean Hiller]

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