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.展开更多
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.展开更多
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.展开更多
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.展开更多
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.展开更多
A 0-1 integer programming model for weekly fleet assignment was put forward based on linear network and weekly flight scheduling in China. In this model, the objective function is to maximize the total profit of fleet...A 0-1 integer programming model for weekly fleet assignment was put forward based on linear network and weekly flight scheduling in China. In this model, the objective function is to maximize the total profit of fleet assignment, subject to the constraints of coverage, aircraft flow balance, fleet size, aircraft availability, aircraft usage, flight restriction, aircraft seat capacity, and stopover. Then the branch-and-bound algorithm based on special ordered set was applied to solve the model. At last, a real- wofld case study on an airline with 5 fleets, 48 aircrafts and 1 786 flight legs indicated that the profit increase was ￥ 1 591276 one week and the running time was no more than 4 rain, which shows that the model and algorithm are fairly good for domestic airline.展开更多
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.展开更多
In this paper, we construct two models for the searching task for a lost plane. Model 1 determines the searching area. We predict the trajectory of floats generated after the disintegration of the plane by using RBF n...In this paper, we construct two models for the searching task for a lost plane. Model 1 determines the searching area. We predict the trajectory of floats generated after the disintegration of the plane by using RBF neural network model, and then determine the searching area according to the trajectory. With the pass of time, the searching area will also be constantly moving along the trajectory. Model 2 develops a maritime search plan to achieve the purpose of completing the search in the shortest time. We optimize the searching time and transform the problem into the 0-1 knapsack problem. Solving this problem by improved genetic algorithm, we can get the shortest searching time and the best choice for the search power.展开更多
文摘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.
文摘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.
基金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.
文摘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.
文摘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 National Natural Science Foundationof China (70473037)
文摘A 0-1 integer programming model for weekly fleet assignment was put forward based on linear network and weekly flight scheduling in China. In this model, the objective function is to maximize the total profit of fleet assignment, subject to the constraints of coverage, aircraft flow balance, fleet size, aircraft availability, aircraft usage, flight restriction, aircraft seat capacity, and stopover. Then the branch-and-bound algorithm based on special ordered set was applied to solve the model. At last, a real- wofld case study on an airline with 5 fleets, 48 aircrafts and 1 786 flight legs indicated that the profit increase was ￥ 1 591276 one week and the running time was no more than 4 rain, which shows that the model and algorithm are fairly good for domestic airline.
文摘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.
文摘In this paper, we construct two models for the searching task for a lost plane. Model 1 determines the searching area. We predict the trajectory of floats generated after the disintegration of the plane by using RBF neural network model, and then determine the searching area according to the trajectory. With the pass of time, the searching area will also be constantly moving along the trajectory. Model 2 develops a maritime search plan to achieve the purpose of completing the search in the shortest time. We optimize the searching time and transform the problem into the 0-1 knapsack problem. Solving this problem by improved genetic algorithm, we can get the shortest searching time and the best choice for the search power.
