An effective GRASP and tabu search for the 0–1 quadratic knapsack problem

As a generalization of the classical 0-1 knapsack problem, the 0-1 Quadratic Knapsack Problem (QKP) that maximizes a quadratic objective function subject to a linear capacity constraint is NP-hard in strong sense. In this paper, we propose a memory based Greedy Randomized Adaptive Search Procedures (GRASP) and a tabu search algorithm to find near optimal solution for the QKP. Computational experiments on benchmarks and on randomly generated instances demonstrate the effectiveness and the efficiency of the proposed algorithms, which outperforms the current state-of-the-art heuristic Mini-Swarm in computational time and in the probability to achieve optimal solutions. Numerical results on large-sized instances with up to 2000 binary variables have also been reported.     

An exact approach for the 0–1 knapsack problem with setups

We consider the 0–1 Knapsack Problem with Setups. We propose an exact approach which handles the structure of the ILP formulation of the problem. It relies on partitioning the variables set into two levels and exploiting this partitioning. The proposed approach favorably compares to the algorithms in literature and to solver CPLEX 12.5 applied to the ILP formulation. It turns out to be very effective and capable of solving to optimality, within limited CPU time, all instances with up to 100, 000 variables.     

Chemical reaction optimization with greedy strategy for the 0–1 knapsack problem

The 0–1 knapsack problem (KP01) is a well-known combinatorial optimization problem. It is an NP-hard problem which plays important roles in computing theory and in many real life applications. Chemical reaction optimization (CRO) is a new optimization framework, inspired by the nature of chemical reactions. CRO has demonstrated excellent performance in solving many engineering problems such as the quadratic assignment problem, neural network training, multimodal continuous problems, etc. This paper proposes a new chemical reaction optimization with greedy strategy algorithm (CROG) to solve KP01. The paper also explains the operator design and parameter turning methods for CROG. A new repair function integrating a greedy strategy and random selection is used to repair the infeasible solutions. The experimental results have proven the superior performance of CROG compared to genetic algorithm (GA), ant colony optimization (ACO) and quantum-inspired evolutionary algorithm (QEA).     

A quantum particle swarm optimization for the 0–1 generalized knapsack sharing problem

This study proposes a new hybrid heuristic approach that combines the quantum particle swarm optimization (QPSO) technique with a local search phase to solve the binary generalized knapsack sharing problem (GKSP). The approach also incorporates a heuristic repair operator that uses problem-specific knowledge instead of the penalty function technique commonly used for constrained problems. This study is the first to report on the application of the QPSO method to the GKSP. The efficiency of our proposed approach was tested on a large set of instances, and the results were compared to those produced by the commercial mixed integer programming solver CPLEX 12.5 of IBM-ILOG. The Experimental results demonstrated the good performance of the QPSO in solving the GKSP.     

Analysis of a Multiobjective Evolutionary Algorithm on the 0–1 knapsack problem

Multiobjective Evolutionary Algorithms (MOEAs) are increasingly being used for effectively solving many real-world problems, and many empirical results are available. However, theoretical analysis is limited to a few simple toy functions. In this work, we select the well-known knapsack problem for the analysis. The multiobjective knapsack problem in its general form is NP-complete. Moreover, the size of the set of Pareto-optimal solutions can grow exponentially with the number of items in the knapsack. Thus, we formalize a (1+ε)$(1+\epsilon )$-approximate set of the knapsack problem and attempt to present a rigorous running time analysis of a MOEA to obtain the formalized set. The algorithm used in the paper is based on a restricted mating pool with a separate archive to store the remaining population; we call the algorithm a Restricted Evolutionary Multiobjective Optimizer (REMO). We also analyze the running time of REMO on a special bi-objective linear function, known as LOTZ (Leading Ones : Trailing Zeros), whose Pareto set is shown to be a subset of the knapsack. An extension of the analysis to the Simple Evolutionary Multiobjective Optimizer (SEMO) is also presented. A strategy based on partitioning of the decision space into fitness layers is used for the analysis.     

Solving 0–1 knapsack problem by a novel binary monarch butterfly optimization

Neural Computing and Applications - This paper presents a novel binary monarch butterfly optimization (BMBO) method, intended for addressing the 0–1 knapsack problem (0–1 KP). Two...     

A cost-optimal parallel algorithm for the 0–1 knapsack problem and its performance on multicore CPU and GPU implementations

The 0–1 knapsack problem has been extensively studied in the past years due to its immediate applications in industry and financial management, such as cargo loading, stock cutting, and budget control. Many algorithms have been proposed to solve this problem, most of which are heuristic, as the problem is well-known to be NP-hard. Only a few optimal algorithms have been designed to solve this problem but with high time complexity. This paper proposes the cost-optimal parallel algorithm (COPA) on an EREW PRAM model with shared memory to solve this problem. COPA is scalable and yields optimal solutions consuming less computational time. Furthermore, this paper implements COPA on two scenarios – multicore CPU based architectures using Open MP and GPU based configurations using CUDA. A series of experiments are conducted to examine the performance of COPA under two different test platforms. The experimental results show that COPA could reduce a significant amount of execution time. Our approach achieves the speedups of up to 10.26 on multicore CPU implementations and 17.53 on GPU implementations when the sequential dynamic programming algorithm for KP01 is considered as a baseline. Importantly, GPU implementations outstand themselves in the experimental results.     

Heuristic and exact algorithms for the max–min optimization of the multi-scenario knapsack problem

We are concerned with a variation of the standard 0–1 knapsack problem, where the values of items differ under possible S scenarios. By applying the ‘pegging test’ the ordinary knapsack problem can be reduced, often significantly, in size; but this is not directly applicable to our problem. We introduce a kind of surrogate relaxation to derive upper and lower bounds quickly, and show that, with this preprocessing, the similar pegging test can be applied to our problem. The reduced problem can be solved to optimality by the branch-and-bound algorithm. Here, we make use of the surrogate variables to evaluate the upper bound at each branch-and-bound node very quickly by solving a continuous knapsack problem. Through numerical experiments we show that the developed method finds upper and lower bounds of very high accuracy in a few seconds, and solves larger instances to optimality faster than the previously published algorithms.     

A multi-dimensional shooting algorithm for the two-facility location–allocation problem with dense demand

We develop an efficient allocation-based solution framework for a class of two-facility location–allocation problems with dense demand data. By formulating the problem as a multi-dimensional boundary value problem, we show that previous results for the discrete demand case can be extended to problems with highly dense demand data. Further, this approach can be generalized to non-convex allocation decisions. This formulation is illustrated for the Euclidean metric case by representing the affine bisector with two points. A specialized multi-dimensional shooting algorithm is presented and illustrated on an example. Comparisons with two alternative methods through a computational study confirm the efficiency of the proposed methodology.     

Fast neighborhood search for the single machine earliness–tardiness scheduling problem

This paper addresses the one machine scheduling problem in which n jobs have distinct due dates with earliness and tardiness costs. Fast neighborhoods are proposed for the problem. They are based on a block representation of the schedule. A timing operator is presented as well as swap and extract-and-reinsert neighborhoods. They are used in an iterated local search framework. Two types of perturbations are developed based, respectively, on random swaps and earliness and tardiness costs. Computational results show that very good solutions for instances with significantly more than 100 jobs can be derived in a few seconds.     

Hardware accelerator for solving 0–1 knapsack problems using binary harmony search

The 0–1 knapsack problem (KP) is a well-known intractable optimization problem with wide range of applications. Harmony Search (HS) is one of the most popular metaheuristic algorithms to successfully solve 0–1 KPs. Nevertheless, metaheuristic algorithms are generally compute intensive and slow when implemented in software. In this paper, we present an FPGA-based pipelined hardware accelerator to reduce computation time for solving large dimension 0–1 KPs using Binary Harmony Search algorithm. The proposed architecture exploits the intrinsic parallelism of population based metaheuristic algorithm and the flexibility and parallel processing capabilities of FPGAs to perform the computation concurrently thus enhancing performance. To validate the efficiency of the proposed hardware accelerator, experiments were conducted using a large number of 0–1 KPs. Comparative analysis on experimental results reveals that the proposed approach offers promising speedups of 51× – 111× as compared with a software implementation and 2× – 5× as compared with a hardware implementation of Binary Particle Swarm Optimization algorithm.     

Discrete approximation heuristics for the capacitated continuous location–allocation problem with probabilistic customer locations

The capacitated continuous location–allocation problem, also called capacitated multisource Weber problem (CMWP), is concerned with locating m facilities in the Euclidean plane, and allocating their capacity to n customers at minimum total cost. The deterministic version of the problem, which assumes that customer locations and demands are known with certainty, is a nonconvex optimization problem. In this work, we focus on a probabilistic extension referred to as the probabilistic CMWP (PCMWP), and consider the situation in which customer locations are randomly distributed according to a bivariate probability distribution. We first formulate the discrete approximation of the problem as a mixed-integer linear programming model in which facilities can be located on a set of candidate points. Then we present three heuristics to solve the problem. Since optimal solutions cannot be found, we assess the performance of the heuristics using the results obtained by an alternate location–allocation heuristic that is originally developed for the deterministic version of the problem and tailored by us for the PCMWP. The new heuristics depend on the evaluation of the expected distances between facilities and customers, which is possible only for a few number of distance function and probability distribution combinations. We therefore propose approximation methods which make the heuristics applicable for any distance function and probability distribution of customer coordinates.     

An iterated “hyperplane exploration” approach for the quadratic knapsack problem

The quadratic knapsack problem (QKP) is a well-known combinatorial optimization problem with numerous applications. Given its NP-hard nature, finding optimal solutions or even high quality suboptimal solutions to QKP in the general case is a highly challenging task. In this paper, we propose an iterated “hyperplane exploration” approach (IHEA) to solve QKP approximately. Instead of considering the whole solution space, the proposed approach adopts the idea of searching over a set of hyperplanes defined by a cardinality constraint to delimit the search to promising areas of the solution space. To explore these hyperplanes efficiently, IHEA employs a variable fixing strategy to reduce each hyperplane-constrained sub-problem and then applies a dedicated tabu search procedure to locate high quality solutions within the reduced solution space. Extensive experimental studies over three sets of 220 QKP instances indicate that IHEA competes very favorably with the state-of-the-art algorithms both in terms of solution quality and computing efficiency. We provide additional information to gain insight into the key components of the proposed approach.     

A capital budgeting problem for preventing workplace mobbing by using analytic hierarchy process and fuzzy 0–1 bidimensional knapsack model

In this paper, a capital budgeting problem for preventive measures of workplace mobbing based on fuzzy 0–1 bidimensional knapsack model with non-financial and financial budget limits is proposed. The weights to be used as the objective function coefficients of the model are obtained from analytic hierarchy process (AHP) methodology that incorporates possible causes of workplace mobbing on criteria level, and possible preventive measures on alternatives level of AHP hierarchy. The quantification of non-financial and financial budgets as well as non-financial and financial costs is developed based on their relative weights. In deterministic model, the relative weights are directly used, whereas in fuzzy model, they are quantified. The defuzzification of the fuzzy model is proposed to be made by using t-norm and t-conorm fuzzy relations which are expected to give the most optimistic, and the most pessimistic results, respectively. The results of the hypothetical example verify the expectations.     

A simple and effective evolutionary algorithm for the capacitated location–routing problem

This paper proposes a hybrid genetic algorithm (GA) to solve the capacitated location–routing problem. The proposed algorithm follows the standard GA framework using local search procedures in the mutation phase. Computational evaluation was carried out on three sets of benchmark instances from the literature. Results show that, although relatively simple, the proposed algorithm is effective, providing competitive results for benchmark instances within reasonable computing time.     

An improved tau method for the multi-dimensional fractional Rayleigh–Stokes problem for a heated generalized second grade fluid

We develop efficient algorithms based on the Legendre-tau approximation for one- and two-dimensional fractional Rayleigh–Stokes problems for a generalized second-grade fluid. The time fractional derivative is described in the Riemann–Liouville sense. Discussions on the $L^2$-convergence of the proposed method are presented. Numerical results for one- and two-dimensional examples with smooth and nonsmooth solutions are provided to verify the validity of the theoretical analysis, and to illustrate the efficiency of the proposed algorithms.     

A virtual pegging approach to the max–min optimization of the bi-criteria knapsack problem

We are concerned with a variation of the knapsack problem, the bi-objective max–min knapsack problem (BKP), where the values of items differ under two possible scenarios. We have given a heuristic algorithm and an exact algorithm to solve this problem. In particular, we introduce a surrogate relaxation to derive upper and lower bounds very quickly, and apply the pegging test to reduce the size of BKP. We also exploit this relaxation to obtain an upper bound in the branch-and-bound algorithm to solve the reduced problem. To further reduce the problem size, we propose a ‘virtual pegging’ algorithm and solve BKP to optimality. As a result, for problems with up to 16,000 items, we obtain a very accurate approximate solution in less than a few seconds. Except for some instances, exact solutions can also be obtained in less than a few minutes on ordinary computers. However, the proposed algorithm is less effective for strongly correlated instances.     

Improving problem reduction for 0–1 Multidimensional Knapsack Problems with valid inequalities

This paper investigates the problem reduction heuristic for the Multidimensional Knapsack Problem (MKP). The MKP formulation is first strengthened by the Global Lifted Cover Inequalities (GLCI) using the cutting plane approach. The dynamic core problem heuristic is then applied to find good solutions. The GLCI is described in the general lifting framework and several variants are introduced. A Two-level Core problem Heuristic is also proposed to tackle large instances. Computational experiments were carried out on classic benchmark problems to demonstrate the effectiveness of this new method.     

Computational performance of basic state reduction based dynamic programming algorithms for bi-objective 0–1 knapsack problems

This paper studies a group of basic state reduction based dynamic programming (DP) algorithms for the multi-objective 0–1 knapsack problem (MKP), which are related to the backward reduced-state DP space (BRDS) and forward reduced-state DP space (FRDS). The BRDS is widely ignored in the literature because it imposes disadvantage for the single objective knapsack problem (KP) in terms of memory requirements. The FRDS based DP algorithm in a general sense is related to state dominance checking, which can be time consuming for the MKP while it can be done efficiently for the KP. Consequently, no algorithm purely based on the FRDS with state dominance checking has ever been developed for the MKP. In this paper, we attempt to get some insights into the state reduction techniques efficient to the MKP. We first propose an FRDS based algorithm with a local state dominance checking for the MKP. Then we evaluate the relative advantage of the BRDS and FRDS based algorithms by analyzing their computational time and memory requirements for the MKP. Finally different combinations of the BRDS and FRDS based algorithms are developed on this basis. Numerical experiments based on the bi-objective KP instances are conducted to compare systematically between these algorithms and the recently developed BRDS based DP algorithm as well as the existing FRDS based DP algorithm without state dominance checking.     

Global optima for the Zhou–Rozvany problem

We consider the minimum compliance topology design problem with a volume constraint and discrete design variables. In particular, our interest is to provide global optimal designs to a challenging benchmark example proposed by Zhou and Rozvany. Global optimality is achieved by an implementation of a local branching method in which the subproblems are solved by a special purpose nonlinear branch-and-cut algorithm. The convergence rate of the branch-and-cut method is improved by strengthening the problem formulation with valid linear inequalities and variable fixing techniques. With the proposed algorithms, we find global optimal designs for several values on the available volume. These designs can be used to validate other methods and heuristics for the considered class of problems.