Integer LP formulation and the existence of a solution

Question

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.

Answer 1

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.