Surrogate upper bound sets for bi-objective bi-dimensional binary knapsack problems
We define an upper bound set for the bi-objective bi-dimensional knapsack problem. It is based on the surrogate relaxation and generalizes the dual surrogate problem. We propose two exact algorithms: an enumerative algorithm and its improved version. We analyze the surrogate multipliers and the dominance relations between bound sets. Based on the improved exact algorithm, an approximated version is derived.
bound sets bi-dimensional binary knapsack problem surrogate relaxation combinatorial optimization multiple objective programming