Robust optimization of linear optimization problems and an approximation approach to solve robust Knapsack Problem

The goal of classical KP, is to find a subset of items whose total weight does not exceed the knapsack capacity, and whose profit is a maximum. In the robust KP the goal is to find a subset of items whose total weight does not exceed the knapsack capacity, and remains near maximum for the worst scenario. Solving the robust KP exactly is difficult due to this data uncertainty and combinatorial structure of the problem. In this research, a polynomial-time algorithm is proposed to approximately obtain a near optimal solution for the robust KP with a provable quality. The quality is described by an error term and it is derived for the proposed algorithm. It is shown that the error depends on the characteristics of the problem. We verify the accuracy of the algorithm theoretically and computationally. It is shown that the error depends on the characteristics of the problem. We verify the accuracy of the algorithm theoretically and computationally