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.     

Stochastic second-order-cone complementarity problems: expected residual minimization formulation and its applications

This paper considers a class of stochastic second-order-cone complementarity problems (SSOCCP), which are generalizations of the noticeable stochastic complementarity problems and can be regarded as the Karush–Kuhn–Tucker conditions of some stochastic second-order-cone programming problems. Due to the existence of random variables, the SSOCCP may not have a common solution for almost every realization . In this paper, motivated by the works on stochastic complementarity problems, we present a deterministic formulation called the expected residual minimization formulation for SSOCCP. We present an approximation method based on the Monte Carlo approximation techniques and investigate some properties related to existence of solutions of the ERM formulation. Furthermore, we experiment some practical applications, which include a stochastic natural gas transmission problem and a stochastic optimal power flow problem in radial network.     

下层独立的一主多从双层随机线性规划问题研究

Herminia I.Calvete等研究了一主多从双层确定性线性规划问题,证明了这类问题等价于一类常规的双层线性规划问题.本文在此基础上,推广确定型的问题到随机型优化情况,考虑了一类下层优化相互独立的一主多从双层随机优化问题(SLBMFP).在特定的随机变量分布条件下,理论上证明了该类问题可以转化为一主一从双层确定性优化问题.本文的研究对于求解一主多从双层随机优化模型,解决此类模型在实际应用中的问题具有一定的意义.     

Two-Stage Approach for Quantitative Policy Analysis Using Bilevel Programming

Quantitative policy analysis problems with hierarchical decision-making can be modeled as bilevel mathematical programming problems. In general, the solution of these models is very difficult; however, special cases exist in which an optimal solution can be obtained by ordinary mathematical programming techniques. In this paper, a two-stage approach for the formulation, construction, solution, and usage of bilevel policy problem is presented. An outline of an example for analyzing Israel's public expenditure policy is also given.     

Parametric global optimisation for bilevel programming

We propose a global optimisation approach for the solution of various classes of bilevel programming problems (BLPP) based on recently developed parametric programming algorithms. We first describe how we can recast and solve the inner (follower’s) problem of the bilevel formulation as a multi-parametric programming problem, with parameters being the (unknown) variables of the outer (leader’s) problem. By inserting the obtained rational reaction sets in the upper level problem the overall problem is transformed into a set of independent quadratic, linear or mixed integer linear programming problems, which can be solved to global optimality. In particular, we solve bilevel quadratic and bilevel mixed integer linear problems, with or without right-hand-side uncertainty. A number of examples are presented to illustrate the steps and details of the proposed global optimisation strategy.     

A bilevel programming approach to the travelling salesman problem

We show that the travelling salesman problem is polynomially reducible to a bilevel toll optimization program. Based on natural bilevel programming techniques, we recover the lifted Miller-Tucker-Zemlin constraints. Next, we derive an O(n²) multi-commodity extension whose LP relaxation is comparable to the exponential formulation of Dantzig, Fulkerson and Johnson.     

A linearization approach to solve the natural gas cash-out bilevel problem

In this article, we discuss a particular imbalance cash-out problem arising in the natural gas supply chain. This problem was created by the liberalization laws that regulate deals between a natural gas shipping company and a pipeline operator. The problem was first modeled as a bilevel nonlinear mixed-integer problem that considers the cash-out penalization for the final imbalance occurring in the system. We extend the original problem’s upper level objective function by including additional terms accounting for the gas shipping company’s daily actions aimed at taking advantage of the price variations. Then we linearize all the constraints at both levels in an equivalent way so as to make easier their numerical solution. The results of numerical experiments are compared with those obtained by the inexact penalization method proposed by the authors in previous papers.     

On the Convergence of Coderivative of SAA Solution Mapping for a Parametric Stochastic Variational Inequality

The aim of this paper is to investigate the convergence properties for Mordukhovich’s coderivative of the solution map of the sample average approximation (SAA) problem for a parametric stochastic variational inequality with equality and inequality constraints. The notion of integrated deviation is introduced to characterize the outer limit of a sequence of sets. It is demonstrated that, under suitable conditions, both the cosmic deviation and the integrated deviation between the coderivative of the solution mapping to SAA problem and that of the solution mapping to the parametric stochastic variational inequality converge almost surely to zero as the sample size tends to infinity. Moreover, the exponential convergence rate of coderivatives of the solution maps to the SAA parametric stochastic variational inequality is established. The results are used to develop sufficient conditions for the consistency of the Lipschitz-like property of the solution map of SAA problem and the consistency of stationary points of the SAA estimator for a stochastic bilevel program.     

Reduction of the bilevel stochastic optimization problem with quantile objective function to a mixed‐integer problem

The paper is devoted to the stochastic optimistic bilevel optimization problem with quantile criterion in the upper level problem. If the probability distribution is finite, the problem can be transformed into a mixed‐integer nonlinear optimization problem. We formulate assumptions guaranteeing that an optimal solution exists. A production planning problem is used to illustrate usefulness of the model. Copyright © 2017 John Wiley & Sons, Ltd.     

Bilevel programming and the separation problem

In recent years, branch-and-cut algorithms have become firmly established as the most effective method for solving generic mixed integer linear programs (MILPs). Methods for automatically generating inequalities valid for the convex hull of solutions to such MILPs are a critical element of branch-and-cut. This paper examines the nature of the so-called separation problem, which is that of generating a valid inequality violated by a given real vector, usually arising as the solution to a relaxation of the original problem. We show that the problem of generating a maximally violated valid inequality often has a natural interpretation as a bilevel program. In some cases, this bilevel program can be easily reformulated as a simple single-level mathematical program, yielding a standard mathematical programming formulation for the separation problem. In other cases, no such polynomial-size single-level reformulation exists unless the polynomial hierarchy collapses to its first level (an event considered extremely unlikely in computational complexity theory). We illustrate our insights by considering the separation problem for two well-known classes of valid inequalities.     

Bilevel optimization applied to strategic pricing in competitive electricity markets

In this paper, we present a bilevel programming formulation for the problem of strategic bidding under uncertainty in a wholesale energy market (WEM), where the economic remuneration of each generator depends on the ability of its own management to submit price and quantity bids. The leader of the bilevel problem consists of one among a group of competing generators and the follower is the electric system operator. The capability of the agent represented by the leader to affect the market price is considered by the model. We propose two solution approaches for this non-convex problem. The first one is a heuristic procedure whose efficiency is confirmed through comparisons with the optimal solutions for some instances of the problem. These optimal solutions are obtained by the second approach proposed, which consists of a mixed integer reformulation of the bilevel model. The heuristic proposed is also compared to standard solvers for nonlinearly constrained optimization problems. The application of the procedures is illustrated in case studies with configurations derived from the Brazilian power system.     

Deriving the Properties of Linear Bilevel Programming via a Penalty Function Approach

For the linear bilevel programming problem, we propose an assumption weaker than existing assumptions, while achieving similar results via a penalty function approach. The results include: equivalence between (i) existence of a solution to the problem, (ii) existence of an exact penalty function approach for solving the problem, and (iii) achievement of the optimal value of the equivalent form of the problem at some vertex of a certain polyhedral convex set. We prove that the assumption is both necessary and sufficient for the linear bilevel programming problem to admit an exact penalty function formulation, provided that the equivalent form of the problem has a feasible solution. A method is given for computing the minimal penalty function parameter value. This method can be executed by solving a set of linear programming problems. Lagrangian duality is also presented.     

随机P矩阵和随机P0矩阵线性互补问题

定义了随机P矩阵和随机P0矩阵,给出了矩阵为随机P矩阵或随机P0矩阵的充要条件.研究了随机线性互补问题(SLCP)的矩阵为随机P矩阵时,期望残差方法(ERM)解集的有界性.得到了期望矩阵为P矩阵时,(ERM)解集非空有界.并且研究离散情形(ERM)与期望值方法(EV)解的关系,给出了(ERM)解唯一的条件.     

极大极小随机规划逼近问题最优解集和最优值的稳定性

研究了特殊的二层极大极小随机规划逼近收敛问题. 首先将下层初始随机规划最优解集拓展到非单点集情形, 且可行集正则的条件下, 讨论了下层随机规划逼近问题最优解集关于上层决策变量参数的上半收敛性和最优值函数的连续性. 然后把下层随机规划的epsilon-最优解向量函数反馈到上层随机规划的目标函数中, 得到了上层随机规划逼近问题的最优解集关于最小信息概率度量收敛的上半收敛性和最优值的连续性.     

On Bilevel Programs with a Convex Lower-Level Problem Violating Slater’s Constraint Qualification

This paper focuses on bilevel programs with a convex lower-level problem violating Slater’s constraint qualification. We relax the constrained domain of the lower-level problem. Then, an approximate solution of the original bilevel program can be obtained by solving this perturbed bilevel program. As the lower-level problem of the perturbed bilevel program satisfies Slater’s constraint qualification, it can be reformulated as a mathematical program with complementarity constraints which can be solved by standard algorithms. The lower convergence properties of the constraint set mapping and the solution set mapping of the lower-level problem of the perturbed bilevel program are expanded. We show that the solutions of a sequence of the perturbed bilevel programs are convergent to that of the original bilevel program under some appropriate conditions. And this convergence result is applied to simple trilevel programs.     

The bilevel knapsack problem with stochastic right-hand sides

We introduce the bilevel knapsack problem with stochastic right-hand sides, and provide necessary and sufficient conditions for the existence of an optimal solution. When the leader’s decisions can take only integer values, we present an equivalent two-stage stochastic programming reformulation with binary recourse. We develop a branch-and-cut algorithm for solving this reformulation, and a branch-and-backtrack algorithm for solving the scenario subproblems. Computational experiments indicate that our approach can solve large instances in a reasonable amount of time.     

Necessary optimality conditions for a special class of bilevel programming problems with unique lower level solution

We consider a bilevel programming problem in Banach spaces whose lower level solution is unique for any choice of the upper level variable. A condition is presented which ensures that the lower level solution mapping is directionally differentiable, and a formula is constructed which can be used to compute this directional derivative. Afterwards, we apply these results in order to obtain first-order necessary optimality conditions for the bilevel programming problem. It is shown that these optimality conditions imply that a certain mathematical program with complementarity constraints in Banach spaces has the optimal solution zero. We state the weak and strong stationarity conditions of this problem as well as corresponding constraint qualifications in order to derive applicable necessary optimality conditions for the original bilevel programming problem. Finally, we use the theory to state new necessary optimality conditions for certain classes of semidefinite bilevel programming problems and present an example in terms of bilevel optimal control.     

Computation of the optimal tolls on the traffic network

The present paper is devoted to the computation of optimal tolls on a traffic network that is described as fuzzy bilevel optimization problem. As a fuzzy bilevel optimization problem we consider bilinear optimization problem with crisp upper level and fuzzy lower level. An effective algorithm for computation optimal tolls for the upper level decision-maker is developed under assumption that the lower level decision-maker chooses the optimal solution as well. The algorithm is based on the membership function approach. This algorithm provides us with a global optimal solution of the fuzzy bilevel optimization problem.     

一种双层规划的光滑化目标罚函数算法

论文研究了一种双层规划的光滑化目标罚函数算法,在一些条件下,证明了光滑化罚优化问题等价于原双层规划问题,而且,当下层规划问题是凸规划问题时, 给出了一个求解算法和收敛性证明.     

Exact and inexact penalty methods for the generalized bilevel programming problem

We consider a hierarchical system where a leader incorporates into its strategy the reaction of the follower to its decision. The follower's reaction is quite generally represented as the solution set to a monotone variational inequality. For the solution of this nonconvex mathematical program a penalty approach is proposed, based on the formulation of the lower level variational inequality as a mathematical program. Under natural regularity conditions, we prove the exactness of a certain penalty function, and give strong necessary optimality conditions for a class of generalized bilevel programs.