0
$\begingroup$

There are $n$ cities and the distance between a city $i$ and a city $j$ is given by $c_{ij}$ for $i,j = 1,2,...,n$ where we have $c_{ii} = \infty$ for all $i$. A salesman has to make a trip through all cities in a way that the total travelling distance is minimal. We make this a combinatorial optimisation problem by introducing $(0,1)$ variables $x_{ij}$ with the following meaning: $x_{ij} = 0$ means the direct route from city $i$ to city $j$ is not chosen, $x_{ij} = 1$ means it is chosen.

So I thought this problem could be written down as follows:

$$ \min \left\{ \displaystyle \sum_{i,j =1}^n c_{ij}x_{ij} \begin{array}{lr} \big\rvert \sum_{i=1}^n x_{ij} = 1,1 \leq j \leq n \\ \big\rvert \sum_{i=1}^n x_{ji} = 1, 1 \leq j \leq n \\ \big\rvert x_{ij} \in \{0\} \text{for every} (i,j) \end{array} \right\}$$

Where $\sum_{i=1}^n x_{ij} = 1,1 \leq j \leq n$ means that for each city $j$ there is one city from which $j$ can be visited, and $\sum_{i=1}^n x_{ji} = 1, 1 \leq j \leq n$ means that we go to just one city from each city $j$.

However, this is apparently incorrect for some reason I don't understand. I was also told that my method is correct if you add the following:

$u_i - u_j + nx_{ij} \leq n-1$ for every $i,j \geq 2$ and $u_i \geq 0$ and integer for $i =1,2,...,n$.

(let the route start in city 1 and interpret $u_i = k$, where city $i$ is the k-th city to be visited from city 1)

However, this correction doesn't help me at all because I don't understand it. Can someone please understand what's wrong with my function and why the above addition rectifies it?

edit: I now know why my function is wrong because of the given answer, but I still don't know how it's rectified by the added constraint.

$\endgroup$

1 Answer 1

0
$\begingroup$

Your function does not guarantee that only one route is defined. It may create sub cycles.

Such sub cycles are forbidden if you add the constraints of your correction: see Section 3 for a justification.

$\endgroup$
4
  • $\begingroup$ what exactly do you mean by sub cycles? $\endgroup$
    – Algebreh
    Dec 10, 2015 at 1:13
  • $\begingroup$ For example, if your cities are A,B,C,D,E,F, it may give you the solution A,B,C,A, and D,E,F,D. $\endgroup$
    – Kuifje
    Dec 10, 2015 at 1:28
  • $\begingroup$ Ok, I now understand the sub cycles part, but I still don't understand how our addition rectifies it. $\endgroup$
    – Algebreh
    Dec 10, 2015 at 20:38
  • $\begingroup$ Check the link in my edit.. $\endgroup$
    – Kuifje
    Dec 10, 2015 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.