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

[Wei Wang]

Hi Gerald,

The new constraints reduced the solving considerably. Thank you so much!

Wei


On 04/13/2014 06:12 PM, 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