[Scip] dependent variables and if-then-else constraints

[Marc Pfetsch]

Hi Wei,

it seems that you are using ZIMPL to formulate the problem. ZIMPL adds 
artificial variables and then generates indicator constraints (so it 
does not use the big-M as indicated in Geralds answer). In any case, 
these artificial variables are easily removed in presolving and SCIP 
usually is fast.

So - I suppose that the long solving time actually arises independently 
of the effect you describe: Such (indicator) models are often hard to 
solve. The relaxations are often bad, especially if the bounds (e.g., 
the M in Geralds model) are large. Heuristics often do not find good 
solutions easily.

Thus, I recommend to check how many variables (and indicator 
constraints) are left after presolving. Moreover, you should check how 
the dual or primal bounds improve over time.

Best

Marc




On 04/14/2014 12:12 AM, Gerald Gamrath wrote:
> Dear Wei,
>
> your variable y_i is already quite similar to the auxiliary variable y
> in your reference.
>
> Therefore, you do not need to introduce any new variables but rather add
> the following two constraints:
> 1) x_i <= 100 + M * y_i
> 2) x_i >= 0 + (100 + epsilon) * y_i
> (supposed your variable x_i is nonnegative). M should be a large value,
> such that 100 + M does not forbid any valid values for x_i, but for
> numerical reasons as small as possible (with this property).
>
> What is the objective function coefficient of y_i and does it occur in
> other constraints? If you are minimizing and y_i has a positive
> coefficient, it might be that you can even omit the second constraint
> because the objective function will always lead to y_i having value 0 if
> x_i <= 100 in any optimal solution.
>
> Best,
> Gerald
>
>
> Am 13.04.2014 23:28, schrieb Wei Wang:
>> Hi,
>>
>> I have a question about if-then-else constraints, and dependent
>> variables. In my MILP problem I have a large number of dependent
>> variables and if-then-else constraints. The constraints look like this,
>>
>> if x_i>100 then y_i = 1 else y_i=0
>>
>> That is, y is a dependent variable of x, and y is also a binary
>> integer variable. I converted this if-then-else constraint to linear
>> equations using the method described here,
>> http://www.yzuda.org/Useful_Links/optimization/if-then-else-02.html.
>>
>> This converting method adds another 4 binary integer variables for
>> each if-then-else constraint.
>>
>> The problem is that I have about 10000 if-then-else constraints, which
>> means, I have to add 40000 binary integer variables. And adding these
>> many variables considerably increases the time to solve my problem.
>>
>> Because the added variables and the y variables are all dependent
>> variables, and I only have about 400 independent variables, I think
>> there should be a way to reduce the solving time. Can somebody give me
>> some suggestions on how to optimize it?
>>
>> thanks,
>> Wei
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip