[gecode-users] Some help required by new gecode users

[Christian Schulte]

Dear Fredrik,

sorry for the delay but I was too busy with other stuff!

I have to admit that I still not fully understand what you try to do, but
maybe I can give some hints already:

Percentage requires division: but you can expresse division by using
multiplication!

As it comes to finding the most balanced choices, there are two possible
ways one can do that (at least in principle):
 1. Do best solution search that maximizes the balance.
 2. Come up with abranching scheme that delivers reasonable balance.

What is it what you want? How big will be the matrices?

Anyhow, to do 2. one most likely has to implement a new branching that does
the following:
 - select a column
 - select a field in the column and try values for that
Therefore one must implement a new branching. A starting point could be to
look at int/branch.hh and related files to find out how simple
variable/value selection-based branching is done. Much of this relies on
kernel/branching.icc which defines variable/value style branchings
parametrized over classes that find variables and values.

Sorry that I cannot be more helpful than that. But please try to ask again,
if this is not sufficient.

All the best
Christian

--
Christian Schulte, http://www.imit.kth.se/~schulte/ 
-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Fredrik Berk
Sent: Tuesday, April 25, 2006 11:40 PM
To: users at gecode.org
Subject: [gecode-users] Some help required by new gecode users


<Description>
We are currently trying to solve a problem using gecode, but cant quite get
it to work the way we want it to.

<Problem description>
For every column in the matrix, all choices must be present once. Not all
rows need to contain a choice, but for every column all choices must be
found in one of the rows. For every row, there is a corresponding constant
in constants. The sum of all choices in a row divided by the constant is put
in percentage. For the entire matrix, we want to find the distribution of
choices in the matrix so that percentage is as even as possible for all
rows.

<What we can't get to work>
We need some help with how to setup this problem. Currently we are branching
on x and while that does give us a valid solution, its not really the one we
are looking for. Ideally we would like to find the most balanced solution
(as determined by the deviation of percentage for every row in comparison to
percentage for the matrix as a whole), not just a solution as we are
currently.

If every row in the matrix consists of:
Xi1 * A1 + Xi2 * A2 + ... + Xin * An + Ri = row_max[i]

We want the smallest possible deviation of  Ri / row_max[i] for all i in the
row_max array.

There are currently two problems facing us. For one, we are unsure of what
relations to enter for percentage, and secondly we are unsure on how to make
gecode pick x for the matrix based on values in percentage.

The code so far looks like this:

Test(const Options& opt)
    : x(this, row_count*col_count, 0, row_sum) 
    {
        MiniModel::Matrix<IntVarArray> m(x, col_count, row_count);
        for (int w = 0; w < col_count; ++w) {
            linear(this, m.col(w), 
                IRT_EQ, col_sum[w], opt.icl);
            }

        IntArgs args(col_count);
        for (int e = 0; e < col_count; ++e)
            args[e] = col_constant[e];

        for (int h = 0; h < row_count; ++h) {
            linear(this, args, m.row(h), 
                IRT_LE, row_max[h], opt.icl);
            linear(this, m.row(h), 
                IRT_EQ, row_sum, opt.icl);
        }
        branch(this, x, BVAR_SIZE_MIN, BVAL_MED);
    }