# Knapsack-type problem where the objective function is a ratio

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?

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

## 1 Answer

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.

• 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/…). – D.W. Sep 15 '18 at 15:30
• 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. – tdawg Sep 16 '18 at 13:50
• 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. – tdawg Oct 4 '18 at 19:51