Min cost max flow optimization problem

Question

Let $I$ be the set of customers and let $J_i \subseteq J$ be the set of items from which customer $i \in I$ wants to buy only one, where $J$ are the items. Denote $w(i,j) \geq 0$ as the price customer $i$ is willing to pay for item $j$. Assume $|I| = |J| = n$.

I want to find an algorithm which computes the maximum number of customers that get an item at the minimum total cost. I'd like to do this using a min-cost max flow theorem. However, I cannot seem to succeed in constructing a graph for this problem where we can both minimize and maximize functions. Can anyone give a suggestion how I should make this graph?

Answer 1

Besides the customer and items nodes, introduce a source node $s$, sink node $t$, and $|I|+|J|=2n$ edges, each with capacity $1$ and cost $0$:

• $(s,i)$ for $i\in I$
• $(j,t)$ for $j\in J$

Answer 2

OP was under the impression that the cost in a min-cost-flow problem should be at most the capacity. This is not the case. As such, the solution is a straightforward application of the min-cost-max-flow algorithm.