The maximum linear programming knapsack problem with extended generalized upper bound constraints

In this paper, we consider a maximin version of the linear programming knapsack problem with extended generalized upper bound (GUB) constraints. We solve the problem efficiently by exploiting its special structure without transforming it into a standard linear programming problem. We present an O(n³) algorithm for deriving the optimal solution where n is the total number of problem variables. We illustrate a numerical example.