Advances in Bi-level Programming with Mixed-Integer or Nonlinear Lower Level

By Alireza Shefaei

Application of bi-level programming (BP) in the modeling of power systems problems has increased recently due to the complicated issues concerning power systems. Network expansion planning, market clearing, and defense against cyber-attacks can be mentioned as some of these issues. The global optimum solution of BP problems can be guaranteed when their lower level have modeled as a linear programming (LP) problem. On the other hand, BP problems with a mixed-integer, nonlinear, or mixed-integer nonlinear model cannot be solved to optimality. The worse problem is that many of the problems in power system are modeled as mixed-integer nonlinear programming (MINLP). The non-convexity of these models prevents using any type of LP-based approaches such as using Karush–Kuhn–Tucker (KKT) conditions of lower level or duality theory based methods. However, significant progress has been achieved in the solution of BP problems with a lower level MINLP by employing decomposition techniques, relaxation or approximation methods, and convexification.

In all fields and applications, the problem of determining a minimum or maximum value of a quantity, means that the problem can be modeled as an optimization problem. These problems have an objective function, which must be minimized or maximized and a series of constraints which must be satisfied. A decision-maker can solve an optimization problem and reach the optimum results and the values of the corresponding variables. Now assume another objective function is posed in one of the constraints of the optimization problem. This type of optimization problem is called bi-level. From the perspective of the decision-maker, there is another decision-maker with a conflicting objective. This look at the problem is mainly taken in game theory in which decision-makers in the upper and lower levels are called leader and follower, respectively.

The solution method of bi-level optimization problems is challenging “proportionally” to the typical optimization problems. The most conventional method for solving a BP problem is its reduction to a single level problem. For this purpose, the lower level of the problem which has been placed on one of the constraints of the main problem is replaced with its KKT optimality conditions. In the same way, the lower level problem is taken over from: the constraints of original lower level, the constraints of dual problem of lower level, and equality constraint of strong duality theory. In both of these approaches, a nonlinear constraint arises, which renders difficult the solution of the problem. Due to the bi-linearity of the nonlinear constraint, it can be solved to optimality by reformulation of the occurring single level problem. Nonetheless, this is true only in the cases that the lower level is a LP problem.

When a BP problem has a discrete variable or nonlinear constraint in the lower level, the problem cannot be changed to single level by the above mentioned methods. In these cases, the problem must be tackled using other approaches, such as decomposition techniques, relaxation or approximation methods, and convexification.

Decomposition techniques have been used to cope with large-scale and decomposable programming problems for years. These techniques decompose complicated variables and constraints and solve the resulting problem in an iterative procedure. A programming problem with decomposable structure can be treated as BP that its lower level is a decomposed part of the main problem. So if a decomposition technique can solve the given programming problem, then it can solve a BP problem.

Relaxation or approximation methods are used to find solution for BP problems with an MINLP model for the lower level problem. These methods solve the BP problem in two different manners. In the first approach, they reduce the problem to a single level one, and in the other, they solve the problem in its original form iteratively. Relaxation methods are used when the lower level has mixed-integer variables. Since these variables do not allow the application of any types of methods for continuous variables, such as those mentioned about LP models, the methods relax them from integer to continuous values. As another alternative, relaxation methods fix integer variables to given feasible integer values. Approximation and convexification methods are utilized to handle nonlinear equations. A nonlinear constraint is approximated with a simpler equation or the search space of the problem is approximated with a convex or at least polynomial region. A combination of the stated methods can be used to lower level MINLP problems.

Recently, application of BP in the modeling of power systems problems has gathered much interest, due to the modernization of conventional power systems. An interesting example of issues in power systems that are modeled by BP are network expansion planning in transmission and distribution systems. In its general model, the upper level is optimized by the system planner and the lower level is optimized by the market operator. Also, in the electricity market, retailers and consumers comprise, essentially, a bi-level game to reach a market clearing price. Determining countermeasures to malicious attacks against power system may also be modeled as a BP; the attacker at the upper level seeks to maximize its attack influence and the operator at the lower level operates the system to minimize damages cost by the attack. Theses examples show the application of BP in power system modeling and the growing trend of adoption of this optimization approach to more realistically represent actual situations. Also, since the lower level of almost all of these problems is an operational problem that may include power flow equality constraints and integer variables related to connection and deployment of equipment, it is necessary to solve a mixed-integer, nonlinear, or mixed-integer nonlinear problem. Taking into account the progresses made in dealing with BP problem with lower level MINLP, more reliable algorithms are needed to achieve optimal solutions within a reasonable time and computing resource bounds.

This article was edited by Dr. Panayiotis (Panos) Moutis.

Contributors