The two pieces of a one-tree can be optimized independently. Compute a minimum spanning tree

F

on vertices

{2, \dots, n}

and choose the two cheapest distinct edges incident to vertex one. Return their union.

Every feasible one-tree contains such a spanning tree and such a pair, so its cost is at least the sum of these two independent minima. Their union is itself feasible, attaining that lower bound. This proves optimality.

Use Prim's algorithm for

F

: repeatedly add a cheapest edge crossing from the current tree to an unvisited vertex. The minimum spanning tree cut property makes each chosen edge safe. With the dense weight matrix of a complete graph, maintain the best connection to each unvisited vertex and select the least one by a scan. There are

n - 2

iterations with

O (n)

work apiece. A further scan finds the two cheapest incident edges. Thus the total complexity is

O (n^{2})

, with

O (n)

additional working storage beyond the input matrix.

b

 0  0

Solution

 0  0

Delete vertex one and its two incident edges from a Hamiltonian cycle. The remaining edges form a Hamiltonian path through all other vertices, hence a spanning tree. Thus every tour is a one-tree, and both problems use the same edge-cost objective. The relaxation enlarges the feasible set, giving

z^{(1)} \leq z^{(2)} .

(1)

Conversely, a one-tree in which every vertex has degree two is connected and two-regular, so it is a Hamiltonian cycle. Such a minimum one-tree therefore also solves the travelling-salesman problem. This is the one-tree travelling-salesman bound.

c

 0  0

Solution

 0  0

Write

ij

for the undirected edge

{i, j}

. At the root of the branch and bound search, the minimum spanning tree on

{2, 3, 4}

{24, 34}

of cost

6 + 4 = 10

. The cheapest edges incident to vertex one are

12, 14

, of cost

3 + 7 = 10

. The root lower bound is therefore twenty, attained by

T_{0} = {12, 14, 24, 34} .

(1)

It is not a tour: vertex four has degree three and vertex three degree one.

A tour must omit at least one edge from

{14, 24, 34}

, since its degree at vertex four is two. Partition tours according to the first omitted edge in that ordered list. This gives three disjoint, exhaustive children, retaining included and excluded edges when recomputing the one-tree relaxation:

Exclude $14$ . The incident pair is now $12, 13$ of cost twelve, and the other spanning tree still costs ten. The resulting one-tree ${12, 13, 24, 34}$ is a tour, so it supplies an incumbent solution of cost $22$ .
Include $14$ and exclude $24$ . The other spanning tree must be ${23, 34}$ of cost fourteen; the cheapest permitted incident pair costs ten. The lower bound is $24 \geq 22$ , so prune this child.
Include $14, 24$ and exclude $34$ . The spanning tree must be ${23, 24}$ of cost sixteen; the incident pair again costs ten. The lower bound is $26 \geq 22$ , so prune this child too.

All tours belong to one of the three children, and no remaining child can improve the incumbent. Therefore

1 \to 2 \to 4 \to 3 \to 1 is optimal, with cost 3 + 6 + 4 + 9 = 22.

(2)

The branching rule is motivated by a violated tour degree equation, rather than by an arbitrary costly edge. This is degree branching with a one-tree bound.

Past exam of the integer programming course of the University of Oxford / 2010 / 1

a

Solution

b

Solution

c

Solution

 Ancestors (10)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

Past exam of the integer programming course of the University of Oxford / 2010 / 1

 Discussion (0)  Subscribe (1) New discussion

 Discussion (0) New discussion