Originally posted by: SystemAdmin

[gramchurn said:]

Hi there,
I'm trying to add the following constraint to my model:

1 + |i-x[i]| <= |y[i] - y[i-1]| <br />
where y[i] is in {0,1} and x[i] is in {0,1} too. i is in {1...10}.
I've seen that CPLEX 9.0 has IloAbs in the C++ version (according to the help files) but could not find anything for the Java version. Am I doomed to recode everything in C++ or C# ?

Your help will be greatly appreciated as i've been struggling with this for a while. I've even tried transforming it into a quadratic constraint but that didn't work because it generated a function that was not positive and semi-definite.... a strict requirement for the QP CPLEX to work...[gramchurn@gmail.coml]
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

Note:  I switched to a more TeX-like notation.  The forum software thinks a lower case i inside square brackets means "I want italics".

[quote author=gramchurn link=topic=1165.msg3345#msg3345 date=1243418768]
Hi there,
I'm trying to add the following constraint to my model:

1 + |i-x_i| <= |y_i - y_{i-1}| <br />
where y_i is in {0,1} and x_i is in {0,1} too. i is in {1...10}.
I've seen that CPLEX 9.0 has IloAbs in the C++ version (according to the help files) but could not find anything for the Java version. Am I doomed to recode everything in C++ or C# ?

Your help will be greatly appreciated as i've been struggling with this for a while. I've even tried transforming it into a quadratic constraint but that didn't work because it generated a function that was not positive and semi-definite.... a strict requirement for the QP CPLEX to work...[gramchurn@gmail.coml]


Avoid IloAbs in any case; it will make your model nonlinear.

You need to add a new divisible variable z >= 0 and a new binary variable w, find an a priori upper bound M for |y[i] - y[i-1], then add the following constraints:

z >= 1 + i - x_i
z >= 1 + x_i - i
z <= y_i - y_{i-1} + M*w<br />z <= y_{i-1} - y_i + M*(1-w).<br />
The first two constraints ensure that z >= 1 + |i - x_i|.  In the third and fourth constraints, the difference in y's will be negative in one case and positive in the other (unless y_i = y_{i-1}); z >= 0 will ensure that w takes the correct value to make the constraint with a negative difference vacuous, in which case you'll be left with z <= the positive difference (i.e., the absolute value).  If y_i = y_{i-1}, it doesn't matter which value w takes; one or the other of the third and fourth constraints will force z <= 0.<br />
/Paul

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[gramchurn said:]

Thanks Paul,

i've tried a different version of what you sent me as the problem is actually:
[i]1-|i-x_i| <= |y_i -y_{i-1}|[/i] (i.e. 1- rather than 1+)<br />Given what you sent me, I tried the following formulation:

[i]z <= 1 -i + x_i[/i]<br />[i]z <= 1 +i -x_i[/i]<br />[i]z <= y_i - y_{i-1} + Mw[/i]<br />[i]z <= y_i - y_{i-1} + M(1-w)[/i]<br />
Unfortunately, doing so, results in CPLEX pushing z in [-10,1] to its negative limit as this value always validates the constraints in all cases....  Is there any way to push z to 1? I'm guessing it's a simple tweak to this but i'm not sure what.


[quote author=prubin link=topic=1165.msg3348#msg3348 date=1243459453]
Note:  I switched to a more TeX-like notation.  The forum software thinks a lower case i inside square brackets means "I want italics".

[quote author=gramchurn link=topic=1165.msg3345#msg3345 date=1243418768]
Hi there,
I'm trying to add the following constraint to my model:

1 + |i-x_i| <= |y_i - y_{i-1}| <br />
where y_i is in {0,1} and x_i is in {0,1} too. i is in {1...10}.
I've seen that CPLEX 9.0 has IloAbs in the C++ version (according to the help files) but could not find anything for the Java version. Am I doomed to recode everything in C++ or C# ?

Your help will be greatly appreciated as i've been struggling with this for a while. I've even tried transforming it into a quadratic constraint but that didn't work because it generated a function that was not positive and semi-definite.... a strict requirement for the QP CPLEX to work...[gramchurn@gmail.coml]


Avoid IloAbs in any case; it will make your model nonlinear.

You need to add a new divisible variable z >= 0 and a new binary variable w, find an a priori upper bound M for |y[i] - y[i-1], then add the following constraints:

z >= 1 + i - x_i
z >= 1 + x_i - i
z <= y_i - y_{i-1} + M*w<br />z <= y_{i-1} - y_i + M*(1-w).<br />
The first two constraints ensure that z >= 1 + |i - x_i|.  In the third and fourth constraints, the difference in y's will be negative in one case and positive in the other (unless y_i = y_{i-1}); z >= 0 will ensure that w takes the correct value to make the constraint with a negative difference vacuous, in which case you'll be left with z <= the positive difference (i.e., the absolute value).  If y_i = y_{i-1}, it doesn't matter which value w takes; one or the other of the third and fourth constraints will force z <= 0.<br />
/Paul


#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

[quote author=gramchurn link=topic=1165.msg3361#msg3361 date=1243614607]
i've tried a different version of what you sent me as the problem is actually:
[i]1-|i-x_i| <= |y_i -y_{i-1}|[/i] (i.e. 1- rather than 1+)<br />Given what you sent me, I tried the following formulation:

[i]z <= 1 -i + x_i[/i]<br />[i]z <= 1 +i -x_i[/i]<br />[i]z <= y_i - y_{i-1} + Mw[/i]<br />[i]z <= y_i - y_{i-1} + M(1-w)[/i]<br />
Unfortunately, doing so, results in CPLEX pushing z in [-10,1] to its negative limit as this value always validates the constraints in all cases....  Is there any way to push z to 1? I'm guessing it's a simple tweak to this but i'm not sure what.


Why did you change the first two inequalities from >= to <=?  The idea is for z to fit between the left and right sides of the original inequalities, not to be smaller than both.<br />
/Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[gramchurn said:]

Hi,
The left hand side of the last two constraints need to be less or equal to 1 (i.e. when i = x_i). If i switch the first two constraints to >=, z will always be positive and this would make the constraint unsatisfiable for most values of i and x_i because -1 <= y_i - y_{i-1} <= 1. By making z <= ..., i'm trying to keep z negative - which is not the right thing to do...<br />
I think i can manage to remove the right hand side modulus with some tricks, so really, it's the left hand side that matters most.

Thanks a lot for your time!
#CPLEXOptimizers
#DecisionOptimization