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 <[email protected]
> 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
>
>
// 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;
}
// 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;
}
};_______________________________________________
Gecode users mailing list
[email protected]
https://www.gecode.org/mailman/listinfo/gecode-users
