Home > Archive > Prolog > July 2006 > Binary vs integer: which is preferable? (X-post on c.constraints
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Binary vs integer: which is preferable? (X-post on c.constraints
|
|
|
| Dear all,
I've a modeling problem that i wish to submit to your experience.
Briefly, I've a constraint which could be expressed in two different ways:
1) X2 > X1 + sum(m){Ym * Tm}
sum(m) {Ym} = 1
where:
X1 and X2 are integer variables
Ym is an array of boolean variables
Tm is an array of constants
m belongs to (1,2,...,M)
2) X2 > X1 + Tm
m = X_m
where:
X1, X2 and X_m are integer variables (X_m belongs to (1,2....,M))
Tm is an array of constants
therefore the index m is an integer that belongs to (1,2....,M)
The question is: from a theoretical point of view, which is the better
formulation?
I mean, in the case 1) I only have two integer variables + M binary
variables, that is with a small domain, while in the case 2) I only have
three variables but with a wider domain for X_m.
I hope it is all clear.
TIA
Libra
| |
| Marco Gavanelli 2006-07-04, 7:59 am |
| Libra wrote:
> Dear all,
>
> I've a modeling problem that i wish to submit to your experience.
> Briefly, I've a constraint which could be expressed in two different ways:
>
> 1) X2 > X1 + sum(m){Ym * Tm}
> sum(m) {Ym} = 1
>
> where:
> X1 and X2 are integer variables
> Ym is an array of boolean variables
> Tm is an array of constants
> m belongs to (1,2,...,M)
>
>
> 2) X2 > X1 + Tm
> m = X_m
>
> where:
> X1, X2 and X_m are integer variables (X_m belongs to (1,2....,M))
> Tm is an array of constants
> therefore the index m is an integer that belongs to (1,2....,M)
If I understand correctly, the second formulation uses the "element"
constraint:
X2 > X1+ E, element(I,T,E).
where T is a list of values.
The first formulation is also an integer linear programming formulation,
so I think that it will be faster if you use an ILP solver. On the other
hand, the second sounds better if you use a Finite Domain solver.
(I don't know about "theoretical" works about this issue, I would simply
try which is faster in the instance you are addressing).
Cheers,
Marco
|
|
|
|
|