10th Homework

This homework has to be prepared in teams. Download hw_10.tar.gz and extract it. Then add your homework solutions to the directory. Rename the directory according to the rules in the syllabus before submitting it as compressed archive. Don't forget to add the correct subject to the email when submitting.

All of the tasks below need to

• run with the provided input data without crashing
• produce correct results
• have proper documentation
• be implemented without using non-English function and variable names, docstrings, comments etc.

in order to receive (full) points.

In this homework, it is up to you to pick one of the tasks below and solve it.

1. Transportation Problem (9 points)
   Suppose a company has a set of warehouses / fulfillment centers ($N$) and a set of retail outlets / demand nodes / customers ($M$). A single product is to be shipped from the fulfillment centers to the customers. Each fulfillment center has a given level of supply, and each customer has a given level of demand. We are also given the transportation costs between every pair of fulfillment center and customer.

   $x_{nm}$

   amount of goods shipped from $n$ to $m$ (integral)

   $c_{nm}$

   cost of shipping one unit from $n$ to $m$

   $u_n$

   units available at fulfillment center $n$ (supply)

   $u_m$

   units demanded by customer $m$

   A straight-forward mixed-integer formulation of this problem is

   $$ \begin{align} \min \quad & \sum_{n \in N}\sum_{m \in M} x_{nm} * c_{nm} & \\ s.t. \quad & \sum_{n \in N} x_{nm} = u_m & \forall m \in M \\ & \sum_{m \in M} x_{nm} \leq u_n & \forall n \in N\\ & x_{nm} \geq 0 & \forall n \in N \quad \forall m \in M \end{align} $$ Implement this LP in the provided file milp.py. You can do it entirely in the the model(.) function. Ideally implement the objective function and each constraint in a separate function and call them from within model(.).
2. Travelling Salesperson Problem (TSP) (9 points)
   Write a program, which can find an optimum solution of the travellings salesperson problem (TSP) by using an ILP solver. To do so enlarge the API designed in the 6th homework. In hw_10.tar.gz you can find the file t_s_p.py containing the class O. Your task is to finish this class.
   Feel free to use any ILP formulation of this famous problem, the easiest (but not the fastest) one can be found here.