[gecode-users] Set constraints working for sequential data, but not non-sequential data. Ideas?

[Holger Winnemoeller]

*QUESTION: How can I solve the following problem for anything but toy
examples?*

Say, I have the following sets:

All : {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
subA: {0,1,2,3,4}
subB: {5,6,7,8,9}

If I ask for a subset of "All" which contains 4 elements, of which 2
elements are from "subA" and 2 elements are from "subB", I get a variety of
results, such as
{0,1,5,6}
{0,1,5,7}
...
{3,4,8,9}
...

etc.

This works perfectly fine.

Now, for cases where subA, and  subB are not strictly sequential (i.e.
sorted but non-consecutive numbers)

subA: {4,8,14,16,17}
subB: {0,3,5,10,12}

The system quickly runs out of steam (maybe not for the toy example here,
but for |All| = 100, |subA| = |subB| = 20, asking for 10 items -- see
attached code). Gecode just keeps computing and never seems to find a
solution.

Given that the sub-sets are disjoint a solution should really be trivial in
any case (take 50% of one subset and 50% of the other). However, I don't
want to make the assumption that they are disjoint.

I have attached some demo code for what I am talking about, so you can
experiment with it.

Thanks for your help!

Holger.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20091215/0f54715c/attachment.htm>
-------------- next part --------------
#include <gecode/set.hh>
#include <gecode/support.hh>
#include <gecode/kernel.hh>
#include <gecode/search.hh>
#include <vector>
#include <algorithm>

using namespace std;
using namespace Gecode;

#define BROKEN_PROBLEM 1 // will not finish
//#define BROKEN_PROBLEM 0 // works just fine

// A "Minimal" space definition for the problem
class MiniSpace: public Space
{
	SetVarArray mSetStore;
	void CreateAndRequestCategory(int numItemsInCategories, int requestFromEachCategory, vector<int>& allItems)
	{
		vector<int> data (numItemsInCategories); // space to hold items
		for(int i=0; i<numItemsInCategories; ++i) // fill data from allItems
		{
			data[i] = allItems.back();
			allItems.pop_back();
		}

		// sort the items before loading them into Gecode -- not sure if this is necessary
		sort(data.begin(), data.end());

		// 1.) Create a new set domain that holds the "special" items
		IntSet specialSet(&data[0], (int)data.size());
		// 2.) Create a set variable that we'll associate with that set later on
		SetVar specialSelected(*this);
		// 3.) Set "specialSelected" to the intersection of whatever a possible solution is, and
		//     the "specialSet". This ensures that we can talk about items that are included
		//     in the solution, but also belong to the special set
		rel(*this, mSetStore[0], SOT_INTER, specialSet, SRT_EQ, specialSelected);
		// 4.) Now ensure that we only have "requestFromEachCategory" of these overlapping items
		cardinality(*this, specialSelected, requestFromEachCategory, requestFromEachCategory);
	}

public:
	MiniSpace(int problemSize, int numItemsInCategories, int numRequestedSize)
	{
		puts("Setting up problem...");
		// Create a SetVariable array (only need one element really, but this allows me to define the domain in one step)
		mSetStore = SetVarArray(*this, 1, IntSet::empty, 0, problemSize);
		SetVar resultSet = mSetStore[0]; // get the one variable that was defined in the above line

		// impose the constraint that we only want "numRequestedSize" items in the result set
		cardinality(*this, resultSet, numRequestedSize, numRequestedSize);

		// Create two sets of random non-overlapping items from inventory
		vector<int> allItems (problemSize);
		for(int i=0; i<problemSize; ++i) allItems[i] = problemSize-1-i; // init items
#if BROKEN_PROBLEM
		random_shuffle(allItems.begin(), allItems.end()); // shuffle items
#endif
		int requestFromEachCategory = numRequestedSize * 4 / 10;
		CreateAndRequestCategory(numItemsInCategories, requestFromEachCategory, allItems); // one category

		// Create another set of items and request elements from it
		CreateAndRequestCategory(numItemsInCategories, requestFromEachCategory, allItems); // another category

		// Given these constraints, branch
		branch(*this, mSetStore, SET_VAR_NONE, SET_VAL_MIN_INC);
	}
	MiniSpace(bool share, MiniSpace& s) : Space(share, s) {mSetStore.update(*this, share, s.mSetStore);}
	virtual Space* copy(bool share) {return new MiniSpace(share, *this);}
	void print() const
	{
		for(SetVarGlbValues d(mSetStore[0]);d();++d)
			std::cout << d.val() << " ";
	}
};

int main(int argc, char* argv[])
{
	// Run the problem
	//MiniSpace problem (
	//	3000,	// total number of items in inventory
	//	200,	// several sub-inventories (non-overlapping) with X elements each
	//	20		// requesting X items
	//); // space instance

	MiniSpace problem (
		100,	// total number of items in inventory
		20,		// several sub-inventories (non-overlapping) with X elements each
		10		// requesting X items
	); // space instance

	DFS<MiniSpace> solver (&problem);
	int count=0;
	puts("Looking for solutions...");
	while(true){
		MiniSpace* solution = solver.next();
		if(!solution) break;
		std::cout << "Solution Nr." << count++ << std::endl;
		solution->print();
		std::cout << std::endl;
		delete solution;
	}
	std::cout << "Done..." << std::endl;
	system("pause");
	return 0;
}