Landscape Analysis of a Class of NP-Hard Binary Packing Problems

Area of Science:

• Computational complexity
• Operations research
• Heuristic optimization

Background:

• Combinatorial optimization problems like number partitioning, binary knapsack, and quadratic binary knapsack are computationally challenging.
• Understanding the fitness landscape is crucial for designing effective local search algorithms.

Purpose of the Study:

• To conduct an exploratory landscape analysis of three NP-hard combinatorial optimization problems.
• To investigate how fitness landscape properties vary with problem parameters, distributions, penalty functions, and neighborhood operators.
• To identify landscape features that correlate with problem difficulty for local search.

Main Methods:

• Empirical examination of fitness landscape properties for randomly generated instances.
• Analysis of instances drawn from various distributions.
• Comparison of properties across different penalty functions and neighborhood operators.

Main Results:

• Identified variations in landscape features across different problem instance distributions for all three problems.
• Quantified these variations using a single, easily calculable parameter.
• Demonstrated the parameter's utility in guiding the selection of neighborhood operators for local search heuristics.

Conclusions:

• Fitness landscape analysis provides insights into the inherent structure and difficulty of NP-hard problems.
• A single parameter can capture variations in landscape features across different instance distributions.
• This parameter offers a practical method for enhancing the performance of local search algorithms by informing operator choice.