Mathematical structure of a bilevel strategic pricing model

This paper is concerned with the characterization of optimal strategies for a service firm acting in an oligopolistic environment. The decision problem is formulated as a leader–follower game played on a transportation network, where the leader firm selects a revenue-maximizing price schedule that takes explicitly into account the rational behavior of the customers. In the context of our analysis, the follower’s problem is associated with a competitive network market involving non atomic customer groups. The resulting bilevel model can therefore be viewed as a model of product differentiation subject to structural network constraints.     

A discrete bilevel brain storm algorithm for solving a sales territory design problem: a case study

A sales territory design problem faced by a manufacturing company that supplies products to a group of customers located in a service region is addressed in this paper. The planning process of designing the territories has the objective to minimizing the total dispersion of the customers without exceeding a limited budget assigned to each territory. Once territories have been determined, a salesperson has to define the day-by-day routes to satisfy the demand of customers. Currently, the company has established a service level policy that aims to minimize total waiting times during the distribution process. Also, each territory is served by a single salesperson. A novel discrete bilevel optimization model for the sales territory design problem is proposed. This problem can be seen as a bilevel problem with a single leader and multiple independent followers, in which the leader’s problem corresponds to the design of territories (manager of the company), and the routing decision for each territory corresponds to each follower. The hierarchical nature of the current company’s decision-making process triggers some particular characteristics of the bilevel model. A brain storm algorithm that exploits these characteristics is proposed to solve the discrete bilevel problem. The main features of the proposed algorithm are that the workload is used to verify the feasibility and to cluster the leader’s solutions. In addition, four discrete mechanisms are used to generate new solutions, and an elite set of solutions is considered to reduce computational cost. This algorithm is used to solve a real case study, and the results are compared against the current solution given by the company. Results show a reduction of more than 20% in the current costs with the solution obtained by the proposed algorithm. Furthermore, a sensitivity analysis is performed, providing interesting managerial insights to improve the current operations of the company.     

Electricity swing option pricing by stochastic bilevel optimization: A survey and new approaches

We demonstrate how the problem of determining the ask price for electricity swing options can be considered as a stochastic bilevel program with asymmetric information. Unlike as for financial options, there is no way for basing the pricing method on no-arbitrage arguments. Two main situations are analyzed: if the seller has strong market power he/she might be able to maximize his/her utility, while in fully competitive situations he/she will just look for a price which makes profit and has acceptable risk. In both cases the seller has to consider the decision problem of a potential buyer – the valuation problem of determining a fair value for a specific option contract – and anticipate the buyer’s optimal reaction to any proposed strike price. We also discuss some methods for finding numerical solutions of stochastic bilevel problems with a special emphasis on using duality gap penalizations.     

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.     

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

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

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

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

Incorporating the threat of terrorist attacks in the design of public service facility networks

In this paper, we consider the design problem of a public service facility network with existing facilities when there is a threat of possible terrorist attacks. The aim of the system planner, who is responsible for the operation of the network, is to open new facilities, relocate existing ones if necessary, and protect some of the facilities to ensure a maximum coverage of the demand that is assumed to be aggregated at customer zones. By doing so, the system planner anticipates that a number of unprotected facilities will be rendered out-of-service by terrorist attacks. It is assumed that the sum of the fixed cost of opening new facilities, the relocation costs, and the protection costs cannot exceed a predetermined budget level. Adopting the approach of gradual (or partial) coverage, we formulate a bilevel programming model where the system planner is the leader and the attacker is the follower. The objective of the former is the maximization of the total service coverage, whereas the latter wants to minimize it. We propose a heuristic solution procedure based on tabu search where the search space consists of the decisions of the system planner, and the corresponding objective value is computed by optimally solving the attacker??s problem using CPLEX. To assess the quality of the solutions produced by the tabu search (TS) heuristic, we also develop an exhaustive enumeration method, which explores all the possible combinations of opening new facilities, relocating existing ones, and protecting them. Since its time complexity is exponential, it can only be used for relatively small instances. Therefore, to be used as a benchmark method, we also implement a hill climbing procedure employed with the same type of moves as the TS heuristic. Besides, we carry out a sensitivity analysis on some of the problem parameters to investigate their effect on the solution characteristics.     

Heston随机波动率模型下的资产负债管理问题

应用随机最优控制方法研究Heston随机波动率模型下带有负债过程的动态投资组合问题,其中假设股票价格服从Heston随机波动率模型,负债过程由带漂移的布朗运动所驱动.金融市场由一种无风险资产和一种风险资产组成.应用随机动态规划原理和变量替换法得出了上述问题在幂效用和指数效用函数下最优投资策略的显示解,并给出数值算例分别分析了市场参数在幂效用和指数效用函数下对最优投资策略的影响.     

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

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

Linear bilevel multi-follower programming with independent followers

This paper considers a particular case of linear bilevel programming problems with one leader and multiple followers. In this model, the followers are independent, meaning that the objective function and the set of constraints of each follower only include the leader’s variables and his own variables. We prove that this problem can be reformulated into a linear bilevel problem with one leader and one follower by defining an adequate second level objective function and constraint region. In the second part of the paper we show that the results on the optimality of the linear bilevel problem with multiple independent followers presented in Shi et al. [The kth-best approach for linear bilevel multi-follower programming, J. Global Optim. 33, 563–578 (2005)] are based on a misconstruction of the inducible region.     

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 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.     

Solving Ill-posed Bilevel Programs

This paper deals with ill-posed bilevel programs, i.e., problems admitting multiple lower-level solutions for some upper-level parameters. Many publications have been devoted to the standard optimistic case of this problem, where the difficulty is essentially moved from the objective function to the feasible set. This new problem is simpler but there is no guaranty to obtain local optimal solutions for the original optimistic problem by this process. Considering the intrinsic non-convexity of bilevel programs, computing local optimal solutions is the best one can hope to get in most cases. To achieve this goal, we start by establishing an equivalence between the original optimistic problem and a certain set-valued optimization problem. Next, we develop optimality conditions for the latter problem and show that they generalize all the results currently known in the literature on optimistic bilevel optimization. Our approach is then extended to multiobjective bilevel optimization, and completely new results are derived for problems with vector-valued upper- and lower-level objective functions. Numerical implementations of the results of this paper are provided on some examples, in order to demonstrate how the original optimistic problem can be solved in practice, by means of a special set-valued optimization problem.     

On a class of bilevel linear mixed-integer programs in adversarial settings

We consider a class of bilevel linear mixed-integer programs (BMIPs), where the follower’s optimization problem is a linear program. A typical assumption in the literature for BMIPs is that the follower responds to the leader optimally, i.e., the lower-level problem is solved to optimality for a given leader’s decision. However, this assumption may be violated in adversarial settings, where the follower may be willing to give up a portion of his/her optimal objective function value, and thus select a suboptimal solution, in order to inflict more damage to the leader. To handle such adversarial settings we consider a modeling approach referred to as \(\alpha \)-pessimistic BMIPs. The proposed method naturally encompasses as its special classes pessimistic BMIPs and max–min (or min–max) problems. Furthermore, we extend this new modeling approach by considering strong-weak bilevel programs, where the leader is not certain if the follower is collaborative or adversarial, and thus attempts to make a decision by taking into account both cases via a convex combination of the corresponding objective function values. We study basic properties of the proposed models and provide numerical examples with a class of the defender–attacker problems to illustrate the derived results. We also consider some related computational complexity issues, in particular, with respect to optimistic and pessimistic bilevel linear programs.     

Bilevel aggregator-prosumers' optimization problem in real-time: A convex optimization approach

This paper proposes a Real-Time Market (RTM) platform for an aggregator and its corresponding prosumers to participate in the electricity wholesale market. The proposed energy market platform is modeled as a bilevel optimization problem where the aggregator and the prosumers are considered as self-interested agents. We present a convex optimization problem which can capture a subset of the set of global optima of the bilevel problem as its optimal solution.     

The traveling purchaser problem with stochastic prices: Exact and approximate algorithms

The paper formulates an extension of the traveling purchaser problem where multiple types of commodities are sold at spatially distributed locations with stochastic prices (each following a known probability distribution). A purchaser’s goal is to find the optimal routing and purchasing strategies that minimize the expected total travel and purchasing costs needed to purchase one unit of each commodity. The purchaser reveals the actual commodity price at a seller upon arrival, and then either purchases the commodity at the offered price, or rejects the price and visits a next seller. In this paper, we propose an exact solution algorithm based on dynamic programming, an iterative approximate algorithm that yields bounds for the minimum total expected cost, and a greedy heuristic for fast solutions to large-scale applications. We analyze the characteristics of the problem and test the computational performance of the proposed algorithms. The numerical results show that the approximate and heuristic algorithms yield near-optimum strategies and very good estimates of the minimum total cost.     

Utility-based indifference pricing in regime-switching models

In this paper, we study utility-based indifference pricing and hedging of a contingent claim in a continuous-time, Markov, regime-switching model. The market in this model is incomplete, so there is more than one price kernel. We specify the parametric form of price kernels so that both market risk and economic risk are taken into account. The pricing and hedging problem is formulated as a stochastic optimal control problem and is discussed using the dynamic programming approach. A verification theorem for the Hamilton-Jacobi-Bellman (HJB) solution to the problem is given. An issuer’s price kernel is obtained from a solution of a system of linear programming problems and an optimal hedged portfolio is determined.     

Dual sourcing using capacity reservation and spot market: Optimal procurement policy and heuristic parameter determination

This contribution focuses on the cost-effective management of the combined use of two procurement options: the short-term option is given by a spot market with random price, whereas the long-term alternative is characterized by a multi period capacity reservation contract with fixed purchase price and reservation level. A reservation cost, proportional with the reservation level, has to be paid for the option of receiving any amount per period up to the reservation level. A long-term decision has to be made regarding the reserved capacity level, and then it has to be decided – period by period – which quantities to procure from the two sources. Considering the multi-period problem with stochastic demand and spot price, the structure of the optimal combined purchasing policy is derived using stochastic dynamic programming. Exploiting these structural properties, an advanced heuristic is developed to determine the respective policy parameters. This heuristic is compared with two rolling-horizon approaches which use the one-period and two-period optimal solution. A comprehensive numerical study reveals that the approaches based on one-period and two-period solutions have considerable drawbacks, while the advanced heuristic performs very well compared to the optimal solution. Finally, by exploiting our numerical results we give some insights into the system’s behavior under problem parameter variations.     

A bilevel fuzzy principal-agent model for optimal nonlinear taxation problems

This paper presents a bilevel fuzzy principal-agent model for optimal nonlinear taxation problems with asymmetric information, in which the government and the monopolist are the principals, the consumer is their agent. Since the assessment of the government and the monopolist about the consumer’s taste is subjective, therefore, it is reasonable to characterize this assessment as a fuzzy variable. What’s more, a bilevel fuzzy optimal nonlinear taxation model is developed with the purpose of maximizing the expected social welfare and the monopolist’s expected welfare under the incentive feasible mechanism. The equivalent model for the bilevel fuzzy optimal nonlinear taxation model is presented and Pontryagin maximum principle is adopted to obtain the necessary conditions of the solutions for the fuzzy optimal nonlinear taxation problems. Finally, one numerical example is given to illustrate the effectiveness of the proposed model, the results demonstrate that the consumer’s purchased quantity not only relates with the consumer’s taste, but also depends on the structure of the social welfare.     

A Bilevel p-median model for the planning and protection of critical facilities

The bilevel p-median problem for the planning and protection of critical facilities involves a static Stackelberg game between a system planner (defender) and a potential attacker. The system planner determines firstly where to open p critical service facilities, and secondly which of them to protect with a limited protection budget. Following this twofold action, the attacker decides which facilities to interdict simultaneously, where the maximum number of interdictions is fixed. Partial protection or interdiction of a facility is not possible. Both the defender’s and the attacker’s actions have deterministic outcome; i.e., once protected, a facility becomes completely immune to interdiction, and an attack on an unprotected facility destroys it beyond repair. Moreover, the attacker has perfect information about the location and protection status of facilities; hence he would never attack a protected facility. We formulate a bilevel integer program (BIP) for this problem, in which the defender takes on the leader’s role and the attacker acts as the follower. We propose and compare three different methods to solve the BIP. The first method is an optimal exhaustive search algorithm with exponential time complexity. The second one is a two-phase tabu search heuristic developed to overcome the first method’s impracticality on large-sized problem instances. Finally, the third one is a sequential solution method in which the defender’s location and protection decisions are separated. The efficiency of these three methods is extensively tested on 75 randomly generated instances each with two budget levels. The results show that protection budget plays a significant role in maintaining the service accessibility of critical facilities in the worst-case interdiction scenario.