Gompertz PSO variants for Knapsack and Multi-Knapsack Problems

Particle Swarm Optimization,a potential swarm intelligence heuristic,has been recognized as a global optimizer for solving various continuous as well as discrete optimization problems.Encourged by the performance of Gompertz PSO on a set of continuous problems,this works extends the application of Gompertz PSO for solving binary optimization problems.Moreover,a new chaotic variant of Gompertz PSO namely Chaotic Gompertz Binary Particle Swarm Optimization(CGBPSO)has also been proposed.The new variant is further analysed for solving binary optimization problems.The new chaotic variant embeds the notion of chaos into GBPSO in later stages of searching process to avoid stagnation phenomena.The efficiency of both the Binary PSO variants has been tested on different sets of Knapsack Problems(KPs):0-1 Knapsack Problem(0-1 KP)and Multidimensional Knapsack Problems(MKP).The concluding remarks have made on the basis of detailed analysis of results,which comprises the comparison of results for Knapsack and Multidimensional Knapsack problems obtained using BPSO,GBPSO and CGBPSO.

SOME EXTENDED KNAPSACK PROBLEMS INVOLVING JOB PARTITION BETWEEN TWO PARTIES

Some novel applications and pragmatic variations of knapsack problem （KP） are presented and constructed, which are formulated and developed from a model initiated in this paper on profit allocation from partition of jobs in terms of two-person discrete cooperation game.

A branch-and-bound algorithm for multi-dimensional quadratic 0-1 knapsack problems

In this paper, a branch-and-bound method for solving multi-dimensional quadratic 0-1 knapsack problems was studied. The method was based on the Lagrangian relaxation and the surrogate constraint technique for finding feasible solutions. The Lagrangian relaxations were solved with the maximum-flow algorithm and the Lagrangian bounds was determined with the outer approximation method. Computational results show the efficiency of the proposed method for multi-dimensional quadratic 0-1 knapsack problems.

Quantum-inspired ant algorithm for knapsack problems

The knapsack problem is a well-known combinatorial optimization problem which has been proved to be NP-hard. This paper proposes a new algorithm called quantum-inspired ant algorithm （QAA） to solve the knapsack problem. QAA takes the advantage of the principles in quantum computing, such as qubit, quantum gate, and quantum superposition of states, to get more probabilistic-based status with small colonies. By updating the pheromone in the ant algorithm and rotating the quantum gate, the algorithm can finally reach the optimal solution. The detailed steps to use QAA are presented, and by solving series of test cases of classical knapsack problems, the effectiveness and generality of the new algorithm are validated.

An efficient algorithm for multi-dimensional nonlinear knapsack problems

Multi-dimensional nonlinear knapsack problem is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to multiple separable nondecreasing constraints. This problem is often encountered in resource allocation, industrial planning and computer network. In this paper, a new convergent Lagrangian dual method was proposed for solving this problem. Cutting plane method was used to solve the dual problem and to compute the Lagrangian bounds of the primal problem. In order to eliminate the duality gap and thus to guarantee the convergence of the algorithm, domain cut technique was employed to remove certain integer boxes and partition the revised domain to a union of integer boxes. Extensive computational results show that the proposed method is efficient for solving large-scale multi-dimensional nonlinear knapsack problems. Our numerical results also indicate that the cutting plane method significantly outperforms the subgradient method as a dual search procedure.

Surrogate dual method for multi-dimensional nonlinear knapsack problems

Multi-dimensional nonlinear knapsack problems are often encountered in resource allocation, industrial planning and computer networks. In this paper, a surrogate dual method was proposed for solving this class of problems. Multiply constrained problem was relaxed to a singly constrained problem by using the surrogate technique. To compute tighter bounds of the primal problem, the cutting plane method was used to solve the surrogate dual problem, where the surrogate relaxation problem was solved by the 0-1 linearization method. The domain cut technique was employed to eliminate the duality gap and thus to guarantee the convergence of tile algorithm. Numerical results were reported for large-scale multi-dimensional nonlinear knapsack problems.

GPS： a constraint-based gene position procurement in chromosome for solving large-scale multiobjective multiple knapsack problems

The multiple knapsack problem （MKP） forms a base for resolving many real-life problems. This has also been considered with multiple objectives in genetic algorithms （GAs） for proving its efficiency. GAs use self- adaptability to effectively solve complex problems with constraints, but in certain cases, self-adaptability fails by converging toward an infeasible region. This pitfall can be resolved by using different existing repairing techniques; however, this cannot assure convergence toward attaining the optimal solution. To overcome this issue, gene position-based suppression （GPS） has been modeled and embedded as a new phase in a classical GA. This phase works on the genes of a newly generated individual after the recombination phase to retain the solution vector within its feasible region and to im- prove the solution vector to attain the optimal solution. Genes holding the highest expressibility are reserved into a subset, as the best genes identified from the current individuals by re- placing the weaker genes from the subset. This subset is used by the next generated individual to improve the solution vec- tor and to retain the best genes of the individuals. Each gene＇s positional point and its genotype exposure for each region in an environment are used to fit the best unique genes. Further, suppression of expression in conflicting gene＇s relies on the requirement toward the level of exposure in the environment or in eliminating the duplicate genes from the environment.The MKP benchmark instances from the OR-library are taken for the experiment to test the new model. The outcome por- trays that GPS in a classical GA is superior in most of the cases compared to the other existing repairing techniques.

Approximation for Knapsack Problemswith Multiple Constraints

in this paper, the approximation for four kinds of knapsack prob- lems with multiple constraints is studied: 0/1 Multiple Constraint Knapsack Problem(0/1 MCKP), Integer Multiple Constraint Knapsack Problem (Integer MCKP), 0/1k-Constraillt Knapsack Problem (0/1 k-CKP) and Integer k-Constraint KnapsackProblem (Integer k-CKP). The following results are obtained:1) Unless NP = co - R, no polynomial time algorithm approximates 0/1 MCKPor Integer MCKP within a factor k(1/2)- for any > 0; unless NP = P, nopolynomial time algorithm approximates 0/1 MCKP or integer MCKP within afactor k(1/4)- for any > 0, where k stands for the number of constraints.2) For any fixed positive integer k, 0/1 k-CKP has a fully polynomial time approximation scheme (FPTAS).3) For any fixed positive integer k, Integer k-CKP has a fast FPTAS which hastime complexity O(n +) and space complexity O(n + (1/3)), andfinds an approximate solution to within 5 of the optimal solution.

A membrane-inspired algorithm with a memory mechanism for knapsack problems

Membrane algorithms are a class of distributed and parallel algorithms inspired by the structure and behavior of living cells. Many attractive features of living cells have already been abstracted as operators to improve the performance of algorithms. In this work, inspired by the function of biological neuron cells storing information, we consider a memory mechanism by introducing memory modules into a membrane algorithm. The framework of the algorithm consists of two kinds of modules (computation modules and memory modules), both of which are arranged in a ring neighborhood topology. They can store and process information, and exchange information with each other. We test our method on a knapsack problem to demonstrate its feasibility and effectiveness. During the process of approaching the optimum solution, feasible solutions are evolved by rewriting rules in each module, and the information transfers according to directions defined by communication rules. Simulation results showed that the performance of membrane algorithms with memory cells is superior to that of algorithms without memory cells for solving a knapsack problem. Furthermore, the memory mechanism can prevent premature convergence and increase the possibility of finding a global solution.

Multiple Perspective of Multipredictor Mechanism and Multihistogram Modification for High-Fidelity Reversible Data Hiding

Reversible data hiding is a confidential communication technique that takes advantage of image file characteristics,which allows us to hide sensitive data in image files.In this paper,we propose a novel high-fidelity reversible data hiding scheme.Based on the advantage of the multipredictor mechanism,we combine two effective prediction schemes to improve prediction accuracy.In addition,the multihistogram technique is utilized to further improve the image quality of the stego image.Moreover,a model of the grouped knapsack problem is used to speed up the search for the suitable embedding bin in each sub-histogram.Experimental results show that the quality of the stego image of our scheme outperforms state-of-the-art schemes in most cases.

2-median location improvement problems under weighted l_1 norm and l_∞ norm on trees

This paper focuses on the 2-median location improvement problem on tree networks and the problem is to modify the weights of edges at the minimum cost such that the overall sum of the weighted distance of the vertices to the respective closest one of two prescribed vertices in the modified network is upper bounded by a given value.l1 norm and l∞norm are used to measure the total modification cost. These two problems have a strong practical application background and important theoretical research value. It is shown that such problems can be transformed into a series of sum-type and bottleneck-type continuous knapsack problems respectively.Based on the property of the optimal solution two O n2 algorithms for solving the two problems are proposed where n is the number of vertices on the tree.

A Weight-Coded Evolutionary Algorithm for the Multidimensional Knapsack Problem

A revised weight-coded evolutionary algorithm (RWCEA) is proposed for solving multidimensional knapsack problems. This RWCEA uses a new decoding method and incorporates a heuristic method in initialization. Computational results show that the RWCEA performs better than a weight-coded evolutionary algorithm pro-posed by Raidl (1999) and to some existing benchmarks, it can yield better results than the ones reported in the OR-library.

SEMI-DEFINITE RELAXATION ALGORITHM OF MULTIPLE KNAPSACK PROBLEM

The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,and each knapsack i has a capacity Ci.The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks.MKP(B,S,m,n) is strongly NP- Complete and no polynomial- time approximation algorithm can have an approxima- tion ratio better than0 .5 .In the last ten years,semi- definite programming has been empolyed to solve some combinatorial problems successfully.This paper firstly presents a semi- definite re- laxation algorithm (MKPS) for MKP (B,S,m,n) .It is proved that MKPS have a approxima- tion ratio better than 0 .5 for a subclass of MKP (B,S,m,n) with n≤ 1 0 0 ,m≤ 5 and maxnj=1{ wj} minmi=1{ Ci} ≤ 2 3 .

Uncertain bilevel knapsack problem and its solution

This paper aims at providing an uncertain bilevel knapsack problem (UBKP) model, which is a type of BKPs involving uncertain variables. And then an uncertain solution for the UBKP is proposed by defining PE Nash equilibrium and PE Stackelberg Nash equilibrium. In order to improve the computational efficiency of the uncertain solution, several operators (binary coding distance, inversion operator, explosion operator and binary back learning operator) are applied to the basic fireworks algorithm to design the binary backward fireworks algorithm (BBFWA), which has a good performance in solving the BKP. As an illustration, a case study of the UBKP model and the P-E uncertain solution is applied to an armaments transportation problem.

Improved Parallel Three-List Algorithm for the Knapsack Problem without Memory Conflicts

Based on the two-list algorithm and the parallel three-list algorithm, an improved parallel three-list algorithm for knapsack problem is proposed, in which the method of divide and conquer, and parallel merging without memory conflicts are adopted. To find a solution for the n-element knapsack problem, the proposed algorithm needs O（2^3n/8） time when O（2^3n/8） shared memory units and O（2^n/4） processors are available. The comparisons between the proposed algorithm and 10 existing algorithms show that the improved parallel three-fist algorithm is the first exclusive-read exclusive-write （EREW） parallel algorithm that can solve the knapsack instances in less than O（2^n/2） time when the available hardware resource is smaller than O（2^n/2） , and hence is an improved result over the past researches.

An Optimal Parallel Algorithm for the Knapsack Problem Based on EREW

A new parallel algorithm is proposed for the knapsack problem where the method of divide and conquer is adopted. Based on an EREW-SIMD machine with shared memory, the proposed algorithm utilizes O(2 n/4 ) 1-ε processors, 0≤ ε ≤1, and O(2 n/2 ) memory to find a solution for the n -element knapsack problem in time O(2 n/4 (2 n/4 ) ε) . The cost of the proposed parallel algorithm is O(2 n/2 ) , which is an optimal method for solving the knapsack problem without memory conflicts and an improved result over the past researches.

An Unbounded Fully Homomorphic Encryption Scheme Based on Ideal Lattices and Chinese Remainder Theorem

We propose an unbounded fully homomorphic encryption scheme, i.e. a scheme that allows one to compute on encrypted data for any desired functions without needing to decrypt the data or knowing the decryption keys. This is a rational solution to an old problem proposed by Rivest, Adleman, and Dertouzos [1] in 1978, and to some new problems that appeared in Peikert [2] as open questions 10 and open questions 11 a few years ago. Our scheme is completely different from the breakthrough work [3] of Gentry in 2009. Gentry’s bootstrapping technique constructs a fully homomorphic encryption (FHE) scheme from a somewhat homomorphic one that is powerful enough to evaluate its own decryption function. To date, it remains the only known way of obtaining unbounded FHE. Our construction of an unbounded FHE scheme is straightforward and can handle unbounded homomorphic computation on any refreshed ciphertexts without bootstrapping transformation technique.

Dynamic Weapon Target Assignment Based on Intuitionistic Fuzzy Entropy of Discrete Particle Swarm

Aiming at the problems of convergence-slow and convergence-free of Discrete Particle Swarm Optimization Algorithm(DPSO) in solving large scale or complicated discrete problem, this article proposes Intuitionistic Fuzzy Entropy of Discrete Particle Swarm Optimization(IFDPSO) and makes it applied to Dynamic Weapon Target Assignment(WTA). First, the strategy of choosing intuitionistic fuzzy parameters of particle swarm is defined, making intuitionistic fuzzy entropy as a basic parameter for measure and velocity mutation. Second, through analyzing the defects of DPSO, an adjusting parameter for balancing two cognition, velocity mutation mechanism and position mutation strategy are designed, and then two sets of improved and derivative algorithms for IFDPSO are put forward, which ensures the IFDPSO possibly search as much as possible sub-optimal positions and its neighborhood and the algorithm ability of searching global optimal value in solving large scale 0-1 knapsack problem is intensified. Third, focusing on the problem of WTA, some parameters including dynamic parameter for shifting firepower and constraints are designed to solve the problems of weapon target assignment. In addition, WTA Optimization Model with time and resource constraints is finally set up, which also intensifies the algorithm ability of searching global and local best value in the solution of WTA problem. Finally, the superiority of IFDPSO is proved by several simulation experiments. Particularly, IFDPSO, IFDPSO1~IFDPSO3 are respectively effective in solving large scale, medium scale or strict constraint problems such as 0-1 knapsack problem and WTA problem.

Intermediate carriers for UAV swarms:problem of fleet composition

This article introduces a fleet composition algorithm for a fleet of intermediate carriers, which should deliver a swarm of miniature unmanned aerial vehicles （mini-UAVs） to a mission area. The algorithm is based on the sequential solution of several knapsack problems with various constraints. The algorithm allows both to form an initial set of required types of intermediate carriers, and to generate a fleet of intermediate carriers. The formation of a fleet of intermediate carriers to solve a suppression of enemy air defense （SEAD） problem is presented to illustrate the proposed algorithm.

Overload problem research on aperiodic real-time tasks

In this paper, a novel scheduling mechanism is proposed to handle the real-time overload problem by maximizing the cumulative values of three types of tasks： the soft, the hard and the imprecise tasks. The simulation results show that the performance of our presented mechanism in this paper is greatly improved, much better than that of the other three mechanisms： earliest deadline first （EDF）, highest value first （HVF） and highest density first （HDF）, under the same conditions of all nominal loads and task type proportions.