[Scip] Transformed variables

Stefan Wiesberg stefan.wiesberg at informatik.uni-heidelberg.de
Fri Jun 15 10:28:48 MEST 2012


Dear Timo,

thanks a lot for your detailed explanation! It answered my questions and
made the concept much clearer to me.

Best wishes
  Stefan


On 14.06.2012 11:51, Timo Berthold wrote:
> Hi Stefan,
>
>> Dear SCIP community,
>>
>> although the concept of transformed variables has already been
>> discussed, I still need to ask for your help on some remaining questions:
>>
>> 1) In the presolving step, every original variable x_i is replaced by a
>> transformed variable t_x_i. As far as I understand, some further
>> variables might be added to the transformed problem. Which possibilities
>> are there?
> In default SCIP for MIP solving, there is only two possibilities:
> 1. Negated variables: t_x_neg = 1- t_x for binary t_x
> 2. Integer variables that have been converted to binaries t_x_bin = t_x -
> lb for integer t_x with bounds [lb,lb+1], lb != 0 (if you create a integer
> variable with bounds 0,1, its type is automatically changed to binary)
>
> Further, if you have a branch-and-price algorithm, the priced variables
> only exist in the transformed problem. Also, for nonlinear problems, a
> couple of cases exist in which auxiliary variables are created. And there
> is a presolvers called boundshift which creates variables in a similar way
> as in case 2 above, but it is deactivated by default!
>
>> 2) I've heard of so-called negation variables. Is it possible that a
>> transformed variable t_x_i is deleted, e.g., because it is replaced by
>> such a negation variable, or do they always co-exist?
> The latter.
>
>> 3) Suppose that a^T x <= b (*) is a valid inequality on original
>> variables for my IP. Is the inequality that evolves from (*) by
>> replacing every x variable by its corresponding t_x variable also valid?
>> E.g., if  x_1 + x_2 + x_3 <= 2 is valid, does this imply that t_x_1 +
>> t_x_2 + t_x_3 <= 2 is valid?
> Yes. In the beginning, the transformed problem is a one-to-one copy of the
> original. All variables get copied, all constraints get copied. Then
> presolving reductions are performed only on the transformed.
>
>> Or equivalently: Does the real-world interpretation of the original
>> variables change during transformation? With "real-world interpretation"
>> I mean a statement like "x_i_j states whether object i is put into bin j".
> No.
>
> You can really think of it as if you would draw the polyhedron which is
> defined by your MIP fromulation on a (n-dimensional ;) ) sheet of paper,
> copy it, and then start editing the copy: you cancel redundant
> inequalities, you scale the normal vectors, you shift the polyhedron to
> the origin, reflect it along a coordinate hyperplane, ... The latter two
> examples are the cases mentioned above: For this, you need to introduce
> new variables and remember what the connection of these is. If you have an
> integer variable x that allows for two values, say 42 and 43, then its
> transformed t_x will represent the same decision: choose either 42 or 43.
> SCIP, however, will do its computations on a binary variable t_x_bin and
> remember that t_x = t_x_bin + 42. Both variables co-exist. Any plugin can
> perform operations on either of them. Say, some propagator detects, that
> in the current sub-problem the decision is fixed. It can tell this to t_x
> or t_x_bin, the result will be the same, the variables will both be fixed.
> When you now, after solving, request the value of the original variable x,
> SCIP will know that x = t_x = t_x_bin + 42 and reconstruct the value for x
> from the value t_x_bin has.
>
> So, why is all this done? The whole purpose is, that you still have the
> original formulation available after the solving process which allows for
> two thigns:
> a) You can check the validity of the solution in the original formulation
> and thereby detect bugs or numerical issues.
> b) you can modify the original problem and start solving again.
>
> Hope that helps
> Timo
>
>
>
>
>> Thanks a lot and kind regards
>>   Stefan
>>
>> --
>> Stefan Wiesberg
>> ____________________________________________________
>> AG Diskrete Optimierung
>> Institut für Informatik
>> Universität Heidelberg
>> Phone: 49 6221 54 5746
>> E-Mail: stefan.wiesberg at informatik.uni-heidelberg.de
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>>



More information about the Scip mailing list