#
# Solutions to Homework 1
#

flame-69:tsp mitchj$ ampl
ILOG AMPL 11.000, licensed to "rensselaer-troy, ny".
AMPL Version 20080102 (Darwin 8.10.1)

#Question 1

ampl: model tsplp.mod; data tsp.dat; solve; display x;
ILOG CPLEX 11.000, licensed to "rensselaer-troy, ny", options: e m b q use=10 
CPLEX 11.0.0: optimal solution; objective 356.5
15 dual simplex iterations (0 in phase I)
x [*,*]
:   1    2    3   4   5   6    7    8    9    10     :=
0   0   0     1   0   0   0   1     0   0     0
1   .   0.5   0   0   0   0   0.5   1   0     0
2   .    .    0   0   0   0   0.5   0   1     0
3   .    .    .   0   0   0   0     0   0     1
4   .    .    .   .   1   1   0     0   0     0
5   .    .    .   .   .   1   0     0   0     0
6   .    .    .   .   .   .   0     0   0     0
7   .    .    .   .   .   .    .    0   0     0
8   .    .    .   .   .   .    .    .   0.5   0.5
9   .    .    .   .   .   .    .    .    .    0.5
;

# clearly not integral.
# also, contains subtour 4-5-6-4

# Question 2

ampl: reset; model tspip.mod; data tsp.dat; solve; display x;
ILOG CPLEX 11.000, licensed to "rensselaer-troy, ny", options: e m b q use=10 
CPLEX 11.0.0: optimal integer solution; objective 385
0 MIP simplex iterations
0 branch-and-bound nodes
x [*,*]
:   1   2   3   4   5   6   7   8   9  10    :=
0   0   0   1   0   0   0   1   0   0   0
1   .   0   0   0   0   0   0   1   0   1
2   .   .   0   0   0   0   1   0   1   0
3   .   .   .   0   0   0   0   0   0   1
4   .   .   .   .   1   1   0   0   0   0
5   .   .   .   .   .   1   0   0   0   0
6   .   .   .   .   .   .   0   0   0   0
7   .   .   .   .   .   .   .   0   0   0
8   .   .   .   .   .   .   .   .   1   0
9   .   .   .   .   .   .   .   .   .   0
;

# now integral, but includes the subtour 4-5-6-4
#   (and also the complementary subtour, 0-3-10-1-8-9-2-7-0).

# Question 3

ampl: reset; model tspsub4lp.mod; data tsp.dat; solve; display x;
ILOG CPLEX 11.000, licensed to "rensselaer-troy, ny", options: e m b q use=10 
CPLEX 11.0.0: optimal solution; objective 371.5
38 dual simplex iterations (18 in phase I) on the dual problem
x [*,*]
:   1    2    3   4   5   6    7    8    9    10     :=
0   0   0     1   1   0   0   0     0   0     0
1   .   0.5   0   0   0   0   0.5   1   0     0
2   .    .    0   0   0   0   0.5   0   1     0
3   .    .    .   0   0   0   0     0   0     1
4   .    .    .   .   1   0   0     0   0     0
5   .    .    .   .   .   1   0     0   0     0
6   .    .    .   .   .   .   1     0   0     0
7   .    .    .   .   .   .    .    0   0     0
8   .    .    .   .   .   .    .    .   0.5   0.5
9   .    .    .   .   .   .    .    .    .    0.5
;

# has no subtours, but not integral

# Question 4

ampl: reset; model tspsub4ip.mod; data tsp.dat; solve; display x;
ILOG CPLEX 11.000, licensed to "rensselaer-troy, ny", options: e m b q use=10 
CPLEX 11.0.0: optimal integer solution; objective 400
26 MIP simplex iterations
0 branch-and-bound nodes
1 Gomory cut
x [*,*]
:   1   2   3   4   5   6   7   8   9  10    :=
0   0   0   1   1   0   0   0   0   0   0
1   .   0   0   0   0   0   0   1   0   1
2   .   .   0   0   0   0   1   0   1   0
3   .   .   .   0   0   0   0   0   0   1
4   .   .   .   .   1   0   0   0   0   0
5   .   .   .   .   .   1   0   0   0   0
6   .   .   .   .   .   .   1   0   0   0
7   .   .   .   .   .   .   .   0   0   0
8   .   .   .   .   .   .   .   .   1   0
9   .   .   .   .   .   .   .   .   .   0
;

# now integral, and also contains no subtours, so optimal.
# optimal tour is 0-3-10-1-8-9-2-7-6-5-4-0.