[Scip] pricing with upper bounds on variables

[Ambros Gleixner]

Hi Martin.

I will leave the column generation aspect of your question to the 
experts, but I can explain the signs of the reduced costs in SCIP.

Suppose the LP relaxation reads

    min{ c^T x | L <= Ax <= U, l <= x <= u }

then its dual written down explicitly would look like

    max{ L^T y - U^T z + l^T r - u^T s | A^T (y - z) + r - s = c,
                                         y, z, r, s >= 0 }

with dual multipliers y for Ax >= L, z for Ax <= U, r for x >= l, and s 
for x <= u.  The reduced cost vector is c - A^T (y - z) = r - s.

Now for ranged row i, SCIProwGetDualsol() would return y_i - z_i. By 
looking at its sign, you know whether the multiplier counts for the 
lower or the upper bound:

    y_i - z_i > 0 ==> z_i = 0 ==> lower bound
    y_i - z_i < 0 ==> y_i = 0 ==> upper bound
    y_i - z_i = 0 ==> y_i, z_i = 0 ==> row is basic

Analogously for the reduced costs: For variable x_k, SCIPgetVarRedcost() 
returns r_k - s_k and by looking at the sign you can figure out wether 
it applies to the upper or lower bound:

    r_k - s_k > 0 ==> s_k = 0 ==> lower bound
    r_k - s_k < 0 ==> r_k = 0 ==> upper bound
    r_k - s_k = 0 ==> r_k, s_k = 0 ==> variable is basic

If upper bounds are defined lazy, i.e., in the LP u_k = +infinity, then 
s_k = 0 and SCIPgetVarRedcost() always returns a nonnegative value.  If 
the upper bounds are present in the LP, then x_k may be tight at its 
upper bound and the reduced cost would be -s_k, i.e., potentially negative.

The issue behind this is that if upper bounds are implicitly enforced by 
rows, then there are multiple dual solutions which prove optimality. By 
making the upper bounds lazy and leaving the, out of the LP, you force 
the LP solver to return a solution with nonnegative reduced costs, 
otherwise you don't.

If you have upper bounds which are not enforced by other rows in the LP, 
you *must not* declare them lazy and need to consider their multipliers, 
the negative reduced costs, in the pricing problem of your column 
generation algorithm.

Hope that helps,
Ambros




Am 19.01.2012 11:59, schrieb Martin Tieves:
> Hallo
>
> I have a problem with my column generation algorithm. Especially, my question centers around pricing variables with upper bounds.
>
> For training issues, I used the cpp interface of scip (soplex solver) to implement my own version of the coloring (pricing: stable set) example.
> I can generate a new variable (stable set) and add it. Then, in the next step, the same variable is generated, again (though it is already used in the new basis solution). From my point of view, the problem lies in the dual variables. Since this variable imposes an upper bound (of value 1 - the stable sets are binary decisions), the infomation about the dual value of this variable is missing in my pricing problem.
> So my question is, how can I obtain that dual value?
>
> I am aware of the SCIPchgVarUbLazy command (e.g. in the above example) - which helps in the above case (and is used in the given coloring example code). But what is to do, if the upper bounds are not implicitely given, such that one realy needs the additional bounds (dual variables). From my understanding, this commands forces to ignore the bound-constraints in the lp calculations, only, is that true?
>
> In this context, I have some question to the SCIPgetVarRedcost command. In the above situation, the already added variable has a negative reduced costs value (which should be impossible in my point of view) in the next pricing step, but only if the variable bound was not decleared as lazy. Why is this? I am not sure if the newly added (variable) bound is treated correctly in the corresponding redcost calculation (though I am probably mistaken here ;)  ). (this behaviour can be observed at the example's code as well, if disabling the "lazy" command.)
>
> I am not sure if I understand correctly what happens, if one defines (not implicitely given) upper bounds in the priced variables, from a computational point of view. Do you have any advice how to avoid the above mentioned problems?
>
> Best Regards
>
> Martin
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-- 
____________________________________________________________
Ambros M. Gleixner
Zuse Institute Berlin - Matheon - Berlin Mathematical School
http://www.zib.de/gleixner