This problem appears as an exercise in an Algorithms text (not homework, just something I’m reading through). The basic setup is this:
A movie producer needs to hire actors and raise money through investors to make the movie. Each actor has a salary s[sub]i[/sub] that must be paid. Each investor will pay an amount p[sub]j[/sub]. However, a given investor will only get involved if some subset L[sub]j[/sub] of the actors is signed on. The funding only comes if all the actors in L[sub]j[/sub] are included.
The producer wishes to maximize the amount of money invested, which is the sum of invested money minus the sum of salaries paid.
There are actually two parts to the question given:
a. Express this as an integer linear program with the variables taking the values {0,1}
b. Relax this to a linear program and show that an integral optimal solution must exist.
So far I’ve got something that I think works, but I’m a little unsure on the second part. Here’s how I’d do it:
Have variables a[sub]i[/sub] for actors and b[sub]j[/sub] for investors.
All a[sub]i[/sub] and b[sub]j[/sub] constrained to {0,1}.
For each investor j, there is a constraint, if L[sub]j[/sub] has k members:
a[sub]j1[/sub] + a[sub]j2[/sub] + … a[sub]jk[/sub] - k*b[sub]j[/sub] >= 0
Objective: Maximize Sum{j}(p[sub]j[/sub]*b[sub]j[/sub]) - Sum{i}(s[sub]i[/sub]*a[sub]i[/sub])
If I relax this, then what I can see is that it doesn’t quite yield an integral solution. If it isn’t included, an investor variable b might get assigned a fractional value. However, I’m pretty sure that all of the actor variables must end up either 0 or 1. Since the solution can be framed solely in term of those values, it’s workable. I’m just not sure it satisfies the question’s requirements. So what I’m asking is, is there another way I ought to do this? (Also, am I correct in assuming this formulation always works?)
Instead of the constraints you give, you could more easily just use the constraints “b[sub]j[/sub] <= a[sub]ji[/sub]” for each investor and prerequisite actor for them (“If I have this investor, then I need this actor”). Of course, you’ll also have to constrain each of these variables to the interval [0, 1].
Hopefully, then the solution will necessarily be integral, though I haven’t bothered establishing this.
If the book you’re looking at covers network flows, it could be that they’re looking for a relaxation that is a network flow. If you can find one, it follows immediately that an integer optimal solution exists.
It looks like a subclass that could be expressed as a transportation algorithm - you either take a route or you don’t, you either hire an actor or you don’t. It might be susceptible to an ingenious fast method that uses uses matrix multiplication but replaces (a+b) with minimum(a,b) and multiply with add between numbers (and uses Infinity in stead of Zero for no link)
Thanks Indistinguishable, those constraints make it a lot simpler.
I’m pretty sure the relaxation works to produce integer values, for the same reason as I thought before. An actor will be included only if it’s attached to some investor that creates a profit. If only a single actor were with each investor, the actor gets included only if for some investor, p[sub]j[/sub] - s[sub]j[/sub] is positive. If b[sub]j[/sub] were fractional, a greater profit would be realized by increasing it (and a[sub]j[/sub] and b[sub]j[/sub] will increase together by the constraint) to the most it can be, 1. With multiple actors in L[sub]j[/sub] there will still be at least one actor for which this is true if the investor is going to be in the solution. ‘Unprofitable’ investors that do get included (due to another investor providing even greater value) will still have their b[sub]j[/sub] set to its maximum, to get the most money possible out of them.
ultrafilter - I did initially spend some time trying to convert it to the max flow problem, but that was beyond me. I was trying the approach of distinguishing the type of flow through a node or ensuring a unique path, but that seemed messy. The problem statement actually mentions network flow, but more as illustration, since relaxation was only briefly touched on in the text (bipartite matching was mentioned too).
Jerseyman - There probably is a simple way to solve it not using LP, but as that wasn’t the exercise I didn’t look too deeply into it (I also wonder if using the profit for each investor might lead to something). If you’re interested, take a stab at it.