[Scip] How to get all transformed and presolved variables?

[Tobias Achterberg]

Martin Bergner wrote:
> My understanding was that active variables are variables that are
> currently in the problem and in the LP-relaxation and are not priced out
> or maybe fixed to some value. Fixed variables are variables which have a
> fixed value and need not to be considered for during the pricing and in
> the problem anymore.
>
> However, the aggregated variables that I have have bounds 0 and 1 and
> are negations of some original integer variables. When I loop over the
> variables of a constraint, I get these transformed and aggregated
> variables. These are, as far as I could tell, not fixed to a particular
> value. I want to know the original transformed variable which belongs to
> this aggregated variable.

The concept of "active" and "fixed" variables does not have anything to do with pricing. 
It is really only the output of presolving.

Initially, all original variables are copied into their transformed counterparts. Without 
presolving, all of these transformed variables would then be the "active" variables of the 
problem, even the ones with equal lower and upper bound.

No, presolving can in particular do the following:

1. Fix a variable, i.e., permanently set y = p.
2. Aggregate a variable, i.e., conclude that y = a*x + c for some values a and c.
3. Multi-aggregate a variable, i.e., conclude that y = a1*x1 + ... + ak*xk + c.

In all cases, y will be removed from the set of "active" variables and instead added to 
the set of "fixed" variables.

Negated variables are a special form of aggregated variables with a = -1 and c = ub.

Note also that the 'x' in the aggregations can be fixed or aggregated themselves. This 
gives an aggregation tree, or more precisely, a DAG with the active variables as sinks.

The B&C procedure only needs to deal with active variables, because once you have found 
values for all active variables, the values of fixed variables are determined.


> I just wondered why I get access to a variable, which is not in the vars
> array. If it is just fixed to a specific value, I thought that SCIP
> would modify the constraint in such a way that the fixed variable
> disappears and the rhs and lhs are updated accordingly. Furthermore, I
> thought that the same invariants (there is no var in a constraint that
> is not in the var array) would hold.

Modifying the constraints to contain only active variables is not possible in all cases. 
It is possible for linear constraints, and there it is done. But for example, set 
partitioning constraints are defined to be

   sum x_i = 1

with all coefficients being +1. Therefore, if some x_i is a negation like x_i = 1 - y_i, 
you cannot substitute x_i for y_i because this would yield a negative coefficient and 
change the right hand side of the constraint.
Similar reasoning applies to other constraints like knapsack, set covering, and so on.

For this reason, many constraints will contain "fixed" variables (usually, these will be 
aggregated variables rather than variables fixed to a specific value). This does no harm, 
because SCIP will automatically translate all operations on these variables into 
equivalent operations on active variables. For example, if you add an aggregated variable 
to a SCIP_ROW, then SCIP will automatically add the corresponding active variable(s) instead.


Tobias