Solution for integer linear bilevel programming problems using orthogonal genetic algorithm

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 DUAL-RELAX PENALTY FUNCTION APPROACH FOR SOLVING NONLINEAR BILEVEL PROGRAMMING WITH LINEAR LOWER LEVEL PROBLEM

The penalty function method, presented many years ago, is an important nu- merical method for the mathematical programming problems. In this article, we propose a dual-relax penalty function approach, which is significantly different from penalty func- tion approach existing for solving the bilevel programming, to solve the nonlinear bilevel programming with linear lower level problem. Our algorithm will redound to the error analysis for computing an approximate solution to the bilevel programming. The error estimate is obtained among the optimal objective function value of the dual-relax penalty problem and of the original bilevel programming problem. An example is illustrated to show the feasibility of the proposed approach.

New partial cooperation model for bilevel programming problems

Partial cooperation models are studied for many years to solve the bilevel programming problems where the follower’s optimal reaction is not unique. However, in these existed models, the follower’s cooperation level does not depend on the leader’s decision. A new model is proposed to solve this deficiency. It is proved the feasibility of the new model when the reaction set of the lower level is lower semicontinuous. And the numerical results show that the new model has optimal solutions when the reaction set of the lower level is discrete, lower semi-continuous and non-lower semi-continuous.

Orthogonal genetic algorithm for solving quadratic bilevel programming problems

A quadratic bilevel programming problem is transformed into a single level complementarity slackness problem by applying Karush-Kuhn-Tucker（KKT） conditions.To cope with the complementarity constraints,a binary encoding scheme is adopted for KKT multipliers,and then the complementarity slackness problem is simplified to successive quadratic programming problems,which can be solved by many algorithms available.Based on 0-1 binary encoding,an orthogonal genetic algorithm,in which the orthogonal experimental design with both two-level orthogonal array and factor analysis is used as crossover operator,is proposed.Numerical experiments on 10 benchmark examples show that the orthogonal genetic algorithm can find global optimal solutions of quadratic bilevel programming problems with high accuracy in a small number of iterations.

Exponential distribution-based genetic algorithm for solving mixed-integer bilevel programming problems

Two classes of mixed-integer nonlinear bilevel programming problems are discussed. One is that the follower＇s functions are separable with respect to the follower＇s variables, and the other is that the follower＇s functions are convex if the follower＇s variables are not restricted to integers. A genetic algorithm based on an exponential distribution is proposed for the aforementioned problems. First, for each fixed leader＇s variable x, it is proved that the optimal solution y of the follower＇s mixed-integer programming can be obtained by solving associated relaxed problems, and according to the convexity of the functions involved, a simplified branch and bound approach is given to solve the follower＇s programming for the second class of problems. Furthermore, based on an exponential distribution with a parameter λ, a new crossover operator is designed in which the best individuals are used to generate better offspring of crossover. The simulation results illustrate that the proposed algorithm is efficient and robust.

THE CONVERGENCE OF APPROACH PENALTY FUNCTION METHOD FOR APPROXIMATE BILEVEL PROGRAMMING PROBLEM

In this paper, a new algorithm-approximate penalty function method is designed, which can be used to solve a bilevel optimization problem with linear constrained function. In this kind of bilevel optimization problem. the evaluation of the objective function is very difficult, so that only their approximate values can be obtained. This algorithm is obtained by combining penalty function method and approximation in bilevel programming. The presented algorithm is completely different from existing methods. That convergence for this algorithm is proved.

Genetic Algorithm for Solving Quadratic Bilevel Programming Problem

By applying Kuhn-Tucker condition the quadratic bilevel programming, a class of bilevel programming, is transformed into a single level programming problem, which can be simplified by some rule. So we can search the optimal solution in the feasible region, hence reduce greatly the searching space. Numerical experiments on several literature problems show that the new algorithm is both feasible and effective in practice.

New partial cooperation model for ill-posed bilevel programming problem via satisfactory degree

Partial cooperation formulation is a more viable option than optimistic＇s and pessimistic＇s to solve an ill-posed bilevel programming problem.Aboussoror＇s partial cooperation model uses a constant as a cooperation index to describe the degree of follower＇s cooperation.The constant only indicates the leader＇s expectation coefficient for the follower＇s action,not the follower＇s own willingness.To solve this situation,a new model is proposed by using the follower＇s satisfactory degree as the cooperation degree.Then,because this new cooperation degree is a function which is dependent on the leader＇s choice and decided by the follower＇s satisfactory degree,this paper proves such proposed model not only leads an optimal value between the optimistic value and pessimistic＇s,but also leads a more satisfactory solution than Aboussoror＇s.Finally,a numerical experiment is given to demonstrate the feasibility of this new model.

Discrete differential evolution algorithm for integer linear bilevel programming problems

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.

Maximum Entropy Approach for Solving Pessimistic Bilevel Programming Problems

Bilevel programming problems are of growing interest both from theoretical and practical points of view.In this paper,we study a pessimistic bilevel programming problem in which the set of solutions of the lower level problem is discrete.We first transform such a problem into a single-level optimization problem by using the maximum-entropy techniques.We then present a maximum entropy approach for solving the pessimistic bilevel programming problem.Finally,two examples illustrate the feasibility of the proposed approach.

Exact Penalty Method for the Nonlinear Bilevel Programming Problem

In this paper,following the method of replacing the lower level problem with its Kuhn-Tucker optimality condition,we transform the nonlinear bilevel programming problem into a normal nonlinear programming problem with the complementary slackness constraint condition.Then,we get the penalized problem of the normal nonlinear programming problem by appending the complementary slackness condition to the upper level objective with a penalty.We prove that this penalty function is exact and the penalized problem and the nonlinear bilevel programming problem have the same global optimal solution set.Finally,we propose an algorithm for the nonlinear bilevel programming problem.The numerical results show that the algorithm is feasible and efficient.

A New Variant of Penalty Method for Weak Linear Bilevel Programming Problems

We present a new variant of penalty method, which is different from the existing penalty methods, for solving the weak linear bilevel programming problems. We then transform it into a single-level optimization problem using Kuhn-Tucker optimality condition and discuss the relations between them. Finally, two examples are used to illustrate the feasibility of the proposed penalty method.

A Branch and Bound-Based Algorithm for the Weak Linear Bilevel Programming Problems

Most real-world optimization problems are hierarchical involving non-cooperative objectives. Many of these problems can be formulated in terms of the first（upper level） objective function being minimized over the solution set mapping of the second（lower level） optimization problem. Often the upper level decision maker is risk-averse. The resulting class of problem is named weak bilevel programming problem. This paper presents a new algorithm which embeds a penalty function method into a branch and bound algorithm to deal with a weak linear bilevel programming problem. An example illustrates the feasibility of the proposed algorithm.

A Trust Region Algorithm for Solving Bilevel Programming Problems

In this paper, we present a new trust region algorithm for a nonlinear bilevel programming problem by solving a series of its linear or quadratic approximation subproblems. For the nonlinear bilevel programming problem in which the lower level programming problem is a strongly convex programming problem with linear constraints, we show that each accumulation point of the iterative sequence produced by this algorithm is a stationary point of the bilevel programming problem.

An Objective Penalty Method for Optimistic Bilevel Programming Problems

In this paper,we consider an optimistic nonlinear bilevel programming problem.Under some conditions,we first show that the sequence of solutions to penalty problems converges to the optimal solution of the original bilevel programming problem.We then present an objective penalty method to solve such a problem.Finally,some numerical experiments are performed to illustrate its feasibility.

A NEW DESCENT ALGORITHM FOR SOLVING QUADRATIC BILEVEL PROGRAMMING PROBLEMS

In this paper, we give a descent algorithm for solving quadratic bilevel programming problems. It is proved that the descent algorithm finds a locally optimal solution to a quadratic bilevel programming problem in a finite number of iterations. Two numerical examples are given to illustrate this algorithm.

Global convergent algorithm for the bilevel linear fractional-linear programming based on modified convex simplex 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 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.

An adaptive genetic algorithm for solving bilevel linear programming problem

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.

Uncertain bilevel knapsack problem and its solution

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 P-E uncertain solution is applied to an armaments transportation problem.

Coordinated planning for flexible interconnection and energy storage system in low-voltage distribution networks to improve the accommodation capacity of photovoltaic

The increasing proportion of distributed photovoltaics(DPVs)and electric vehicle charging stations in low-voltage distribution networks(LVDNs)has resulted in challenges such as distribution transformer overloads and voltage violations.To address these problems,we propose a coordinated planning method for flexible interconnections and energy storage systems(ESSs)to improve the accommodation capacity of DPVs.First,the power-transfer characteristics of flexible interconnection and ESSs are analyzed.The equipment costs of the voltage source converters(VSCs)and ESSs are also analyzed comprehensively,considering the differences in installation and maintenance costs for different installation locations.Second,a bilevel programming model is established to minimize the annual comprehensive cost and yearly total PV curtailment capacity.Within this framework,the upper-level model optimizes the installation locations and capacities of the VSCs and ESSs,whereas the lower-level model optimizes the operating power of the VSCs and ESSs.The proposed model is solved using a non-dominated sorting genetic algorithm with an elite strategy(NSGA-II).The effectiveness of the proposed planning method is validated through an actual LVDN scenario,which demonstrates its advantages in enhancing PV accommodation capacity.In addition,the economic benefits of various planning schemes with different flexible interconnection topologies and different PV grid-connected forms are quantitatively analyzed,demonstrating the adaptability of the proposed coordinated planning method.