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.     

Multi-period price promotions in a single-supplier, multi-retailer supply chain under asymmetric demand information

This paper considers a two-stage supply chain in which a supplier serves a set of stores in a retail chain. We consider a two-stage Stackelberg game in which the supplier must set price discounts for each period of a finite planning horizon under uncertainty in retail-store demand. As a mechanism to stimulate sales, the supplier offers periodic off-invoice price discounts to the retail chain. Based on the price discounts offered by the supplier, and after store demand uncertainty is resolved, the retail chain determines individual store order quantities in each period. Because the supplier offers store-specific prices, the retailer may ship inventory between stores, a practice known as diverting. We demonstrate that, despite the resulting bullwhip effect and associated costs, a carefully designed price promotion scheme can improve the supplier’s profit when compared to the case of everyday low pricing (EDLP). We model this problem as a stochastic bilevel optimization problem with a bilinear objective at each level and with linear constraints. We provide an exact solution method based on a Reformulation-Linearization Technique (RLT). In addition, we compare our solution approach with a widely used heuristic and another exact solution method developed by Al-Khayyal (Eur. J. Oper. Res. 60(3):306–314, 1992) in order to benchmark its quality.     

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.     

On a Heuristic Inventory-replenishment Rule for Items with a Linearly Increasing Demand Incorporating Shortages

A heuristic decision rule is derived for the replenishment of items with a linearly increasing demand rate over a finite planning horizon during which shortages are allowed. When compared with the exact decision rule, the heuristic is found to incur negligible cost penalty for the numerical example which is given to illustrate the use of the heuristic.     

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.     

Necessary optimality conditions for bilevel minimization problems

In this paper we study bilevel minimization problems. Using the implicit function theorem, variational analysis and exact penalty results we establish necessary optimality conditions for these problems.     

Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality constraints

In this paper we consider heuristic algorithms for a special case of the generalized bilevel mathematical programming problem in which one of the levels is represented as a variational inequality problem. Such problems arise in network design and economic planning. We obtain derivative information needed to implement these algorithms for such bilevel problems from the theory of sensitivity analysis for variational inequalities. We provide computational results for several numerical examples.     

New algorithmic alternatives for the O–D matrix adjustment problem on traffic networks

In the last years the O–D matrix adjustment problem using link counts on a traffic network modelled by means of a static user equilibrium approach has been formulated advantageously by means of bilevel programs. The algorithms developed to solve the problem present heuristic components in a lesser or greater degree. In this paper two new algorithmic alternatives are presented for this problem. The first alternative is an hybrid scheme proximal point-steepest descent that is based on a development of Codina for the approximation of the steepest descent direction of the upper level function and the second alternative is developed by García and Marín and consists of solving a sequence of simplified bilevel programs. In order to highlight the characteristics of the two methods a set of test problems have been solved in conjunction with other well known methods, such as the method of Spiess, the method of Chan, the method of Yang as well as with an adaptation of the Wolfe’s conjugate directions method for non-differentiable optimization, in order to provide a better perspective of their advantages and tradeoffs.     

A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen

We address a variant of the vehicle routing problem with time windows that includes the decision of how many deliverymen should be assigned to each vehicle. In this variant, the service time at each customer depends on the size of the respective demand and on the number of deliverymen assigned to visit this customer. In addition, the objective function consists of minimizing a weighted sum of the total number of routes, number of deliverymen and traveled distance. These characteristics make this variant very challenging for exact methods. To date, only heuristic approaches have been proposed for this problem, and even the most efficient optimization solvers cannot find optimal solutions in a reasonable amount of time for instances of moderate size when using the available mathematical formulations. We propose a branch-price-and-cut method based on a new set partitioning formulation of the problem. To accelerate the convergence of the method, we rely on an interior-point column and cut generation process, a strong branching strategy and a mixed-integer programming-based primal heuristic. Additionally, a hierarchical branching strategy is used to take into account the different components of the objective function. The computational results indicate the benefits of using the proposed exact solution approach. We closed several instances of the problem and obtained upper bounds that were previously unknown in the literature.     

OD估计双层规划扩展模型

利用双层规划模型进行OD估计,建立双层规划扩展模型.考虑OD估计问题中的随机误差,基于Bayes估计和多元正态分布建立上层目标函数;考虑用户路径选择行为的随机性,基于随机用户均衡建立需求可变动的下层目标函数,同时该扩展模型能适应我国混合交通的实际,既能适用于拥挤网络、也能适用于非拥挤网络,最后通过算例证明此模型的有效性.     

The capacitated team orienteering and profitable tour problems

In this paper, we study the capacitated team orienteering and profitable tour problems (CTOP and CPTP). The interest in these problems comes from recent developments in the use of the Internet for a better matching of demand and offer of transportation services. We propose exact and heuristic procedures for the CTOP and the CPTP. The computational results show that the heuristic procedures often find the optimal solution and in general cause very limited errors.     

Modeling formulation and a new heuristic for the railroad blocking problem

The railroad blocking problem is an important issue at the tactical level of railroad freight transportation. This problem consists of determining paths between the origins and destinations of each shipment to minimize the operating and user costs while satisfying the railroad supply and demand restrictions. A mixed-integer program (MIP) is developed to find the optimal paths, and a new heuristic is developed to solve the proposed model. This heuristic decomposes the model into two sub-problems of manageable size and then provides feasible solutions. We discuss the performance of the proposed heuristic for a set of instances with up to 90 stations. A comparison with the CPLEX MIP solver shows that the heuristic gives the exact solution for 10 out of 15 instances. For the remaining instances, the heuristic obtained solutions within a tolerance of 0.03–0.84%. Furthermore, compared with the CPLEX MIP solver, the heuristic reduced the run time by an average of 85% for all 15 instances. Finally, we present the computational results of the heuristic applied to Iranian railroads.     

A penalty function method based on bilevel programming for solving inverse optimal value problems

In this work, we reformulate the inverse optimal value problem equivalently as a corresponding nonlinear bilevel programming (BLP) problem. For the nonlinear BLP problem, the duality gap of the lower level problem is appended to the upper level objective with a penalty, and then a penalized problem is obtained. On the basis of the concept of partial calmness, we prove that the penalty function is exact. Then, an algorithm is proposed and an inverse optimal value problem is resolved to illustrate the 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 numerical method for the mathematical programming problems. In this article, we propose a dual-relax penalty function approach, which is significantly different from penalty function 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.     

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

' 1 IntroductionWe collsider the fOllowi11g bilevel programndng problen1:max f(x, y),(BP) s.t.x E X = {z E RnIAx = b,x 2 0}, (1)y e Y(x).whereY(x) = {argmaxdTyIDx Gy 5 g, y 2 0}, (2)and b E R", d, y E Rr, g E Rs, A, D.and G are m x n1 s x n aild 8 x r matrices respectively. If itis not very difficult to eva1uate f(and/or Vf) at all iteration points, there are many algorithmeavailable fOr solving problem (BP) (see [1,2,3etc1). However, in some problems (see [4]), f(x, y)is too com…     

The bilevel programming problem: reformulations, constraint qualifications and optimality conditions

We consider the bilevel programming problem and its optimal value and KKT one level reformulations. The two reformulations are studied in a unified manner and compared in terms of optimal solutions, constraint qualifications and optimality conditions. We also show that any bilevel programming problem where the lower level problem is linear with respect to the lower level variable, is partially calm without any restrictive assumption. Finally, we consider the bilevel demand adjustment problem in transportation, and show how KKT type optimality conditions can be obtained under the partial calmness, using the differential calculus of Mordukhovich.     

Medium Term Production Management for Cyclic Deliveries

The growing quality and delay requirements have catalyzed the emergence of new commercial paradigms, which have strongly modified the customer–supplier relationship. Customers and suppliers become more and more linked with contracts or global orders spanned over a relatively important period. This paper, examines a type of contract which specifies a fixed and cyclic delivery dates with delivery quantities varying between a min and a max values. The exact delivery quantities are usually known only few days before the delivery. A company which produces n items on a bottleneck facility is considered; each item is confronted to a cyclic demand and has an important holding cost in comparison to set-up costs. We propose heuristic approaches, to build, in a medium term level, cyclic production schedules. These schedules face the demand and minimize a total cost function composed of holding and set-up costs. An experiment is proposed in order to prove the effectiveness of our approaches.     

Descent approaches for quadratic bilevel programming

The bilevel programming problem involves two optimization problems where the data of the first one is implicitly determined by the solution of the second. In this paper, we introduce two descent methods for a special instance of bilevel programs where the inner problem is strictly convex quadratic. The first algorithm is based on pivot steps and may not guarantee local optimality. A modified steepest descent algorithm is presented to overcome this drawback. New rules for computing exact stepsizes are introduced and a hybrid approach that combines both strategies is discussed. It is proved that checking local optimality in bilevel programming is a NP-hard problem.Support of this work has been provided by INIC (Portugal) under Contract 89/EXA/5, by FCAR (Québec), and by NSERC and DND-ARP (Canada).     

Natural gas cash-out problem: Bilevel stochastic optimization approach

A stochastic formulation of the natural gas cash-out problem is given in a form of a bilevel multi-stage stochastic programming model with recourse. After reducing the original formulation to a bilevel linear problem, a stochastic scenario tree is defined by its node events, and time series forecasting is used to produce stochastic values for data of natural gas price and demand. Numerical experiments were run to compare the stochastic solution with the perfect information solution and the expected value solutions.     

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.