Hello,

I´m using the Java API to code a Vehicle Routing Problem.

The program often works as intended, however, in some instances , constraints are ignored but the solver says it has found a solution.

For instance, these two constraints ensure that each location is entered once and exited once by only one vehicle:

These constraints are usually respected, but sometimes they are not and the solver still gives a solution.

I have exported the model to an lp file and I have checked that these constraints are actually stated, but still not respected by the solver.

I'm using cplex 12.10, is this a cplex bug? How can i deal with this problem?

Thanks.

------------------------------
Pedro Pereira
------------------------------

#DecisionOptimization

Did you check that the solution violates the constraints as they appear in the .lp file, or as they appear in the image? I'm wondering if the constraints, while present in the .lp file, might be incorrect there (so that the solution violates the constraints in the image but satisfies the ones in the file).

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

Original Message:
Sent: Sun September 27, 2020 03:13 PM
From: Pedro Pereira
Subject: Cplex doesn't respect constraints but says it has found solution

Hello,

I´m using the Java API to code a Vehicle Routing Problem.

The program often works as intended, however, in some instances , constraints are ignored but the solver says it has found a solution.

For instance, these two constraints ensure that each location is entered once and exited once by only one vehicle:

These constraints are usually respected, but sometimes they are not and the solver still gives a solution.

I have exported the model to an lp file and I have checked that these constraints are actually stated, but still not respected by the solver.

I'm using cplex 12.10, is this a cplex bug? How can i deal with this problem?

Thanks.

------------------------------
Pedro Pereira
------------------------------

#DecisionOptimization

Hello,

Thank you for your answer.

I have run an instance of a vehicle routing problem with only one vehicle and 54 locations to verify what is happening.
I have come to the conclusion that the binary variables that I'm using, when they are equal to one they sometimes are really not equal to one but approximately equal to one.

For instance for the 41st location I stated the following constraint (taken form the resulting .lp file):

x_41_0_0 + x_41_1_0 + x_41_2_0 + x_41_3_0 + x_41_4_0
+ x_41_5_0 + x_41_6_0 + x_41_7_0 + x_41_8_0 + x_41_9_0
+ x_41_10_0 + x_41_11_0 + x_41_12_0 + x_41_13_0 + x_41_14_0
+ x_41_15_0 + x_41_16_0 + x_41_17_0 + x_41_18_0 + x_41_19_0
+ x_41_20_0 + x_41_21_0 + x_41_22_0 + x_41_23_0 + x_41_24_0
+ x_41_25_0 + x_41_26_0 + x_41_27_0 + x_41_28_0 + x_41_29_0
+ x_41_30_0 + x_41_31_0 + x_41_32_0 + x_41_33_0 + x_41_34_0
+ x_41_35_0 + x_41_36_0 + x_41_37_0 + x_41_38_0 + x_41_39_0
+ x_41_40_0 + x_41_42_0 + x_41_43_0 + x_41_44_0 + x_41_45_0
+ x_41_46_0 + x_41_47_0 + x_41_48_0 + x_41_49_0 + x_41_50_0
+ x_41_51_0 + x_41_52_0 + x_41_53_0 = 1

This means that the vehicle has to exit the 41st location exactly once, so one of these variables have to be equal to one. However, the x_41_23_0 value is equal to 1.0000000000001599 instead of exactly one (see figure below, igual means equal):


Since i was checking if the variable is exactly equal to 1 I was not identifying these values.

Why does this happen and why does the x_41_12_0 variable is also not equal to exactly zero but approximately zero?
Is there a better way to verify a binary variable value other than the getValue method (I´m using the JAVA API)?

Thanks in advance

------------------------------
Pedro Pereira
------------------------------

Original Message:
Sent: Mon September 28, 2020 03:02 PM
From: Paul Rubin
Subject: Cplex doesn't respect constraints but says it has found solution

Did you check that the solution violates the constraints as they appear in the .lp file, or as they appear in the image? I'm wondering if the constraints, while present in the .lp file, might be incorrect there (so that the solution violates the constraints in the image but satisfies the ones in the file).

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

Original Message:
Sent: Sun September 27, 2020 03:13 PM
From: Pedro Pereira
Subject: Cplex doesn't respect constraints but says it has found solution

Hello,

I´m using the Java API to code a Vehicle Routing Problem.

The program often works as intended, however, in some instances , constraints are ignored but the solver says it has found a solution.

For instance, these two constraints ensure that each location is entered once and exited once by only one vehicle:

These constraints are usually respected, but sometimes they are not and the solver still gives a solution.

I have exported the model to an lp file and I have checked that these constraints are actually stated, but still not respected by the solver.

I'm using cplex 12.10, is this a cplex bug? How can i deal with this problem?

Thanks.

------------------------------
Pedro Pereira
------------------------------
#DecisionOptimization

This is standard with integer programming. Internally, almost all solvers use double precision values for integer variables (including binary variables), and there is always rounding and truncation error. CPLEX, like other solvers, has a nonzero integrality tolerance. In the Java API, its name is IloCplex.Param.MIP.Tolerances.Integrality and its default value is 1e-5. So, by default, any value within +/- 1e-5 of the nearest integer is considered to satisfy an integrality requirement for the corresponding variable.

When I'm solving a problem with binary variables, I just compare the value from getValue to 0.5 and call it 0 or 1 depending on which side of 0.5 it falls. Barring some serious problems with numerical stability in the model, CPLEX will never give you a value near 0.5 for a binary; it's just a convenient break point for the comparison.

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

Original Message:
Sent: Mon September 28, 2020 04:00 PM
From: Pedro Pereira
Subject: Cplex doesn't respect constraints but says it has found solution

Hello,

Thank you for your answer.

I have run an instance of a vehicle routing problem with only one vehicle and 54 locations to verify what is happening.
I have come to the conclusion that the binary variables that I'm using, when they are equal to one they sometimes are really not equal to one but approximately equal to one.

For instance for the 41st location I stated the following constraint (taken form the resulting .lp file):

x_41_0_0 + x_41_1_0 + x_41_2_0 + x_41_3_0 + x_41_4_0
+ x_41_5_0 + x_41_6_0 + x_41_7_0 + x_41_8_0 + x_41_9_0
+ x_41_10_0 + x_41_11_0 + x_41_12_0 + x_41_13_0 + x_41_14_0
+ x_41_15_0 + x_41_16_0 + x_41_17_0 + x_41_18_0 + x_41_19_0
+ x_41_20_0 + x_41_21_0 + x_41_22_0 + x_41_23_0 + x_41_24_0
+ x_41_25_0 + x_41_26_0 + x_41_27_0 + x_41_28_0 + x_41_29_0
+ x_41_30_0 + x_41_31_0 + x_41_32_0 + x_41_33_0 + x_41_34_0
+ x_41_35_0 + x_41_36_0 + x_41_37_0 + x_41_38_0 + x_41_39_0
+ x_41_40_0 + x_41_42_0 + x_41_43_0 + x_41_44_0 + x_41_45_0
+ x_41_46_0 + x_41_47_0 + x_41_48_0 + x_41_49_0 + x_41_50_0
+ x_41_51_0 + x_41_52_0 + x_41_53_0 = 1

This means that the vehicle has to exit the 41st location exactly once, so one of these variables have to be equal to one. However, the x_41_23_0 value is equal to 1.0000000000001599 instead of exactly one (see figure below, igual means equal):

Since i was checking if the variable is exactly equal to 1 I was not identifying these values.

Why does this happen and why does the x_41_12_0 variable is also not equal to exactly zero but approximately zero?
Is there a better way to verify a binary variable value other than the getValue method (I´m using the JAVA API)?

Thanks in advance

------------------------------
Pedro Pereira

Original Message:
Sent: Mon September 28, 2020 03:02 PM
From: Paul Rubin
Subject: Cplex doesn't respect constraints but says it has found solution

Did you check that the solution violates the constraints as they appear in the .lp file, or as they appear in the image? I'm wondering if the constraints, while present in the .lp file, might be incorrect there (so that the solution violates the constraints in the image but satisfies the ones in the file).

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

Original Message:
Sent: Sun September 27, 2020 03:13 PM
From: Pedro Pereira
Subject: Cplex doesn't respect constraints but says it has found solution

Hello,

I´m using the Java API to code a Vehicle Routing Problem.

The program often works as intended, however, in some instances , constraints are ignored but the solver says it has found a solution.

For instance, these two constraints ensure that each location is entered once and exited once by only one vehicle:

These constraints are usually respected, but sometimes they are not and the solver still gives a solution.

I have exported the model to an lp file and I have checked that these constraints are actually stated, but still not respected by the solver.

I'm using cplex 12.10, is this a cplex bug? How can i deal with this problem?

Thanks.

------------------------------
Pedro Pereira
------------------------------
#DecisionOptimization