The study was aimed at determining the impacts of operating Manually Operated Hand Lever Knapsack Sprayers (MOHLKS) on physiological responses of the operators as dependent on anthropometric variations and sex. Twenty...The study was aimed at determining the impacts of operating Manually Operated Hand Lever Knapsack Sprayers (MOHLKS) on physiological responses of the operators as dependent on anthropometric variations and sex. Twenty eight subjects, (4 female, 24 male) Mean ± SD: Age 22.5 ± 1.92, 24.29 ± 2.2 years;Body Mass Index 24.6 ± 4.8, 21.7 ± 2.4 kg/m<sup>2</sup> were employed in the study. Selected anthropometric parameters of weight and height were used to determine body mass index (BMI), with these are arm-reach forward, elbow to fingertip, hand length and hand width were measured to establish human variations in diversity. Subjects undertook the operation at 5 replicates each, before and after which information about operators’ body pain locations and body physiological changes of heart rates were obtained. Measured parameters were used in the determination of expended energy (EE), physiological cost (PC), oxygen intake (VO<sub>2</sub>) and aerobic power (VO<sub>2</sub>max). Alongside with these were operational parameters of stroke, pace and time taken to get the operation done and environmental factors of temperature and relative humidity. The results revealed on the average that the BMI (24.61 ± 4.78 kg/m<sup>2</sup>) in female operators was higher, this corresponded to PC and VO<sub>2</sub>, while the VO<sub>2</sub>max (34.83 ± 3.30 ml/min/kg) in males is higher. More EE was obtained in female subjects (3.53 ± 3.76 kCal/min) as compared to male subjects (3.42 ± 7.48 kCal/min). The main effects plot of operational factors on EE displayed the stroke made by the subjects during spraying operation as parameter with largest effect on EE. Regression equation for EE and PCI is given as PCI = 1.97 + 25.2 EE, while the P-value at α = 0.05 is 0.000 and R<sup>2</sup> = 98.8%. Post operational body pain showed that 19 out of 28 subjects incurred at least one type of body pain, with shoulder pain as most frequent. The results of the study suggest that early incidence of fatigue may occur in female operators as compared to the males, and in addition, cumulative trauma at shoulder, back, and upper and lower arm may result over time. Hence, it is recommended that the tank volume should be reduced and the straps for the shoulders should be supported with additional cushion.展开更多
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 G...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.展开更多
In this paper a hybrid parallel multi-objective genetic algorithm is proposed for solving 0/1 knapsack problem. Multi-objective problems with non-convex and discrete Pareto front can take enormous computation time to ...In this paper a hybrid parallel multi-objective genetic algorithm is proposed for solving 0/1 knapsack problem. Multi-objective problems with non-convex and discrete Pareto front can take enormous computation time to converge to the true Pareto front. Hence, the classical multi-objective genetic algorithms (MOGAs) (i.e., non- Parallel MOGAs) may fail to solve such intractable problem in a reasonable amount of time. The proposed hybrid model will combine the best attribute of island and Jakobovic master slave models. We conduct an extensive experimental study in a multi-core system by varying the different size of processors and the result is compared with basic parallel model i.e., master-slave model which is used to parallelize NSGA-II. The experimental results confirm that the hybrid model is showing a clear edge over master-slave model in terms of processing time and approximation to the true Pareto front.展开更多
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. Computatio...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.展开更多
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 equili...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 PE uncertain solution is applied to an armaments transportation problem.展开更多
Key information extraction can reduce the dimensional effects while evaluating the correct preferences of users during semantic data analysis.Currently,the classifiers are used to maximize the performance of web-page ...Key information extraction can reduce the dimensional effects while evaluating the correct preferences of users during semantic data analysis.Currently,the classifiers are used to maximize the performance of web-page recommendation in terms of precision and satisfaction.The recent method disambiguates contextual sentiment using conceptual prediction with robustness,however the conceptual prediction method is not able to yield the optimal solution.Context-dependent terms are primarily evaluated by constructing linear space of context features,presuming that if the terms come together in certain consumerrelated reviews,they are semantically reliant.Moreover,the more frequently they coexist,the greater the semantic dependency is.However,the influence of the terms that coexist with each other can be part of the frequency of the terms of their semantic dependence,as they are non-integrative and their individual meaning cannot be derived.In this work,we consider the strength of a term and the influence of a term as a combinatorial optimization,called Combinatorial Optimized Linear Space Knapsack for Information Retrieval(COLSK-IR).The COLSK-IR is considered as a knapsack problem with the total weight being the“term influence”or“influence of term”and the total value being the“term frequency”or“frequency of term”for semantic data analysis.The method,by which the term influence and the term frequency are considered to identify the optimal solutions,is called combinatorial optimizations.Thus,we choose the knapsack for performing an integer programming problem and perform multiple experiments using the linear space through combinatorial optimization to identify the possible optimum solutions.It is evident from our experimental results that the COLSK-IR provides better results than previous methods to detect strongly dependent snippets with minimum ambiguity that are related to inter-sentential context during semantic data analysis.展开更多
This paper describes methods to merge two cover inequalities and also simultaneously merge multiple cover inequalities in a multiple knapsack instance. Theoretical results provide conditions under which merged cover i...This paper describes methods to merge two cover inequalities and also simultaneously merge multiple cover inequalities in a multiple knapsack instance. Theoretical results provide conditions under which merged cover inequalities are valid. Polynomial time algorithms are created to find merged cover inequalities. A computational study demonstrates that merged inequalities improve the solution times for benchmark multiple knapsack instances by about 9% on average over CPLEX with default settings.展开更多
In order to optimize the knapsack problem further, this paper proposes an innovative model based on dynamic expectation efficiency, and establishes a new optimization algorithm of 0-1 knapsack problem after analysis a...In order to optimize the knapsack problem further, this paper proposes an innovative model based on dynamic expectation efficiency, and establishes a new optimization algorithm of 0-1 knapsack problem after analysis and research. Through analyzing the study of 30 groups of 0-1 knapsack problem from discrete coefficient of the data, we can find that dynamic expectation model can solve the following two types of knapsack problem. Compared to artificial glowworm swam algorithm, the convergence speed of this algorithm is ten times as fast as that of artificial glowworm swam algorithm, and the storage space of this algorithm is one quarter that of artificial glowworm swam algorithm. To sum up, it can be widely used in practical problems.展开更多
The advancements of mobile devices, public networks and the Internet of creature huge amounts of complex data, both construct & unstructured are being captured in trust to allow organizations to produce better bus...The advancements of mobile devices, public networks and the Internet of creature huge amounts of complex data, both construct & unstructured are being captured in trust to allow organizations to produce better business decisions as data is now pivotal for an organizations success. These enormous amounts of data are referred to as Big Data, which enables a competitive advantage over rivals when processed and analyzed appropriately. However Big Data Analytics has a few concerns including Management of Data, Privacy & Security, getting optimal path for transport data, and Data Representation. However, the structure of network does not completely match transportation demand, i.e., there still exist a few bottlenecks in the network. This paper presents a new approach to get the optimal path of valuable data movement through a given network based on the knapsack problem. This paper will give value for each piece of data, it depends on the importance of this data (each piece of data defined by two arguments size and value), and the approach tries to find the optimal path from source to destination, a mathematical models are developed to adjust data flows between their shortest paths based on the 0 - 1 knapsack problem. We also take out computational experience using the commercial software Gurobi and a greedy algorithm (GA), respectively. The outcome indicates that the suggest models are active and workable. This paper introduced two different algorithms to study the shortest path problems: the first algorithm studies the shortest path problems when stochastic activates and activities does not depend on weights. The second algorithm studies the shortest path problems depends on weights.展开更多
The nonlinear multidimensional knapsack problem is defined as the minimization of a convex function with multiple linear constraints. The methods developed for nonlinear multidimensional programming problems are often...The nonlinear multidimensional knapsack problem is defined as the minimization of a convex function with multiple linear constraints. The methods developed for nonlinear multidimensional programming problems are often applied to solve the nonlinear multidimensional knapsack problems, but they are inefficient or limited since most of them do not exploit the characteristics of the knapsack problems. In this paper, by establishing structural properties of the continuous separable nonlinear multidimensional knapsack problem, we develop a multi-tier binary solution method for solving the continuous nonlinear multidimensional knapsack problems with general structure. The computational complexity is polynomial in the number of variables. We presented two examples to illustrate the general application of our method and we used statistical results to show the effectiveness of our method.展开更多
Aiming at constructing the multi-knapsack model of collaborative portfolio configurations in multi-strategy oriented, the hybrid evolutionary algorithm was designed based on greedy method, combining with the organizat...Aiming at constructing the multi-knapsack model of collaborative portfolio configurations in multi-strategy oriented, the hybrid evolutionary algorithm was designed based on greedy method, combining with the organization of the multiple strategical guidance and multi-knapsack model. Furthermore, the organizing resource utility and risk management of portfolio were considered. The experiments were conducted on three main technological markets which contain communication, transportation and industry. The results demonstrated that the proposed model and algorithm were feasible and reliable.展开更多
The 0/1 Multidimensional Knapsack Problem (0/1 MKP) is an interesting NP-hard combinatorial optimization problem that can model a number of challenging applications in logistics, finance, telecommunications and other ...The 0/1 Multidimensional Knapsack Problem (0/1 MKP) is an interesting NP-hard combinatorial optimization problem that can model a number of challenging applications in logistics, finance, telecommunications and other fields. In the 0/1 MKP, a set of items is given, each with a size and value, which has to be placed into a knapsack that has a certain number of dimensions having each a limited capacity. The goal is to find a subset of items leading to the maximum total profit while respecting the capacity constraints. Even though the 0/1 MKP is well studied in the literature, we can just find a little number of recent review papers on this problem. Furthermore, the existing reviews focus particularly on some specific issues. This paper aims to give a general and comprehensive survey of the considered problem so that it can be useful for both researchers and practitioners. Indeed, we first describe the 0/1 MKP and its relevant variants. Then, we present the detailed models of some important real-world applications of this problem. Moreover, an important collection of recently published heuristics and metaheuristics is categorized and briefly reviewed. These approaches are then quantitatively compared through some indicative statistics. Finally, some synthetic remarks and research directions are highlighted in the conclusion.展开更多
Binary wolf pack algorithm (BWPA) is a kind of intelligence algorithm which can solve combination optimization problems in discrete spaces.Based on BWPA, an improved binary wolf pack algorithm (AIBWPA) can be proposed...Binary wolf pack algorithm (BWPA) is a kind of intelligence algorithm which can solve combination optimization problems in discrete spaces.Based on BWPA, an improved binary wolf pack algorithm (AIBWPA) can be proposed by adopting adaptive step length and improved update strategy of wolf pack. AIBWPA is applied to 10 classic 0-1 knapsack problems and compared with BWPA, DPSO, which proves that AIBWPA has higher optimization accuracy and better computational robustness. AIBWPA makes the parameters simple, protects the population diversity and enhances the global convergence.展开更多
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....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.展开更多
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 ...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.展开更多
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 i...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.展开更多
文摘The study was aimed at determining the impacts of operating Manually Operated Hand Lever Knapsack Sprayers (MOHLKS) on physiological responses of the operators as dependent on anthropometric variations and sex. Twenty eight subjects, (4 female, 24 male) Mean ± SD: Age 22.5 ± 1.92, 24.29 ± 2.2 years;Body Mass Index 24.6 ± 4.8, 21.7 ± 2.4 kg/m<sup>2</sup> were employed in the study. Selected anthropometric parameters of weight and height were used to determine body mass index (BMI), with these are arm-reach forward, elbow to fingertip, hand length and hand width were measured to establish human variations in diversity. Subjects undertook the operation at 5 replicates each, before and after which information about operators’ body pain locations and body physiological changes of heart rates were obtained. Measured parameters were used in the determination of expended energy (EE), physiological cost (PC), oxygen intake (VO<sub>2</sub>) and aerobic power (VO<sub>2</sub>max). Alongside with these were operational parameters of stroke, pace and time taken to get the operation done and environmental factors of temperature and relative humidity. The results revealed on the average that the BMI (24.61 ± 4.78 kg/m<sup>2</sup>) in female operators was higher, this corresponded to PC and VO<sub>2</sub>, while the VO<sub>2</sub>max (34.83 ± 3.30 ml/min/kg) in males is higher. More EE was obtained in female subjects (3.53 ± 3.76 kCal/min) as compared to male subjects (3.42 ± 7.48 kCal/min). The main effects plot of operational factors on EE displayed the stroke made by the subjects during spraying operation as parameter with largest effect on EE. Regression equation for EE and PCI is given as PCI = 1.97 + 25.2 EE, while the P-value at α = 0.05 is 0.000 and R<sup>2</sup> = 98.8%. Post operational body pain showed that 19 out of 28 subjects incurred at least one type of body pain, with shoulder pain as most frequent. The results of the study suggest that early incidence of fatigue may occur in female operators as compared to the males, and in addition, cumulative trauma at shoulder, back, and upper and lower arm may result over time. Hence, it is recommended that the tank volume should be reduced and the straps for the shoulders should be supported with additional cushion.
文摘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.
文摘In this paper a hybrid parallel multi-objective genetic algorithm is proposed for solving 0/1 knapsack problem. Multi-objective problems with non-convex and discrete Pareto front can take enormous computation time to converge to the true Pareto front. Hence, the classical multi-objective genetic algorithms (MOGAs) (i.e., non- Parallel MOGAs) may fail to solve such intractable problem in a reasonable amount of time. The proposed hybrid model will combine the best attribute of island and Jakobovic master slave models. We conduct an extensive experimental study in a multi-core system by varying the different size of processors and the result is compared with basic parallel model i.e., master-slave model which is used to parallelize NSGA-II. The experimental results confirm that the hybrid model is showing a clear edge over master-slave model in terms of processing time and approximation to the true Pareto front.
文摘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.
基金supported by the National Natural Science Foundation of China(7160118361502522)
文摘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 PE uncertain solution is applied to an armaments transportation problem.
文摘Key information extraction can reduce the dimensional effects while evaluating the correct preferences of users during semantic data analysis.Currently,the classifiers are used to maximize the performance of web-page recommendation in terms of precision and satisfaction.The recent method disambiguates contextual sentiment using conceptual prediction with robustness,however the conceptual prediction method is not able to yield the optimal solution.Context-dependent terms are primarily evaluated by constructing linear space of context features,presuming that if the terms come together in certain consumerrelated reviews,they are semantically reliant.Moreover,the more frequently they coexist,the greater the semantic dependency is.However,the influence of the terms that coexist with each other can be part of the frequency of the terms of their semantic dependence,as they are non-integrative and their individual meaning cannot be derived.In this work,we consider the strength of a term and the influence of a term as a combinatorial optimization,called Combinatorial Optimized Linear Space Knapsack for Information Retrieval(COLSK-IR).The COLSK-IR is considered as a knapsack problem with the total weight being the“term influence”or“influence of term”and the total value being the“term frequency”or“frequency of term”for semantic data analysis.The method,by which the term influence and the term frequency are considered to identify the optimal solutions,is called combinatorial optimizations.Thus,we choose the knapsack for performing an integer programming problem and perform multiple experiments using the linear space through combinatorial optimization to identify the possible optimum solutions.It is evident from our experimental results that the COLSK-IR provides better results than previous methods to detect strongly dependent snippets with minimum ambiguity that are related to inter-sentential context during semantic data analysis.
文摘This paper describes methods to merge two cover inequalities and also simultaneously merge multiple cover inequalities in a multiple knapsack instance. Theoretical results provide conditions under which merged cover inequalities are valid. Polynomial time algorithms are created to find merged cover inequalities. A computational study demonstrates that merged inequalities improve the solution times for benchmark multiple knapsack instances by about 9% on average over CPLEX with default settings.
文摘In order to optimize the knapsack problem further, this paper proposes an innovative model based on dynamic expectation efficiency, and establishes a new optimization algorithm of 0-1 knapsack problem after analysis and research. Through analyzing the study of 30 groups of 0-1 knapsack problem from discrete coefficient of the data, we can find that dynamic expectation model can solve the following two types of knapsack problem. Compared to artificial glowworm swam algorithm, the convergence speed of this algorithm is ten times as fast as that of artificial glowworm swam algorithm, and the storage space of this algorithm is one quarter that of artificial glowworm swam algorithm. To sum up, it can be widely used in practical problems.
文摘The advancements of mobile devices, public networks and the Internet of creature huge amounts of complex data, both construct & unstructured are being captured in trust to allow organizations to produce better business decisions as data is now pivotal for an organizations success. These enormous amounts of data are referred to as Big Data, which enables a competitive advantage over rivals when processed and analyzed appropriately. However Big Data Analytics has a few concerns including Management of Data, Privacy & Security, getting optimal path for transport data, and Data Representation. However, the structure of network does not completely match transportation demand, i.e., there still exist a few bottlenecks in the network. This paper presents a new approach to get the optimal path of valuable data movement through a given network based on the knapsack problem. This paper will give value for each piece of data, it depends on the importance of this data (each piece of data defined by two arguments size and value), and the approach tries to find the optimal path from source to destination, a mathematical models are developed to adjust data flows between their shortest paths based on the 0 - 1 knapsack problem. We also take out computational experience using the commercial software Gurobi and a greedy algorithm (GA), respectively. The outcome indicates that the suggest models are active and workable. This paper introduced two different algorithms to study the shortest path problems: the first algorithm studies the shortest path problems when stochastic activates and activities does not depend on weights. The second algorithm studies the shortest path problems depends on weights.
文摘The nonlinear multidimensional knapsack problem is defined as the minimization of a convex function with multiple linear constraints. The methods developed for nonlinear multidimensional programming problems are often applied to solve the nonlinear multidimensional knapsack problems, but they are inefficient or limited since most of them do not exploit the characteristics of the knapsack problems. In this paper, by establishing structural properties of the continuous separable nonlinear multidimensional knapsack problem, we develop a multi-tier binary solution method for solving the continuous nonlinear multidimensional knapsack problems with general structure. The computational complexity is polynomial in the number of variables. We presented two examples to illustrate the general application of our method and we used statistical results to show the effectiveness of our method.
文摘Aiming at constructing the multi-knapsack model of collaborative portfolio configurations in multi-strategy oriented, the hybrid evolutionary algorithm was designed based on greedy method, combining with the organization of the multiple strategical guidance and multi-knapsack model. Furthermore, the organizing resource utility and risk management of portfolio were considered. The experiments were conducted on three main technological markets which contain communication, transportation and industry. The results demonstrated that the proposed model and algorithm were feasible and reliable.
文摘The 0/1 Multidimensional Knapsack Problem (0/1 MKP) is an interesting NP-hard combinatorial optimization problem that can model a number of challenging applications in logistics, finance, telecommunications and other fields. In the 0/1 MKP, a set of items is given, each with a size and value, which has to be placed into a knapsack that has a certain number of dimensions having each a limited capacity. The goal is to find a subset of items leading to the maximum total profit while respecting the capacity constraints. Even though the 0/1 MKP is well studied in the literature, we can just find a little number of recent review papers on this problem. Furthermore, the existing reviews focus particularly on some specific issues. This paper aims to give a general and comprehensive survey of the considered problem so that it can be useful for both researchers and practitioners. Indeed, we first describe the 0/1 MKP and its relevant variants. Then, we present the detailed models of some important real-world applications of this problem. Moreover, an important collection of recently published heuristics and metaheuristics is categorized and briefly reviewed. These approaches are then quantitatively compared through some indicative statistics. Finally, some synthetic remarks and research directions are highlighted in the conclusion.
文摘Binary wolf pack algorithm (BWPA) is a kind of intelligence algorithm which can solve combination optimization problems in discrete spaces.Based on BWPA, an improved binary wolf pack algorithm (AIBWPA) can be proposed by adopting adaptive step length and improved update strategy of wolf pack. AIBWPA is applied to 10 classic 0-1 knapsack problems and compared with BWPA, DPSO, which proves that AIBWPA has higher optimization accuracy and better computational robustness. AIBWPA makes the parameters simple, protects the population diversity and enhances the global convergence.
基金supported by the National Natural Science Foundation of China(70871081)the Shanghai Leading Academic Discipline Project(S30504).
文摘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.
基金Project supported by the National Natural Science Foundation of China (Grant No.10571116)
文摘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.
文摘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.