Ebiefung, Aniekan; Saleh, Ossama; Gunasekera, Sumith
College of Arts and Sciences
University of Tennessee at Chattanooga
Place of Publication
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.
SIMCenter-Center of Excellence in Applied Computational Science and Engineering at University of Tennessee Chattanooga
M. S.; A thesis submitted to the faculty of the University of Tennessee at Chattanooga in partial fulfillment of the requirements of the degree of Master of Science.
Mathematical optimization; Knapsack problem (Mathematics)
xiii, 68 leaves
Smith, Blake, "Robust optimization of linear optimization problems and an approximation approach to solve robust Knapsack Problem" (2019). Masters Theses and Doctoral Dissertations.