Bilevel programming: A survey

This paper provides an introductory survey of a class of optimization problems known as bilevel programming. We motivate this class through a simple application, and then proceed with the general formulation of bilevel programs. We consider various cases (linear, linear-quadratic, nonlinear), describe their main properties and give an overview of solution approaches.Received: April 2005, Revised: May 2005, AMS classification: 90C05, 90C11, 90C20, 90C27, 90C3D, 65K05     

A novel approach to Bilevel nonlinear programming

Recently developed methods of monotonic optimization have been applied successfully for studying a wide class of nonconvex optimization problems, that includes, among others, generalized polynomial programming, generalized multiplicative and fractional programming, discrete programming, optimization over the efficient set, complementarity problems. In the present paper the monotonic approach is extended to the General Bilevel Programming GBP Problem. It is shown that (GBP) can be transformed into a monotonic optimization problem which can then be solved by “polyblock” approximation or, more efficiently, by a branch-reduce-and-bound method using monotonicity cuts. The method is particularly suitable for Bilevel Convex Programming and Bilevel Linear Programming.      

Bilevel programming approach applied to the flow shop scheduling problem under fuzziness

This paper presents a fuzzy bilevel programming approach to solve the flow shop scheduling problem. The problem considered here differs from the standard form in that operators are assigned to the machines and imposing a hierarchy of two decision makers with fuzzy processing times. The shop owner considered higher level and assigns the jobs to the machines in order to minimize the flow time while the customer is the lower level and decides on a job schedule in order to minimize the makespan. In this paper, we use the concepts of tolerance membership function at each level to define a fuzzy decision model for generating optimal (satisfactory) solution for bilevel flow shop scheduling problem. A solution algorithm for solving this problem is given. Mathematics Subject Classification: 90C70, 90B36, 90C99     

Bilevel programming problems with simple convex lower level

This article is dedicated to the study of bilevel optimal control problems equipped with a fully convex lower level of special structure. In order to construct necessary optimality conditions, we consider a general bilevel programming problem in Banach spaces possessing operator constraints, which is a generalization of the original bilevel optimal control problem. We derive necessary optimality conditions for the latter problem using the lower level optimal value function, ideas from DC-programming and partial penalization. Afterwards, we apply our results to the original optimal control problem to obtain necessary optimality conditions of Pontryagin-type. Along the way, we derive a handy formula, which might be used to compute the subdifferential of the optimal value function which corresponds to the lower level parametric optimal control problem.     

Comment to “interactive fuzzy goal programming approach for bilevel programming problem” by S.R. Arora and R. Gupta

The fuzzy bilevel programming problem is solved in the paper [1] using an approach of fuzzy goal programming. Using a simple example we show that this will not lead to a satisfactory solution. Especially the fuzzy constraint that the upper level variable is near some desired one has no influence on the computed solution in the example. This constraint is used to model the hierarchy in the approach in [1]. At the end of the paper we suggest one straightforward possibility for modeling the fuzzy bilevel programming problem and converting it into a crisp substitute.     

On bilevel programming,Part I: General nonlinear cases

This paper is concerned with general nonlinear nonconvex bilevel programming problems (BLPP). We derive necessary and sufficient conditions at a local solution and investigate the stability and sensitivity analysis at a local solution in the BLPP. We then explore an approach in which a bundle method is used in the upper-level problem with subgradient information from the lower-level problem. Two algorithms are proposed to solve the general nonlinear BLPP and are shown to converge to regular points of the BLPP under appropriate conditions. The theoretical analysis conducted in this paper seems to indicate that a sensitivity-based approach is rather promising for solving general nonlinear BLPP.This research is sponsored by the Office of Naval Research under contract N00014-89-J-1537.     

Test problem construction for linear bilevel programming problems

A method of constructing test problems for linear bilevel programming problems is presented. The method selects a vertex of the feasible region, far away from the solution of the relaxed linear programming problem, as the global solution of the bilevel problem. A predetermined number of constraints are systematically selected to be assigned to the lower problem. The proposed method requires only local vertex search and solutions to linear programs.     

Exact Penalty Functions for Convex Bilevel Programming Problems

In this paper, we propose a new constraint qualification for convex bilevel programming problems. Under this constraint qualification, a locally and globally exact penalty function of order 1 for a single-level reformulation of convex bilevel programming problems is given without requiring the linear independence condition and the strict complementarity condition to hold in the lower-level problem. Based on these results, locally and globally exact penalty functions for two other single-level reformulations of convex bilevel programming problems can be obtained. Furthermore, sufficient conditions for partial calmness to hold in some single-level reformulations of convex bilevel programming problems can be given.     

Stability of Regularized Bilevel Programming Problems

A bilevel programming problem S is considered. First, sufficient conditions of minimal character are given on the data of the problem in order to guarantee the lower semicontinuity of the marginal function of the upper level problem. Then, for >0, a regularized problem S() is considered for which continuity of the regularized marginal function and convergence of the approximate value, as goes to zero, are obtained. Moreover, under perturbations on the data, convergence results for the perturbed marginal functions and the solutions to the problem S _n() are given for any >0.     

Multi-product production planning: A goal programming approach

Cost minimization multi-product production problems with static production resource usage and internal product flow requirements have been solved by linear programming (LP) with input/output analysis. If the problem is complicated by interval resource estimates, interval linear programming (ILP) can be used. The solution of realistic problems by the above method is cumbersome. This paper suggests that linear goal programming (LGP) can be used to model a multi-product production system. LGP's unique modeling capabilities are used to solve a production planning problem with variable resource parameters. Input/output analysis is used to determine the technological coefficients for the goal constraints and is also used to derive an information sub-model that is used to reduce the number of variable resource goal constraints. Preliminary findings suggest that the LGP approach is more cost-efficient (in terms of CPU time) and in addition provides valuable information for aggregate planning.     

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.     

数学规划与约束规划整合下的多目标分组排序问题研究

分组排序问题属于NP-难题, 单纯的数学规划模型或约束规划模型都无法在有效时间内解决相当规模的此类问题. 控制成本、缩短工期和减少任务延迟是排序问题的三个基本目标, 在实际工作中决策者通常需要兼顾三者, 并在 三者之间进行权衡. 多目标分组排序问题 的研究增强了排序问题的实际应用价值, 有利于帮助决策者处理复杂的多目标环境. 然而, 多目标的引入也增加了问题求解难度, 针对数学规划擅长寻找最优, 约束规划擅长排序的特点, 将两类方法整合起来, 提出一个基于Benders分解算法, 极大提高了此类问题的求解 效率.     

The nonlinear bilevel programming problem:formulations,regularity and optimality conditions

In this paper, we study regularity and optimality conditions for the BLPP by using a marginal function formulation, where the marginal function is defined by the optimal value function of the lower problem. We address the regularity issue by exploring the structure of the tangent cones of the feasible set of the BLPP. These regularity results indicate that the nonlinear/nonlinear BLPP is most likely degenerate and a class of nonlinear/linear BLPP is regular in the conventional sense. Existence of exact penalty function is proved for a class of nonlinear/linear BLPP. Fritz-John type optimality conditions are derived for nonlinear BLPP, while KKT type conditions are obtained for a class of nonlinear/linear BLPP in the framework of nonsmooth analysis. A typical example is examined for these conditions and some applications of these conditions are pointed out     

On a class of iterative projection and contraction methods for linear programming

In this paper, based on the idea of a projection and contraction method for a class of linear complementarity problems (Refs. 1 and 2), we develop a class of iterative algorithms for linear programming with linear speed of convergence. The algorithms are used to solve transportation and network problems with up to 10,000 variables. Our experiments indicate that the algorithms are simple, easy to parallelize, and more efficient for some large practical problems.This research was done while the author was visiting the Department of Mathematics at the University of Würzburg, Würzburg, Germany.     

Weak linear bilevel programming problems: existence of solutions via a penalty method

We are concerned with a class of weak linear bilevel programs with nonunique lower level solutions. For such problems, we give via an exact penalty method an existence theorem of solutions. Then, we propose an algorithm.     

On regularization methods based on dynamic programming techniques

In this article, we investigate the connection between regularization theory for inverse problems and dynamic programming theory. This is done by developing two new regularization methods, based on dynamic programming techniques. The aim of these methods is to obtain stable approximations to the solution of linear inverse ill-posed problems. We follow two different approaches and derive a continuous and a discrete regularization method. Regularization properties for both methods are proved as well as rates of convergence. A numerical benchmark problem concerning integral operators with convolution kernels is used to illustrate the theoretical results.     

Discretization methods for the solution of semi-infinite programming problems

In the first part of this paper, we prove the convergence of a class of discretization methods for the solution of nonlinear semi-infinite programming problems, which includes known methods for linear problems as special cases. In the second part, we modify and study this type of algorithms for linear problems and suggest a specific method which requires the solution of a quadratic programming problem at each iteration. With this algorithm, satisfactory results can also be obtained for a number of singular problems. We demonstrate the performance of the algorithm by several numerical examples of multivariate Chebyshev approximation problems.     

A study of mixed discrete bilevel programs using semidefinite and semi-infinite programming

In this paper, we study the bilevel programming problem with discrete polynomial lower level problem. We start by transforming the problem into a bilevel problem comprising a semidefinite program (SDP for short) in the lower level problem. Then, we are able to deduce some conditions of existence of solutions for the original problem. After that, we again change the bilevel problem with SDP in the lower level problem into a semi-infinite program. With the aid of the exchange technique, for simple bilevel programs, an algorithm for computing a global optimal solution is suggested, the convergence is shown, and a numerical example is given.     

A fuzzy goal programming approach for mid-term assortment planning in supermarkets

We develop a fuzzy mixed integer non-linear goal programming model for the mid-term assortment planning of supermarkets in which three conflicting objectives namely profitability, customer service, and space utilization are incorporated. The items and brands in a supermarket compete to obtain more space and better shelf level. This model offers different service levels to loyal and disloyal customers, applies joint replenishment policy, and accounts for the holding time limitation of perishable items. We propose a fuzzy approach due to the imprecise nature of the goals’ target levels and priorities as well as critical data. A heuristic method inspiring by the problem-specific rules is developed to solve this complex model approximately within a reasonable time. Finally, the proposed approach is validated through several numerical examples and results are reported.