Source-linked AI summary
The multiobjective multidimensional knapsack problem: a survey and a new approach
Thibaut Lust, Jacques Teghem
TL;DR
The paper addresses how to obtain or approximate efficient solutions for multiobjective and multidimensional knapsack problems, where exact determination and quality comparison are difficult. It surveys existing methods and adapts two-phase Pareto local search with a very-large scale neighborhood, achieving stronger heuristic results on biobjective instances but facing high convergence time in three-objective cases.
Problem
The paper studies obtaining or approximating efficient solutions for multiobjective knapsack problems, where exact determination is difficult and approximation quality is itself difficult to assess.
Method
The paper surveys existing work and adapts two-phase Pareto local search using a very-large scale neighborhood in its second phase.
Results
2PPLS with the VLSN produced better biobjective results than existing methods, including about 90%, 70%, and 20% of non-dominated points for the 250-2, 500-2, and 750-2 instances.
Takeaways & Limitations
VLSN-based 2PPLS is promising for biobjective MOMKP instances, whereas three-objective cases favor MEMOTS because 2PPLS converges too slowly.
Takeaways & Limitations
For three-objective instances, 2PPLS has very high convergence time and is impractical for 500-3 and 750-3 unless stopped early or its neighborhood is drastically limited.
Abstract
from arXiv · showhide
The knapsack problem (KP) and its multidimensional version (MKP) are basic problems in combinatorial optimization. In this paper we consider their multiobjective extension (MOKP and MOMKP), for which the aim is to obtain or to approximate the set of efficient solutions. In a first step, we classify and describe briefly the existing works, that are essentially based on the use of metaheuristics. In a second step, we propose the adaptation of the two-phase Pareto local search (2PPLS) to the resolution of the MOMKP. With this aim, we use a very-large scale neighborhood (VLSN) in the second phase of the method, that is the Pareto local search. We compare our results to state-of-the-art results and we show that we obtain results never reached before by heuristics, for the biobjective instances. Finally we consider the extension to three-objective instances.
1 Introduction
Multiobjective combinatorial optimization seeks efficient solutions across several objectives, but discrete feasible and objective sets can be large and difficult to determine exactly. The paper motivates heuristic approximation and discusses the competing needs of approximation quality, diversity, and evaluation.
- Multiobjective optimization evaluates feasible solutions using more than one objective in many real applications.
- Efficient solutions are those for which no feasible alternative dominates their objective vector.
- Supported efficient solutions come from weighted single-objective optimization, whereas non-supported efficient solutions arise from the non-convex objective space.
- The efficient and Pareto-front sets may have very large cardinality, and non-supported solutions are especially difficult to determine.
- Exact determination is NP-hard for these multiobjective combinatorial problems, so heuristic methods commonly produce approximations of the efficient set and Pareto front.
- Approximation methods must balance intensity, which seeks closeness to the Pareto front, with diversity, which seeks coverage across it.
- Comparing approximation quality remains difficult because the assessment itself is multicriteria, and no indicator alone establishes superiority.
2 The multiobjective knapsack literature
The multiobjective multidimensional knapsack problem selects items to maximize several profits under multiple capacity constraints. Its development builds on single-objective knapsack methods, especially core-based reductions around a split item.
- MOMKP selects items to maximize p total profits while respecting m capacity constraints for characteristics such as weight or volume.
- The binary variable x_i indicates whether item i is selected, and most surveyed instances use two objectives, with some using three.
- The single-constraint case m = 1 is the multiobjective knapsack problem, while m = p = 1 recovers the classical knapsack problem.
- For the classical knapsack problem, ordering items by non-increasing profit-to-weight efficiency yields an optimal solution to its linear relaxation.
- Core methods restrict attention to a subset of items around the split item and fix variables outside that subset.
2.1 The MOKP
The MOKP literature includes exact methods, approximation schemes, and metaheuristics. Research spans two-phase, dynamic-programming, scalarization, evolutionary, and local-search approaches for approximating or determining efficient solutions.
- MOKP methods are organized into exact algorithms, approximation algorithms, and heuristic methods based on metaheuristics.
- Two-phase methods first generate supported efficient solutions through weighted aggregations, then search between consecutive supported points for non-supported solutions.
- Dynamic-programming extensions use additional dominance relations to discard partial solutions and have solved large biobjective instances, while three-objective instances remain smaller.
- A hybrid two-phasification method combining the two-phase approach with dynamic programming improved results on random and correlated instances and matched them on uncorrelated instances.
- Approximation approaches include FPTAS and PTAS methods, with FPTAS algorithms polynomial in ǫ^-1.
- Metaheuristics include simulated annealing, tabu search, genetic algorithms, and scatter search, often using scalarization or diversification mechanisms.
2.2 The MOMKP
MOMKP research is dominated by heuristic methods, including evolutionary and local-search hybrids. Studies report comparisons among major metaheuristics, while exact and core-based approaches address smaller or restricted instances.
- MOMKP research has mainly developed heuristic methods, commonly grouped by evolutionary algorithms and local search.
- Early comparative studies introduced benchmark instances and reported SPEA or MOGLS outperforming several competing multiobjective genetic or hybrid algorithms.
- MEMOTS used a dynamic objective-space hypergrid for parent selection and tabu search for offspring improvement, outperforming MOGLS and PMA on reported indicators.
- Hybrid methods combine tabu search, estimation of distribution, GRASP, surrogate relaxation, or guided local search with multiobjective search.
- Local dominance and local recombination performed better together with different locality than alone or with the same locality.
- Exact branch-and-bound methods and core-based reductions were also applied, including exact comparisons on three-objective or small biobjective instances.
3 New approach
The paper adapts two-phase Pareto local search to MOMKP by combining a very-large scale neighborhood with heuristic management of residual problems. The method uses weighted sums to generate supported solutions and Pareto local search to explore non-supported solutions.
- 3 New approach: The proposed method couples 2PPLS with a VLSN that heuristically manages the residual problems arising from a divide-and-conquer decomposition.Unlike core-based approaches that may solve residual problems exactly, the VLSN selects and manages them heuristically.
- 3 New approach: 2PPLS combines a first phase for supported efficient solutions with a second Pareto-local-search phase for non-supported solutions.The first phase uses weighted sums and efficient single-objective solvers; the second uses a neighborhood function.
- 3 New approach: The VLSN constructs neighborhoods by selecting L candidate removals and L candidate additions, then merging them into a residual MOMKP with 2L items.Items already in the solution are ranked for removal, while missing items are ranked for addition.
- 3 New approach: For biobjective instances, the weight set used in neighborhood ratios reflects the selected solution’s relative performance across objectives; for three objectives, it is randomly generated.Higher-performing objectives receive higher weights in the biobjective setting.
- 3 New approach: The residual problem can be solved exactly with branch and bound or heuristically with a simplified MEMOTS variant to permit larger neighborhoods and reasonable running times.The simplified variant omits the hypergrid, reducing complexity and parameters to tune.
4 Data and reference sets
The evaluation uses ZMKP instances with varying item, objective, and constraint counts, and assesses approximation quality with unary indicators and reference sets. Reference sets are exact for biobjective instances but heuristic approximations for three-objective instances.
- 4 Data and reference sets: The experiments use ZMKP instances with 250, 500, or 750 items, either two objectives and constraints or three objectives and constraints.For example, a 250-2 instance has 250 items and two objectives.
- 4 Data and reference sets: Approximation quality is assessed using the unary indicators introduced earlier in the paper.Some indicators require a reference set.
- 4 Data and reference sets: For biobjective instances, the reference set consists of non-dominated points generated with the ǫ-constraint method and CPLEX.These points were generated by Tuyttens.
- 4 Data and reference sets: For three-objective instances, the reference set is approximated by repeatedly running MEMOTS and MOGLS for many iterations and retaining potentially non-dominated points.The resulting set is heuristic rather than generated by an exact solver.
- 4 Data and reference sets: Hypervolume is not computed for three-objective instances because its computation is too time-consuming for the large sets involved.For biobjective instances, the hypervolume uses (0,0) as the bounding point.
5 Results
The experiments study neighborhood length, compare EXACT and MEMOTS residual-problem subroutines, and evaluate 2PPLS against reference and competing methods. 2PPLS performs strongly on biobjective instances, while three-objective performance involves substantial runtime and convergence trade-offs.
- Influence of neighborhood length: Increasing L strongly improves PYN with EXACT, but running time grows exponentially and values above 8 become unreasonable.The study varies L from 4 to 8 on instance 500-2.
- Influence of neighborhood length: With MEMOTS, higher N improves PYN for larger L, but increases running time and can degrade PYN when N is too small.For L around 16 and N = 100 or 200, PYN deteriorates despite increasing running time.
- Subroutine comparison: For fixed small running times EXACT is preferable, whereas MEMOTS becomes better as more time is allowed.The suitable combination of L and N depends on the available running time.
- Biobjective comparisons: 2PPLS with MEMOTS obtains better-than-or-equal indicator values than reference set ALL in reasonable times: 7s, 23s, and 18s.These times correspond respectively to instances 250-2, 500-2, and 750-2.
- Biobjective comparisons: Except at small running times, 2PPLS outperforms MEMOTS and reaches about 90%, 70%, and 20% of non-dominated points on 250-2, 500-2, and 750-2.For 250-2, 2PPLS reaches 81% in about 15s versus about 30 minutes for Mavrotas et al.; 93% requires 42s versus 21 hours.
- Three-objective instances: For 250-3, 2PPLS yields better indicator quality and over five times more potentially efficient solutions, but requires about 8 hours.Many potentially efficient solutions make the Pareto local search stop condition slow on three-objective instances.
- Three-objective instances: On 250-3 under equal runtime limits, MEMOTS is generally better, while stopping 2PPLS before convergence can produce second-rate quality.The search is less guided in 2PPLS than in MEMOTS, which continually targets low-density objective-space regions.
- Overall conclusions: The study concludes that 2PPLS is more suited to biobjective instances and is impractical for larger three-objective instances without early stopping or a drastically limited neighborhood.The stated boundary concerns 500-3 and 750-3 instances.
6 Conclusion and perspectives
The paper surveys MOMKP research and proposes 2PPLS with a VLSN. The approach performs better on biobjective instances but is less efficient than MEMOTS on three-objective instances, motivating interactive search guidance.
- Conclusion: 2PPLS with a VLSN and simplified MEMOTS produces better results than existing methods on biobjective instances.The comparison specifically identifies MEMOTS among the methods outperformed.
- Conclusion: VLSN-based methods are presented as a promising research direction for multiobjective combinatorial optimization.
- Perspectives: On three-objective instances, 2PPLS has very high convergence time, while MEMOTS is more efficient.
- Perspectives: For randomly generated MOMKP instances with more than two objectives, decision-maker involvement can direct the search and limit generated solutions.The paper suggests involvement at the beginning or during algorithm execution and recommends modifying 2PPLS interactively.