A LONGEST PATH FORMULATION FOR INTEGER KNAPSACK PROBLEM WITH SETUPS

Knapsack problems with setups find their application in many concrete industrial and financial problems. A special case is the bounded integer knapsack problem with setups. In this paper, we consider this case and formulate it as a longest path problem. Finally, we consider the running time when the corresponding problem is solved by running Dijkstra’s algorithm.