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

[Fredrik Berk]

<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);

    }
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20060425/8843fb4e/attachment.htm>