RATIO COMBINATORIAL PROGRAMS

We consider here a combinatorial optimization problem where the object ive function is a ratio of two linear functions. One way of solving th is problem is to solve repeatedly an auxiliary problem with a paramete rized linear objective function. In this paper we relate this method t o Newton's method for solving equations and present a modification of this algorithm which solves the ratio problem epsilon-approximately by repeatedly solving the auxiliary linear problems with the same accura cy. We demonstrate, by reporting results of extensive computational ex periments, that the above modified algorithm for the epsilon-approxima te knapsack problem performs extremely well in practice.