Fast,effective heuristics for the 0–1 multi-dimensional knapsack problem

The objective of the multi-dimensional knapsack problem (MKP) is to find a subset of items with maximum value that satisfies a number of knapsack constraints. Solution methods for MKP, both heuristic and exact, have been researched for several decades. This paper introduces several fast and effective heuristics for MKP that are based on solving the LP relaxation of the problem. Improving procedures are proposed to strengthen the results of these heuristics. Additionally, the heuristics are run with appropriate deterministic or randomly generated constraints imposed on the linear relaxation that allow generating a number of good solutions. All algorithms are tested experimentally on a widely used set of benchmark problem instances to show that they compare favourably with the best-performing heuristics available in the literature.     

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.     

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.     

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.     

A computational study of parametric tabu search for 0–1 mixed integer programs

We present a computational study of parametric tabu search for solving 0–1 mixed integer programming (MIP) problems, a generic heuristic for general MIP problems proposed by Glover [Glover F. Parametric tabu-search for mixed integer programs. Computers and Operations Research 2006; 33: 2449–94.]. This approach solves a series of linear programming problems by incorporating branching inequalities as weighted terms in the objective function. New strategies are proposed for uncovering feasible and high-quality solutions and extensive computational tests are performed on instances from the literature.     

Interactive fuzzy stochastic multi-level 0–1 programming using tabu search and probability maximization

In this paper, we consider interactive fuzzy programming for multi-level 0–1 programming problems involving random variable coefficients both in objective functions and constraints. Following the probability maximization model together with the concept of chance constraints, the formulated stochastic multi-level 0–1 programming problems are transformed into deterministic ones. Taking into account vagueness of judgments of the decision makers, we present interactive fuzzy programming. In the proposed interactive method, after determining the fuzzy goals of the decision makers at all levels, a satisfactory solution is derived efficiently by updating satisfactory levels of the decision makers with considerations of overall satisfactory balance among all levels. For solving the transformed deterministic problems efficiently, we also introduce novel tabu search for general 0–1 programming problems. A numerical example for a three-level 0–1 programming problem is provided to illustrate the proposed method.     

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.     

Block approach—tabu search algorithm for single machine total weighted tardiness problem

Problem of scheduling on a single machine to minimize total weighted tardiness of jobs can be described as follows: there are n jobs to be processed, each job has an integer processing time, a weight and a due date. The objective is to minimize the total weighted tardiness of jobs. The problem belongs to the class of NP-hard problems. Some new properties of the problem associated with the blocks have been presented and discussed. These properties allow us to propose a new fast local search procedure based on a tabu search approach with a specific neighborhood which employs blocks of jobs and a compound moves technique. A compound move consists in performing several moves simultaneously in a single iteration of algorithm and allows us to accelerate the convergence to good solutions. In the algorithm, we use an idea which decreases the complexity for the search of neighborhood from O(n³) to O(n²). Additionally, the neighborhood is reduced by using some elimination criteria. The method presented in this paper is deterministic one and has not any random element, as distinct from other effective but non-deterministic methods proposed for this problem, such as tabu search of Crauwels, H. A. J., Potts, C. N., & Van Wassenhove, L. N. (1998). Local search heuristics for the single machine total weighted tardiness Scheduling Problem. INFORMS Journal on Computing, 10(3), 341–350, iterated dynasearch of Congram, R. K., Potts C. N., & Van de Velde, S. L. (2002). An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem. INFORMS Journal on Computing, 14(1), 52–67 and enhanced dynasearch of Grosso, A., Della Croce, F., & Tadei, R. (2004). An enhanced dynasearch neighborhood for single-machine total weighted tardiness scheduling problem. Operations Research Letters, 32, 68–72. Computational experiments on the benchmark instances from OR-Library (http://people.brunel.ac.uk/mastjjb/jeb/info.html) are presented and compared with the results yielded by the best algorithms discussed in the literature. These results show that the algorithm proposed allows us to obtain the best known results for the benchmarks in a short time. The presented properties and ideas can be applied in any local search procedures.     

A tabu search heuristic for a sequence-dependent and time-dependent scheduling problem on a single machine

This paper introduces a tabu search heuristic for a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. The problem consists in scheduling a set of dependent jobs, where the transition between two jobs comprises an unrestricted setup that can be performed at any time, and a restricted setup that must be performed outside of a given time interval which repeats daily in the same position. The setup time between two jobs is thus a function of the completion time of the first job. The tabu search heuristic relies on shift and swap moves, and a surrogate objective function is used to speed-up the neighborhood evaluation. Computational experiments show that the proposed heuristic consistently finds better solutions in less computation time than a recent branch-and-cut algorithm. Furthermore, on instances where the branch-and-cut algorithm cannot find the optimal solution, the heuristic always identifies a better solution.     

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 reactive GRASP and path relinking for a combined production–distribution problem

An NP-hard production–distribution problem for one product over a multi-period horizon is investigated. The aim is to minimize total cost taking production setups, inventory levels and distribution into account. An integer linear model is proposed as a compact problem specification but it cannot be solved to optimality for large instances. Instead of using a classical two-phase approach (production planning and then route construction for each day), metaheuristics that simultaneously tackle production and routing decisions are developed: a GRASP (greedy randomized adaptive search procedure) and two improved versions using either a reactive mechanism or a path-relinking process. These algorithms are evaluated on 90 randomly generated instances with 50, 100 and 200 customers and 20 periods. The results confirm the interest of integrating production and distribution decisions, compared to classical two-phase methods. Moreover, reaction and path-relinking give better results than the GRASP alone.     

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.     

Tabu search and lower bounds for a combined production–transportation problem

In this paper we consider a combined production–transportation problem, where n jobs have to be processed on a single machine at a production site before they are delivered to a customer. At the production stage, for each job a release date is given; at the transportation stage, job delivery should be completed not later than a given due date. The transportation is done by m identical vehicles with limited capacity. It takes a constant time to deliver a batch of jobs to the customer. The objective is to find a feasible schedule minimizing the maximum lateness.     

An alternate quantum adiabatic evolution for the Deutsch–Jozsa problem

Deutsch–Jozsa algorithm has been implemented via quantum adiabatic evolutions by Das et al. (Phys Rev A 65:062310, 2002) and Wei et al. (Phys Lett A 354:271, 2006). In the latter literature, the authors have shown a modified version of the adiabatic evolution which can improve the performance of the algorithm of S. Das et al’s to constant time. In this paper, we also improve the algorithm of S. Das et al’s in a constant time but by using a different construction of adiabatic evolution, i.e., adding ancillary qubits. The algorithm in this paper provides an alternative option to potential users.     

Family of quadratic spline difference schemes for a convection–diffusion problem

We consider the finite difference approximation of a singularly perturbed one-dimensional convection–diffusion two-point boundary value problem. It is discretized using quadratic splines as approximation functions, equations with various piecewise constant coefficients as collocation equations and a piecewise uniform mesh of Shishkin type. The family of schemes is derived using the collocation method. The numerical methods developed here are non-monotone and therefore apart from the consistency error we use Green's grid function analysis to prove uniform convergence. We prove the almost first order of convergence and furthermore show that some of the schemes have almost second-order convergence. Numerical experiments presented in the paper confirm our theoretical results.     

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.     

A novel hybrid DE–random search approach for unit commitment problem

Differential evolution (DE) is a population-based stochastic search algorithm, whose simple yet powerful and straightforward features make it very attractive for numerical optimization. DE uses a rather greedy and less stochastic approach to problem-solving than other evolutionary algorithms. DE combines simple arithmetic operators with the classical operators of recombination, mutation and selection to evolve from a randomly generated starting population to a final solution. Although global exploration ability of DE algorithm is adequate, its local exploitation ability is feeble and convergence velocity is too low and it suffers from the problem of untime convergence for multimodal objective function, in which search process may be trapped in local optima and it loses its diversity. Also, it suffers from the stagnation problem, where the search process may infrequently stop proceeding toward the global optimum even though the population has not converged to a local optimum or any other point. To improve the exploitation ability and global performance of DE algorithm, a novel and hybrid version of DE algorithm is presented in the proposed research. This research paper presents a hybrid version of DE algorithm combined with random search for the solution of single-area unit commitment problem. The hybrid DE–random search algorithm is tested with IEEE benchmark systems consisting of 4, 10, 20 and 40 generating units. The effectiveness of proposed hybrid algorithm is compared with other well-known evolutionary, heuristics and meta-heuristics search algorithms, and by experimental analysis, it has been found that proposed algorithm yields global results for the solution of unit commitment problem.

     

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.     

Incorporating ϵ-dominance in AMOSA: Application to multiobjective 0/1 knapsack problem and clustering gene expression data

Recently, a new model of multiobjective simulated annealing, AMOSA, was developed which was found to provide improved performance for several multi objective optimization problems especially for problems with many objectives. In this article, we aim to further improve the performance of AMOSA by incorporating the concept of ?-dominance which is a more generalized form of conventional dominance. This strategy is referred to as ?-AMOSA. The result of ?-AMOSA is compared with those of AMOSA, NSGA-II and ?-MOEA and AMOSA for several test problems with number of objectives varying from two to fifteen and the number of variables varying from one to thirty. The performance of ?-AMOSA is also compared with other strategies for multiobjective 0/1 knapsack problem. A real life application of ?-AMOSA for clustering genes from gene expression data is also demonstrated. The results demonstrate the effectiveness of ?-AMOSA.