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

Gerald Gamrath gamrath at zib.de
Mon Apr 14 00:12:20 CEST 2014


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



More information about the Scip mailing list