Question

Hollywood. A film producer is seeking actors and investors for his new movie. There are $\mathbf{n}$ available actors; actor$\mathbf{i}$ charges${\mathbf{S}}_{\mathbf{j}}$ dollars. For funding, there are$\mathbf{m}$ available investors. Investor$\mathbf{j}$ will provide${\mathbf{p}}_{\mathbf{j}}$ dollars, but only on the condition that certain actors$\mathbf{Lj}\mathbf{\subseteq }\mathbf{\{}\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}\mathbf{n}\mathbf{\}}$ are included in the cast (all of these actors${\mathbf{L}}_{\mathbf{j}}$ must be chosen in order to receive funding from investorrole="math" localid="1658404523817" $\mathbf{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 $\mathbf{\{}\mathbf{0}\mathbf{,}\mathbf{1}\mathbf{\}}$.

(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).

Short answer

1. The linear programming is explained.
2. It is shown that there is an integral optimal solution.

Step-by-step solution

Integer Linear Programme (a)

Write this problem as such an integer linear program, with the variables taking on values on a scale of one to ten.$[0,1]$ .

$\max :{\sum }_{\mathrm{i}}^{\mathrm{m}}{\mathrm{y}}_{\mathrm{i}·{\mathrm{p}}_{\mathrm{i}}}-{\sum }_{\mathrm{i}}^{\mathrm{m}}{\mathrm{x}}_{\mathrm{i}}·8_{\mathrm{j}}$

Subject to: ${\mathrm{x}}_{\mathrm{i}}\ge {\mathrm{y}}_{\mathrm{j}}$, $\forall \mathrm{i}\in {\mathrm{L}}_{\mathrm{j}}$

$0\le {\mathrm{x}}_{\mathrm{i}}\ge 1$ , $\forall \mathrm{i}$

$0\le {\mathrm{y}}_{\mathrm{j}}\ge 1$ ,$\forall \mathrm{j}$

Part (b)

You may observe this if we choose an investor. Every one of the investors' performers must be chosen.${\mathrm{x}}_{\mathrm{j}}$ for $\mathrm{i}\in {\mathrm{L}}_{\mathrm{j}}$. With us profit comes from the money left over after paying performers..

Demonstrate there has to be an integral optimal strategy (as is the case, for example, with maximum flow and bipartite matching).

${\mathrm{x}}_{\mathrm{i}}\le 1$and the${\mathrm{y}}_{\mathrm{i}}\le 1$ constraints should give q non-zero objective function in the dual. Just using${\mathrm{x}}_{\mathrm{i}}\ge {\mathrm{y}}_{\mathrm{i}}$.

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

Observe that A is an$\mathrm{NxM}$ matrix where$\mathrm{N}=\mathrm{n}+\mathrm{m}$ and$\mathrm{M}={\sum }_{\mathrm{j}}^{\mathrm{m}}\left|{\mathrm{L}}_{\mathrm{j}}\right|$ . This is indeed a bipartite incidence matrix, among each row corresponding to one edge.$({\mathrm{x}}_{\mathrm{j}},{\mathrm{y}}_{\mathrm{j}})$ with coefficients $(-1,1)$. Whatever cycle with in graph described by A will be balanced, as we can see. That is true for any cycle. $\mathrm{C}$, ${\prod }_{\mathrm{e}\in \mathrm{C}:\mathrm{e}=(\mathrm{u},\mathrm{v})}{\mathrm{A}}_{\mathrm{e},\mathrm{v}}=1$.

It is the observation that just about any cycle in a graph structure is even can be used to prove this. As a result, the incidences matrix for just any balancing signed graph is completely unimodular.