A Direct Descent Binary Knapsack Algorithm

Publisher Website
Google Scholar
Abstract
A direct descent algorithm for the binary knapsack problem is presented The problem variables are entered into a hst according to decreasing (increasing) contribution/resource ratios The variables are examined in descending order untd one of several fathoming conditions estabhshes that further descent is not necessary. A backtrack up the list ensues, followed by a subsequent descent. This pattern continues untd the optimum is located TMs strategy has two advantages (1) A linear programming bound is available at each point, and (2) the search is easily managed, in fact, the current position m the search is completely characterized by the set of varmbles fixed at 1 and the index of the variable being examined Since the binary knapsack usually has many incumbents, a reduction ~s incorporated into the search Several theoretical results which were useful m the ~mplementatlon of the direct descent algorithm, computational results companng the algorithm wtth several branch-and-bound algorithms, and extensions of the algorithm to the interval bounded binary knapsack problem are also presented.