We can do better by setting up and solving a linear program. We start with a set

of holes, and the horizontal and vertical coordinates of each:

IMSE $3005,$ Assignment #$3$ Page $5$

set HOLES ordered;

param hpos $\{$HOLES$\}>=0$;

param vpos $\{$HOLES$\}>=0$;

Given this information, we can define the set of all unique pairs of holes, and the

distance between each pair:

set PAIRS :$=\{$i in HOLES, j in HOLES: ord$($i$)<$ ord$($j$)\}$;

param dist $\{($i$,$j$)$ in PAIRS$\}$

:$=$ sqrt$(($hpos$[$j$]-$hpos$[$i$])**2+($vpos$[$j$]-$vpos$[$i$])**2)$;

Let us define variables Use, indexed over the pairs of holes, with the idea that

Use$[$i$,$j$]$ will be $1$ if the move between i to j is used as part of the tour, and that

Use$[$i$,$j$]$ will be zero otherwise. Then it is easy to see that the total length of the

tour is the sum of dist$[$i$,$j$]*$ Use$[$i$,$j$]$ over all pairs of holes i and j$.$ Since we

want the tour to be as short as possible, we have:

var Use $\{$PAIRS$\}>=0,<=1$;

minimize Tour$\_$Length: sum $\{($i$,$j$)$ in PAIRS$\}$ dist$[$i$,$j$]*$ Use$[$i$,$j$]$;

a: To force the variables Use$[$i$,$j$]$ to correspond to a tour, we propose to add

the following constraints:

subject to Visit$\_$All $\{$i in HOLES$\}$:

sum $\{($i$,$j$)$ in PAIRS$\}$ Use$[$i$,$j$]+$ sum $\{($j$,$i$)$ in PAIRS$\}$ Use$[$j$,$i$]=2$;

Briefly explain why, if the values of the Use$[$i$,$j$]$ variables do not satisfy these

constraints, then they cannot possibly describe a tour.

b: For the particular holes shown in our diagram, the data values are as follows:

param: HOLES: hpos vpos :$=$

A $00$ I $34$

B $01$ J $44$

C $02$ K $50$

D $04$ L $61$

E $12$ M $72$

F $13$ N $74$

G $20$ O $42$

H $24$ P $83$

Q $84$ ;

The model from $($a$)$ together with this data are posted in files holes.mod

and holes.dat. Solve the resulting linear program. $($Be sure you get the

optimal solution message!$)$ Use the following commands to get a concise

listing of the solution:

option display$\_$eps $\mathrm{.}000001$;

option omit$\_$zero$\_$rows $1$;

display Use;

Draw a diagram of the solution, with a solid line showing each variable that

is $1,$ and a dashed line showing each variable that is $1/2.$ Why is this solution

not useful for the hole$-$drilling problem?

c: To try to make the linear program more useful, you can add $$subtour elimina$-$

tion$$ constraints, which say that at least two moves must connect the nodes

in any subset to the nodes not in the subset. Constraints of this kind can be

written in AMPL as follows:

IMSE $3005,$ Assignment #$3$ Page $6$

param nSubtours $>=0$ integer;

set SUB $\{1..$nSubtours$\}$ within HOLES;

subject to Subtour$\_$Elimination $\{$k in $1..$nSubtours$\}$:

sum $\{$i in SUB$[$k$],$ j in HOLES diff SUB$[$k$]\}$

if $($i$,$j$)$ in PAIRS then Use$[$i$,$j$]$ else Use$[$j$,$i$]>=2$;

You can see that in your diagram there is only one move connecting the nodes

in subset $$L$,$ M$,$ N$,$ P$,$ Q $$ to the other nodes. Here is data for the subtour

elimination constraint for this set:

param nSubtours :$=1$ ;

set SUB$[1]$ :$=$ L M N P Q ;

Add these lines to the given model and data files, producing files holes$2.$mod

and holes$2.$dat.

Solve and diagram the result. You should find that the variables are now all $0$

or $1,$ but that the solution is composed of three separate tours, through three

separate subsets of nodes. What are these subsets?

d: Add three more subtour elimination constraints to holes$2.$dat, corresponding

to the three subtours in the solution, and solve again. What subtours do you

find now?

e: Continue adding subtour elimination constraints to holes$2.$dat until you find

a solution that has no subtours or fractional variables. Diagram this optimal

tour. Were there any optimal tours among those that you found earlier in

this assignment? model file:set HOLES ordered;

param hpos $\{$HOLES$\}>=0$;

param vpos $\{$HOLES$\}>=0$;

set PAIRS :$=\{$i in HOLES, j in HOLES: ord$($i$)<$ ord$($j$)\}$;

param dist $\{($i$,$j$)$ in PAIRS$\}$

:$=$ sqrt$(($hpos$[$j$]-$hpos$[$i$])**2+($vpos$[$j$]-$vpos$[$i$])**2)$;

var Use $\{$PAIRS$\}>=0,<=1$;

minimize Tour$\_$Length: sum $\{($i$,$j$)$ in PAIRS$\}$ dist$[$i$,$j$]*$ Use$[$i$,$j$]$;

subject to Visit$\_$All $\{$i in HOLES$\}$:

sum $\{($i$,$j$)$ in PAIRS$\}$ Use$[$i$,$j$]+$ sum $\{($j$,$i$)$ in PAIRS$\}$ Use$[$j$,$i$]=2$;

data file: param: HOLES: hpos vpos :$=$

A $00$

B $01$

C $02$

D $04$

E $12$

F $13$

G $20$

H $24$

I $34$

J $44$

K $50$

L $61$

M $72$

N $74$

O $42$

P $83$

Q $84$ ;