1
$\begingroup$

I am trying to model the following problem correctly as a min-cut network flow problem. I have $n$ books and 2 boxes. I also have books that I know must go in one of the two boxes. In addition, each book has a certain profit if I put it in the same box with another book. So for instance, if I pair book $i$ with book $j$ I might have a profit of 10 dollars so long as they're in the same box. If I have 3 books in one box, I'd have to sum the profit of 1 and 2, 2 and 3, and 1 and 3. I want to find the best way to assign the not-yet assigned books to either box 1 or 2 to maximize my profit. Formally:

  • 2 boxes: $b_1$ and $b_2$
  • Set: $N$ of $1...n$ books
  • $S_1$ = set of all books that must go to box 1
  • $S_2$ = set of all books that must go to box 2
  • $p_{ij}$ = The profit by having books $i$ and $j$ in the same box
  • Objective (roughly): $max(\sum_{i=1}^{2}\sum p_{ij})$ (maximize the profit over all boxes)

My ideas so far:

  • Formulate the problem as a min-cut problem because we are trying to end up with two sets of books (one for box 1, one for box 2). Would it be correct to say that $-min(-\sum_{1}^{2}\sum p_{ij})$ is equivalent to our maximization above? I tried simplifying it further but I'm not sure how.

    • Make source node for box 1, node for each book not assigned (not in $S_1$ and not in $S_2$) and a sink node for box 2.

My question:

With the previous formulation in mind, I'm confused on what the edges would be like. I have edges from box 1 to the book nodes and then the book nodes to box 2 but I'm not sure if this makes sense, largely because I need to make sure my summation notation is correct and how to turn that into an appropriate graph. Could anyone offer advice on the minimization I wrote above and how to translate it to a graph correctly?

$\endgroup$
0
$\begingroup$

First, I assume that it doesn't matter which box a pair of books go into, e.g., the value of book 1 and 2 being in box 1 is the same as the value of book 1 and 2 being in box 2. Now, denote $B_1, B_2$ as the books in boxes 1 and 2 respectively. The value of this partitioning is precisely $$ \sum_{{i,j} \in B_1:\ i<j} p_{ij}+ \sum_{{i,j} \in B_2:\ i<j} p_{ij}= \sum_{{i,j} \in N:\ i<j} p_{ij} - \sum_{i \in B_1}\sum_{j\in B_2}p_{ij}$$ (in words, the value of the paired books in box 1 + the values of the paired books in box 2 = the value of all paired books - the value of the books that aren't paired)

Observe that $\sum_{{i,j} \in N:\ i<j} p_{ij}$ is constant regardless of how you place your books and therefore maximizing $\sum_{{i,j} \in B_1:\ i<j} p_{ij}+ \sum_{{i,j} \in B_2:\ i<j} p_{ij}$ is equivalent to minimizing $\sum_{i \in B_1}\sum_{j\in B_2}p_{ij}$ (as you've roughly stated).

Under this assumption (that the box doesn't matter), we now exactly have a min cut problem.

Let your set of vertices be $N$ (there is no need for a source node to identify which box is which). We let the graph be complete (there is an edge between every pair of nodes) the value of the edge between $i$ and $j$ is $p_{ij}$. A cut on this graph is a partitioning ${B_1,B_2}$. The value of such a cut is $\sum_{i \in B_1}\sum_{j\in B_2}p_{ij}$. Hence, to find the maximum way to place your books, it suffices to find a minimum cut on this graph.


In the event you want a formulation with terminal nodes (sink/sources), you can add in dummy nodes s and t (denoting box 1 and box 2), connect edges from all books to these nodes with an arbitrary weight W. A partitioning that divides s, t has weight \begin{align}\sum_{i \in B_1}\sum_{j\in B_2}p_{ij}+\sum_{j\in B_2}p_{sj}+\sum_{i\in B_1} p_{it}&=\sum_{i \in B_1}\sum_{j\in B_2}p_{ij}+|B_2|⋅W+|B_1|⋅W\\ &=\sum_{i \in B_1}\sum_{j\in B_2}p_{ij}+|N|⋅W.\end{align}

In this formulation, a valid cut is $\{s\},\{t,N\}$ with value $W\cdot |N|$ and therefore to ensure at least one book goes in each box, $W$ needs to be made large.


There is one final component of your problem we have not addressed, i.e., there is a set of books $S_1$ that MUST go into box 1 and a set $S_2$ that MUST go into box 2.

Off the top of my head, I do not see a way to fix this without incorporating a source and sink $s$ and $t$ (for box 1 and 2 respectively). The formulation I've given above is almost sufficient. If $j\in S_1$ (book j MUST go into box 1), make $p_{sj}$ arbitrarily large (much more than $W$). This ensures an arbitrarily large cost will be charged if you try to but a book that must go into box 1 into box 2. Similarly, if $i\in S_2$, make $p_{jt}$ arbitrarily large.

Assuming $S_1$, and $S_2$ are non-empty (that books are already forced into each box), $W$ can be taken as 0 (since a proper partition is enforced by $S_1,S_2$) and $p_{sj}=p_{it}$ for $j\in S_1, i\in S_2$ can be as little as $\sum_{{i,j} \in N:\ i<j} p_{ij}$ (assuming each $p_{ij}\geq 0$).

$\endgroup$
0
$\begingroup$

Make a graph with vertices $v_1, ..., v_n$ for the $n$ books. Let an edge $v_i, v_j$ for books $v_i$ and $v_j$ have weight $p_{ij}$.

Now, create two vertices $b_1$ and $b_2$ and make edges from $b_1$ to all vertices that should go to Box 1, respectively for $b_2$ and Box 2. Let the weights be "infinite", e.g. $1+\sum_{i, j \leq n} p_{ij}$.

Now, a min-cut in this graph will create two or more components, one component that $b_1$ belongs to and one component that $b_2$ belongs to. These determine the optimal locations of the books. The rest are just "isolated" books that you can put wherever you want.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.