# Integer LP formulation and the existence of a solution

A film producer is seeking actors and investors for his new movie. There are $n$ available actors; actor $i$ charges $s_i$ dollars. For funding, there are $m$ available investors. Investor $j$ will provide $p_j$ dollars, but only on the condition that certain actors $L_j \subseteq \{1,2,...,n\}$, are included in the cast (all actors $i \in L_j$ must be chosen in order to receive funding from investor $j$). The producer's profit is the sum of the payments from investors minus the payments to actors. The goal is to maximize this profit.

1. Express this problem as an integer linear program in which the variables take on values on [0,1]
2. Show that there must in fact be an integral optimal solution (as is the case, for example, with maximum flow and bipartite matching).

I am lost on both parts for this problem.

• A hint. You probably want a variable, $x_i$, that is $1$ if actor $i$ is involved, and $0$ otherwise, and a similar variable $y_j$ for investor $j$. Now, start writing down inequalities, objective functions, equations, etc. – Peter Shor Nov 9 '12 at 14:05
• david, is there a reason why you completely removed the problem definition? – Nicholas Mancuso Nov 10 '12 at 1:28
• @David: People invested time to come up with a solution for your problem, but then you make their answer useless by completely changing your question. I strongly advise to put back the necessary part of the original question to make Nicolas answer meaningful. The question in the present form is not a real question. – A.Schulz Nov 10 '12 at 9:57
• @A.Schulz Feel free to roll back to a reasonable revision. If there are copyright issues here, david should speak up. – Raphael Nov 12 '12 at 11:23

Express this problem as an integer linear program in which the variables take on values on [0,1]

\begin{align} \text{max: } &\sum_i^m y_i \cdot p_i - \sum_j^n x_j \cdot s_j &\\ \text{subject to: } &x_i \geq y_j &\forall i \in L_j \\ &0 \leq x_i \leq 1 &\forall i \\ &0 \leq y_j \leq 1 &\forall j \end{align}

We see that if we select an investor $y_j$ we must select all of the investor's actors $x_i$ for $i \in L_j$. Our profit is the residual income left over from paying actors.

Show that there must in fact be an integral optimal solution (as is the case, for example, with maximum flow and bipartite matching)

If our constraint matrix $A$ is totally unimodular, then the relaxed LP is sufficient to give a 0-1 solution.

Sketch: Observe that $A$ is an $N \times M$ matrix where $N = n + m$ and $M = \sum_j^m |L_j|$. This defines an incidence matrix of a bipartite graph where each row corresponds to an edge $(y_j, x_i)$ with coefficients $(-1, 1)$. We see that any cycle in the graph defined by $A$ will be balanced. That is, for any cycle $C$, $\prod_{e \in C: e=(u,v)} A_{e, v} = 1$. The proof for this can be done using the fact that any cycle in a bipartite graph is even. The corollary to this is that the incidence matrix for any balanced signed graph is totally unimodular.

• The $x_i \leq 1$ and the $y_j \leq 1$ constraints should give q non-zero objective function in the dual. – Peter Shor Nov 10 '12 at 2:33
• D'oh, that's right. I was just using $x_i \geq y_j$. – Nicholas Mancuso Nov 10 '12 at 17:22