optimizationlinear-programminglinearization

Converting conditional subtour elimination of CVRP into normal ones

I am trying to eliminate the if condition constraints from the following CVRP formulation.

enter image description here

I tried some big M methods on paper but failed to come up with a proper reformulation. Can you please help me to find a solution?

Thanks!

Solution

  • You can split the equation into two inequalities and the apply the big-M method:

    ui + qj <= uj + M(1-xij)
ui + qj >= uj - M(1-xij)

    Models with big-M constants tend to be weak and numerically instable, so I suggest to select the constant as small as possible (i.e. make M depend on ij, if possible). To learn more about that have a look at the Perils of "Big M".