[gecode-users] Help: Howto combine sets and value constraints?

[Holger Winnemoeller]

I am trying to create a solver that (as a toy explanation) can create sets
with
certain properties, such as:

1) The resulting set size is specified
2) The resulting set contains a certain number of items that belong to a
  "special" group
3) The total "weight" of items is below a certain threshold

I can easily enough create constraints for 1) and 2), but I would love to
get
some help in how I integrate constraint 3) into the mix. Supposedly I would
create a set of variables for the weights and specify a constraint on the
sum of
these weights. But I have no idea about how to express in Gecode that I want
to
sum up the weights of exactly the ids that are in the currently selected
set.

My approach to doing 1)&2) is attached below. The question is: How do I
specify
that the total weight of selected items should be less than, say
"maxWeight".

(Note: This is not a homework problem :-) It's an abstraction of a set
selector
that I want to include in a user interface for suggesting available sets to
users)

Thanks for your time,
Holger.
========================< main.cpp >===========================
#include <gecode/set.hh>
#include <gecode/support.hh>
#include <gecode/kernel.hh>
#include <gecode/search.hh>

using namespace Gecode;

// Some data to play with
int numItems = 10;                    // total number of items in inventory
int numSpecialItems = 4;            // number of items in inventory with
"special" attribute
int numRequestedSize = 6;            // requested size of result set
int numRequestedSpecialSize = 2;    // requested size of "special" items in
result set
float maxWeight = 1.8f;                // requested maximum weight of all
items in result set (NOT IMPLEMENTED!)

int allItems[] = {0,1,2,3,4,5,6,7,8,9}; // 10 items (their id's)
float itemWeights[] = {0.1f, 0.5f, 0.2f, 0.2f, 0.6f, 0.8f, 1.0f, 0.3f, 0.7f,
0.6f}; // their associated weights
int specialItems[] = {2,5,8,9}; // a subset of items having the attribute
"special"

// Little helper function
bool isInSet(int id, int set[], int setSize)
{
    for(int i=0; i<setSize; ++i)
        if(id == set[i]) return true;
    return false;
}

// A "Minimal" space definition for the problem
class MiniSpace: public Space
{
        SetVarArray mSetStore;
public:
    MiniSpace(){
        // 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, numItems);
        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);

        // now impose the fact that we want exactly
"numRequestedSpecialSize" items coming from the special set
        // 1.) Create a new set domain that represents the "special" items
        IntSet specialSet(specialItems, numSpecialItems);
        // 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, resultSet, SOT_INTER, specialSet, SRT_EQ,
specialSelected);
        // 4.) Now ensure that we only have "numRequestedSpecialSize" of
these overlapping items
        cardinality(*this, specialSelected, numRequestedSpecialSize,
numRequestedSpecialSize);

        // 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
    {
        int countAsSpecial = 0;
        for(SetVarGlbValues d(mSetStore[0]);d();++d)
        {
            int id = d.val();
            if(isInSet(id, specialItems, numSpecialItems)) countAsSpecial++;
            std::cout << id << " ";
        } // for
        std::cout << ". Nr. of specials: " << countAsSpecial;
    }
};

int main(int argc, char* argv[])
{
    // Run the problem
    MiniSpace problem; // space instance
    //Search::Options options
    DFS<MiniSpace> solver (&problem);
    int count=0;
    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;
    return 0;
}
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20091214/4c6293a9/attachment-0001.htm>