Matheuristic fixed set search applied to the multidimensional knapsack problem and the knapsack problem with forfeit sets

Jovanovic, Raka; Voß, Stefan Article — Published Version Matheuristic fixed set search applied to the multidimensional knapsack problem and the knapsack problem with forfeit sets OR Spectrum Provided in Cooperation with: Springer Nature Suggested Citation: Jovanovic, Raka; Voß, Stefan (2024) : Matheuristic fixed set search applied to the multidimensional knapsack problem and the knapsack problem with forfeit sets, OR Spectrum, ISSN 1436-6304, Springer, Berlin, Heidelberg, Vol. 46, Iss. 4, pp. 1329-1365, https://doi.org/10.1007/s00291-024-00746-2 This Version is available at: https://hdl.handle.net/10419/313829 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Vol.:(0123456789) OR Spectrum (2024) 46:1329–1365 https://doi.org/10.1007/s00291-024-00746-2 1 3 ORIGINAL ARTICLE Matheuristic fixed set search applied tothemultidimensional knapsack problem andtheknapsack problem withforfeit sets RakaJovanovic1 · StefanVoß2,3 Received: 9 July 2023 / Accepted: 4 January 2024 / Published online: 12 February 2024 © The Author(s) 2024 Abstract In this paper, we present a solution method for the multidimensional knapsack problem (MKP) and the knapsack problem with forfeit sets (KPFS) using a populationbased matheuristic approach. Specifically, the learning mechanism of the fixed set search (FSS) metaheuristic is combined with the use of integer programming for solving subproblems. This is achieved by introducing a new ground set of elements that can be used for both the MKP and the KPFS that aim to maximize the information provided by the fixed set. The method for creating fixed sets is also adjusted to enhance the diversity of generated solutions. Compared to state-of-the-art methods for the MKP and the KPFS, the proposed approach offers an implementation that can be easily extended to other variants of the knapsack problem. Computational experiments indicate that the matheuristic FSS is highly competitive to best-per- forming methods from the literature. The proposed approach is robust in the sense of having a good performance for a wide range of parameter values of the method. Keywords Metaheuristics· Multidimensional knapsack problem· Knapsack problem with forfeit sets· Fixed set search· Matheuristic * Raka Jovanovic rjov[email protected] Stefan Voß stefan.v[email protected] 1 Qatar Environment andEnergy Research Institute, Hamad bin Khalifa University, POBox5825Doha, Qatar 2 Institute ofInformation Systems, University ofHamburg, Von-Melle-Park 5, 20146Hamburg, Germany 3 Escuela de Ingenieria Industrial, Pontificia Universidad Católica de Valparaíso, Valparaíso, Chile 1330 R.Jovanovic, S.Voß 1 3 1 Introduction The knapsack problem (KP) and its variants are among the most researched combinatorial optimization problems. Due to the NP-hardness of these problems, many heuristic and metaheuristic methods have been developed for solving them. In this paper, a general method is proposed that can be potentially applied to a wide range of them. The approach is illustrated on two variants of the knapsack problem with different properties. To be specific, the proposed approach is applied on the multidimensional knapsack problem (MKP) and the knapsack problem with forfeit sets (KPFS). The MKP is a versatile problem with a wide range of practical applications such as cutting stock (Gilmore and Gomory 1966), loading (Shih 1979), and many others. However, solving it is computationally challenging due to its NP-hardness (Garey and Johnson 1979). Despite this, it has been extensively studied, and numerous solution approaches have been proposed. A comprehensive review of representative studies up to 2004 can be found in Fréville (2004), and more recent studies are discussed in Lai etal. (2018). Interesting variants of the MKP include the multiple multidimensional knapsack problem (Mancini etal. 2021), the multiple-choice multidimensional knapsack problem (Chen and Hao 2014), the robust multiple-choice multidimensional knapsack problem (Caserta and Voß 2019), and the multidemand multidimensional knapsack problem (Lai etal. 2019). Another group of variations of the KP is based on the idea of incompatible items (Basnet 2018; Coniglio etal. 2021). One of the main representatives of this type of problem is the knapsack problem with conflict graphs (KPCG), which deals with incompatibilities between item pairs and is proven to be strongly NP-hard (Pferschy and Schauer 2009; Li etal. 2021). A closely related variant is the knapsack problem with forfeits (KPF), where item pairs come with associated penalty costs (Capobianco etal. 2022). In this paper, the analysis focuses on the newly introduced knapsack problem with forfeit sets (KPFS) which can be understood as a generalization of the KPF (D’Ambrosio etal. 2023). In it, forfeit costs are associated with subsets of items, and an allowance parameter determines how many items can be chosen from each set before incurring penalty costs. 1.1 Related work Methods for solving the MKP can be exact or heuristic. Exact ones frequently use branch and bound, like those by Shih (1979) and Vimont etal. (2008), and hybridization with other strategies like Boussier etal. (2010) and Mansini and Speranza (2012). The best exact algorithms (e.g., Vimont etal. (2008), Boussier etal. (2010), and Mansini and Speranza (2012)) produce optimal solutions quickly for small benchmark instances but have a prohibitive computational cost for large ones. Besides exact solution methods, the literature contains several heuristic algorithms categorized as either single-solution-based local search or population-based optimization. Local search algorithms, such as tabu search (Dammeyer and Voß 1993; 1331 1 3 Matheuristic fixed set search applied tothemultidimensional… Glover and Kochenberger 1996; Hanafi and Freville 1998; Vasquez and Vimont 2005), simulated annealing (Drexl 1988), and kernel search (Angelelli etal. 2010), have been shown to be successful. Population-based methods include genetic and memetic algorithms (Chu and Beasley 1998; Rezoug etal. 2018), hybrid binary particle swarm optimization (Haddar etal. 2016; Mingo López etal. 2018), ant colony optimization (Al-Shihabi and Ólafsson 2010), path relinking (Arin and Rabadi 2016), and many others. The MKP also attracts research related to general artificial intelligence exposition. For instance, in García etal. (2020), the authors propose an improved binarization framework, which uses the K-means technique to enable the use of continuous metaheuristics for the MKP. One of the best-performing metaheuristic algorithms for the MKP is the twophase tabu-evolutionary algorithm (TPTEA) (Lai etal. 2018) which was also highly successful for the multidemand multidimensional knapsack problem (Lai et al. 2019). This approach combines two solution-based tabu search methods with an evolutionary framework that utilizes a hyperplane-constrained crossover operator to generate offspring solutions. Additionally, it employs a dynamic method to identify areas of interest for the search and a diversity-based population updating rule to ensure that a diverse and healthy population is maintained. Another effective method for the MKP, known as the diversity-preserving quantum particle swarm optimization (Lai etal. 2020), relies on quantum particle swarm optimization (Haddar etal. 2016) and exhibits a substantially lower computational cost compared to TPTEA. However, it achieves solutions of lower quality, as demonstrated by Lai etal. (2020). This technique combines a diversity-preserving strategy based on distance to manage the population, along with a solution improvement method that employs variable neighborhood descent for local optimization. Since the KPFS is a newly introduced problem, only limited research has been done on the development of solution methods. To be specific, in the work of D’Ambrosio etal. (2023), a mixed integer programming model has been introduced. In the same paper, a fast solution method based on the carousel greedy algorithm is also presented. In addition, an advanced memetic algorithm (MA) is proposed which extends the genetic algorithm paradigm by including a local refinement mechanism. 1.2 Fixed set search The fixed set search (FSS) is a population-based metaheuristic that adds a learning mechanism to the greedy randomized adaptive search procedure (GRASP) (Feo and Resende 1995). The GRASP involves generating solutions using a randomized greedy algorithm and applying a local search to each of them. The FSS has been successfully applied to solve several problems, including the traveling salesman problem (Jovanovic etal. 2019), the power dominating set problem (Jovanovic and Voss 2020), machine scheduling (Jovanovic and Voß 2021), the minimum weighted vertex cover problem (Jovanovic and Voß 2019), the covering location with interconnected facilities problem (Lozano-Osorio et al. 2023), the clique partitioning 1332 R.Jovanovic, S.Voß 1 3 problem (Jovanovic et al. 2023b), as well as bi-objective optimization problems (Jovanovic etal. 2022). The FSS is inspired by the fact that high-quality solutions for a specific problem instance often have many of the same elements in common. Therefore, the FSS generates new solutions that contain these fixed elements, and the computational effort is focused on completing the partial solution. The idea of using frequently occurring elements in high-quality solutions is based on earlier notions of chunking (Voß and Gutenschwager 1998; Woodruff 1998), vocabulary building, and consistent chains (Sondergeld and Voß 1999) as they have been used in relation to tabu search. Closely related concepts have also been used in the matheuristic POPMUSIC paradigm (Taillard and Voß 2002). Matheuristic approaches, such as kernel search (Angelelli etal. 2010; Maniezzo etal. 2021) and heuristic concentration (Rosing and ReVelle 1997), are based on the idea of generating numerous solutions to identify elements that commonly appear in high-quality solutions. These methods then fix these elements and solve the corresponding mathematical programming problem. On the other hand, the FSS utilizes a mechanism that can generate various fixed sets or kernels based on elements that frequently appear in different subsets of high-quality solutions, resulting in a more efficient global search. While kernel search and heuristic concentration share similarities with the FSS, the latter offers a more diverse range of fixed sets or kernels. 1.3 Contributions One of the drawbacks of the best-performing methods for the MKP and the KPFS is that they have a highly complex implementation. The main reason is that they hybridize different metaheuristics and use several distinct solution neighborhoods. In this work, the goal is to provide a simple-to-implement method to solve the MKP and the KPFS based on the FSS. To be specific, the idea is to combine the FSS with the use of integer programming (IP). Related methods combining heuristics/ metaheuristics with IPs are frequently called matheuristics, for which a recent review can be found in Boschetti and Maniezzo (2022). It should be noted that a method of this type has recently been successfully applied to the closely related quadratic multiple knapsack problem (Galli etal. 2023). In the development of the matheuristic FSS (MFSS) for the MKP and the KPFS, several new concepts are explored in relation to the basic FSS. Firstly, a novel way for defining the ground set of elements for 0-1 problems is introduced that aims to maximize the amount of information that the fixed set provides. Next, an effective mechanism is proposed for incorporating the learning mechanism in a matheuristic setting. In this way, the need for defining a randomized greedy algorithm and a local search, as in the original FSS, can be avoided making the implementation of the method less complex. Another novel idea in the MFSS is using the method for generating fixed sets to diversify the generated solutions. The conducted computational 1333 1 3 Matheuristic fixed set search applied tothemultidimensional… experiments show that the MFSS is highly competitive to state-of-the-art methods for the MKP and outperforms the ones for the KPFS. The paper is organized as follows. Section2 is dedicated to the problem formulations of the MKP and the KPFS. Next, Sect.3 provides details of applying the MFSS to the problems of interest. The following Sect.4 is dedicated to the presentation of the conducted computational experiments. The paper is finalized in Sect.5 with some concluding remarks. 2 Problem formulations The knapsack problem is defined for a set of items V and a capacity c. Each item j∈V has a non-negative profit value pj and a non-negative weight wj . The goal is to select a set of items S⊂V such that the sum of the profit values of items in S is maximized while satisfying the constraint that the sum of the weights is less or equal to the capacity c. 2.1 The multidimensional knapsack problem The multidimensional knapsack problem (MKP) extends this concept to have multiple constraints. Now, the capacity is an m-dimensional vector having values ci , for i=1..m . Each item j∈V has an m-dimensional weight vector, having as value wij . The goal is to maximize the sum of profit values while ensuring that the sum of the weights in each dimension i=1..m does not exceed the capacity ci . Formally, the MKP can be specified using an IP model with a set of binary decision variables xj defined for j∈V using the following objective function: Constraints (2) guarantee the satisfaction of the capacity constraints for each of the m dimensions, and variable definitions are provided in (3). 2.2 The knapsack problem withforfeit sets In this subsection, the formulation of the KPFS is given as proposed by D’Ambrosio etal. (2023). The KPFS uses the same set of items j∈V , item profit values pj , (1) Maximize ∑ j ∈ V pjx j (2) Subject to ∑ j ∈ V wijxj≤cii=1.. m (3) xj∈{0, 1}j∈V 1334 R.Jovanovic, S.Voß 1 3 item weights wj , and capacity c as in the KP. Also, a solution S⊆V must satisfy the constraint that the total weight of the items in the solution is less or equal to the knapsack capacity c. Additionally, there exists a collection of l forfeit sets, denoted as C={C1,…,Cl} , where each set Ci is a subset of V. These sets satisfy the condition |Ci| ≥ 2 for i = 1, .., l , where the notation |Ci| is used for the cardinality of the set. Each set Ci is associated with a non-negative cost di and an integer allowance hi , ensuring 0 ≤ hi ≤ |Ci| . For a given solution S, nS i = | C i ∩S | is introduced to represent the number of elements shared between Ci and S. If nS i >h i , a penalty equal to ( n S i −h i )d i must be paid. In such instances, we state that nS i −h i violations are linked to Ci in solution S. Finally, an integer upper bound k≥0 is imposed on the total number of violations allowed in a solution. Formally, a solution S is considered feasible if and only if: This condition ensures that the cumulative violations across all forfeit sets in S do not exceed the predefined limit k. The integer programming formulation is as follows. For each j∈V , a binary variable xj is defined and equals 1 if j is chosen, and 0 otherwise. Next, for each Ci∈C , the integer variable vi is defined and represents the number of violations associated with the set. Using these decision variables, the IP for the KPFS can be fully specified using the following formulation. (4) ∑ i ∈{1,…,l}∶nS i >h i (nS i−hi)≤k (5) Maximize n ∑ j=1 pjxj− l ∑ i=1 div i (6) Subject to n ∑ j=1 wjxj≤ c (7) l ∑ i=1 vi≤ k (8) ∑ j∈C i xj−vi≤hii=1.. l (9) xj∈{0, 1}j∈V (10) vi ∈{0, …, | C i| −h i }i=1.. l 1335 1 3 Matheuristic fixed set search applied tothemultidimensional… The objective function, given in (5), maximizes profit, which is the sum of the profits of all selected items minus the associated costs. Constraint (6) ensures that the sum of the weights of items in the solution does not exceed the capacity. Similarly, Constraint (7) enforces the limit on the number of allowed violations. Constraints (8) represent the relationship among the selected items, the allowance value, and the resulting violations for each forfeit set. Finally, Constraints (9)–(10) define the domain of the decision variables. It should be noted that, as proven by D’Ambrosio etal. (2023), in the formulation of the KPFS, it is not necessary for variables vi to be integer. 3 A matheuristic based onthefixed set search The FSS algorithm takes advantage of the fact that many high-quality solutions for a particular combinatorial optimization problem have common elements. The FSS incorporates some of these elements into newly generated solutions and focuses computational effort on finding optimal or near-optimal solutions in the corresponding subset of the solution space. This selected set of common elements is called the “fixed set." The goal of the FSS is to “fill in the gaps" and complete the partial solution corresponding to the fixed set. In the FSS, this is exploited through adding a learning mechanism to the GRASP. In this section, we present the MFSS which extends this concept to a matheuristic setting. The MFSS consists of several building blocks, including representing the problem solution as a subset of a ground set of elements, defining methods for generating fixed sets, implementing the learning mechanism, and defining a method for completing a solution from a fixed set. 3.1 Fixed set In this section, we describe the approach for generating fixed sets for the MKP and the KPFS. To use the MFSS algorithm, a solution must be represented as a subset of a ground set of elements. For the two problems of interest, a natural way to represent the solution is as a subset S of the set of all items V. In the adaptation of the FSS to a matheuristic approach, our goal is to use a representation of a solution that provides as much information as possible on all items i∈V . Because of this, an alternative ground set is used. Let us note that each item i∈V can either be inside the knapsack or outside of it. Using this idea, the ground set can be defined as G=V×{⊤,⊥} , where a pair (i,⊤) means that item i is selected to be inside the knapsack and (i,⊥) the opposite. Now, a solution S is a subset of the ground set G and satisfies |S|=|V| , or in other words has the same cardinality as the set of items. A graphical illustration of the two types of ground sets is shown in Fig.1. The next step is defining a procedure for generating multiple fixed sets F with a controllable size (cardinality) |F|. Note that it should be possible to use such fixed sets to produce feasible solutions of equal or higher quality than the solutions already 1336 R.Jovanovic, S.Voß 1 3 generated. We begin with some definitions: The notation Sn={S1, .., Sn} represents the set of n best solutions generated in the previous steps of the algorithm. A base solution B∈Sn is a randomly selected solution from the best n solutions. If the fixed set satisfies F⊂B , it can be used to generate a feasible solution of at least the same quality as B. Moreover, F can contain an arbitrary number of elements of B. The idea is to create F such that it contains frequently occurring elements in a group of high-quality solutions. We define Skn as the set of k randomly selected solutions out of the n best solutions, Sn . Let us define the function C(e,S), for a solution S and element e, as 1 if e∈S and 0 otherwise. Using C(e,S), we can count that the number of times an element e occurs in Skn with the function: Then, we define F⊂B as the set of elements e with the largest value of O(e,Skn) . Furthermore, we define the function F=Fix(B,Skn,Size) as the fixed set generated for a base solution B, a set of solutions Skn with Size elements. In the case of the original FSS, the diversification is done through the use of a randomized greedy algorithm with a pre-selected set of elements. In the case of the MFSS, this is partly done in the method for generating the fixed set. To be more precise, we utilize the way ties are resolved. Let us make the following observation. The last element e that should be added to the fixed set F has the value of O(e,Skn)=f . In the general case, there are multiple elements that have the same value of this function. Let us assume that there is a total of l>Size elements e∈B that have a value of the function O(e,Skn) greater or equal than f. Let us use the notation  F for the set of such elements. In the proposed approach, in such cases, the function Fix(B,Skn,Size) returns  F with l−Size random elements removed. Note that a removed element e does not necessarily have the lowest value of O(e,Skn) . A graphical illustration of the method for generating fixed sets is shown in Fig.2. (11) O (e,Skn)= ∑ S∈S kn C(e,S ) a b c d (a) Representationofasolution using the basic ground set V a b c d a b c d (b)Representationofasolution usingthe extended ground set G Fig. 1 Illustration of the different ground sets for the MKP and the KPFS. The items inside the gray shape represent the solution. In case of the extended ground set, circles with full lines indicate that an item is inside the knapsack and a circle with a dashed line the opposite 1343 1 3 Matheuristic fixed set search applied tothemultidimensional… initial maximal computational time for the IPS is 0.1s. The number of n best solutions that are considered for selecting the base solution and Skn is 100. The value of the parameter k for generating Skn is a randomly selected integer value from the interval [5,9]. The algorithm is considered stagnant if in the last MaxStag =50 iterations, there have been no changes of the set of the n best solutions Sn . The maximal allowed calculation time for the MFSS is 600s. It should be noted that in case of the MKP, the maximal size of the subproblem that has been solved, SizeMax, has never been changed. This is due to the fact that proven optimal solutions have not been frequently found; consequently, the MFSS parameters 𝛾 and 𝛿 have not been used. The computational experiments are performed on the instances described in the previous subsubsection. The setting of the experiments is the same as the one used in Lai etal. (2020); for each test instance, ten independent runs are performed. The evaluation is done based on the difference between the optimal or best-known solution for an instance to the solution acquired by the methods used in the comparison. In the later text, this difference is called the error. Since ten independent runs are performed for each method on each instance, aggregated values of these runs are observed. To be specific, the minimal error over all the runs and the average error are used. The results of the comparison are shown in Tables1, 2, 3, 4, 5, and 6 for instance groups with a different number of items and constraints.1 Note that the values for the other methods have been taken from the corresponding papers. For GA and F&F, the average results over ten independent runs were not available in the published papers. The first thing that can be observed is that the TPTEA, DQPSO, and MFSS have significantly better results than the other methods. In case of instances with 250 items with 5 or 10 constraints (Tables1 and 2) and with 500 items and 5 constraints (Table4) out of 90 instances, TPTEA, DQPSO, and MFSS missed on finding all optimal solutions only in 2, 9, and 2 cases, respectively. For the last group of instances with known optimal solutions with 500 items and 10 constraints (Table5), TPTEA, DQPSO, and MFSS find 12, 8, and 9 optimal solutions out of 30 instances, respectively. In summary, the MFSS clearly outperforms DQPSO over all the metrics for all instance groups. Its performance is very similar to that of TPTEA. It has a more robust behavior than TPTEA regarding the average solution quality over 10 runs for each instance being better in five out of six test groups, although the difference is relatively small. On the other hand, when the quality of the best-found solutions is compared, TPTEA and MFSS have a very similar behavior. TPTEA manages to find better solutions for a few more instances than MFSS. On the other hand, the MFSS has better average values of best-found solutions for a few problem sizes. In case of the hardest problem groups, without known optimal solutions in Tables3 and 6, the MFSS and TPTEA have been once better/worse than the other method when the average quality of the best-found solution or average solution quality over the 10 runs are compared. On the other hand, TPTEA managed to find 29 and 12 best-known solutions out of 30 test instances compared to MFSS’s 28 and 7 for the hardest instances with 250 and 500 items, respectively. 1 Underlined Avg. values indicate best values in the respective comparison. 1344 R.Jovanovic, S.Voß 1 3 Table 1 Comparison of the state-of-the-art methods to MFSS on instances with 250 items and five constraints The evaluation is done based on the difference between the optimal solution and the solution acquired by a method ( OPT −X ). The columns "Best" represent the minimal difference, and "Average" is the average difference over 10 independent runs ID OPT Best Average GA F&F QPSO TPTEA DQPSO MFSS QPSO TPTEA DQPSO MFSS 0 59,312 0 0 0 0 0 0 0.00 0.00 0.00 0.00 1 61,472 0 4 0 0 0 0 2.00 0.00 0.28 0.00 2 62,130 0 0 0 0 0 0 0.00 0.00 0.00 0.00 3 59,463 17 27 36 0 0 0 36.00 0.67 21.07 3.00 4 58,951 0 0 0 0 0 0 0.00 0.00 0.00 0.00 5 60,077 21 15 0 0 0 0 21.00 7.50 6.66 0.00 6 60,414 0 0 0 0 0 0 0.00 0.00 0.00 0.00 7 61,472 0 18 0 0 0 0 11.50 0.00 0.00 0.00 8 61,885 0 0 0 0 0 0 0.00 0.00 0.00 0.00 9 58,959 0 0 0 0 0 0 33.50 0.00 0.00 0.00 10 109,109 0 0 43 0 0 0 50.50 0.00 1.54 0.00 11 109,841 0 0 0 0 0 0 0.00 0.00 0.00 0.00 12 108,508 19 0 0 0 0 0 0.00 0.00 0.00 0.00 13 109,383 0 0 27 0 0 0 35.50 0.00 0.00 0.00 14 110,720 0 0 0 0 0 0 10.00 0.00 1.90 0.00 15 110,256 0 0 0 0 0 0 0.00 0.00 5.29 0.00 16 109,040 24 0 0 0 0 0 17.50 0.00 0.00 0.00 17 109,042 5 26 0 0 0 0 23.50 0.00 0.68 0.00 18 109,971 14 14 0 0 0 0 16.00 0.00 0.00 0.00 19 107,058 20 0 0 0 0 0 10.00 0.00 0.91 0.00 20 149,665 6 6 0 0 0 0 14.50 0.00 3.90 0.00 21 155,944 4 0 0 0 4 0 2.00 0.13 4.00 0.00 22 149,334 18 0 0 0 0 0 0.00 0.00 1.54 0.00 23 152,130 0 0 0 0 0 0 0.00 0.00 0.00 0.00 24 150,353 0 0 0 0 0 0 0.00 0.00 0.00 0.00 25 150,045 0 0 0 0 0 0 0.00 0.00 0.00 0.00 26 148,607 0 0 0 0 0 0 0.00 0.00 0.00 0.00 27 149,782 10 0 10 0 0 0 19.50 0.00 6.60 0.00 28 155,075 0 0 18 0 0 0 30.00 0.00 0.00 0.00 29 154,668 6 0 0 0 0 0 0.00 0.00 0.00 0.00 Avg. 5.47 3.67 4.47 0.00 0.13 0.00 11.10 0.28 1.81 0.10 #worse 12 7 5 0 1 16 2 12 #equal 18 23 25 30 29 14 27 18 #better 0 0 0 0 0 0 1 0 1345 1 3 Matheuristic fixed set search applied tothemultidimensional… Table 2 Comparison of the state-of-the-art methods to MFSS on instances with 250 items and 10 constraints ID OPT Best Average GA F&F QPSO TPTEA DQPSO MFSS QPSO TPTEA DQPSO MFSS 0 59,187 0 23 5 0 0 0 14.00 0.00 0.00 0.00 1 58,781 119 88 0 0 76 0 48.00 37.87 94.88 8.00 2 58,097 3 3 0 0 0 0 1.50 0.00 10.14 0.00 3 61,000 0 28 0 0 0 0 14.00 1.43 10.93 0.00 4 58,092 0 0 0 0 0 0 0.00 1.43 3.62 0.00 5 58,824 21 0 0 0 0 0 0.00 1.40 20.58 0.00 6 58,704 97 72 98 0 0 0 107.50 0.00 11.61 0.00 7 58,936 19 19 34 0 6 0 46.50 3.90 14.53 1.00 8 59,387 3 6 15 0 0 0 29.50 0.00 3.59 0.00 9 59,208 15 0 0 0 0 0 0.00 0.00 0.00 0.00 10 110,913 50 24 56 0 0 0 70.00 0.00 0.00 0.00 11 108,717 58 15 30 0 0 2 30.00 0.00 14.45 5.00 12 108,932 0 10 41 0 0 0 43.00 0.00 1.37 0.00 13 110,086 49 27 0 0 0 0 25.50 0.00 24.67 1.00 14 108,485 62 0 0 0 0 0 25.50 0.00 0.00 0.00 15 110,845 4 4 0 0 0 0 2.00 1.33 4.78 0.00 16 106,077 2 2 30 0 0 0 41.00 1.27 0.59 0.00 17 106,686 0 1 0 0 0 0 4.50 0.00 0.00 0.00 18 109,829 4 7 41 0 4 0 74.00 1.60 6.00 1.00 19 106,723 0 0 0 0 0 0 0.00 0.00 0.00 0.00 20 151,809 19 19 30 0 0 0 40.00 0.00 2.08 0.00 21 148,772 0 0 0 0 0 0 0.00 0.00 0.00 0.00 22 151,909 9 0 0 0 0 0 0.00 0.00 0.00 0.00 23 151,324 49 43 43 0 0 0 43.00 0.00 47.61 0.00 1346 R.Jovanovic, S.Voß 1 3 The evaluation is done based on the difference between the optimal solution and the solution acquired by a method ( OPT −X ). The columns “Best” represent the minimal difference, and “Average” is the average difference over ten independent runs Table 2 (continued) ID OPT Best Average GA F&F QPSO TPTEA DQPSO MFSS QPSO TPTEA DQPSO MFSS 24 151,966 18 0 0 0 0 0 28.00 4.20 12.06 0.00 25 152,109 0 0 0 0 0 0 0.00 0.00 0.00 0.00 26 153,131 0 0 0 0 0 0 0.00 0.00 0.00 0.00 27 153,578 58 45 49 0 0 0 49.00 0.00 17.60 0.00 28 149,160 5 0 0 0 0 0 15.00 0.00 3.47 0.00 29 149,704 0 16 58 0 0 0 67.00 0.00 0.00 0.00 Avg. 22.13 15.07 17.67 0.00 2.87 0.07 27.28 1.81 10.15 0.53 #worse 20 19 13 0 3 22 9 19 #equal 10 11 17 29 26 8 19 11 #better 0 0 0 1 1 0 2 0 1347 1 3 Matheuristic fixed set search applied tothemultidimensional… Table 3 Comparison of the state-of-the-art methods to MFSS on instances with 250 items and 30 constraints ID BKS Best Average GA F&F QPSO TPTEA DQPSO MFSS QPSO TPTEA DQPSO MFSS 0 56,842 149 46 46 18 46 0 96.50 18.00 96.70 16.20 1 58,520 202 187 218 0 169 0 218.00 0.00 200.12 11.40 2 56,614 61 61 0 0 0 0 43.50 0.00 57.84 29.40 3 56,930 67 0 0 0 0 0 38.00 0.00 0.65 0.00 4 56,629 0 0 0 0 0 0 0.00 0.00 0.00 0.00 5 57,205 86 56 59 0 16 0 89.50 0.00 57.72 15.50 6 56,357 65 94 54 0 54 4 110.50 23.60 133.94 27.20 7 56,457 54 0 65 0 0 0 82.50 0.00 0.09 0.00 8 57,474 32 101 27 0 0 0 66.50 15.10 54.64 12.80 9 56,447 0 0 0 0 0 0 0.00 0.00 0.00 0.00 10 107,770 81 35 67 0 38 0 74.00 6.90 50.11 15.90 11 108,392 54 54 54 0 13 13 55.50 4.77 14.29 13.00 12 106,442 57 27 0 0 0 0 28.50 2.40 14.31 0.80 13 106,876 80 44 25 0 0 0 48.00 0.00 54.37 7.10 14 107,414 18 0 32 0 18 0 32.00 0.00 18.00 0.00 15 107,271 25 0 0 0 0 0 34.50 0.00 26.19 2.50 16 106,372 64 95 124 0 7 0 130.00 0.23 52.70 10.10 17 104,032 39 29 44 0 18 0 44.00 13.00 31.41 17.20 18 106,856 21 21 0 0 21 0 10.50 3.50 49.00 14.70 19 105,780 29 38 29 0 29 0 40.00 0.83 29.00 10.00 20 150,163 80 25 67 0 25 0 111.00 0.00 51.67 5.00 21 149,958 51 0 0 0 51 0 25.50 0.00 51.00 0.00 22 153,007 14 0 0 0 0 0 0.00 0.00 13.58 0.00 23 153,234 65 52 0 0 0 0 34.00 0.00 45.19 1.30 1348 R.Jovanovic, S.Voß 1 3 These instances do not have proven optimal solutions but only best-known solutions (BKS). The evaluation is done based on the difference between the BKS and the solution acquired by a method ( BKS − X ). The columns “Best” represent the minimal difference, and “Average“ is the average difference over ten independent runs Table 3 (continued) ID BKS Best Average GA F&F QPSO TPTEA DQPSO MFSS QPSO TPTEA DQPSO MFSS 24 150,287 0 0 0 0 0 0 0.00 0.00 0.00 0.00 25 148,574 30 25 30 0 0 0 45.50 0.00 13.26 3.10 26 147,477 6 22 6 0 0 0 14.00 0.00 0.00 0.00 27 152,912 71 71 77 0 0 0 77.00 0.00 17.63 0.00 28 149,570 2 0 0 0 0 0 29.00 0.00 0.14 0.00 29 149,668 96 81 0 0 67 0 48.00 0.00 67.00 9.70 Avg. 53.30 38.80 34.13 0.60 19.07 0.57 54.20 2.94 40.02 7.43 #worse 27 20 17 1 13 25 3 26 #equal 3 10 13 27 17 4 11 4 #better 0 0 0 2 0 1 16 0 1349 1 3 Matheuristic fixed set search applied tothemultidimensional… Table 4 Comparison of the state-of-the-art methods to MFSS on instances with 500 items and five constraints ID OPT Best Average GA F&F QPSO TPTEA DQPSO MFSS QPSO TPTEA DQPSO MFSS 0 120,148 18 14 18 0 0 0 42.30 21.10 10.20 7.00 1 117,879 42 15 35 0 15 0 44.70 28.17 26.60 14.00 2 121,131 22 0 0 0 0 0 39.00 18.77 5.13 3.00 3 120,804 6 10 52 0 0 0 63.70 17.60 8.41 8.00 4 122,319 0 0 0 0 0 0 18.30 0.00 3.00 0.00 5 122,024 17 0 0 0 0 0 42.30 15.17 9.52 9.00 6 119,127 14 18 33 0 0 0 52.00 6.50 4.50 6.00 7 120,568 0 0 32 0 0 0 54.70 19.90 3.12 0.00 8 121,586 11 11 0 11 11 0 58.70 26.83 25.33 12.00 9 120,717 18 10 32 0 0 0 54.70 22.00 9.14 13.00 10 218,428 6 0 0 0 2 0 33.30 16.73 13.55 1.00 11 221,202 11 0 0 11 0 0 49.70 17.10 24.56 5.00 12 217,542 8 8 14 0 6 0 29.00 16.10 8.11 2.00 13 223,560 2 2 0 0 0 0 22.30 1.13 0.02 0.00 14 218,966 4 0 1 0 0 0 1.70 0.00 0.32 0.00 15 220,530 16 0 3 0 0 0 31.30 1.93 3.20 2.00 16 219,989 2 0 46 0 0 0 57.70 3.10 0.74 1.00 17 218,215 21 0 0 0 0 0 30.00 14.63 16.65 4.00 18 216,976 0 0 0 0 0 0 20.70 0.00 0.00 0.00 19 219,719 26 0 0 0 0 0 21.00 3.40 1.98 3.00 20 295,828 0 0 0 0 0 0 30.30 0.00 0.00 0.00 21 308,086 9 7 0 0 0 0 22.00 4.13 6.50 1.00 22 299,796 0 0 8 0 0 0 18.00 0.00 0.00 0.00 23 306,480 4 4 0 0 0 0 13.70 1.53 1.44 0.00 1350 R.Jovanovic, S.Voß 1 3 The evaluation is done based on the difference between the optimal solution and the solution acquired by a method ( OPT −X ). The columns “Best” represent the minimal difference, and “Average” is the average difference over ten independent runs Table 4 (continued) ID OPT Best Average GA F&F QPSO TPTEA DQPSO MFSS QPSO TPTEA DQPSO MFSS 24 300,342 0 0 0 0 0 0 32.00 1.33 0.00 0.00 25 302,571 11 0 11 0 0 0 24.00 5.60 8.75 7.00 26 301,339 17 10 17 0 0 0 21.70 8.33 9.79 7.00 27 306,454 24 24 32 0 0 0 45.00 0.00 5.64 2.00 28 302,828 14 14 0 0 0 0 19.30 7.30 4.30 4.00 29 299,910 6 6 0 0 6 4 24.70 8.20 7.81 5.00 Avg. 10.97 5.10 11.13 0.73 1.33 0.13 33.93 9.55 7.28 3.87 #worse 24 14 14 2 5 30 22 22 #equal 6 16 15 27 25 0 5 4 #better 0 0 1 1 0 0 3 4 1351 1 3 Matheuristic fixed set search applied tothemultidimensional… Table 5 Comparison of the state-of-the-art methods to MFSS on instances with 500 items and 10 constraints ID OPT Best Average GA F&F QPSO TPTEA DQPSO MFSS QPSO TPTEA DQPSO MFSS 0 117,821 95 87 77 20 42 12 87.50 84.83 66.18 27.00 1 119,249 110 68 72 49 43 47 100.50 111.53 69.26 65.00 2 119,215 56 21 0 56 0 4 68.50 106.73 52.39 15.00 3 118,829 27 45 54 0 16 16 81.50 35.07 51.64 19.00 4 116,530 96 59 28 74 21 21 80.50 124.83 69.17 47.00 5 119,504 50 62 102 21 34 0 112.50 62.20 68.43 37.00 6 119,827 78 63 0 52 0 17 43.00 87.30 44.24 46.00 7 118,344 56 35 35 21 24 11 61.50 85.73 78.70 30.00 8 117,815 36 34 94 14 34 34 105.00 109.03 51.76 40.00 9 119,251 126 68 0 55 39 20 50.50 89.10 84.46 45.00 10 217,377 59 59 69 26 12 0 87.50 63.33 50.97 27.00 11 219,077 55 41 0 18 14 0 27.50 54.30 49.46 17.00 12 217,847 75 50 50 0 0 50 75.00 60.27 86.37 51.00 13 216,868 66 25 0 0 25 0 42.00 31.67 43.95 8.00 14 213,873 64 62 78 59 30 14 90.00 92.73 55.92 20.00 15 215,086 73 65 0 0 24 1 32.50 36.43 51.32 27.00 16 217,940 44 60 72 14 9 9 87.00 55.20 55.64 20.00 17 219,990 41 21 41 6 6 6 70.50 42.63 24.93 11.00 18 214,382 50 36 0 19 0 27 18.00 54.57 44.86 33.00 19 220,899 66 50 72 12 34 13 84.50 34.57 51.90 32.00 20 304,387 43 43 43 0 0 0 57.50 22.53 32.99 26.00 21 302,379 47 34 38 0 21 0 38.00 14.53 32.96 20.00 22 302,417 63 9 0 1 9 1 30.50 18.87 17.90 6.00 23 300,784 41 41 0 0 0 0 20.50 25.20 38.54 36.00 1352 R.Jovanovic, S.Voß 1 3 The evaluation is done based on the difference between the optimal solution and the solution acquired by a method ( OPT −X ). The columns “Best” represent the minimal difference, and “Average” is the average difference over ten independent runs Table 5 (continued) ID OPT Best Average GA F&F QPSO TPTEA DQPSO MFSS QPSO TPTEA DQPSO MFSS 24 304,374 30 17 34 0 0 7 45.50 12.87 20.25 15.00 25 301,836 106 94 0 40 70 0 48.50 95.57 83.52 35.00 26 304,952 3 41 0 0 3 3 27.50 0.00 3.00 3.00 27 296,478 41 31 41 0 19 12 46.00 22.47 33.84 19.00 28 301,359 46 28 66 0 2 2 75.00 9.73 26.76 5.00 29 307,089 75 11 87 0 0 0 125.50 0.77 20.17 5.00 Avg. 60.60 45.33 38.43 18.57 17.70 10.90 64.00 54.82 48.72 26.23 #worse 29 28 18 13 14 27 24 28 #equal 1 2 5 7 10 0 0 1 #better 0 0 7 10 6 3 6 1 1359 1 3 Matheuristic fixed set search applied tothemultidimensional… robust in the sense that it has a good performance for a wide range of parameter values. Keep in mind that certain parameters of the MFSS are related to the execution time of the IPS and their optimal values are hardware-dependent. Our aim is to understand the impact of the MFSS parameters without emphasizing specific values. The initial step of the algorithm is generating the initial population of solutions (see Sarhani etal. (2023) for some general exposition on initial populations in metaheuristics). In practice, it is most important to generate at least n solutions that are used in the learning mechanism, consequently, Npop should be equal or greater than n. Since a random method is used for generating solutions, which eventually produces low-quality feasible solutions, there is no significant advantage in using a higher value of Npop than n. On the other hand, if a more advanced method is used for generating initial solutions, i.e., by incorporating some local search, the value of Npop should be higher since there is a potential of acquiring more high-quality solutions. This is due to the fact that the use of the IPS is computationally expensive, and it is preferable to only apply it to high-quality solutions. The parameters kmin and kmax are used to provide diversity in generating new solutions, through the randomization of the size of the set Skn . A small value of k Table 9 Comparison of the state-of-the-art methods to MFSS on instances with various numbers of items, instance types, and scenarios for the KPFS The underlined values for CPLEX are used for proven optimal values Type Items Scenario 3 Scenario 4 CPLEX MA MFSS CPLEX MA MFSS NC 300 1033.3 1027.7 1033.3 908.7 903.0 908.7 NC 500 1404.5 1386.8 1404.2 1178.7 1168.3 1178.7 NC 700 – 1676.0 1695.0 1428.3 1401.9 1427.2 NC 800 – 1813.1 1836.9 1475.4 1449.4 1474.4 NC 1000 – 1949.8 1987.0 1544.4 1513.2 1543.7 C 300 968.3 960.2 968.3 906.2 896.4 906.2 C 500 1453.8 1439.4 1456.2 1321.5 1308.1 1321.5 C 700 – 1859.0 1884.8 – 1726.4 1748.3 C 800 – 2068.7 2089.3 – 1879.3 1905.0 C 1000 – 2426.4 2449.2 – 2150.4 2178.3 FC 300 955.0 952.0 954.8 895.8 889.7 895.8 FC 500 1435.6 1423.9 1436.0 1323.4 1313.6 1324.6 FC 700 – 1843.9 1864.4 – 1759.9 1781.0 FC 800 – 2054.0 2072.1 – 1937.2 1957.2 FC 1000 – 2433.1 2453.2 – 2302.3 2328.4 Avg. 1687.60 1705.65 1506.61 1525.27 #Better 0 0 #Equal 0 0 #Worse 15 15 1360 R.Jovanovic, S.Voß 1 3 results in fixed sets with a higher level of randomness. If a smaller number of test solutions is considered, there is a higher number of elements e∈B with the same value of the O(e,Skn) ; consequently, a larger number of them will be randomly removed from  F . On the other hand, a higher value of k makes the generation of fixed sets more deterministic since there are less such elements, and the difference between Size and |  F| is lower. The value of the initial computational time tinit of the IPS is highly hardwaredependent and is found empirically. In general, it should be the lowest value that makes it highly probable for the IPS to improve the solutions in the initial population. In relation, StagMax is used to increase the computational time for the IPS and is effective for a very wide range of values. It has been observed that after a minimal value of MaxStag for which the solution space is effectively explored, higher values of MaxStag only increase the computational cost without providing additional benefits. In our initial test, we have observed that MaxStag =50 and MaxStag =20 are effective values for the used hardware and the MKP and KPFS, respectively. The parameters 𝛾 and 𝛿 related to the change in the size of the fixed set have the following effect. The portion of acquired proven optimal solutions 𝛿 that is considered to result in stagnation related to the size of the fixed set had the following effect. In the case, this value is too high, very rarely will the size of the fixed set be decreased. Consequently, when the allowed computational time is increased, there will be no change in the size of the neighborhood being explored, so it is unlikely that stagnation of the algorithm will stop. On the other hand, if the value of 𝛿 is too low, the size of the fixed set will be decreased too frequently, and the resulting subproblems will quickly become of a size too large for the IPS to be solved effectively. We have empirically observed that for the KPFS, a value of 𝛿=0.9 produces good results. The value of the parameter 𝛾 is used to decrease the size of the fixed sets being used in the MFSS. The idea is to gradually decrease the size of the fixed set avoiding prematurely generating subproblems that are too large for the IPS to effectively solve with the current quality of fixed sets and time limit. In the case of the KPFS, we have observed that the value 𝛾=1.25 produces good results, but we expect that the value of this method parameter is highly problem-dependent. The size of the subproblem being solved, Sizemax , has a high impact on the performance of the MFSS when both convergence speed and solution quality are considered. A graphical illustration of the effect of this parameter is shown in Fig.3 for one instance of the MKP but similar behavior is observed for the KPFS. In it, the convergence speed of the average solution quality of ten independent runs of the MFSS for different values of Sizemax is presented. From this figure, it can be observed that a higher value of Sizemax provides an increase in convergence speed and solution quality. In practice, this means that its value should be at most one for which the IPS can be effectively applied within a short computational time. It is important to point out that similar behavior can be observed for instances with a different number of items and constraints. The last parameter that is analyzed is the size of the number of the best solutions n that is considered when generating the base solution B and the set of test solutions Skn . The main idea of the MFSS is to make it possible to solve significantly larger instances than it is possible using the IP, and the effect of the 1361 1 3 Matheuristic fixed set search applied tothemultidimensional… parameter n is observed in this context. Because of this, the effect of this parameter is evaluated for the case when the number of items (|V|) in the problem instance is much larger than the number of items Sizemax for which the subproblem can be effectively solved. In Fig.4, the average convergence speed over ten independent runs of MFSS with Sizemax = 25 for a problem instance with 250 items and 10 constraints is presented. It is important to point out that similar behavior Fig. 3 Illustration of convergence speed for different values of SizeMax for the instance with 500 items, 30 constraints and ID =0 . The graphs represent the average distance to the best-known solution over ten runs at different time periods Fig. 4 Illustration of the convergence speed for different values of n for the instance with 250 items, 10 constraints and ID =0 . The MFSS solves subproblems with Sizemax = 25 items. The graphs represent the average distance to an optimal solution over ten runs at different time periods 1362 R.Jovanovic, S.Voß 1 3 can be observed for other instances of the MKP and for the KPFS. From Fig.4, it can be observed that for a smaller population of test solutions, parameter n, the initial convergence speed is much higher but the method can easily get trapped in a locally optimal solution. By increasing the value of n, the convergence speed is decreased, but the MFSS has a higher probability of escaping locally optimal solutions. In practice, a larger value of n results in a wider search of the solution space. Consequently, if a long execution time is available, it is possible to acquire higher quality solutions for larger values of n. It is important to mention once more that the performance of the MFSS is highly dependent on the used IPS. That is, to be specific, it depends on the size of problems that the IPS can effectively solve. It has been empirically observed that the MFSS is highly effective in solving problem instances 7-10 times larger than the IPS can be effectively applied to. On the other hand, standard metaheuristics can frequently be applied to much larger problem instances compared to the IPS. In practice, this means that above a certain problem size, it is more suitable to use metaheuristics than the MFSS. 5 Conclusions In this paper, two generalizations of the knapsack problem, the multidimensional knapsack problem (MKP) and the knapsack problem with forfeit sets (KPFS), have been solved using a population-based matheuristic. To be specific, the fixed set search (FSS) has been extended to a matheuristic setting. To achieve this, a new ground set of elements for the family of knapsack problems has been introduced that maximizes the amount of information that the fixed set provides. In addition, the method for generating fixed sets has been adapted to increase the diversity of the generated solutions. The main advantage of the proposed method, compared to existing ones for the MKP and the KPFS, is the simplicity of implementation in the sense of the adaptability of the method to different problems. That is, to a large extent, due to the use of the FSS learning mechanism and by avoiding the need for defining solution neighborhoods. The computational experiments have shown that the MFSS is highly competitive with state-of-the-art methods for the problems of interest. The proposed approach is robust in the sense that it is effective for a wide range of method parameters. It is important to point out that the MFSS does not exploit any specific properties of the MKP or the KPFS but only uses the respective IP model. This indicates the potential future application of the MFSS to other 0-1 problems, like the minimum vertex cover problem, the facility location problem, etc., without the need for large changes to the method. The practicality of the MFSS’s simple adaptation to complex problems is effectively illustrated through its use for optimizing the scheduling of electric buses in public transport (Jovanovic etal. 2023a). On the other hand, due to the simplicity of the approach, it is possible to improve its performance by hybridizing it with other heuristic/metaheuristic approaches or by exploiting some specific properties of the MKP or the KPFS. 1363 1 3 Matheuristic fixed set search applied tothemultidimensional… Funding Open Access funding provided by the Qatar National Library. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/ licenses/by/4.0/. References Al-Shihabi S, Ólafsson S (2010) A hybrid of nested partition, binary ant system, and linear programming for the multidimensional knapsack problem. Comput Oper Res 37(2):247–255 Angelelli E, Mansini R, Speranza MG (2010) Kernel search: a general heuristic for the multi-dimen- sional knapsack problem. Comput Oper Res 37(11):2017–2026 Arin A, Rabadi G (2016) Local search versus path relinking in metaheuristics: redesigning Meta-RaPS with application to the multidimensional knapsack problem. Appl Soft Comput 46:317–327 Basnet C (2018) Heuristics for the multiple knapsack problem with conflicts. Int J Oper Res 32(4):514–525 Boschetti MA, Maniezzo V (2022) Matheuristics: using mathematics for heuristic design. 4OR 20(2):173–208 Boussier S, Vasquez M, Vimont Y, Hanafi S, Michelon P (2010) A multi-level search strategy for the 0–1 multidimensional knapsack problem. Discret Appl Math 158(2):97–109 Capobianco G, D’Ambrosio C, Pavone L, Raiconi A, Vitale G, Sebastiano F (2022) A hybrid metaheuristic for the knapsack problem with forfeits. Soft Comput 26:749–762 Caserta M, Voß S (2019) The robust multiple-choice multidimensional knapsack problem. Omega 86:16–27. https:// doi. org/ 10. 1016/j. omega. 2018. 06. 014 Chen Y, Hao JK (2014) A “reduce and solve’’ approach for the multiple-choice multidimensional knapsack problem. Eur J Oper Res 239(2):313–322. https:// doi. org/ 10. 1016/j. ejor. 2014. 05. 025 Chu PC, Beasley JE (1998) A genetic algorithm for the multidimensional knapsack problem. J Heuristics 4:63–86 Coniglio S, Furini F, San Segundo P (2021) A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts. Eur J Oper Res 289(2):435–455 Dammeyer F, Voß S (1993) Dynamic tabu list management using the reverse elimination method. Ann Oper Res 41:29–46. https:// doi. org/ 10. 1007/ BF020 22561 Drexl A (1988) A simulated annealing approach to the multiconstraint zero-one knapsack problem. Computing 40(1):1–8 D’Ambrosio C, Laureana F, Raiconi A, Vitale G (2023) The knapsack problem with forfeit sets. Comput Oper Res 151(106):093 Feo TA, Resende MG (1995) Greedy randomized adaptive search procedures. J Global Optim 6(2):109–133 Fréville A (2004) The multidimensional 0–1 knapsack problem: an overview. Eur J Oper Res 155(1):1–21. https:// doi. org/ 10. 1016/ S0377- 2217(03) 00274-1 Galli L, Martello S, Rey C, Toth P (2023) Lagrangian matheuristics for the quadratic multiple knapsack problem. Discret Appl Math 335:36–51 García J, Lalla-Ruiz E, Voß S, Droguett E (2020) Enhancing a machine learning binarization framework by perturbation operators: analysis on the multidimensional knapsack problem. Int J Mach Learn Cybern 11:1951–1970. https:// doi. org/ 10. 1007/ s13042- 020- 01085-8 Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-complete- ness. W. H. Freeman, New York Gilmore P, Gomory RE (1966) The theory and computation of knapsack functions. Oper Res 14(6):1045–1074 1364 R.Jovanovic, S.Voß 1 3 Glover F, Kochenberger GA (1996) Critical event tabu search for multidimensional knapsack problems. In: Osman IH, Kelly JP (eds) Meta-heuristics: theory and applications. Kluwer, Boston, pp 407–427. https:// doi. org/ 10. 1007/ 978-1- 4613- 1361-8_ 25 Haddar B, Khemakhem M, Hanafi S, Wilbaut C (2016) A hybrid quantum particle swarm optimization for the multidimensional knapsack problem. Eng Appl Artif Intell 55:1–13 Hanafi S, Freville A (1998) An efficient tabu search approach for the 0–1 multidimensional knapsack problem. Eur J Oper Res 106(2–3):659–675 Jovanovic R, Voß S (2019) Fixed set search applied to the minimum weighted vertex cover problem. In: International symposium on experimental algorithms. Springer, pp 490–504 Jovanovic R, Voss S (2020) The fixed set search applied to the power dominating set problem. Expert Syst 37(6):e12559 Jovanovic R, Voß S (2021) Fixed set search application for minimizing the makespan on unrelated parallel machines with sequence-dependent setup times. Appl Soft Comput 110(107):521 Jovanovic R, Tuba M, Voß S (2019) Fixed set search applied to the traveling salesman problem. In: International workshop on hybrid metaheuristics. Springer, pp 63–77 Jovanovic R, Sanfilippo AP, Voß S (2022) Fixed set search applied to the multi-objective minimum weighted vertex cover problem. J Heuristics 28:481–508 Jovanovic R, Bayhan S, Voß S (2023a) Matheuristic fixed set search applied to electric bus fleet scheduling. In: Sellmann M, Tierney K (eds) Learning and intelligent optimization. Springer, Cham, pp 393–407 Jovanovic R, Sanfilippo AP, Voß S (2023b) Fixed set search applied to the clique partitioning problem. Eur J Oper Res 309(1):65–81 Khemakhem M, Haddar B, Chebil K, Hanafi S (2012) A filter-and-fan metaheuristic for the 0–1 multidimensional knapsack problem. Int J Appl Metaheur Comput (IJAMC) 3(4):43–63 Lai X, Hao JK, Glover F, Lü Z (2018) A two-phase tabu-evolutionary algorithm for the 0–1 multidimensional knapsack problem. Inf Sci 436–437:282–301. https:// doi. org/ 10. 1016/j. ins. 2018. 01. 026 Lai X, Hao JK, Yue D (2019) Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem. Eur J Oper Res 274(1):35–48. https:// doi. org/ 10. 1016/j. ejor. 2018. 10. 001 Lai X, Hao JK, Fu ZH, Yue D (2020) Diversity-preserving quantum particle swarm optimization for the multidimensional knapsack problem. Expert Syst Appl 149(113):310. https:// doi. org/ 10. 1016/j. eswa. 2020. 113310 Li J, Lan Y, Chen F, Han X, Blazewicz J (2021) A fast algorithm for knapsack problem with conflict graph. Asia-Pacific J Oper Res 38(06):2150010 Lozano-Osorio I, Sánchez-Oro J, Martínez-Gavara A, López-Sánchez AD, Duarte A (2023) An efficient fixed set search for the covering location with interconnected facilities problem. In: Metaheuristics: 14th international conference. Springer, pp 485–490 Maniezzo V, Boschetti MA, Stützle T (2021) Kernel search. In: Matheuristics. Springer, pp 189–197 Mancini S, Ciavotta M, Meloni C (2021) The multiple multidimensional knapsack with family-split penalties. Eur J Oper Res 289(3):987–998. https:// doi. org/ 10. 1016/j. ejor. 2019. 07. 052 Mansini R, Speranza MG (2012) Coral: an exact algorithm for the multidimensional knapsack problem. Informs J Comput 24(3):399–415 Mingo López LF, Gómez Blas N, Arteta Albert A (2018) Multidimensional knapsack problem optimization using a binary particle swarm model with genetic operations. Soft Comput 22:2567–2582 PassMark (2022) CPU benchmark. www.cpubenchmark.net, last visited 2022-01-30 Pferschy U, Schauer J (2009) The knapsack problem with conflict graphs. J Graph Algorithms Appl 13(2):233–249 Rezoug A, Bader-El-Den M, Boughaci D (2018) Guided genetic algorithm for the multidimensional knapsack problem. Memet Comput 10:29–42 Rosing K, ReVelle C (1997) Heuristic concentration: two stage solution construction. Eur J Oper Res 97(1):75–86 Sarhani M, Voß S, Jovanovic R (2023) Initialization of metaheuristics: comprehensive review, critical analysis, and research directions. Int Trans Oper Res 30:3361–3397. https:// doi. org/ 10. 1111/ itor. 13237 Shih W (1979) A branch and bound method for the multiconstraint zero-one knapsack problem. J Oper Res Soc 30(4):369–378 1365 1 3 Matheuristic fixed set search applied tothemultidimensional… Sondergeld L, Voß S (1999) Cooperative intelligent search using adaptive memory techniques. In: Voß S, Martello S, Osman I, Roucairol C (eds) Meta-heuristics: advances and trends in local search paradigms for optimization. Kluwer, Boston, pp 297–312 Taillard E, Voß S (2002) POPMUSIC—a partial optimization metaheuristic under special intensification conditions. In: Ribeiro C, Hansen P (eds) Essays and surveys in metaheuristics. Kluwer, Boston, pp 613–629 Vasquez M, Vimont Y (2005) Improved results on the 0–1 multidimensional knapsack problem. Eur J Oper Res 165(1):70–81 Vimont Y, Boussier S, Vasquez M (2008) Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem. J Comb Optim 15(2):165–178 Voß S, Gutenschwager K (1998) A chunking based genetic algorithm for the Steiner tree problem in graphs. In: Pardalos P, Du DZ (eds) Network design: connectivity and facilities location, DIMACS series in discrete mathematics and theoretical computer science, vol 40. Princeton, AMS, pp 335–355 Woodruff D (1998) Proposals for chunking and tabu search. Eur J Oper Res 106:585–598 Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.