Hi,

I have an OPL model with a variable x that can be either 0, or between x_min and x_max (both positive with x_max >= x_min).

I recently found out that OPL allows to use logical symbols, and these are recommended over Big M formulations. However, since in this case the x variable has a real upper bound x_max, I am not sure which formulation of the 2 following can be better from a computational point of view.

1)

x == 0 || x >= x_min ;
x <= x_max ;

2)

x <= x_max * Bool_x_not_null ;
x >= x_min - x_max * ( 1 - Bool_x_not_null ) ;

Which one is better? What are advantages and disadvantages of the 2 variants?

Thank you.

Regards,
Matteo.

------------------------------
Matteo Fineschi
------------------------------

#DecisionOptimization

Hi,
could 
https://www.ibm.com/support/pages/node/397209
help ?


By the way unless you have some performance issue, I recommend to choose what is easier to write and read.

(So the logical constraints)

See also https://www.ibm.com/support/pages/modeling-semi-continuous-variables-opl

for semi-continuous in OPL

regards

------------------------------
ALEX FLEISCHER
------------------------------

What you have are actually semi-integer (or semi-continuous variables). Unfortunately, this variable type is supported by the engines but not by OPL. The ways of formulating such variables is described in this technical document. Using logical constraints will implicitly create binary variables.

Whether the different formulations make difference in solution time has to be tested. My gut feeling is that it will not make a difference. So I would go with whatever is easier to read for you. Personally, I would prefer 2 since with this I know exactly what is going to end up in the model while with 1 I don't know how OPL translates logical constraints. On the other hand, in formulation 1 the bounds appear only as bounds on the variable (and not as coefficients of variables), which is less likely to create numerical issues in case one of them gets very big.

------------------------------
Daniel Junglas
------------------------------

Hello Alex, Hello Daniel,

Thank you both very much for your answers.

In one of the links you sent, there is written that "some of the more advanced features of CPLEX do not operate on indicator constraints, so this reformulation may slow performance."

May I ask which CPLEX features do not support indicator constraints?

Moreover, while reading in Daniel's answer the sentence "Whether the different formulations make difference in solution time has to be tested", another doubt I was thinking about came to my mind.
Maybe it should be written in a new post, but I will try to ask it here:

What is the correct way to compare the effect of 2 different alternative formulations of a constraint in a model?

It may seem a naive question, so I'll try to explain better. There are mainly 2 points:

1) If I run multiple times an identical problem (same model and data), with same time limit etc., is it guaranteed that the runs will have the same result? From my empirical experience, the answer is no. Even completely identical tasks can have different results. What is the cause of this variability?

2) In order to compare 2 alternative formulations, given the variability of point 1, intuitively I would say to solve both the models (with same data) to optimality, and compare the running times. However, solving a big model to optimality might be hard, and the convergence of the solution to the optimal one might be very different (so it doesn't really make sense if during the usual usage of the model I use only sub-optimal solutions).
Moreover, solving the 2 models to a set gap and comparing the solutions doesn't seem correct either. First, again because of the variability mentioned in point 1). Second, it's not easy to say which solution is the best, since usually they are both nondominated. (e.g. with a gap limit of 1%, one solution can have higher gap (0.7%) and worst objective, but smaller running time. The other one better gap (0.5%) and objective, but longer running time, which seems to be a difference caused only by a different final iteration).

What can be a correct approach to do these comparisons?

Thanks a lot,
Matteo.


------------------------------
Vladimír Jirsa
------------------------------

Original Message:
Sent: Fri June 19, 2020 06:03 AM
From: Daniel Junglas
Subject: OPL: Logical OR vs. "small" M formulation.

What you have are actually semi-integer (or semi-continuous variables). Unfortunately, this variable type is supported by the engines but not by OPL. The ways of formulating such variables is described in this technical document. Using logical constraints will implicitly create binary variables.

Whether the different formulations make difference in solution time has to be tested. My gut feeling is that it will not make a difference. So I would go with whatever is easier to read for you. Personally, I would prefer 2 since with this I know exactly what is going to end up in the model while with 1 I don't know how OPL translates logical constraints. On the other hand, in formulation 1 the bounds appear only as bounds on the variable (and not as coefficients of variables), which is less likely to create numerical issues in case one of them gets very big.

------------------------------
Daniel Junglas
------------------------------

Two runs with the exact same input on the exact same machine will give the exact same result, unless you explicitly switch CPLEX to non-deterministic mode or use an inherently non-deterministic resource limit (such as a wallclock time limit).

In order to compare different formulations you can use the "runseed" feature of CPLEX that runs the same problem with different random seeds (thus artificially causing variability).

Another useful strategy would be to feed your model with different datasets and see whether one formulation is consistently better than the other.

I cannot find the sentence about slow performance, can you provide a link to the respective page?

------------------------------
Daniel Junglas
------------------------------

Original Message:
Sent: Fri June 19, 2020 09:10 AM
From: Vladimír Jirsa
Subject: OPL: Logical OR vs. "small" M formulation.

Hello Alex, Hello Daniel,

Thank you both very much for your answers.

In one of the links you sent, there is written that "some of the more advanced features of CPLEX do not operate on indicator constraints, so this reformulation may slow performance."

May I ask which CPLEX features do not support indicator constraints?

Moreover, while reading in Daniel's answer the sentence "Whether the different formulations make difference in solution time has to be tested", another doubt I was thinking about came to my mind.
Maybe it should be written in a new post, but I will try to ask it here:

What is the correct way to compare the effect of 2 different alternative formulations of a constraint in a model?

It may seem a naive question, so I'll try to explain better. There are mainly 2 points:

1) If I run multiple times an identical problem (same model and data), with same time limit etc., is it guaranteed that the runs will have the same result? From my empirical experience, the answer is no. Even completely identical tasks can have different results. What is the cause of this variability?

2) In order to compare 2 alternative formulations, given the variability of point 1, intuitively I would say to solve both the models (with same data) to optimality, and compare the running times. However, solving a big model to optimality might be hard, and the convergence of the solution to the optimal one might be very different (so it doesn't really make sense if during the usual usage of the model I use only sub-optimal solutions).
Moreover, solving the 2 models to a set gap and comparing the solutions doesn't seem correct either. First, again because of the variability mentioned in point 1). Second, it's not easy to say which solution is the best, since usually they are both nondominated. (e.g. with a gap limit of 1%, one solution can have higher gap (0.7%) and worst objective, but smaller running time. The other one better gap (0.5%) and objective, but longer running time, which seems to be a difference caused only by a different final iteration).

What can be a correct approach to do these comparisons?

Thanks a lot,
Matteo.


------------------------------
Vladimír Jirsa
------------------------------


Original Message:
Sent: Fri June 19, 2020 06:03 AM
From: Daniel Junglas
Subject: OPL: Logical OR vs. "small" M formulation.

What you have are actually semi-integer (or semi-continuous variables). Unfortunately, this variable type is supported by the engines but not by OPL. The ways of formulating such variables is described in this technical document. Using logical constraints will implicitly create binary variables.

Whether the different formulations make difference in solution time has to be tested. My gut feeling is that it will not make a difference. So I would go with whatever is easier to read for you. Personally, I would prefer 2 since with this I know exactly what is going to end up in the model while with 1 I don't know how OPL translates logical constraints. On the other hand, in formulation 1 the bounds appear only as bounds on the variable (and not as coefficients of variables), which is less likely to create numerical issues in case one of them gets very big.

------------------------------
Daniel Junglas

Hello Daniel,

Thank you for the answer.

This is the link:
https://www.ibm.com/support/pages/node/397051 
You can find that sentence at the bottom of the document.

Matteo.

------------------------------
Vladimír Jirsa
------------------------------

Original Message:
Sent: Fri June 19, 2020 09:17 AM
From: Daniel Junglas
Subject: OPL: Logical OR vs. "small" M formulation.

Two runs with the exact same input on the exact same machine will give the exact same result, unless you explicitly switch CPLEX to non-deterministic mode or use an inherently non-deterministic resource limit (such as a wallclock time limit).

In order to compare different formulations you can use the "runseed" feature of CPLEX that runs the same problem with different random seeds (thus artificially causing variability).

Another useful strategy would be to feed your model with different datasets and see whether one formulation is consistently better than the other.

I cannot find the sentence about slow performance, can you provide a link to the respective page?

------------------------------
Daniel Junglas
------------------------------


Original Message:
Sent: Fri June 19, 2020 09:10 AM
From: Vladimír Jirsa
Subject: OPL: Logical OR vs. "small" M formulation.

Hello Alex, Hello Daniel,

Thank you both very much for your answers.

In one of the links you sent, there is written that "some of the more advanced features of CPLEX do not operate on indicator constraints, so this reformulation may slow performance."

May I ask which CPLEX features do not support indicator constraints?

Moreover, while reading in Daniel's answer the sentence "Whether the different formulations make difference in solution time has to be tested", another doubt I was thinking about came to my mind.
Maybe it should be written in a new post, but I will try to ask it here:

What is the correct way to compare the effect of 2 different alternative formulations of a constraint in a model?

It may seem a naive question, so I'll try to explain better. There are mainly 2 points:

1) If I run multiple times an identical problem (same model and data), with same time limit etc., is it guaranteed that the runs will have the same result? From my empirical experience, the answer is no. Even completely identical tasks can have different results. What is the cause of this variability?

2) In order to compare 2 alternative formulations, given the variability of point 1, intuitively I would say to solve both the models (with same data) to optimality, and compare the running times. However, solving a big model to optimality might be hard, and the convergence of the solution to the optimal one might be very different (so it doesn't really make sense if during the usual usage of the model I use only sub-optimal solutions).
Moreover, solving the 2 models to a set gap and comparing the solutions doesn't seem correct either. First, again because of the variability mentioned in point 1). Second, it's not easy to say which solution is the best, since usually they are both nondominated. (e.g. with a gap limit of 1%, one solution can have higher gap (0.7%) and worst objective, but smaller running time. The other one better gap (0.5%) and objective, but longer running time, which seems to be a difference caused only by a different final iteration).

What can be a correct approach to do these comparisons?

Thanks a lot,
Matteo.


------------------------------
Vladimír Jirsa


Original Message:
Sent: Fri June 19, 2020 06:03 AM
From: Daniel Junglas
Subject: OPL: Logical OR vs. "small" M formulation.

What you have are actually semi-integer (or semi-continuous variables). Unfortunately, this variable type is supported by the engines but not by OPL. The ways of formulating such variables is described in this technical document. Using logical constraints will implicitly create binary variables.

Whether the different formulations make difference in solution time has to be tested. My gut feeling is that it will not make a difference. So I would go with whatever is easier to read for you. Personally, I would prefer 2 since with this I know exactly what is going to end up in the model while with 1 I don't know how OPL translates logical constraints. On the other hand, in formulation 1 the bounds appear only as bounds on the variable (and not as coefficients of variables), which is less likely to create numerical issues in case one of them gets very big.

------------------------------
Daniel Junglas