A novel chaotic search method is proposed,and a hybrid algorithm combining particle swarm optimization(PSO) with this new method,called CLSPSO,is put forward to solve 14 integer and mixed integer programming problems....A novel chaotic search method is proposed,and a hybrid algorithm combining particle swarm optimization(PSO) with this new method,called CLSPSO,is put forward to solve 14 integer and mixed integer programming problems.The performances of CLSPSO are compared with those of other five hybrid algorithms combining PSO with chaotic search methods.Experimental results indicate that in terms of robustness and final convergence speed,CLSPSO is better than other five algorithms in solving many of these problems.Furthermore,CLSPSO exhibits good performance in solving two high-dimensional problems,and it finds better solutions than the known ones.A performance index(PI) is introduced to fairly compare the above six algorithms,and the obtained values of(PI) in three cases demonstrate that CLSPSO is superior to all the other five algorithms under the same conditions.展开更多
An integer linear bilevel programming problem is firstly transformed into a binary linear bilevel programming problem, and then converted into a single-level binary implicit programming. An orthogonal genetic algorith...An integer linear bilevel programming problem is firstly transformed into a binary linear bilevel programming problem, and then converted into a single-level binary implicit programming. An orthogonal genetic algorithm is developed for solving the binary linear implicit programming problem based on the orthogonal design. The orthogonal design with the factor analysis, an experimental design method is applied to the genetic algorithm to make the algorithm more robust, statistical y sound and quickly convergent. A crossover operator formed by the orthogonal array and the factor analysis is presented. First, this crossover operator can generate a smal but representative sample of points as offspring. After al of the better genes of these offspring are selected, a best combination among these offspring is then generated. The simulation results show the effectiveness of the proposed algorithm.展开更多
A stochastic resource allocation model, based on the principles of Markov decision processes(MDPs), is proposed in this paper. In particular, a general-purpose framework is developed, which takes into account resource...A stochastic resource allocation model, based on the principles of Markov decision processes(MDPs), is proposed in this paper. In particular, a general-purpose framework is developed, which takes into account resource requests for both instant and future needs. The considered framework can handle two types of reservations(i.e., specified and unspecified time interval reservation requests), and implement an overbooking business strategy to further increase business revenues. The resulting dynamic pricing problems can be regarded as sequential decision-making problems under uncertainty, which is solved by means of stochastic dynamic programming(DP) based algorithms. In this regard, Bellman’s backward principle of optimality is exploited in order to provide all the implementation mechanisms for the proposed reservation pricing algorithm. The curse of dimensionality, as the inevitable issue of the DP both for instant resource requests and future resource reservations,occurs. In particular, an approximate dynamic programming(ADP) technique based on linear function approximations is applied to solve such scalability issues. Several examples are provided to show the effectiveness of the proposed approach.展开更多
Concave resource allocation problem is an integer programming problem of minimizing a nonincreasing concave function subject to a convex nondecreasing constraint and bounded integer variables. This class of problems a...Concave resource allocation problem is an integer programming problem of minimizing a nonincreasing concave function subject to a convex nondecreasing constraint and bounded integer variables. This class of problems are encountered in optimization models involving economies of scale. In this paper, a new hybrid dynamic programming method was proposed for solving concave resource allocation problems. A convex underestimating function was used to approximate the objective function and the resulting convex subproblem was solved with dynamic programming technique after transforming it into a 0-1 linear knapsack problem. To ensure the convergence, monotonicity and domain cut technique was employed to remove certain integer boxes and partition the revised domain into a union of integer boxes. Computational results were given to show the efficiency of the algorithm.展开更多
In this study, we aimed to assess the solution quality for location-allocation problems from facilities generated by the software TransCAD®?, a Geographic Information System for Transportation (GIS-T). Such fa...In this study, we aimed to assess the solution quality for location-allocation problems from facilities generated by the software TransCAD®?, a Geographic Information System for Transportation (GIS-T). Such facilities were obtained after using two routines together: Facility Location and Transportation Problem, when compared with optimal solutions from exact mathematical models, based on Mixed Integer Linear Programming (MILP), developed externally for the GIS. The models were applied to three simulations: the first one proposes opening factories and customer allocation in the state of Sao Paulo, Brazil;the second involves a wholesaler and a study of location and allocation of distribution centres for retail customers;and the third one involves the location of day-care centers and allocation of demand (0 - 3 years old children). The results showed that when considering facility capacity, the MILP optimising model presents results up to 37% better than the GIS and proposes different locations to open new facilities.展开更多
In order to address the output feedback issue for linear discrete-time systems, this work suggests a brand-new adaptive dynamic programming(ADP) technique based on the internal model principle(IMP). The proposed metho...In order to address the output feedback issue for linear discrete-time systems, this work suggests a brand-new adaptive dynamic programming(ADP) technique based on the internal model principle(IMP). The proposed method, termed as IMP-ADP, does not require complete state feedback-merely the measurement of input and output data. More specifically, based on the IMP, the output control problem can first be converted into a stabilization problem. We then design an observer to reproduce the full state of the system by measuring the inputs and outputs. Moreover, this technique includes both a policy iteration algorithm and a value iteration algorithm to determine the optimal feedback gain without using a dynamic system model. It is important that with this concept one does not need to solve the regulator equation. Finally, this control method was tested on an inverter system of grid-connected LCLs to demonstrate that the proposed method provides the desired performance in terms of both tracking and disturbance rejection.展开更多
The double row layout problem(DRLP)is to assign facilities on two rows in parallel so that the total cost of material handling among facilities is minimized.Since it is vital to save cost and enhance productivity,the ...The double row layout problem(DRLP)is to assign facilities on two rows in parallel so that the total cost of material handling among facilities is minimized.Since it is vital to save cost and enhance productivity,the DRLP plays an important role in many application fields.Nevertheless,it is very hard to handle the DRLP because of its complex model.In this paper,we consider a new simplified model for the DRLP(SM-DRLP)and provide a mixed integer programming(MIP)formulation for it.The continuous decision variables of the DRLP are divided into two parts:start points of double rows and adjustable clearances between adjacent facilities.The former one is considered in the new simplified model for the DRLP with the purpose of maintaining solution quality,while the latter one is not taken into account with the purpose of reducing computational time.To evaluate its performance,our SM-DRLP is compared with the model of a general DRLP and the model of another simplified DRLP.The experimental results show the efficiency of our proposed model.展开更多
This research develops a solution method for project scheduling represented by a max-plus-linear (MPL) form. Max-plus-linear representation is an approach to model and analyze a class of discrete-event systems, in whi...This research develops a solution method for project scheduling represented by a max-plus-linear (MPL) form. Max-plus-linear representation is an approach to model and analyze a class of discrete-event systems, in which the behavior of a target system is represented by linear equations in max-plus algebra. Several types of MPL equations can be reduced to a constraint satisfaction problem (CSP) for mixed integer programming. The resulting formulation is flexible and easy-to-use for project scheduling;for example, we can obtain the earliest output times, latest task-starting times, and latest input times using an MPL form. We also develop a key method for identifying critical tasks under the framework of CSP. The developed methods are validated through a numerical example.展开更多
Having lectured in some universities and polytechnics in Nigeria, the researchers observed problems in course allocations. There are no lay-down techniques on how courses should be allocated with respect to the minimu...Having lectured in some universities and polytechnics in Nigeria, the researchers observed problems in course allocations. There are no lay-down techniques on how courses should be allocated with respect to the minimum and maximum credit a lecturer should carry in a semester. Many lecturers were overloaded while others were under-loaded. For this reason, dynamic programming model was developed for allocating courses among lecturers in the Nigerian universities using the Department of Statistics, Federal University of Technology Owerri, as a case study. From our analysis, we observed that among all the optimal allocations discovered in the study, the best optimal allocation policy was achieved at the point (1, 2, 1, 2). Allocation of courses in this order will yield an optimal credit hour of 12 per lecturer per semester.展开更多
The stochastic dual dynamic programming (SDDP) algorithm is becoming increasingly used. In this paper we present analysis of different methods of lattice construction for SDDP exemplifying a realistic variant of the n...The stochastic dual dynamic programming (SDDP) algorithm is becoming increasingly used. In this paper we present analysis of different methods of lattice construction for SDDP exemplifying a realistic variant of the newsvendor problem, incorporating storage of production. We model several days of work and compare the profits realized using different methods of the lattice construction and the corresponding computer time spent in lattice construction. Our case differs from the known one because we consider not only a multidimensional but also a multistage case with stage dependence. We construct scenario lattice for different Markov processes which play a crucial role in stochastic modeling. The novelty of our work is comparing different methods of scenario lattice construction. We considered a realistic variant of the newsvendor problem. The results presented in this article show that the Voronoi method slightly outperforms others, but the k-means method is much faster overall.展开更多
Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing probl...Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing problem is NP-hard. In this paper, it is shown for even graphs that if such a collection satisfies the condition that it minimizes the quantityon the set of all edge-disjoint cycle collections, then it is a maximum cycle packing. The paper shows that the determination of such a packing can be solved by a dynamic programming approach. For its solution, an-shortest path procedure on an appropriate acyclic networkis presented. It uses a particular monotonous node potential.展开更多
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.展开更多
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.展开更多
基金Projects(50275150,61173052) supported by the National Natural Science Foundation of ChinaProject(14FJ3112) supported by the Planned Science and Technology of Hunan Province,ChinaProject(14B033) supported by Scientific Research Fund Education Department of Hunan Province,China
文摘A novel chaotic search method is proposed,and a hybrid algorithm combining particle swarm optimization(PSO) with this new method,called CLSPSO,is put forward to solve 14 integer and mixed integer programming problems.The performances of CLSPSO are compared with those of other five hybrid algorithms combining PSO with chaotic search methods.Experimental results indicate that in terms of robustness and final convergence speed,CLSPSO is better than other five algorithms in solving many of these problems.Furthermore,CLSPSO exhibits good performance in solving two high-dimensional problems,and it finds better solutions than the known ones.A performance index(PI) is introduced to fairly compare the above six algorithms,and the obtained values of(PI) in three cases demonstrate that CLSPSO is superior to all the other five algorithms under the same conditions.
基金supported by the Fundamental Research Funds for the Central Universities(K50511700004)the Natural Science Basic Research Plan in Shaanxi Province of China(2013JM1022)
文摘An integer linear bilevel programming problem is firstly transformed into a binary linear bilevel programming problem, and then converted into a single-level binary implicit programming. An orthogonal genetic algorithm is developed for solving the binary linear implicit programming problem based on the orthogonal design. The orthogonal design with the factor analysis, an experimental design method is applied to the genetic algorithm to make the algorithm more robust, statistical y sound and quickly convergent. A crossover operator formed by the orthogonal array and the factor analysis is presented. First, this crossover operator can generate a smal but representative sample of points as offspring. After al of the better genes of these offspring are selected, a best combination among these offspring is then generated. The simulation results show the effectiveness of the proposed algorithm.
文摘A stochastic resource allocation model, based on the principles of Markov decision processes(MDPs), is proposed in this paper. In particular, a general-purpose framework is developed, which takes into account resource requests for both instant and future needs. The considered framework can handle two types of reservations(i.e., specified and unspecified time interval reservation requests), and implement an overbooking business strategy to further increase business revenues. The resulting dynamic pricing problems can be regarded as sequential decision-making problems under uncertainty, which is solved by means of stochastic dynamic programming(DP) based algorithms. In this regard, Bellman’s backward principle of optimality is exploited in order to provide all the implementation mechanisms for the proposed reservation pricing algorithm. The curse of dimensionality, as the inevitable issue of the DP both for instant resource requests and future resource reservations,occurs. In particular, an approximate dynamic programming(ADP) technique based on linear function approximations is applied to solve such scalability issues. Several examples are provided to show the effectiveness of the proposed approach.
基金Project supported by the National Natural Science Foundation oChina (Grant os.79970107 and 10271073)
文摘Concave resource allocation problem is an integer programming problem of minimizing a nonincreasing concave function subject to a convex nondecreasing constraint and bounded integer variables. This class of problems are encountered in optimization models involving economies of scale. In this paper, a new hybrid dynamic programming method was proposed for solving concave resource allocation problems. A convex underestimating function was used to approximate the objective function and the resulting convex subproblem was solved with dynamic programming technique after transforming it into a 0-1 linear knapsack problem. To ensure the convergence, monotonicity and domain cut technique was employed to remove certain integer boxes and partition the revised domain into a union of integer boxes. Computational results were given to show the efficiency of the algorithm.
文摘In this study, we aimed to assess the solution quality for location-allocation problems from facilities generated by the software TransCAD®?, a Geographic Information System for Transportation (GIS-T). Such facilities were obtained after using two routines together: Facility Location and Transportation Problem, when compared with optimal solutions from exact mathematical models, based on Mixed Integer Linear Programming (MILP), developed externally for the GIS. The models were applied to three simulations: the first one proposes opening factories and customer allocation in the state of Sao Paulo, Brazil;the second involves a wholesaler and a study of location and allocation of distribution centres for retail customers;and the third one involves the location of day-care centers and allocation of demand (0 - 3 years old children). The results showed that when considering facility capacity, the MILP optimising model presents results up to 37% better than the GIS and proposes different locations to open new facilities.
基金supported by the National Science Fund for Distinguished Young Scholars (62225303)the Fundamental Research Funds for the Central Universities (buctrc202201)+1 种基金China Scholarship Council,and High Performance Computing PlatformCollege of Information Science and Technology,Beijing University of Chemical Technology。
文摘In order to address the output feedback issue for linear discrete-time systems, this work suggests a brand-new adaptive dynamic programming(ADP) technique based on the internal model principle(IMP). The proposed method, termed as IMP-ADP, does not require complete state feedback-merely the measurement of input and output data. More specifically, based on the IMP, the output control problem can first be converted into a stabilization problem. We then design an observer to reproduce the full state of the system by measuring the inputs and outputs. Moreover, this technique includes both a policy iteration algorithm and a value iteration algorithm to determine the optimal feedback gain without using a dynamic system model. It is important that with this concept one does not need to solve the regulator equation. Finally, this control method was tested on an inverter system of grid-connected LCLs to demonstrate that the proposed method provides the desired performance in terms of both tracking and disturbance rejection.
基金Supported by the National Natural Science Foundation of China(61871204,62174033)the Natural Science Foundation of Fujian Province(2017J01767,2020J01843)+1 种基金the Program for New Century Excellent Talents in Fujian Province Universitythe Science and Technology Project of Minjiang University(MYK19017)。
文摘The double row layout problem(DRLP)is to assign facilities on two rows in parallel so that the total cost of material handling among facilities is minimized.Since it is vital to save cost and enhance productivity,the DRLP plays an important role in many application fields.Nevertheless,it is very hard to handle the DRLP because of its complex model.In this paper,we consider a new simplified model for the DRLP(SM-DRLP)and provide a mixed integer programming(MIP)formulation for it.The continuous decision variables of the DRLP are divided into two parts:start points of double rows and adjustable clearances between adjacent facilities.The former one is considered in the new simplified model for the DRLP with the purpose of maintaining solution quality,while the latter one is not taken into account with the purpose of reducing computational time.To evaluate its performance,our SM-DRLP is compared with the model of a general DRLP and the model of another simplified DRLP.The experimental results show the efficiency of our proposed model.
文摘This research develops a solution method for project scheduling represented by a max-plus-linear (MPL) form. Max-plus-linear representation is an approach to model and analyze a class of discrete-event systems, in which the behavior of a target system is represented by linear equations in max-plus algebra. Several types of MPL equations can be reduced to a constraint satisfaction problem (CSP) for mixed integer programming. The resulting formulation is flexible and easy-to-use for project scheduling;for example, we can obtain the earliest output times, latest task-starting times, and latest input times using an MPL form. We also develop a key method for identifying critical tasks under the framework of CSP. The developed methods are validated through a numerical example.
文摘Having lectured in some universities and polytechnics in Nigeria, the researchers observed problems in course allocations. There are no lay-down techniques on how courses should be allocated with respect to the minimum and maximum credit a lecturer should carry in a semester. Many lecturers were overloaded while others were under-loaded. For this reason, dynamic programming model was developed for allocating courses among lecturers in the Nigerian universities using the Department of Statistics, Federal University of Technology Owerri, as a case study. From our analysis, we observed that among all the optimal allocations discovered in the study, the best optimal allocation policy was achieved at the point (1, 2, 1, 2). Allocation of courses in this order will yield an optimal credit hour of 12 per lecturer per semester.
文摘The stochastic dual dynamic programming (SDDP) algorithm is becoming increasingly used. In this paper we present analysis of different methods of lattice construction for SDDP exemplifying a realistic variant of the newsvendor problem, incorporating storage of production. We model several days of work and compare the profits realized using different methods of the lattice construction and the corresponding computer time spent in lattice construction. Our case differs from the known one because we consider not only a multidimensional but also a multistage case with stage dependence. We construct scenario lattice for different Markov processes which play a crucial role in stochastic modeling. The novelty of our work is comparing different methods of scenario lattice construction. We considered a realistic variant of the newsvendor problem. The results presented in this article show that the Voronoi method slightly outperforms others, but the k-means method is much faster overall.
文摘Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing problem is NP-hard. In this paper, it is shown for even graphs that if such a collection satisfies the condition that it minimizes the quantityon the set of all edge-disjoint cycle collections, then it is a maximum cycle packing. The paper shows that the determination of such a packing can be solved by a dynamic programming approach. For its solution, an-shortest path procedure on an appropriate acyclic networkis presented. It uses a particular monotonous node potential.
文摘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.
文摘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.
