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.展开更多
0-1 programming is a special case of the integer programming, which is commonly encountered in many optimization problems. Neural network and its general energy function are presented for 0-1 optimization problem. The...0-1 programming is a special case of the integer programming, which is commonly encountered in many optimization problems. Neural network and its general energy function are presented for 0-1 optimization problem. Then, the 0-1 optimization problems are solved by a neural network model with transient chaotic dynamics (TCNN). Numerical simulations of two typical 0-1 optimization problems show that TCNN can overcome HNN's main drawbacks that it suffers from the local minimum and can search for the global optimal solutions in to solveing 0-1 optimization problems.展开更多
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 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 consider the socalled k-coloring problem in general case.Firstly, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above...In this paper, we consider the socalled k-coloring problem in general case.Firstly, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above quadratic0-1 programming and its relaxed problem, k-coloring problem is converted intoa class of (continuous) nonconvex quadratic programs, and several theoreticresults are also introduced. Thirdly, linear programming approximate algorithmis quoted and verified for this class of nonconvex quadratic programs. Finally,examining problems which are used to test the algorithm are constructed andsufficient computation experiments are reported.展开更多
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 Fuzz...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.展开更多
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.展开更多
基金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.
基金This project was supported by the National Natural Science Foundation of China (79970042).
文摘0-1 programming is a special case of the integer programming, which is commonly encountered in many optimization problems. Neural network and its general energy function are presented for 0-1 optimization problem. Then, the 0-1 optimization problems are solved by a neural network model with transient chaotic dynamics (TCNN). Numerical simulations of two typical 0-1 optimization problems show that TCNN can overcome HNN's main drawbacks that it suffers from the local minimum and can search for the global optimal solutions in to solveing 0-1 optimization problems.
文摘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 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 consider the socalled k-coloring problem in general case.Firstly, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above quadratic0-1 programming and its relaxed problem, k-coloring problem is converted intoa class of (continuous) nonconvex quadratic programs, and several theoreticresults are also introduced. Thirdly, linear programming approximate algorithmis quoted and verified for this class of nonconvex quadratic programs. Finally,examining problems which are used to test the algorithm are constructed andsufficient computation experiments are reported.
基金supported by The National Natural Science Foundation of China under Grant Nos.61402517, 61573375The Foundation of State Key Laboratory of Astronautic Dynamics of China under Grant No. 2016ADL-DW0302+2 种基金The Postdoctoral Science Foundation of China under Grant Nos. 2013M542331, 2015M572778The Natural Science Foundation of Shaanxi Province of China under Grant No. 2013JQ8035The Aviation Science Foundation of China under Grant No. 20151996015
文摘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.
基金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.
