Bi-dimensional knapsack problems with one soft constraint are considered. A bi-objective solution approach for providing trade-off information is proposed. Introduction of bound computations based on negative coefficients. A predefined region of interest focuses the search on interesting solutions.