How to get only one path beginning and ending at same node?

Question

I'm trying to run this model in Cplex/OPL to find the best path given distances of shops, and quantities + prices in each shop for different products. The problem is I'm getting results of paths that are disjointed - "islands". What constraint do i need to add to get only one closed path that begins and ends at node 1? this is the model:

 dvar float+ x[products,stores];
 dvar boolean y[stores,stores];


 minimize ((sum(i in products, j in stores) prices[i,j]*x[i,j]) + (sum(j in stores, k     
 in stores) gas*distance[j,k]*y[j,k]));

  subject to {
    sum(k in stores) y[1,k] == 1;
    sum(j in stores) y[j,1] == 1;
    forall(j in stores) 
        sum(i in products) x[i,j] <= M*sum(k in stores) y[j,k];
    forall(j in stores)
        sum(i in products) x[i,j] <= M*sum(k in stores) y[k,j];
    forall(i in products) sum(j in stores) x[i,j] == demand[i];
    forall(i in products, j in stores) x[i,j] <= quantity[i,j];
    forall(j in stores, k in stores) y[j,k] + y[k,j] <= 1;
    forall(j in stores) sum(k in stores) y[j,k] == sum(k in stores) y[k,j];

}

Thanks!

Answer 1

What you are solving is a variation of the traveling salesman problem. Specifically, what you are getting are called subtours, which is a closed path that involves fewer than all of the nodes (shops in your case.)

There are an exponential number of subtours for a given set of nodes. A huge body of literature exists around subtour elimination constraints. Fortunately, for smallish problems in practice, we can get away with adding subtour elimination constraints on an as needed basis.

Subtour Elimination

Here's the idea for how to eliminate a subtour S that involves s shops (s < num_stores):

In English: We start off by partitioning the set of nodes (shops) into two groups S and T. Let S be the set of shops in the subtour. Let T be the set of shops outside of S, i.e. all the other shops. We want to break the single-loop path which involves just the shops in S.

Pseudocode

Do while:
    Solve the current problem 
    If you don't find any subtours, you are done. Exit.
    If there are subtours, add the subtour elimination constraints (see details below)
    Continue

Implementing a set of constraints to eliminate current subtour

For each subtour ("island") you have to first create a set of shops_in_subtour. All the other nodes (shops) go into the other set (T) shops_not_in_subtour

Add the following to the your constraints set:

forall(s in shops_in_subtour)
  forall(t in shops_not_in_subtour)
    sum y[s,t] > = 1; // at least one edge must leave S and go to T
    sum y[t,s] > = 1; // at least one edge must enter the set S from T

If your problem is small, you will see that adding a few of these sets of constraints will suffice. Hope that helps you move forward.

Update based on OP's follow-up question

How to Detect Subtours

You will check of the existence of subtours outside of CPLEX/Solver

Idea in English: You start from the origin shop and traverse the path, keeping track of each visited shop. If you come back to the origin, and there are still some binary Y variables left, you have one or more subtours. (Technically, you can start from any shop, but starting from one is easier to understand.)

Initialize visited_shop = NULL; 
Find the Yij that is 1. (Starting edge for the path)
Do while (There are more Y variables = 1 remaining)
  Add the destination of the new binary variable to list of visited_shops
  Check if you are done (are you back at shop 1):
    if Yes: 
       If no more binary variables left, you are done. Exit.
       If there are some more non-zero binary variables, subtour detected
    if No: 
       pick the next Y variable whose origin is current Y_variable's destination
  Continue