An improved interactive hybrid method for the linear multi-objective knapsack problem

In many situations, the knapsack problem in the presence of multiple, conflicting objectives frequently occurs in, for example, capital budgeting, project selection and capital investment, and budget control. Previous work was done to solve decision problems that had a weak point. An improved hybrid method is suggested to reduce the burden to the decision maker (DM) in selecting a solution and to obtain computational efficiency. In the method, bounding of the DM's utility value based on the revealed preference information is incorporated into a dynamic programming framework. In finding the most preferred solution (MPS), an implicit utility function is approximated by a linear function completely described by the scaling constants. The DM's partial preference expression is translated into a set of possible scaling constants. In the stagewise solution process, an ideal objectives achievement of each partial solution is derived, and examined for whether it can give the highest utility value by comparing to the best-known objectives achievement. Elimination of partial solutions, which have proved not to lead to the MPS, is done to make the procedure more effective in finding the MPS. A suggested scheme based on the DM partial preference expression can give computational efficiency, which will be shown through computational experiments.