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 of these actors $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.
(a) Express this problem as an integer linear program in which the variables take on values on $[0,1]$ (b) Now relax this to a linear program, and 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.
Best Answer
Let $n$ be the number of actors and let $m$ be the number of investors. One way to write your problem as an integer linear program is to have variables $x_1,\dots,x_n,y_1,\dots,y_m\in\{0,1\}$; the problem is to maximize $\sum y_j p_j-\sum x_i s_i$ subject to $y_j-x_i\leq 0$ for all investors $j$ and all $i\in L_j$. Written in this way, the LP relaxation is obvious: allow the variables to take any value from $0$ to $1$.
There are various ways to show that there is an integral optimum - you should probably follow your course notes on this.
One argument is to consider an extreme point $p=(x^*_1,\dots,x^*_n,y^*_1,\dots,y^*_m)$ of the polyhedron defined by the inequalities $y_j-x_i\leq 0$ ($i\in L_j$) and $0\leq x^*_i,y^*_j\leq 1$ (all $i,j$). Let $M$ be the maximum coordinate less than $1$, and suppose for contradiction that $M>0$. Setting all the non-integral coordinates of $p$ to zero gives a new point $p_0$ of the polyhedron. Multiplying all the non-integral coordinates of $p$ by $1/M$ gives a new point $p_{1/M}$ of the polyhedron. We chose $p$ to be an extreme point, but $p=(1-M)p_0+Mp_{1/M}$, so $p=p_0=p_{1/M}$, a contradiction.