Exercise 7.1 (The caterer problem)

Question

A catering company must provide to a client $r_i$ tablecloths on each of $N$ consecutive days. The catering company can buy new tablecloths at a price of $p$ per item, or launder the used ones. Laundering can be done at a fast service that takes $n$ days and costs $f$ per item or slow service that takes $m$ days and costs $g$ per item. Note that $n < m$ and $f > g$. The caterer's problem is to decide how to meet the demand at minimum cost, starting with zero tablecloths and under the assumption that any leftover tablecloths have no value. Show that this problem can be formulated as a network flow problem.

Armaan · Accepted Answer

Let us order the day by $t = 1, \dots, N$ ; and have two nodes for each $t \in [N]$. One of the node is named $c_t$ and the other is names $d_t$ (for clean and dirty tablecloths on a day). The node $c_t$ has a supply of $r_t$ and the node $d_t$ has a demand of supply $r_t$. We also introduce a separate source arc $s$, we design the arcs in the network as follows: 
\begin{itemize}
\item Each node $c_t$ we have an arc $(s, c_t)$ with a cost $p$ and capacity $\infty$
\item Each node $c_t$ receives laundry from 'fast' via arcs $(d_{i-n-j}, c_i)$ if $(i-j) > n$ with a cost $f$ and capacity $\infty$
\item   Each node $c_t$ receives laundry from 'slow' via arcs $(d_{i-m-j}, c_i)$ if $(i-j) > m$ with a cost $f$ and capacity $\infty$
\item Each node $d_t$ is connected to the source $s$ via an arc $(d_t, s)$ with zero-cost and capacity $\infty$ 
\end{itemize}

We can solve a minimum-cost flow problem on the network (we have flow conservation and non-negativity constraints)

Exercise 7.1 (The caterer problem)

Answers

Comments

Exercise 7.1 (The caterer problem)

Answers

Comments

Add answer