Hi,

I am implementing Benders decomposition with lazy constraints and am having an issue. 

Below I am sharing two lazy constraints generated for variable t_2 which is the estimation of the true objective. 

(1.0*t_2 - 0.1*x_0 - 0.1*y_0 - 0.78*x_1 - 0.78*y_1 - 0.05*x_3 - 0.05*y_3 - 0.15*x_4 - 0.15*y_4 - 0.03*x_5 - 0.03*y_5) <= 0.0

(1.0*t_2 + 0.78*x_2 + 0.78*y_2) <= 0.78

When the algorithm stops, the optimal solution is reported as x[0] =1, y[4] =1 where t_2 gets the value of 0.78. 

However, this is not the true optimal. In fact, looking at the first lazy constraint generated by CPLEX, the constraint should be violated since it becomes t_2 <= 0.25 when plugging the values of X and Y. 

Can someone help me out to understand what exactly is going on?


------------------------------
Ser Giovio
------------------------------
#DecisionOptimization

First question: Is there any chance that there is an indexing error in the code somewhere, and that either x_1 or y_1 is actually getting the value 1 in the "optimal" solution?

Second question: Are you setting the cut management parameter to purgeable when you add the Benders cuts? (The default is to force the cuts to stay in the model, so you would have to use the optional management argument to change that.) If so, the first cut could drop out of the model, although your callback should add it back when the "final" solution is found.

All else failing, you can try running in a debugger with a breakpoint in the callback triggered when t_2 = 0.78, then trace it to make sure that the cut added actually cuts off that solution and that the solution is not repeated in a subsequent call to the callback.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------

Original Message:
Sent: Thu October 29, 2020 07:49 PM
From: Ser Giovio
Subject: CPLEX gives optimal solution even though a lazy constraint is violated

Hi,

I am implementing Benders decomposition with lazy constraints and am having an issue. 

Below I am sharing two lazy constraints generated for variable t_2 which is the estimation of the true objective. 

(1.0*t_2 - 0.1*x_0 - 0.1*y_0 - 0.78*x_1 - 0.78*y_1 - 0.05*x_3 - 0.05*y_3 - 0.15*x_4 - 0.15*y_4 - 0.03*x_5 - 0.03*y_5) <= 0.0

(1.0*t_2 + 0.78*x_2 + 0.78*y_2) <= 0.78

When the algorithm stops, the optimal solution is reported as x[0] =1, y[4] =1 where t_2 gets the value of 0.78. 

However, this is not the true optimal. In fact, looking at the first lazy constraint generated by CPLEX, the constraint should be violated since it becomes t_2 <= 0.25 when plugging the values of X and Y. 

Can someone help me out to understand what exactly is going on?


------------------------------
Ser Giovio
------------------------------
#DecisionOptimization

Hi,

1) I double-checked the indexing and everything seems correct. 

2) I am currently adding Benders cuts only at integer solutions for testing purposes. Normally, I set UseCutPurge as False. However, as you mentioned, even if the cut drops out, it should be back.

I tested my implementation on a bigger data set (i.e., a network with 25 nodes) and have encountered the same problem. For example, the optimal solution reported by CPLEX is  (x[23] =1, y[0] = 1, y[1] = 1, y[14] = 1)

I printed out the cuts containing t_3.

i) (1.0*t_3 - 0.1947*x_0 - 0.1947*y_0 - 0.6878*x_1 - 0.6878*y_1 - 0.0532*x_2 - 0.0532*y_2 - 0.0033*x_4 - 0.0033*y_4 - 0.0046*x_5 - 0.0046*y_5 - 0.0499*x_6 - 0.0499*y_6) <= 0.0
ii) (1.0*t_3 + 0.6878*x_3 + 0.6878*y_3 <= 0.6878

As you can see t_3 cannot be larger than 0.6878. Yet, CPLEX reports t_3 as 0.8825.

To check whether the cut is added or not, I started printing the cuts before using rejectCandidate method as shown below.

if ( context.inCandidate() ) {
  System.out.println(violated[i]);
  context.rejectCandidate(violated[i]);

Everything seems working there too. 

Edit: I should also mention that the cut causing the problem seems to be created multiple times. I am assuming this is because of multi threading. If not, do you think that the problem might occur because of this?

IloRange : -infinity <= (1.0*t_3 + 0.6878*x_3 + 0.6878*y_3 ) <= 0.6878
IloRange : -infinity <= (1.0*t_3 + 0.6878*x_3 + 0.6878*y_3 ) <= 0.6878
IloRange : -infinity <= (1.0*t_3 + 0.6878*x_3 + 0.6878*y_3 ) <= 0.6878

------------------------------
Ser Giovio
------------------------------

Original Message:
Sent: Fri October 30, 2020 05:10 PM
From: Paul Rubin
Subject: CPLEX gives optimal solution even though a lazy constraint is violated

First question: Is there any chance that there is an indexing error in the code somewhere, and that either x_1 or y_1 is actually getting the value 1 in the "optimal" solution?

Second question: Are you setting the cut management parameter to purgeable when you add the Benders cuts? (The default is to force the cuts to stay in the model, so you would have to use the optional management argument to change that.) If so, the first cut could drop out of the model, although your callback should add it back when the "final" solution is found.

All else failing, you can try running in a debugger with a breakpoint in the callback triggered when t_2 = 0.78, then trace it to make sure that the cut added actually cuts off that solution and that the solution is not repeated in a subsequent call to the callback.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University

Original Message:
Sent: Thu October 29, 2020 07:49 PM
From: Ser Giovio
Subject: CPLEX gives optimal solution even though a lazy constraint is violated

Hi,

I am implementing Benders decomposition with lazy constraints and am having an issue. 

Below I am sharing two lazy constraints generated for variable t_2 which is the estimation of the true objective. 

(1.0*t_2 - 0.1*x_0 - 0.1*y_0 - 0.78*x_1 - 0.78*y_1 - 0.05*x_3 - 0.05*y_3 - 0.15*x_4 - 0.15*y_4 - 0.03*x_5 - 0.03*y_5) <= 0.0

(1.0*t_2 + 0.78*x_2 + 0.78*y_2) <= 0.78

When the algorithm stops, the optimal solution is reported as x[0] =1, y[4] =1 where t_2 gets the value of 0.78. 

However, this is not the true optimal. In fact, looking at the first lazy constraint generated by CPLEX, the constraint should be violated since it becomes t_2 <= 0.25 when plugging the values of X and Y. 

Can someone help me out to understand what exactly is going on?


------------------------------
Ser Giovio
------------------------------
#DecisionOptimization

You appear to be using a generic callback. Have you taken care to make it thread-safe? Thread safety was not an issue with the legacy callbacks, due I think to the way CPLEX called them, but with generic callbacks it is left to the user to make the callback thread-safe.

I do not think that generating the same cut in separate threads is necessarily a problem.

One other debugging trick you can try is to store each of the cuts in a global array. In the Java API, this array would be declared as IloRange[]. Once CPLEX reports an "optimal" solution, you can invoke IloCplex.getSlacks() on the array to get all slacks, and/or invoke IloRange.getExpr() on one of them to get the expression in the cut and then IloCplex.getValue() on that expression to get what CPLEX thinks is the value of that expression at the optimal solution. This might narrow down whether CPLEX is somehow evaluating the cuts incorrectly or whether the cuts themselves are somehow wrong.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------

Original Message:
Sent: Sat October 31, 2020 09:55 PM
From: Ser Giovio
Subject: CPLEX gives optimal solution even though a lazy constraint is violated

Hi,

1) I double-checked the indexing and everything seems correct. 

2) I am currently adding Benders cuts only at integer solutions for testing purposes. Normally, I set UseCutPurge as False. However, as you mentioned, even if the cut drops out, it should be back.

I tested my implementation on a bigger data set (i.e., a network with 25 nodes) and have encountered the same problem. For example, the optimal solution reported by CPLEX is  (x[23] =1, y[0] = 1, y[1] = 1, y[14] = 1)

I printed out the cuts containing t_3.

i) (1.0*t_3 - 0.1947*x_0 - 0.1947*y_0 - 0.6878*x_1 - 0.6878*y_1 - 0.0532*x_2 - 0.0532*y_2 - 0.0033*x_4 - 0.0033*y_4 - 0.0046*x_5 - 0.0046*y_5 - 0.0499*x_6 - 0.0499*y_6) <= 0.0
ii) (1.0*t_3 + 0.6878*x_3 + 0.6878*y_3 <= 0.6878

As you can see t_3 cannot be larger than 0.6878. Yet, CPLEX reports t_3 as 0.8825.

To check whether the cut is added or not, I started printing the cuts before using rejectCandidate method as shown below.

if ( context.inCandidate() ) {
  System.out.println(violated[i]);
  context.rejectCandidate(violated[i]);

Everything seems working there too. 

Edit: I should also mention that the cut causing the problem seems to be created multiple times. I am assuming this is because of multi threading. If not, do you think that the problem might occur because of this?

IloRange : -infinity <= (1.0*t_3 + 0.6878*x_3 + 0.6878*y_3 ) <= 0.6878
IloRange : -infinity <= (1.0*t_3 + 0.6878*x_3 + 0.6878*y_3 ) <= 0.6878
IloRange : -infinity <= (1.0*t_3 + 0.6878*x_3 + 0.6878*y_3 ) <= 0.6878

------------------------------
Ser Giovio

Original Message:
Sent: Fri October 30, 2020 05:10 PM
From: Paul Rubin
Subject: CPLEX gives optimal solution even though a lazy constraint is violated

First question: Is there any chance that there is an indexing error in the code somewhere, and that either x_1 or y_1 is actually getting the value 1 in the "optimal" solution?

Second question: Are you setting the cut management parameter to purgeable when you add the Benders cuts? (The default is to force the cuts to stay in the model, so you would have to use the optional management argument to change that.) If so, the first cut could drop out of the model, although your callback should add it back when the "final" solution is found.

All else failing, you can try running in a debugger with a breakpoint in the callback triggered when t_2 = 0.78, then trace it to make sure that the cut added actually cuts off that solution and that the solution is not repeated in a subsequent call to the callback.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University

Original Message:
Sent: Thu October 29, 2020 07:49 PM
From: Ser Giovio
Subject: CPLEX gives optimal solution even though a lazy constraint is violated

Hi,

I am implementing Benders decomposition with lazy constraints and am having an issue. 

Below I am sharing two lazy constraints generated for variable t_2 which is the estimation of the true objective. 

(1.0*t_2 - 0.1*x_0 - 0.1*y_0 - 0.78*x_1 - 0.78*y_1 - 0.05*x_3 - 0.05*y_3 - 0.15*x_4 - 0.15*y_4 - 0.03*x_5 - 0.03*y_5) <= 0.0

(1.0*t_2 + 0.78*x_2 + 0.78*y_2) <= 0.78

When the algorithm stops, the optimal solution is reported as x[0] =1, y[4] =1 where t_2 gets the value of 0.78. 

However, this is not the true optimal. In fact, looking at the first lazy constraint generated by CPLEX, the constraint should be violated since it becomes t_2 <= 0.25 when plugging the values of X and Y. 

Can someone help me out to understand what exactly is going on?


------------------------------
Ser Giovio
------------------------------
#DecisionOptimization

Thanks for your time and suggestions. I believe that there might be something wrong with my Benders cuts. I will work on it and give it a try to what you suggested.

------------------------------
Ser Giovio
------------------------------

Original Message:
Sent: Sun November 01, 2020 01:59 PM
From: Paul Rubin
Subject: CPLEX gives optimal solution even though a lazy constraint is violated

You appear to be using a generic callback. Have you taken care to make it thread-safe? Thread safety was not an issue with the legacy callbacks, due I think to the way CPLEX called them, but with generic callbacks it is left to the user to make the callback thread-safe.

I do not think that generating the same cut in separate threads is necessarily a problem.

One other debugging trick you can try is to store each of the cuts in a global array. In the Java API, this array would be declared as IloRange[]. Once CPLEX reports an "optimal" solution, you can invoke IloCplex.getSlacks() on the array to get all slacks, and/or invoke IloRange.getExpr() on one of them to get the expression in the cut and then IloCplex.getValue() on that expression to get what CPLEX thinks is the value of that expression at the optimal solution. This might narrow down whether CPLEX is somehow evaluating the cuts incorrectly or whether the cuts themselves are somehow wrong.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University

Original Message:
Sent: Sat October 31, 2020 09:55 PM
From: Ser Giovio
Subject: CPLEX gives optimal solution even though a lazy constraint is violated

Hi,

1) I double-checked the indexing and everything seems correct. 

2) I am currently adding Benders cuts only at integer solutions for testing purposes. Normally, I set UseCutPurge as False. However, as you mentioned, even if the cut drops out, it should be back.

I tested my implementation on a bigger data set (i.e., a network with 25 nodes) and have encountered the same problem. For example, the optimal solution reported by CPLEX is  (x[23] =1, y[0] = 1, y[1] = 1, y[14] = 1)

I printed out the cuts containing t_3.

i) (1.0*t_3 - 0.1947*x_0 - 0.1947*y_0 - 0.6878*x_1 - 0.6878*y_1 - 0.0532*x_2 - 0.0532*y_2 - 0.0033*x_4 - 0.0033*y_4 - 0.0046*x_5 - 0.0046*y_5 - 0.0499*x_6 - 0.0499*y_6) <= 0.0
ii) (1.0*t_3 + 0.6878*x_3 + 0.6878*y_3 <= 0.6878

As you can see t_3 cannot be larger than 0.6878. Yet, CPLEX reports t_3 as 0.8825.

To check whether the cut is added or not, I started printing the cuts before using rejectCandidate method as shown below.

if ( context.inCandidate() ) {
  System.out.println(violated[i]);
  context.rejectCandidate(violated[i]);

Everything seems working there too. 

Edit: I should also mention that the cut causing the problem seems to be created multiple times. I am assuming this is because of multi threading. If not, do you think that the problem might occur because of this?

IloRange : -infinity <= (1.0*t_3 + 0.6878*x_3 + 0.6878*y_3 ) <= 0.6878
IloRange : -infinity <= (1.0*t_3 + 0.6878*x_3 + 0.6878*y_3 ) <= 0.6878
IloRange : -infinity <= (1.0*t_3 + 0.6878*x_3 + 0.6878*y_3 ) <= 0.6878

------------------------------
Ser Giovio

Original Message:
Sent: Fri October 30, 2020 05:10 PM
From: Paul Rubin
Subject: CPLEX gives optimal solution even though a lazy constraint is violated

First question: Is there any chance that there is an indexing error in the code somewhere, and that either x_1 or y_1 is actually getting the value 1 in the "optimal" solution?

Second question: Are you setting the cut management parameter to purgeable when you add the Benders cuts? (The default is to force the cuts to stay in the model, so you would have to use the optional management argument to change that.) If so, the first cut could drop out of the model, although your callback should add it back when the "final" solution is found.

All else failing, you can try running in a debugger with a breakpoint in the callback triggered when t_2 = 0.78, then trace it to make sure that the cut added actually cuts off that solution and that the solution is not repeated in a subsequent call to the callback.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University

Original Message:
Sent: Thu October 29, 2020 07:49 PM
From: Ser Giovio
Subject: CPLEX gives optimal solution even though a lazy constraint is violated

Hi,

I am implementing Benders decomposition with lazy constraints and am having an issue. 

Below I am sharing two lazy constraints generated for variable t_2 which is the estimation of the true objective. 

(1.0*t_2 - 0.1*x_0 - 0.1*y_0 - 0.78*x_1 - 0.78*y_1 - 0.05*x_3 - 0.05*y_3 - 0.15*x_4 - 0.15*y_4 - 0.03*x_5 - 0.03*y_5) <= 0.0

(1.0*t_2 + 0.78*x_2 + 0.78*y_2) <= 0.78

When the algorithm stops, the optimal solution is reported as x[0] =1, y[4] =1 where t_2 gets the value of 0.78. 

However, this is not the true optimal. In fact, looking at the first lazy constraint generated by CPLEX, the constraint should be violated since it becomes t_2 <= 0.25 when plugging the values of X and Y. 

Can someone help me out to understand what exactly is going on?


------------------------------
Ser Giovio
------------------------------
#DecisionOptimization