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

in order to receive (full) points.

  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(.).