[Scip] Transformed variables

Timo Berthold berthold at zib.de
Thu Jun 14 11:51:20 MEST 2012


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