Explore the vast range of titles available.

In this paper, we present a solution method for the multidimensional knapsack problem (MKP) and the knapsack problem with forfeit sets (KPFS) using a population-based 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-performing 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.

In this paper, a novel modified whale optimization algorithm based on Tent chaos map and tournament selection strategy (MWOA) was presented. The aim of the improved algorithm is to reduce the possibility of the standard whale algorithm falling into local optimal. During the initialization of the population, in order to increase population diversity and randomness, MWOA cites the Tent chaos map. In the optimization process, in order to improve the development ability of the standard algorithm, the tournament selection strategy was employed to improve the algorithm accuracy. Numerical simulation and example calculation results show that the improved algorithm is superior to the standard WOA algorithm. The improved method provides a new method for truss structure optimization.

A number of scientific fields rely on placing permanent magnets in order to produce a desired magnetic field. We have shown in recent work that the placement process can be formulated as sparse regression. However, binary, grid-aligned solutions are desired for realistic engineering designs. We now show that the binary permanent magnet problem can be formulated as a quadratic program with quadratic equality constraints, the binary, grid-aligned problem is equivalent to the quadratic knapsack problem with multiple knapsack constraints, and the single-orientation-only problem is equivalent to the unconstrained quadratic binary problem. We then provide a set of simple greedy algorithms for solving variants of permanent magnet optimization, and demonstrate their capabilities by designing magnets for stellarator plasmas. The algorithms can a-priori produce sparse, grid-aligned, binary solutions. Despite its simple design and greedy nature, we provide an algorithm that compares with or even outperforms the state-of-the-art algorithms while being substantially faster, more flexible, and easier to use.

For the classic 0–1 knapsack problem, there can be pairs of items that are in conflict. In other words, either at most one item can be inserted into the knapsack (hard conflict constraint) from the conflict pair or there may be a penalty (soft conflict constraint) if both items in a conflict pair are inserted into the knapsack. The benefit of having two or more knapsacks when the conflict constraints are hard was recently demonstrated in the literature. By using 120 knapsack problem with forfeits (KPF) (soft constraints) from the literature and 40 new KPF instances with the Gurobi software, the purpose of this paper is simply to quantify the benefit of using two or more knapsacks for the KPF while the total capacity of the knapsacks is fixed. It will be shown that for the base case 40 KPF instances, the average objective function value improves by 37% when two knapsacks are used instead of one. More importantly, it is shown that increasing either knapsack capacity (64% improvement) or the number of conflict constraints (47% improvement) or both (49.7% improvement) results in even larger improvements in the objective function value. In contrast, going from two to three knapsacks, the improvement over all 160 KPF instances is only 12% and drops dramatically beyond three knapsacks. Finally, it will be shown that based on these 160 KPF instances, the KPF solutions with four knapsacks are essentially the same as the solutions with one knapsack with no forfeit constraints. This is the first time that the multiple knapsack problem with forfeits (MKPF) is discussed in the literature.

Weighted superposition attraction algorithm (WSA) is a new generation population-based metaheuristic algorithm, which has been recently proposed to solve various optimization problems. Inspired by the superposition of particles principle in physics, individuals of WSA generate a superposition, which leads other agents (solution vectors). Alternatively, based on the quality of the generated superposition, individuals occasionally tend to perform random walks. Although WSA is proven to be successful in both real-valued and some dynamic optimization problems, the performance of this new algorithm needs to be examined also in stationary binary optimization problems, which is the main motivation of the present study. Accordingly, WSA is first designed for stationary binary spaces. In this modification, WSA does not require any transfer functions to convert real numbers to binary, whereas such functions are commonly used in numerous approximation algorithms. Moreover, a step sizing function, which encourages population diversity at earlier iterations while intensifying the search towards the end, is adopted in the proposed WSA. Thus, premature convergence and local optima problems are attempted to be avoided. In this context, the contribution of the present study is twofold: first, WSA is modified for stationary binary optimization problems, secondarily, it is further enhanced by the proposed step sizing function. The performance of the modified WSA is examined by using three well-known binary optimization problems, including uncapacitated facility location problem, 0–1 knapsack problem and a natural extension of it, the set union knapsack problem. As demonstrated by the comprehensive experimental study, results point out the efficiency of the proposed WSA modification in binary optimization problems.

We consider the bilevel quadratic knapsack problem (BQKP) that model settings where a leader appropriates a budget for a follower, who solves a quadratic 0–1 knapsack problem. BQKP generalizes the bilevel knapsack problem introduced by Dempe and Richter (Cent Eur J Oper Res 8(2):93–107, 2000), where the follower solves a linear 0–1 knapsack problem. We present an exact-solution approach for BQKP based on extensions of dynamic programs for QKP bounds and the branch-and-backtrack algorithm. We compare our approach against a two-phase method computed using an optimization solver in both phases: it first computes the follower’s value function for all feasible leader’s decisions, and then solves a single-level, value-function reformulation of BQKP as a mixed-integer quadratically constrained program. Our computational experiments show that our approach for solving BQKP outperforms the two-phase method computed by a commercial state-of-the-art optimization software package.

0–1 knapsack problem (KP01) is one of the classic variants of knapsack problems in which the aim is to select the items with the total profit to be in the knapsack. In contrast, the constraint of the maximum capacity of the knapsack is satisfied. KP01 has many applications in real-world problems such as resource distribution, portfolio optimization, etc. The purpose of this work is to gather the latest SA-based solvers for KP01 together and compare their performance with the state-of-the-art meta-heuristics in the literature to find the most efficient one(s). This paper not only studies the introduced and non-introduced single-solution SA-based algorithms for KP01 but also proposes a new population-based SA (PSA) for KP01 and compares it with the existing methods. Computational results show that the proposed PSA is the most efficient optimization algorithm for KP01 among all SA-based solvers. Also, PSA’s exploration and exploitation are stronger than the other SA-based algorithms since it generates several initial solutions instead of one. Moreover, it finds the neighbor solutions based on the greedy repair and improvement mechanism and uses both mutation and crossover operators to explore and exploit the solution space. Suffice to say that the next version of SA algorithms for KP01 can be enhanced by designing a population-based version of them and choosing the greedy-based approaches for the initial solution phase and local search policy.

In this paper, we address the difficulty of solving large-scale multi-dimensional knapsack instances (MKP), presenting a novel deep reinforcement learning (DRL) framework. In this DRL framework, we train different agents compatible with a discrete action space for sequential decision-making while still satisfying any resource constraint of the MKP. This novel framework incorporates the decision variable values in the 2D DRL where the agent is responsible for assigning a value of 1 or 0 to each of the variables. To the best of our knowledge, this is the first DRL model of its kind in which a 2D environment is formulated, and an element of the DRL solution matrix represents an item of the MKP. Our framework is configured to solve MKP instances of different dimensions and distributions. We propose a K-means approach to obtain an initial feasible solution that is used to train the DRL agent. We train four different agents in our framework and present the results comparing each of them with the CPLEX commercial solver. The results show that our agents can learn and generalize over instances with different sizes and distributions. Our DRL framework shows that it can solve medium-sized instances at least 45 times faster in CPU solution time and at least 10 times faster for large instances, with a maximum solution gap of 0.28% compared to the performance of CPLEX. Furthermore, at least 95% of the items are predicted in line with the CPLEX solution. Computations with DRL also provide a better optimality gap with respect to state-of-the-art approaches.

Whale optimization algorithm (WOA) is a recently proposed meta-heuristic algorithm which imitates the hunting behavior of humpback whales. Due to its characteristic advantages, it has found its place in the mature population-based methods in many scientific and engineering fields. Because WOA was proposed for continuous optimization, it cannot be directly used to solve discrete optimization problems. For this purpose, we first give a new V -shaped function by drawing lesson from the existing discretization methods, which transfer a real vector to an integer vector. On this basis, we propose a novel discrete whale optimization algorithm (DWOA). DWOA uses the new proposed V -shaped function to generate an integer vector, and it can be used to solve discrete optimization problems with solution space 0,1,…,m1×0,1,…,m2×… ×0,1,…,mn. To verify effectiveness of DWOA for the 0-1 knapsack problem and the discount 0-1 knapsack problem, we solve their benchmark instances from published literature and compare with the state-of-the-art algorithms. The comparison results show that the DWOA has more superiority than existing algorithms for the two kinds of knapsack problems.

Benchmark instances for the unbounded knapsack problem are typically generated according to specific criteria within a given constant range R, and these instances can be referred to as the unbounded knapsack problem with bounded coefficients (UKPB). In order to increase the difficulty of solving these instances, the knapsack capacity C is usually set to a very large value. While current efficient algorithms primarily center on the Fast Fourier Transform (FFT) and (min,+)-convolution method, there is a simpler method worth considering. In this paper, based on the basic Unbounded-DP algorithm, we utilize a recent branch and bound (B&B) result and basic theory of linear Diophantine equation, and propose an improved Unbounded-DP algorithm with time complexity of O(R4) and space complexity of O(R3). Additionally, the algorithm can also solve the All-capacities unbounded knapsack problem within the complexity O(R4+C). In particular, the proof techniques required by the algorithm are primarily covered in the first-year mathematics curriculum, which is convenient for subsequent researchers to grasp.