Parametric Solution for Linear Bicriteria Knapsack Models

Linear weighing is a common approach to handle multiple criteria and the "knapsack" is a well-known combinatorial optimization problem. A knapsack problem with two linearly weighted, objective criteria is considered in this paper. For better support, it is important to provide the decision maker with information that covers the whole range of alternatives. Toward this goal, an algorithm for the construction of a parametric solution to the problem, i.e., for any combination of weights, is developed, which is based on finding a longest path in a network which compactly represents all feasible solutions to the knapsack problem. Exploiting the special structure of the knapsack model, the algorithm efficiently constructs the parametric solution in time that is linear in the product of the number of variables, the resource limit (right-hand side of the constraint), and the (finite) number of vectors which constitute the solution. The amount of memory required is linear in the product of the number of variables and the resource limit. Results of computational study are reported. The results are used to assess the efficiency of the algorithm and characterize its behavior with respect to the parameter values.