1
$\begingroup$

I have a problem where I have a number of proposed initiatives each with a cost and payoff. I need to select a subset of these initiatives in order to maximize the ROI for the selected set as a whole while staying within a total cost constraint. Specifically, the problem is:

Maximize [sum(v_i*x_i)/sum(c_i*x_i)]
Subject to sum(c_i*x_i) <= C and x in {0,1}
Where v_i = payoff from initiative i, c_i = cost of initiative i, and x_i = 0/1 decision to select investment i or not

I understand that if the objective function in such a problem is just a sum then it is a 0/1 knapsack problem. If the function is a ratio as in this case, is there a specific name for this kind of a problem, or a recommended algorithm for solving it?

$\endgroup$
  • $\begingroup$ Are the costs integers? About how large is $C$? About how large is the typical $c_i$? $\endgroup$ – D.W. Sep 15 '18 at 15:28
1
$\begingroup$

I can't refer you to literature on this subject, but I did come up with a strategy to solve it.

Do the regular dynamic programming approach to solve simply maximizing $\sum v_ix_i$. In that approach you end up with an array $m[i, c]$ which is the maximum value you can reach with cost less than or equal to $c$ using items up to $i$.

Then simply do a $O(C)$ loop to find the best possible $\frac{m[n, c]}c$ for each $c$ where $n$ is the number of items.

$\endgroup$
  • $\begingroup$ Nice! Caveat: this works if the $c_i$'s are integers and $C$ is not too large*, but not if the $c_i$'s are continuous/real numbers or if $C$ is super-large (though still it's possible to use this method to get an approximation, as in en.wikipedia.org/wiki/…). $\endgroup$ – D.W. Sep 15 '18 at 15:30
  • $\begingroup$ Thanks! I'll try that. The c_i's are whole number but there is no meaningful loss of information from rounding them to integers, and C is not too large relative to the c_i's. $\endgroup$ – tdawg Sep 16 '18 at 13:50
  • $\begingroup$ In case others have this question: A problem setup where the objective is a ratio of linear functions is called fractional programming. This paper - journal.library.iisc.ernet.in/index.php/iisc/article/viewFile/… - has simple but effective algorithms to convert such a problem into a series of linear programming problems. $\endgroup$ – tdawg Oct 4 '18 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.