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