# Assigning books to boxes

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?

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 (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 is constant regardless of how you place your books and therefore maximizing $$\sum_{{i,j} \in B_1:\ i 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 (assuming each $$p_{ij}\geq 0$$).

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.