Every week Mighty Mo Manufacturing makes one production run of each of its 4 different kinds of metal cookware. Setup times to make any particular product vary depending on what was produced most recently. The following table shows the time (in hours) required to convert from any product to any other.

1 2 3 4 1 — 4.2 1.5 6.5 2 5.0 — 8.5 1.0 3 1.2 7.7 — 8.0 4 5.5 1.8 6.0 —

Mighty Mo would like to find the production sequence that minimizes total setup time.

(a) Explain why this problem can be viewed as an asymmetric traveling salesman problem.

(b) Formulate this problem (incompletely) as a linear assignment problem to choose a successor for each product.

(c) Use class optimization software to show that your ILP of part

(b) produces a subtour 1–3–1.

(d) Formulate a subtour elimination constraint that precludes the solution of part (c).

(e) Use class optimization software to show that an optimal route results when your subtour elimination constraint is added to the formulation of part (b).

(f) Formulate this problem as a quadratic assignment INLP.