[gecode-users] Question about: Float variables, Literals and/or Constants

[Holger Winnemoeller]

Great! Again, this was totally the solution. Thank you.

Just in case this is ever relevant to someone else, I am attaching my little
demo program that I used to test the approach.

Cheers,
Holger.

On Wed, Dec 16, 2009 at 10:53 PM, Mikael Zayenz Lagerkvist <zayenz at gmail.com
> wrote:

> Hi,
>
> The float variables are not yet truly integrated into Gecode, so I would
> not advise to use them currently.
>
> As for how to express the multiplication with a constant, I would suggest
> you use the minimodel interface:
>     post(*this, d*mutualSize == n*resultSize);
>
> Cheers,
> Mikael
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20091217/90328ac0/attachment.htm>
-------------- next part --------------
// 12/16/2009 By Holger Winnemoeller
// License: Do with this what you will - hope it helps...
#include <gecode/set.hh>
#include <gecode/support.hh>
#include <gecode/minimodel.hh>
#include <gecode/kernel.hh>
#include <gecode/search.hh>
#include <vector>
#include <algorithm>

#include "quotient.hpp"

using namespace std;
using namespace Gecode;

struct SubSet : public vector<int>
{
	Quotient quota;
	SubSet(){}
	SubSet(vector<int>& inventory, int takeNumItems, const Quotient& quota) : vector<int> (takeNumItems), quota(quota)
	{
		for(int i=0; i<takeNumItems; ++i) // fill data from allItems
		{
			(*this)[i] = inventory.back();
			inventory.pop_back();
			sort(begin(), end());
		}
	}
	bool contains(int val) const
	{
		for(size_t i=0; i < size(); ++i)
			if((*this)[i] == val) return true;
		return false;
	}
};

// A "Minimal" space definition for the problem
class MiniSpace: public Space
{
	SetVarArray mSetStore;
	void RequestFromSubset(SubSet& subset, IntVar& resultSetSize, int numRequestedSize)
	{
		// 1.) Create a new set domain that holds the "special" items
		IntSet specialSet(&subset[0], (int)subset.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
		IntVar intersectionSize (*this, 0, (int)subset.size());
		cardinality(*this, specialSelected, intersectionSize);

#if 1	// Using the Minimodel interface
		post(*this, subset.quota.numerator * resultSetSize == subset.quota.denominator * intersectionSize);
#else	// Using the clunky Holger way...
		const Quotient& requestFromEachCategory = subset.quota;
		IntVar lhs (*this, 0, requestFromEachCategory.denominator * (int)subset.size());				
		IntVar rhs (*this, 0, requestFromEachCategory.numerator   * numRequestedSize);	
		
		IntVar numerator(*this, requestFromEachCategory.numerator, requestFromEachCategory.numerator);
		IntVar denominator(*this, requestFromEachCategory.denominator, requestFromEachCategory.denominator);

		mult(*this, intersectionSize, denominator, lhs);				
		mult(*this, resultSetSize,    numerator,   rhs);	

		rel(*this, lhs, IRT_EQ, rhs);
#endif
		branch(*this, specialSelected, SET_VAL_MIN_INC); //  THIS IS THE SAVER!!!!!
	}

public:
	MiniSpace(int problemSize, vector<SubSet>& subsets, 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
		IntVar resultSetSize(*this, 0, numRequestedSize);
		cardinality(*this, resultSet, resultSetSize);
		rel(*this, resultSetSize, IRT_EQ, numRequestedSize);

		for(size_t i=0; i<subsets.size(); ++i)
			RequestFromSubset(subsets[i], resultSetSize, numRequestedSize); 

		// 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 vector<SubSet>& subsets) const
	{   // Print out a result set, but also a distribution of what subsets of an inventory the items belong to
		// the last number is for items that don't belong to any subset (i.e. inventory diff (union subsets))
		vector<int> scores (subsets.size()+1);
		for(size_t i=0; i<scores.size(); ++i)
			scores[i] = 0;
		int nonSubSetIdx = (int) subsets.size();
		for(SetVarGlbValues d(mSetStore[0]);d();++d)
		{
			int id = d.val();
			bool fromSet = false;
			for(size_t i=0; i<subsets.size(); ++i)
				if(subsets[i].contains(id))
				{
					scores[i]++;
					fromSet = true;
					break;
				}
			if(!fromSet)
				scores[nonSubSetIdx]++;
			std::cout << d.val() << " ";
		}
		printf(". Dist(");
		int total = 0;
		for(size_t i=0; i<scores.size(); ++i)
		{
			total += scores[i];
			printf("%s%i",i?",":"",scores[i]);
		}
		printf("), Sum = %i\n", total);

	}
};

int main(int argc, char* argv[])
{
	// Generate an inventory
	int problemSize = 3000;
	int numItemsInCategories = 200;
	int numSubCategories = 4;
	int requestedSize = 40;

	vector<int> inventory (problemSize);
	for(int i=0; i<problemSize; ++i) inventory[i] = problemSize-1-i; // init items
	
	// just to make it a bit more realistic
	random_shuffle(inventory.begin(), inventory.end()); // shuffle items

	// Float support in Gecode still experimental, apparently. Use quotients instead
	Quotient quotas [] = {Quotient(0.5), Quotient(0.25), Quotient(0.1), Quotient(0.1)};

	vector<SubSet> subsets(numSubCategories);
	for(int i=0; i<numSubCategories; ++i)
		subsets[i] = SubSet(inventory, numItemsInCategories, quotas[i]);

	// Run the problem
	MiniSpace problem (
		problemSize,	// total number of items in inventory
		subsets,		// several sub-inventories (non-overlapping) 
		requestedSize	// requesting X items
	); // space instance

	// Gimme my solutions
	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(subsets);
		std::cout << std::endl;
		delete solution;
	}
	std::cout << "Done..." << std::endl;
	system("pause");
	return 0;
}

-------------- next part --------------
// Conversion from float adapted from: http://stackoverflow.com/questions/1656945/how-can-i-turn-a-floating-point-number-into-the-closest-fraction-represented-by-a 
// License: whatever it says in the above link
#pragma once

#include <math.h>

struct Quotient
{
	int numerator, denominator;
	Quotient() : numerator(0), denominator(1){} // equiv = 0
	Quotient(int numerator, int denominator) : numerator(numerator), denominator(denominator){}
	Quotient (float val)
	{
		float input = val;
		int p0 = 1;
		int q0 = 0;
		int p1 = (int) floorf(input);
		int q1 = 1;
		int p2;
		int q2;

		float r = input - p1;
		float next_cf;
		while(r != 0.0f)
		{
			r = 1.0f / r;
			next_cf = floorf(r);
			p2 = (int) (next_cf * p1 + p0);
			q2 = (int) (next_cf * q1 + q0);

			// Limit the numerator and denominator to be 256 or less
			if(p2 > 256 || q2 > 256)
				break;

			// remember the last two fractions
			p0 = p1;
			p1 = p2;
			q0 = q1;
			q1 = q2;

			r -= next_cf;
		}

		input = (float) p1 / q1;
		// hard upper and lower bounds for ratio
		if(input > 256.0f)
		{
			p1 = 256;
			q1 = 1;
		}
		else if(input < 1.0f / 256.0f)
		{
			p1 = 1;
			q1 = 256;
		}
		numerator = p1;
		denominator = q1;
		float error = (toFloat() - val) / val;
		printf("%f = %i / %i with %.2f %% error\n",val, numerator, denominator, 100.0f * error);
	}
	float toFloat() const 
	{
		return (float) numerator / (float) denominator;
	}
};