[gecode-users] Newbie: Cost function with squared variables propagation trouble

[Mikael Zayenz Lagerkvist]

On 1/5/07, Pieter Thysebaert <pieter.thysebaert at intec.ugent.be> wrote:
> Hello,
>
> I'm using Gecode 1.2.2 on Debian sarge.
>
> While modelling a scheduling problem I have stumbled across the following:
>
> Let's say the decision variables of my problem are X_ijk, binary.
> Let integer variables Y_i >= 0 be related to the X_ij by  Y_i = k <=>
> X_ijk = 1 for some range of j, expressed by using constraints like
> eq(this, Y_i, k, X_ijk); for that range of j
>
> The cost function I want to minimize is
> sum_over_i  (Y_i - Constant_i)^2
>
> Clearly, if for some i, Constant_i < 0 the cost is at least (Y_i -
> Constant_i)^2.
>
> However, for all but the most trivial instances of my problem, the
> minimal cost after initial propagation is smaller than this "intuitive"
> lower bound.
> I believe (but I can be wrong) that this is partly due to my feable
> modelling skills: in order to implement the cost function above, I have
>
> 1. expanded each square term into a polynomial
> 2. introduced auxiliary variables Z_i = sqr(Y_i)
> 3. written the cost as a sum of Z_i and Y_i terms
>
> Is there a more concise way to express the cost function above without
> introducing explicit extra constraints stating the obvious (i.e. cost >=
> intuitive lower bound for Constant_i < 0) that will nevertheless
> propagate and find these "intuitive" cost bounds?
> If not, can someone point me to an exmaple which would show me how to
> implement my own propagator for such a cost function?

In general the arithmetic constraints reason on the bounds of the
variables. For some constraints there is also stronger propagation
available (using ICL_DOM) although this is usually very costly. For
the multiplication propagator, though, bounds propagation is the only
propagation available in Gecode.

I'm not sure what the obvious lower bound is in your example, and
where it is missing. Could you perhaps give a small example that
demonstrates the problem?


> As a side note, I have also been caught by the following oddity (well
> that's how it seemed to me at first).
> If I want to build a MiniModel::LinExpr using the following code
>
> LinExpr myExpr;
>
> for (int i = 0; i < ...; i++) {
>     myExpr = myExpr + some_term(i);
> }
>
> On my machine, this code fails upon the first assignment to the empty
> LinExpr, and only works when explicitly initializing myExpr with the
> first term and then adding the others.
> Is this standard behavior?

Yes, this is standard behaviour currently. The LinExpr are originally
designed for construction from expressions by overloaded operators, in
which case there is always a first term to start from.


Cheers,
Mikael

-- 
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/