An Exact Algorithm for the Unbounded Knapsack Problem with Minimizing Maximum Processing Time‪.‬

INTRODUCTION One of the most frequently used decision making that operations researchers must deal is to decide which subset of n items or projects should be selected such that the total profit sum of the selected items or projects is maximized, without exceeding the capital budget, referred generally as the knapsack problem (KP). This problem can be formulated as a mathematical model (an integer linear program) and is one of an NP-hard combinatorial optimization problem by which can be solved successfully by various exact algorithms. The commonly used techniques are the dynamic programming and branch-and-bound methods and the branch-and-cut and branch-and-price methods as described in Toth(1). This kind of problem can be applied and arises in many real world situations. In the following, we will provide a historical overview of this problem and various involved algorithms.