Bilevel multiplicative problems: A penalty approach to optimality and a cutting plane based algorithm

Bilevel programming has been proposed for dealing with decision processes involving two decision makers with a hierarchical structure. They are characterised by the existence of two optimisation problems in which the constraint region of the upper level problem is implicitly determined by the lower level optimisation problem. In this paper we focus on the class of bilevel problems in which the upper level objective function is linear multiplicative, the lower level one is linear and the common constraint region is a bounded polyhedron. After replacing the lower level problem by its Karush–Kuhn–Tucker conditions, the existence of an extreme point which solves the problem is proved by using a penalty function approach. Besides, an algorithm based on the successive introduction of valid cutting planes is developed obtaining a global optimal solution. Finally, we generalise the problem by including upper level constraints which involve both level variables.     

Multiobjective bilevel optimization

In this work nonlinear non-convex multiobjective bilevel optimization problems are discussed using an optimistic approach. It is shown that the set of feasible points of the upper level function, the so-called induced set, can be expressed as the set of minimal solutions of a multiobjective optimization problem. This artificial problem is solved by using a scalarization approach by Pascoletti and Serafini combined with an adaptive parameter control based on sensitivity results for this problem. The bilevel optimization problem is then solved by an iterative process using again sensitivity theorems for exploring the induced set and the whole efficient set is approximated. For the case of bicriteria optimization problems on both levels and for a one dimensional upper level variable, an algorithm is presented for the first time and applied to two problems: a theoretical example and a problem arising in applications.     

A genetic algorithm for solving linear fractional bilevel problems

Bilevel programming has been proposed for dealing with decision processes involving two decision makers with a hierarchical structure. They are characterized by the existence of two optimization problems in which the constraint region of the upper level problem is implicitly determined by the lower level optimization problem. In this paper a genetic algorithm is proposed for the class of bilevel problems in which both level objective functions are linear fractional and the common constraint region is a bounded polyhedron. The algorithm associates chromosomes with extreme points of the polyhedron and searches for a feasible solution close to the optimal solution by proposing efficient crossover and mutation procedures. The computational study shows a good performance of the algorithm, both in terms of solution quality and computational time.     

An interval approach based on expectation optimization for fuzzy random bilevel linear programming problems

This paper considers a class of bilevel linear programming problems in which the coefficients of both objective functions are fuzzy random variables. The main idea of this paper is to introduce the Pareto optimal solution in a multi-objective bilevel programming problem as a solution for a fuzzy random bilevel programming problem. To this end, a stochastic interval bilevel linear programming problem is first introduced in terms of α-cuts of fuzzy random variables. On the basis of an order relation of interval numbers and the expectation optimization model, the stochastic interval bilevel linear programming problem can be transformed into a multi-objective bilevel programming problem which is solved by means of weighted linear combination technique. In order to compare different optimal solutions depending on different cuts, two criterions are given to provide the preferable optimal solutions for the upper and lower level decision makers respectively. Finally, a production planning problem is given to demonstrate the feasibility of the proposed approach.     

Linear bilevel programming with interval coefficients

In this paper, we address linear bilevel programs when the coefficients of both objective functions are interval numbers. The focus is on the optimal value range problem which consists of computing the best and worst optimal objective function values and determining the settings of the interval coefficients which provide these values. We prove by examples that, in general, there is no precise way of systematizing the specific values of the interval coefficients that can be used to compute the best and worst possible optimal solutions. Taking into account the properties of linear bilevel problems, we prove that these two optimal solutions occur at extreme points of the polyhedron defined by the common constraints. Moreover, we develop two algorithms based on ranking extreme points that allow us to compute them as well as determining settings of the interval coefficients which provide the optimal value range.     

Finding an efficient solution to linear bilevel programming problem: An effective approach

Multilevel programming is developed to solve the decentralized problem in which decision makers (DMs) are often arranged within a hierarchical administrative structure. The linear bilevel programming (BLP) problem, i.e., a special case of multilevel programming problems with a two level structure, is a set of nested linear optimization problems over polyhedral set of constraints. Two DMs are located at the different hierarchical levels, both controlling one set of decision variables independently, with different and perhaps conflicting objective functions. One of the interesting features of the linear BLP problem is that its solution may not be Paretooptimal. There may exist a feasible solution where one or both levels may increase their objective values without decreasing the objective value of any level. The result from such a system may be economically inadmissible. If the decision makers of the two levels are willing to find an efficient compromise solution, we propose a solution procedure which can generate effcient solutions, without finding the optimal solution in advance. When the near-optimal solution of the BLP problem is used as the reference point for finding the efficient solution, the result can be easily found during the decision process.     

A new approach for solving linear bilevel problems using genetic algorithms

Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. This paper develops a genetic algorithm for the linear bilevel problem in which both objective functions are linear and the common constraint region is a polyhedron. Taking into account the existence of an extreme point of the polyhedron which solves the problem, the algorithm aims to combine classical extreme point enumeration techniques with genetic search methods by associating chromosomes with extreme points of the polyhedron. The numerical results show the efficiency of the proposed algorithm. In addition, this genetic algorithm can also be used for solving quasiconcave bilevel problems provided that the second level objective function is linear.     

A cutting plane method for bilevel linear programming with interval coefficients

This article considers the bilevel linear programming problem with interval coefficients in both objective functions. We propose a cutting plane method to solve such a problem. In order to obtain the best and worst optimal solutions, two types of cutting plane methods are developed based on the fact that the best and worst optimal solutions of this kind of problem occur at extreme points of its constraint region. The main idea of the proposed methods is to solve a sequence of linear programming problems with cutting planes that are successively introduced until the best and worst optimal solutions are found. Finally, we extend the two algorithms proposed to compute the best and worst optimal solutions of the general bilevel linear programming problem with interval coefficients in the objective functions as well as in the constraints.     

Scalarization and optimality conditions for vector equilibrium problems

In this paper, we investigated vector equilibrium problems and gave the scalarization results for weakly efficient solutions, Henig efficient solutions, and globally efficient solutions to the vector equilibrium problems without the convexity assumption. Using nonsmooth analysis and the scalarization results, we provided the necessary conditions for weakly efficient solutions, Henig efficient solutions, globally efficient solutions, and superefficient solutions to vector equilibrium problems. By the assumption of convexity, we gave sufficient conditions for those solutions. As applications, we gave the necessary and sufficient conditions for corresponding solutions to vector variational inequalities and vector optimization problems.     

Bilevel problems over polyhedra with extreme point optimal solutions

Bilevel programming involves two optimization problems where the constraint region of the upper level problem is implicitly determined by another optimization problem. In this paper we focus on bilevel problems over polyhedra with upper level constraints involving lower level variables. On the one hand, under the uniqueness of the optimal solution of the lower level problem, we prove that the fact that the objective functions of both levels are quasiconcave characterizes the property of the existence of an extreme point of the polyhedron defined by the whole set of constraints which is an optimal solution of the bilevel problem. An example is used to show that this property is in general violated if the optimal solution of the lower level problem is not unique. On the other hand, if the lower level objective function is not quasiconcave but convex quadratic, assuming the optimistic approach we prove that the optimal solution is attained at an extreme point of an ??enlarged?? polyhedron.     

The bilevel linear/linear fractional programming problem

Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. In this paper we consider the bilevel linear/linear fractional programming problem in which the objective function of the first level is linear, the objective function of the second level is linear fractional and the feasible region is a polyhedron. For this problem we prove that an optimal solution can be found which is an extreme point of the polyhedron. Moreover, taking into account the relationship between feasible solutions to the problem and bases of the technological coefficient submatrix associated to variables of the second level, an enumerative algorithm is proposed that finds a global optimum to the problem.     

带有限反馈下层的二层规划问题的部分合作模型

对下层最优反馈为离散有限多个的二层规划问题的部分合作模型进行探讨. 当下层的合作程度依赖于上层的决策变量时, 给出一个确定合作系数函数的一般方法, 进而得到一个新的部分合作模型. 在适当地假设下, 可保证所给的部分合作模型一定可以找到比悲观解要好的解, 并结合新的部分合作模型对原不适定问题进行分析, 得到了一些有益的结论. 最后以实际算例说明了所给部分合作模型的可行性.     

Solving discrete linear bilevel optimization problems using the optimal value reformulation

In this article, we consider two classes of discrete bilevel optimization problems which have the peculiarity that the lower level variables do not affect the upper level constraints. In the first case, the objective functions are linear and the variables are discrete at both levels, and in the second case only the lower level variables are discrete and the objective function of the lower level is linear while the one of the upper level can be nonlinear. Algorithms for computing global optimal solutions using Branch and Cut and approximation of the optimal value function of the lower level are suggested. Their convergence is shown and we illustrate each algorithm via an example.     

Optimality conditions for mixed discrete bilevel optimization problems

In this article, we consider bilevel optimization problems with discrete lower level and continuous upper level problems. Taking into account both approaches (optimistic and pessimistic) which have been developed in the literature to deal with this type of problem, we derive some conditions for the existence of solutions. In the case where the lower level is a parametric linear problem, the bilevel problem is transformed into a continuous one. After that, we are able to discuss local optimality conditions using tools of variational analysis for each of the different approaches. Finally, we consider a simple application of our results namely the bilevel programming problem with the minimum spanning tree problem in the lower level.     

Necessary Optimality Conditions and a New Approach to Multiobjective Bilevel Optimization Problems

Multiobjective optimization problems typically have conflicting objectives, and a gain in one objective very often is an expense in another. Using the concept of Pareto optimality, we investigate a multiobjective bilevel optimization problem (say, P). Our approach consists of proving that P is locally equivalent to a single level optimization problem, where the nonsmooth Mangasarian–Fromovitz constraint qualification may hold at any feasible solution. With the help of a special scalarization function introduced in optimization by Hiriart–Urruty, we convert our single level optimization problem into another problem and give necessary optimality conditions for the initial multiobjective bilevel optimization problem P.     

Robustness to uncertain optimization using scalarization techniques and relations to multiobjective optimization

In this paper, we propose two kinds of robustness concepts by virtue of the scalarization techniques (Benson’s method and elastic constraint method) in multiobjective optimization, which can be characterized as special cases of a general non-linear scalarizing approach. Moreover, we introduce both constrained and unconstrained multiobjective optimization problems and discuss their relations to scalar robust optimization problems. Particularly, optimal solutions of scalar robust optimization problems are weakly efficient solutions for the unconstrained multiobjective optimization problem, and these solutions are efficient under uniqueness assumptions. Two examples are employed to illustrate those results. Finally, the connections between robustness concepts and risk measures in investment decision problems are also revealed.     

An Objective Penalty Function of Bilevel Programming

Penalty methods are very efficient in finding an optimal solution to constrained optimization problems. In this paper, we present an objective penalty function with two penalty parameters for inequality constrained bilevel programming under the convexity assumption to the lower level problem. Under some conditions, an optimal solution to a bilevel programming defined by the objective penalty function is proved to be an optimal solution to the original bilevel programming. Moreover, based on the objective penalty function, an algorithm is developed to obtain an optimal solution to the original bilevel programming, with its convergence proved under some conditions.     

关于二层规划的逼近问题

下层问题以上层决策变量作为参数,而上层是以下层问题的最优值作为响应 的一类最优化问题——二层规划问题。我们给出了由一系列此类二层规划去逼近原二层规划的逼近法,得到了这种逼近的一些有趣的结果.     

二层决策问题的灵敏度分析(2)

二层决策系统包含着两个最优化决策问题,其中上层决策问题的目标值是由下层决策的解所隐含地确定的.本文研究了二层决策问题的另一方面的灵敏度分析问题,讨论了上层决策者的价值系数发生变化而二层决策问题的最优解不变所产生的灵敏度分析问题.为了确定二层决策问题价值系数发生变化的范围,首先我们给出了灵敏度分析的基本方法,结合“k th-best”算法我们又给出了灵敏度分析的操作步骤.在所确定的变化范围内,价值系数的变化,不会引起二层决策问题的全局最优解的变化,从而为决策者提供了相对稳定的决策方案.最后我们给出了数值实例,它表明本文所给出的灵敏度分析的方法是正确的.     

A Revised Pascoletti–Serafini Scalarization Method for Multiobjective Optimization Problems

The presented study deals with the scalarization techniques for solving multiobjective optimization problems. The Pascoletti–Serafini scalarization technique is considered, and it is attempted to sidestep two weaknesses of this method, namely the inflexibility of the constraints and the difficulties of checking proper efficiency. To this end, two modifications for the Pascoletti–Serafini scalarization technique are proposed. First, by including surplus variables in the constraints and penalizing the violations in the objective function, the inflexibility of the constraints is resolved. Moreover, by including slack variables in the constraints, easy-to-check statements on proper efficiency are obtained. Thereafter, the two proposed modifications are combined to obtain the revised Pascoletti–Serafini scalarization method. Theorems are provided on the relation of (weakly, properly) efficient solutions of the multiobjective optimization problem and optimal solutions of the proposed scalarized problems. All the provided results are established with no convexity assumption. Moreover, the capability of the proposed approaches is demonstrated through numerical examples.