0
$\begingroup$

Create a closed tour visiting the numbers. The tour must start and end at the same cell. During the tour, you can only visit the neighboring cell (up,down,left,right). The tour cannot contain a number more than once.

Under these conditions, what can be the maximum total-value of such a tour (sum of visited numbers)?

I thought to formulate it as a linear programming. It seems similar to a TSP. However, there are some differences: First, not all the nodes must be visited. In TSP, you visit all the nodes. Second, the starting point of the tour is not known. How can I eliminate sub-tours (using MTZ formulation), if I don't know the starting cell and if I don't need to visit all cells?

How can we formulate this in a convenient way using LP?

Tour question

$\endgroup$
6
  • $\begingroup$ @lulu "Each number must be visited maximum once." If you start from upper left and go all the way right, you visit the number 17 twice. Hence this constraint does not hold. $\endgroup$ Commented Sep 10 at 15:29
  • $\begingroup$ How do you go from 3 to 1 in the first step? This is not allowed. You can only move to the neighbors (for example from 3 to 7, or 3 to 10 -at the upper left-). $\endgroup$ Commented Sep 10 at 15:43
  • $\begingroup$ ok, then see my previous comment. While going straight across the top row, you visit the number 17 twice, don't you? $\endgroup$ Commented Sep 10 at 15:47
  • $\begingroup$ Yes, I edited the question. $\endgroup$ Commented Sep 10 at 16:05
  • $\begingroup$ There is no solution passing through all numbers. You can start from each 17 without success (for the leftmost 17, try to join 1, and fail). This comment doesn't answer at all your question. $\endgroup$ Commented Sep 10 at 16:29

1 Answer 1

Reset to default
0
$\begingroup$

You can solve it as a MIP (not an LP). To answer your question about start/end node, just add a dummy node with arcs to and from every node in the original grid. Your tour will start and end at the dummy node. The MTZ subtour elimination approach does not require that every node is visited; it just requires that the added counter variable for each visited node be at least one greater than the count at the previous stop.

$\endgroup$
4
  • $\begingroup$ But, if I use a dummy node, and my tour starts&ends at the dummy node; how can I assure that I have a tour at the end? I mean, for example, having 0 as dummy node, I start from upper left, and go through values 0-3-7-4-11-0. This is in your suggestion a valid tour, but it is actually not valid because it starts at 3 and ends at 11 (it had to end at 3 again). Or am I missing something? $\endgroup$ Commented Sep 10 at 19:12
  • $\begingroup$ Good point. You'll need to add a constraint that says that if the tour goes j -> 0 -> i then j and i must be adjacent (or i = j, which would make for a short "tour" but conceivably could occur, for instance if all the cell rewards were identical). $\endgroup$ Commented Sep 10 at 20:42
  • $\begingroup$ If we number your grid 1 (top left) to 64 (bottom right) in raster scan order, an optimal tour is 39 - 47 - 55 - 54 - 53 - 61 - 60 - 52 - 44 - 43 - 35 - 36 - 37 - 29 - 30 - 31 - 39 with total objective value 181. $\endgroup$ Commented Sep 11 at 2:34
  • 1
    $\begingroup$ Thank you, now with the additional constraint, it worked. I also found the result as 181, as you mentioned. $\endgroup$ Commented Sep 11 at 12:16

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.