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 discrete differential evolution algorithm combined with the branch and bound method is developed to solve the integer linear bilevel programming problems, in which both upper level and lower level variables are forc...A discrete differential evolution algorithm combined with the branch and bound method is developed to solve the integer linear bilevel programming problems, in which both upper level and lower level variables are forced to be integer. An integer coding for upper level variables is adopted, and then a discrete differential evolution algorithm with an improved feasibility-based comparison is developed to directly explore the integer solution at the upper level. For a given upper level integer variable, the lower level integer programming problem is solved by the existing branch and bound algorithm to obtain the optimal integer solution at the lower level. In the same framework of the algorithm, two other constraint handling methods, i.e. the penalty function method and the feasibility-based comparison method are also tested. The experimental results demonstrate that the discrete differential evolution algorithm with different constraint handling methods is effective in finding the global optimal integer solutions, but the improved constraint handling method performs better than two compared constraint handling methods.展开更多
Linear bilevel programming deals with optimization problems in which the constraint region is implicitly determined by another optimization problem. This paper presents a new algorithm for solving linear bilevel progr...Linear bilevel programming deals with optimization problems in which the constraint region is implicitly determined by another optimization problem. This paper presents a new algorithm for solving linear bilevel programs. A numerical example is given to illustrate this method.展开更多
A global convergent algorithm is proposed to solve bilevel linear fractional-linear programming, which is a special class of bilevel programming. In our algorithm, replacing the lower level problem by its dual gap equ...A global convergent algorithm is proposed to solve bilevel linear fractional-linear programming, which is a special class of bilevel programming. In our algorithm, replacing the lower level problem by its dual gap equaling to zero, the bilevel linear fractional-linear programming is transformed into a traditional sin- gle level programming problem, which can be transformed into a series of linear fractional programming problem. Thus, the modi- fied convex simplex method is used to solve the infinite linear fractional programming to obtain the global convergent solution of the original bilevel linear fractional-linear programming. Finally, an example demonstrates the feasibility of the proposed algorithm.展开更多
Bilevel linear programming, which consists of the objective functions of the upper level and lower level, is a useful tool for modeling decentralized decision problems. Various methods are proposed for solving this pr...Bilevel linear programming, which consists of the objective functions of the upper level and lower level, is a useful tool for modeling decentralized decision problems. Various methods are proposed for solving this problem. Of all the algorithms, the ge- netic algorithm is an alternative to conventional approaches to find the solution of the bilevel linear programming. In this paper, we describe an adaptive genetic algorithm for solving the bilevel linear programming problem to overcome the difficulty of determining the probabilities of crossover and mutation. In addition, some techniques are adopted not only to deal with the difficulty that most of the chromosomes maybe infeasible in solving constrained optimization problem with genetic algorithm but also to improve the efficiency of the algorithm. The performance of this proposed algorithm is illustrated by the examples from references.展开更多
For the optimum price problem of charging for effluent, this paper analyzes the optimal Pigovian Tax and the serious information asymmetry problem existing in the application process of optimal Pigovian Tax, which is ...For the optimum price problem of charging for effluent, this paper analyzes the optimal Pigovian Tax and the serious information asymmetry problem existing in the application process of optimal Pigovian Tax, which is predominant in theory. Then the bilevel system optimizing decision-making theory is applied to give bilevel linear programming decision-making model of charging for effluent, in which the government (environmental protection agency) acts as the upper level decision-making unit and the polluting enterprises act as the lower level decision-making unit. To some extent, the model avoids the serious information asymmetry between the government and the polluting enterprises on charging for effluent.展开更多
In this papert a cutting planelnethod is presented for solving the linear BLPP.An optimality criterion for the linear BLPP is derived from two related linear programsconstructed by using the complementarity conditions...In this papert a cutting planelnethod is presented for solving the linear BLPP.An optimality criterion for the linear BLPP is derived from two related linear programsconstructed by using the complementarity conditions for the second level problem. Twotypes of cutting planes are developed in order to deal with different situations and to obtaina maximal efficiency. The method makes use of the special cuts and the implicit vertexenumeration idea to avoid some drawbacks in some existing cuttillg plane methods. Thealgorithm can be proved to be finitely convergent.展开更多
In this paper, we study sensitivity analysis of bilevel linear programming. Twocases of the leader’s objective function and the right-hand side of the constraints includingparameters are discussed separately. We pres...In this paper, we study sensitivity analysis of bilevel linear programming. Twocases of the leader’s objective function and the right-hand side of the constraints includingparameters are discussed separately. We presellt a necessary and sufficient optimalitycondition for an optimal solution to a bilevel linear programming problem and its equivalentexpression in nonconvex quadratic programming. The necessary and sufficient conditionsare proposed to guarantee that the current optimal solution or the corresponding basisremains optimal when the parameters vary. An algorithm is also proposed to determinethe set of the parameters which leaves the current optimal solution optimal or -optimal.展开更多
基金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.
基金supported by the Natural Science Basic Research Plan in Shaanxi Province of China(2013JM1022)the Fundamental Research Funds for the Central Universities(K50511700004)
文摘A discrete differential evolution algorithm combined with the branch and bound method is developed to solve the integer linear bilevel programming problems, in which both upper level and lower level variables are forced to be integer. An integer coding for upper level variables is adopted, and then a discrete differential evolution algorithm with an improved feasibility-based comparison is developed to directly explore the integer solution at the upper level. For a given upper level integer variable, the lower level integer programming problem is solved by the existing branch and bound algorithm to obtain the optimal integer solution at the lower level. In the same framework of the algorithm, two other constraint handling methods, i.e. the penalty function method and the feasibility-based comparison method are also tested. The experimental results demonstrate that the discrete differential evolution algorithm with different constraint handling methods is effective in finding the global optimal integer solutions, but the improved constraint handling method performs better than two compared constraint handling methods.
文摘Linear bilevel programming deals with optimization problems in which the constraint region is implicitly determined by another optimization problem. This paper presents a new algorithm for solving linear bilevel programs. A numerical example is given to illustrate this method.
基金supported by the National Natural Science Foundation of China(70771080)the Special Fund for Basic Scientific Research of Central Colleges+2 种基金China University of Geosciences(Wuhan) (CUG090113)the Research Foundation for Outstanding Young TeachersChina University of Geosciences(Wuhan)(CUGQNW0801)
文摘A global convergent algorithm is proposed to solve bilevel linear fractional-linear programming, which is a special class of bilevel programming. In our algorithm, replacing the lower level problem by its dual gap equaling to zero, the bilevel linear fractional-linear programming is transformed into a traditional sin- gle level programming problem, which can be transformed into a series of linear fractional programming problem. Thus, the modi- fied convex simplex method is used to solve the infinite linear fractional programming to obtain the global convergent solution of the original bilevel linear fractional-linear programming. Finally, an example demonstrates the feasibility of the proposed algorithm.
基金the National Natural Science Foundation of China(Nos.60574071 and70771080)
文摘Bilevel linear programming, which consists of the objective functions of the upper level and lower level, is a useful tool for modeling decentralized decision problems. Various methods are proposed for solving this problem. Of all the algorithms, the ge- netic algorithm is an alternative to conventional approaches to find the solution of the bilevel linear programming. In this paper, we describe an adaptive genetic algorithm for solving the bilevel linear programming problem to overcome the difficulty of determining the probabilities of crossover and mutation. In addition, some techniques are adopted not only to deal with the difficulty that most of the chromosomes maybe infeasible in solving constrained optimization problem with genetic algorithm but also to improve the efficiency of the algorithm. The performance of this proposed algorithm is illustrated by the examples from references.
基金the National Social Science Foundation of China(Grant No.04BJY026).
文摘For the optimum price problem of charging for effluent, this paper analyzes the optimal Pigovian Tax and the serious information asymmetry problem existing in the application process of optimal Pigovian Tax, which is predominant in theory. Then the bilevel system optimizing decision-making theory is applied to give bilevel linear programming decision-making model of charging for effluent, in which the government (environmental protection agency) acts as the upper level decision-making unit and the polluting enterprises act as the lower level decision-making unit. To some extent, the model avoids the serious information asymmetry between the government and the polluting enterprises on charging for effluent.
文摘In this papert a cutting planelnethod is presented for solving the linear BLPP.An optimality criterion for the linear BLPP is derived from two related linear programsconstructed by using the complementarity conditions for the second level problem. Twotypes of cutting planes are developed in order to deal with different situations and to obtaina maximal efficiency. The method makes use of the special cuts and the implicit vertexenumeration idea to avoid some drawbacks in some existing cuttillg plane methods. Thealgorithm can be proved to be finitely convergent.
文摘In this paper, we study sensitivity analysis of bilevel linear programming. Twocases of the leader’s objective function and the right-hand side of the constraints includingparameters are discussed separately. We presellt a necessary and sufficient optimalitycondition for an optimal solution to a bilevel linear programming problem and its equivalentexpression in nonconvex quadratic programming. The necessary and sufficient conditionsare proposed to guarantee that the current optimal solution or the corresponding basisremains optimal when the parameters vary. An algorithm is also proposed to determinethe set of the parameters which leaves the current optimal solution optimal or -optimal.
基金This paper was partly supported by National Outstanding Young Investigator Grant (70225005) of National Natural Science Foundation of China and Teaching & Research Award Program for Outstanding Young Teachers (2001) in Higher Education Institutions of Ministry of Education, China.
