Greetings,
I'm using a model in which I rely heavily on reified linear sums of
booleans. Unfortunately the existing boolean reified linear sum
implementatiom is horribly slow for this ! To overcome this, I'm currently
channeling all boolean variables to integers, and posting the reified
linear sum over the integers. This gives incredibly faster runtimes.
The first batch of constraints are regular reified linear sums, they are
constructed by reading a binary matrix and creating an IntArgs 'row' which
contains 0 or 1 (out or in). This 'row' is multiplied by an array of
decision variables, each representing one column. Doing so selects the
desired subset of those variables after which they are constrained and
reified to the variable representing that row:
for (int r = 0; r!=nr_r;r++ ) {
// make row
for (int c = 0; c!=nr_c;c++ ) {
row[c] = (1-tdb[r][c]); // complement
}
// sum(row*col_vars) = 0 <=> row_vars[r]
linear(this, row, col_vars, IRT_EQ, 0, row_varsBool[r]);
}
here, the col_vars is an IntVarArgs that is channeled to corresponding
BoolVars.
The second batch of constraints are imply-reified linear sums, having one
sided reification. Because one-sided reification is not implemented in
gecode directly, an extra auxiliary variable and constraint is used to
manage it:
for (int c = 0; c!=nr_c;c++ ) {
// make col
for (int r = 0; r!=nr_r;r++ ) {
col[r] = tdb[r][c];
}
// sum(col*row_vars) >= X <=> col_aux[c]
linear(this, col, row_vars, IRT_GQ, X, col_aux[c]);
// col_aux[c] => col_varsBool[c] (one-sided reificiation, reformulation
is) col_aux[c] =< col_varsBool[c]
rel(this, col_aux[c], IRT_LQ, col_varsBool[c]);
}
similarly as above, row_vars is an IntVarArgs channeled to corresponding
BoolVars.
This model works very well but still, I'm wondering if there would be a
better or cleaner way to model this, and if there are any plans to improve
the reified linear sum of boolean constraints.
Kind regards,
Tias
_______________________________________________
Gecode users mailing list
[EMAIL PROTECTED]
https://www.gecode.org/mailman/listinfo/gecode-users
