On local search for bi-objective knapsack problems

Area of Science:

• Operations Research
• Combinatorial Optimization
• Algorithm Design

Background:

• The bi-objective binary knapsack problem involves maximizing profit and minimizing weight simultaneously.
• Existing exact algorithms can be computationally intensive for large problem instances.

Purpose of the Study:

• To propose and evaluate a local search approach for the bi-objective binary knapsack problem.
• To investigate the structural properties of the efficient set for this problem.

Main Methods:

• An experimental study on the connectedness property of the efficient set.
• Development of a local search algorithm based on the identified property.
• Comparison of the local search algorithm against exact algorithms using runtime and solution quality metrics.

Main Results:

• The local search algorithm effectively identifies a representative set of optimal solutions in most cases.
• The proposed algorithm significantly outperforms exact algorithms in terms of runtime.
• The algorithm's performance is robust across different variants of the problem.

Conclusions:

• A simple local search approach is a highly efficient method for solving the bi-objective binary knapsack problem.
• This method provides a practical alternative to exact algorithms, especially for large-scale instances.
• The findings highlight the utility of exploiting structural properties of the efficient set in algorithm design.