$9$:$29$ AM Thu May $9$

A

production$-$gradescope$-$uploads.s$3-$us$-$west$-2.$amazonaws.com

$5$ of $7$

$3$

ISE$-321$

HW$-3$

Problem #$3$ Practice Only

An fuel supplying company is considering to find the optimal sequence of fuels $(A,B,C,D,E,F)$ that should to sent through their pipelines to minimize the total mixture fuels. During the change of fuels from fuel A to fuel B$,$ the amount of mixture fuel generated is $9$ barrel units. Similarly for any other change, the mixture fuel values are given below:

$([,9,8,9,5,9],[7,3,5,1,6],[8,6,3,7,1],[1,6,5,1,4],[3,8,9,7,3],[1,9,6,7,7,])$

The sequence will be used over the entire day. At the end of the day, there will be no supply. Thus, at the beginning of the next day, the pipeline will be dry and empty. That is$,$ any fuel can be sent without any overlap at the beginning of the day.

$($a$)$ Convert the problem and data into standard TSP$.$

$($b$)$ Identify an upper bound of the TSP$.$ How is the upper bound related to the original protein problem?

$($c$)$ Identify a lower bound for the TSP$.$ How is the lower bound related to the original protein problem?

$($d$)$ Find the solution of TSP using B & B approach. At each node, solve an assignment problem related to the TSP$.$ Use the following strategy: When there are many open nodes, select the node with best bound. When there are many open branches, pick the branch, whose variable corresponds to highest distance$/$cost$.$ At a given node, if there are many subtours, pick the subtour with smallest cardinality. Break ties arbitrarily.

$($e$)$ Write the mathematical formulation of the above TSP$,$ which can be used in a commercial MIP solver for obtaining the complete tour.