Decision Optimization

Hi all,

I am working on a variant of the vehicle routing problem with CPLEX and the solver returns solutions for binary decision variables that are far from binary, things like 0.1, 0.3, 0.5, etc., also some very small numbers or very close to 1, which is less problematic.

I thought the reason could be numerical instability due to using big M, but even if I switch off parts of the model using big M, which are not essential to model for instance the flow, it still gives very weird solutions.

Any help would be highly appreciated!

Thanks,

Jacob Trepat

------------------------------
Jacob Trepat
------------------------------

#DecisionOptimization

Hello,

Could you post CPLEX's log? That would help diagnosing the issue... :-).

Cheers,
--Laci

------------------------------
Laszlo Ladanyi
------------------------------

Original Message:
Sent: Sun May 10, 2020 01:35 AM
From: Jacob Trepat
Subject: Cplex returns fractional solutions for binary variables in VRP variant

Hi all,

I am working on a variant of the vehicle routing problem with CPLEX and the solver returns solutions for binary decision variables that are far from binary, things like 0.1, 0.3, 0.5, etc., also some very small numbers or very close to 1, which is less problematic.

I thought the reason could be numerical instability due to using big M, but even if I switch off parts of the model using big M, which are not essential to model for instance the flow, it still gives very weird solutions.

Any help would be highly appreciated!

Thanks,

Jacob Trepat

------------------------------
Jacob Trepat
------------------------------

#DecisionOptimization

Even for a model with bad numerics, I think a value of 0.5 for a binary variable is way too off. Maybe CPLEX treats your binary as floating point for some reason. How exactly do you create your model (OPL, programming API, write LP file by hand, ...)? Can you share the offending model?

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

Original Message:
Sent: Sun May 10, 2020 01:35 AM
From: Jacob Trepat
Subject: Cplex returns fractional solutions for binary variables in VRP variant

Hi all,

I am working on a variant of the vehicle routing problem with CPLEX and the solver returns solutions for binary decision variables that are far from binary, things like 0.1, 0.3, 0.5, etc., also some very small numbers or very close to 1, which is less problematic.

I thought the reason could be numerical instability due to using big M, but even if I switch off parts of the model using big M, which are not essential to model for instance the flow, it still gives very weird solutions.

Any help would be highly appreciated!

Thanks,

Jacob Trepat

------------------------------
Jacob Trepat
------------------------------

#DecisionOptimization

Hi Laszlo and Daniel,

Thanks for your replies!

I assume that by CPLEX's log you mean the output lp file, right?

I attach it here, together with the written mathematical formulation, which may help as well.

I am using Matlab to write the code.

Some explanations:

So I have this problem formulation (I show just the relevant sections): I have flow variables x_ij^t and variables to model the origin and destination of a vehicle, o_i^t and d_i^t respectively. The problem is found in the variables relating to the subset T^EXT \subset T, I find non-binary variables for x_ij^t, o_i^t and d_i^t. These variables appear in equations (1) to (2), (12) to (18), (25), (27) to (29) and (44). I show in the pdf which ones are switched off in the model from the lp file. Vehicles belonging to the subset T^EXT have to select 1 origin and 1 destination among a subset of possible nodes. The rest of the vehicles (T^RR and T^ST) have their origin and destination fixed. In the lp file, there is only one vehicle belonging to T^EXT, which is numbered as 'c330'.

In the lp file you can find these equations numbered as follows:
(1) objective function
(2) from #2667 to #2798
(12) to (13) from #8791 to #8792
(44) from #9506 to #10051

Please let me know if you need any additional information. Thanks a lot!

Best,

Jacob Trepat

------------------------------
Jacob Trepat
------------------------------

Original Message:
Sent: Mon May 11, 2020 11:23 AM
From: Daniel Junglas
Subject: Cplex returns fractional solutions for binary variables in VRP variant

Even for a model with bad numerics, I think a value of 0.5 for a binary variable is way too off. Maybe CPLEX treats your binary as floating point for some reason. How exactly do you create your model (OPL, programming API, write LP file by hand, ...)? Can you share the offending model?

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

Original Message:
Sent: Sun May 10, 2020 01:35 AM
From: Jacob Trepat
Subject: Cplex returns fractional solutions for binary variables in VRP variant

Hi all,

I am working on a variant of the vehicle routing problem with CPLEX and the solver returns solutions for binary decision variables that are far from binary, things like 0.1, 0.3, 0.5, etc., also some very small numbers or very close to 1, which is less problematic.

I thought the reason could be numerical instability due to using big M, but even if I switch off parts of the model using big M, which are not essential to model for instance the flow, it still gives very weird solutions.

Any help would be highly appreciated!

Thanks,

Jacob Trepat

------------------------------
Jacob Trepat
------------------------------

#DecisionOptimization

The LP file does not contain any binary variables. That explains why you get fractional values. Do you happen to specify your integer variables like in this thread:
https://stackoverflow.com/questions/58461110/why-do-i-get-non-integer-results-from-milp-problem
If so, then I think that is where the problem is. The "integer" keyword may be ignored. Does it help to specify the binary variables similar to what is done in mipex1.m or cplexmilpex.m (both are shipped with CPLEX)? I.e., does it help to specify the variable type as ctype argument using 'B' for binary variables?

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

Original Message:
Sent: Tue May 12, 2020 05:46 AM
From: Jacob Trepat
Subject: Cplex returns fractional solutions for binary variables in VRP variant

Hi Laszlo and Daniel,

Thanks for your replies!

I assume that by CPLEX's log you mean the output lp file, right?

I attach it here, together with the written mathematical formulation, which may help as well.

I am using Matlab to write the code.

Some explanations:

So I have this problem formulation (I show just the relevant sections): I have flow variables x_ij^t and variables to model the origin and destination of a vehicle, o_i^t and d_i^t respectively. The problem is found in the variables relating to the subset T^EXT \subset T, I find non-binary variables for x_ij^t, o_i^t and d_i^t. These variables appear in equations (1) to (2), (12) to (18), (25), (27) to (29) and (44). I show in the pdf which ones are switched off in the model from the lp file. Vehicles belonging to the subset T^EXT have to select 1 origin and 1 destination among a subset of possible nodes. The rest of the vehicles (T^RR and T^ST) have their origin and destination fixed. In the lp file, there is only one vehicle belonging to T^EXT, which is numbered as 'c330'.

In the lp file you can find these equations numbered as follows:
(1) objective function
(2) from #2667 to #2798
(12) to (13) from #8791 to #8792
(44) from #9506 to #10051

Please let me know if you need any additional information. Thanks a lot!

Best,

Jacob Trepat

------------------------------
Jacob Trepat

Original Message:
Sent: Mon May 11, 2020 11:23 AM
From: Daniel Junglas
Subject: Cplex returns fractional solutions for binary variables in VRP variant

Even for a model with bad numerics, I think a value of 0.5 for a binary variable is way too off. Maybe CPLEX treats your binary as floating point for some reason. How exactly do you create your model (OPL, programming API, write LP file by hand, ...)? Can you share the offending model?

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

Original Message:
Sent: Sun May 10, 2020 01:35 AM
From: Jacob Trepat
Subject: Cplex returns fractional solutions for binary variables in VRP variant

Hi all,

I am working on a variant of the vehicle routing problem with CPLEX and the solver returns solutions for binary decision variables that are far from binary, things like 0.1, 0.3, 0.5, etc., also some very small numbers or very close to 1, which is less problematic.

I thought the reason could be numerical instability due to using big M, but even if I switch off parts of the model using big M, which are not essential to model for instance the flow, it still gives very weird solutions.

Any help would be highly appreciated!

Thanks,

Jacob Trepat

------------------------------
Jacob Trepat
------------------------------

#DecisionOptimization

Yes, Daniel is correct: the 'integer' keyword is ignored. I have just posted a trivial workaround to that stackoverflow thread, please, take a look at it.

--Laci

------------------------------
Laszlo Ladanyi
------------------------------

Original Message:
Sent: Tue May 12, 2020 09:34 AM
From: Daniel Junglas
Subject: Cplex returns fractional solutions for binary variables in VRP variant

The LP file does not contain any binary variables. That explains why you get fractional values. Do you happen to specify your integer variables like in this thread:
https://stackoverflow.com/questions/58461110/why-do-i-get-non-integer-results-from-milp-problem
If so, then I think that is where the problem is. The "integer" keyword may be ignored. Does it help to specify the binary variables similar to what is done in mipex1.m or cplexmilpex.m (both are shipped with CPLEX)? I.e., does it help to specify the variable type as ctype argument using 'B' for binary variables?

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

Original Message:
Sent: Tue May 12, 2020 05:46 AM
From: Jacob Trepat
Subject: Cplex returns fractional solutions for binary variables in VRP variant

Hi Laszlo and Daniel,

Thanks for your replies!

I assume that by CPLEX's log you mean the output lp file, right?

I attach it here, together with the written mathematical formulation, which may help as well.

I am using Matlab to write the code.

Some explanations:

So I have this problem formulation (I show just the relevant sections): I have flow variables x_ij^t and variables to model the origin and destination of a vehicle, o_i^t and d_i^t respectively. The problem is found in the variables relating to the subset T^EXT \subset T, I find non-binary variables for x_ij^t, o_i^t and d_i^t. These variables appear in equations (1) to (2), (12) to (18), (25), (27) to (29) and (44). I show in the pdf which ones are switched off in the model from the lp file. Vehicles belonging to the subset T^EXT have to select 1 origin and 1 destination among a subset of possible nodes. The rest of the vehicles (T^RR and T^ST) have their origin and destination fixed. In the lp file, there is only one vehicle belonging to T^EXT, which is numbered as 'c330'.

In the lp file you can find these equations numbered as follows:
(1) objective function
(2) from #2667 to #2798
(12) to (13) from #8791 to #8792
(44) from #9506 to #10051

Please let me know if you need any additional information. Thanks a lot!

Best,

Jacob Trepat

------------------------------
Jacob Trepat

Original Message:
Sent: Mon May 11, 2020 11:23 AM
From: Daniel Junglas
Subject: Cplex returns fractional solutions for binary variables in VRP variant

Even for a model with bad numerics, I think a value of 0.5 for a binary variable is way too off. Maybe CPLEX treats your binary as floating point for some reason. How exactly do you create your model (OPL, programming API, write LP file by hand, ...)? Can you share the offending model?

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

Original Message:
Sent: Sun May 10, 2020 01:35 AM
From: Jacob Trepat
Subject: Cplex returns fractional solutions for binary variables in VRP variant

Hi all,

I am working on a variant of the vehicle routing problem with CPLEX and the solver returns solutions for binary decision variables that are far from binary, things like 0.1, 0.3, 0.5, etc., also some very small numbers or very close to 1, which is less problematic.

I thought the reason could be numerical instability due to using big M, but even if I switch off parts of the model using big M, which are not essential to model for instance the flow, it still gives very weird solutions.

Any help would be highly appreciated!

Thanks,

Jacob Trepat

------------------------------
Jacob Trepat
------------------------------

#DecisionOptimization

Hi Daniel and Laszlo,

Indeed, the ctype argument was switched off, so it was a very silly mistake. Now it works perfectly. Thanks a lot for noticing!

Best,

------------------------------
Jacob Trepat
------------------------------

Original Message:
Sent: Tue May 12, 2020 05:05 PM
From: Laszlo Ladanyi
Subject: Cplex returns fractional solutions for binary variables in VRP variant

Yes, Daniel is correct: the 'integer' keyword is ignored. I have just posted a trivial workaround to that stackoverflow thread, please, take a look at it.

--Laci

------------------------------
Laszlo Ladanyi

Original Message:
Sent: Tue May 12, 2020 09:34 AM
From: Daniel Junglas
Subject: Cplex returns fractional solutions for binary variables in VRP variant

The LP file does not contain any binary variables. That explains why you get fractional values. Do you happen to specify your integer variables like in this thread:
https://stackoverflow.com/questions/58461110/why-do-i-get-non-integer-results-from-milp-problem
If so, then I think that is where the problem is. The "integer" keyword may be ignored. Does it help to specify the binary variables similar to what is done in mipex1.m or cplexmilpex.m (both are shipped with CPLEX)? I.e., does it help to specify the variable type as ctype argument using 'B' for binary variables?

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

Original Message:
Sent: Tue May 12, 2020 05:46 AM
From: Jacob Trepat
Subject: Cplex returns fractional solutions for binary variables in VRP variant

Hi Laszlo and Daniel,

Thanks for your replies!

I assume that by CPLEX's log you mean the output lp file, right?

I attach it here, together with the written mathematical formulation, which may help as well.

I am using Matlab to write the code.

Some explanations:

So I have this problem formulation (I show just the relevant sections): I have flow variables x_ij^t and variables to model the origin and destination of a vehicle, o_i^t and d_i^t respectively. The problem is found in the variables relating to the subset T^EXT \subset T, I find non-binary variables for x_ij^t, o_i^t and d_i^t. These variables appear in equations (1) to (2), (12) to (18), (25), (27) to (29) and (44). I show in the pdf which ones are switched off in the model from the lp file. Vehicles belonging to the subset T^EXT have to select 1 origin and 1 destination among a subset of possible nodes. The rest of the vehicles (T^RR and T^ST) have their origin and destination fixed. In the lp file, there is only one vehicle belonging to T^EXT, which is numbered as 'c330'.

In the lp file you can find these equations numbered as follows:
(1) objective function
(2) from #2667 to #2798
(12) to (13) from #8791 to #8792
(44) from #9506 to #10051

Please let me know if you need any additional information. Thanks a lot!

Best,

Jacob Trepat

------------------------------
Jacob Trepat

Original Message:
Sent: Mon May 11, 2020 11:23 AM
From: Daniel Junglas
Subject: Cplex returns fractional solutions for binary variables in VRP variant

Even for a model with bad numerics, I think a value of 0.5 for a binary variable is way too off. Maybe CPLEX treats your binary as floating point for some reason. How exactly do you create your model (OPL, programming API, write LP file by hand, ...)? Can you share the offending model?

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

Original Message:
Sent: Sun May 10, 2020 01:35 AM
From: Jacob Trepat
Subject: Cplex returns fractional solutions for binary variables in VRP variant

Hi all,

I am working on a variant of the vehicle routing problem with CPLEX and the solver returns solutions for binary decision variables that are far from binary, things like 0.1, 0.3, 0.5, etc., also some very small numbers or very close to 1, which is less problematic.

I thought the reason could be numerical instability due to using big M, but even if I switch off parts of the model using big M, which are not essential to model for instance the flow, it still gives very weird solutions.

Any help would be highly appreciated!

Thanks,

Jacob Trepat

------------------------------
Jacob Trepat
------------------------------

#DecisionOptimization