A bilevel programming problem with maximization of a supermodular function in the lower level

In bilevel programming there are two decision makers, the leader and the follower, who act in a hierarchy. In this paper we deal with a bilevel problem where the follower maximizes a supermodular function. The payoff for the leader is given by the weighted set that is chosen by the follower. To increase his payoff the leader can increase the supermodular function of the follower by a modular one, thus influencing the follower’s decision, but he has to pay a penalty for this. We want to find an optimum strategy for the leader. This is a bilevel programming problem with continuous variables in the upper level and a parametric supermodular maximization problem in the lower level. We analyze the structure of the bilevel problem. This we use to provide an equivalent one-level combinatorial problem. Finally, we investigate the properties of the new problem.     

Optimality conditions for a bilevel matroid problem

In bilevel programming there are two decision makers, the leader and the follower, who act in a hierarchy. In this paper we deal with a weighted matroid problem where each of the decision makers has a different set of weights. The independent set of the matroid that is chosen by the follower determines the payoff to both the leader and the follower according to their different weights. The leader can increase his payoff by changing the weights of the follower, thus influencing the follower’s decision, but he has to pay a penalty for this. We want to find an optimum strategy for the leader. This is a bilevel programming problem with continuous variables in the upper level and a parametric weighted matroid problem in the lower level. We analyze the structure of the lower level problem. We use this structure to develop local optimality criteria for the bilevel problem that can be verified in polynomial time.     

高等教育最优投资双层规划模型研究

高等教育投资具有"双层"的特点,上层为省级主管部门,下层为高等学校。本文成功运用了双层规划模型,在不考虑高校自筹发展资金投入的情况下,建立了高等教育最优投资双层规划模型,研究了模型最优解的存在性,给出并证明了模型最优解的等价形式,设计了模型解的算法并进行了算法复杂性分析。通过求解模型,可以同时得到省级主管部门和高等学校的最优投资决策方案。文章最后还给出了考虑高校自筹发展资金的两种情况下建立投资模型和求得最优解的方法。     

线性二层决策问题的期望收益模型及算法

下层反应不唯一时 ,如何确定二层线性决策问题最优策略为一非确定型决策问题 .对此类问题 ,本文通过引入领导者对追随者合作程度的期望系数 ,提出期望收益模型 .利用双罚函数把该问题转换为一单层次优化问题 ,并提出一种求解问题的全局优化算法 .应用此模型分析二层线性问题可知 :对存在不确定性反应的二层决策问题 ,下层追随者与上层领导者的合作态度是领导者确定其最优策略的关键 ;对下层追随者而言 ,某些情况下 ,采取与领导者部分合作的态度对其自身收益的提高是合理的     

求解非线性二层规划问题的模拟植物生长算法

本文以植物向光性生长理论为启发式准则,提出了一种求解非线性二层规划问题的智能优化算法。在该算法中,将二层规划上层解空间和下层反应集分别作为植物的两个生长环境,建立以生长规则为基础的植物系统演绎方式和以植物向光性理论为基础的概率生长模型,两者结合所形成的优化模式,实现了模拟植物从初始状态到完整形式的终态(没有新的树枝生长),从而得到二层规划问题的解。该方法具有搜索精度较高,求解稳定性较强的特点,通过与国外学者在非线性二层规划实际测试问题的最优值进行精度比较,表明模拟植物生长算法是有效可行的。     

Network Reconfiguration for Increasing Transportation System Resilience Under Extreme Events

Evacuating residents out of affected areas is an important strategy for mitigating the impact of natural disasters. However, the resulting abrupt increase in the travel demand during evacuation causes severe congestions across the transportation system, which thereby interrupts other commuters' regular activities. In this article, a bilevel mathematical optimization model is formulated to address this issue, and our research objective is to maximize the transportation system resilience and restore its performance through two network reconfiguration schemes: contraflow (also referred to as lane reversal) and crossing elimination at intersections. Mathematical models are developed to represent the two reconfiguration schemes and characterize the interactions between traffic operators and passengers. Specifically, traffic operators act as leaders to determine the optimal system reconfiguration to minimize the total travel time for all the users (both evacuees and regular commuters), while passengers act as followers by freely choosing the path with the minimum travel time, which eventually converges to a user equilibrium state. For each given network reconfiguration, the lower‐level problem is formulated as a traffic assignment problem (TAP) where each user tries to minimize his/her own travel time. To tackle the lower‐level optimization problem, a gradient projection method is leveraged to shift the flow from other nonshortest paths to the shortest path between each origin–destination pair, eventually converging to the user equilibrium traffic assignment. The upper‐level problem is formulated as a constrained discrete optimization problem, and a probabilistic solution discovery algorithm is used to obtain the near‐optimal solution. Two numerical examples are used to demonstrate the effectiveness of the proposed method in restoring the traffic system performance.     

Planning of a decentralized distribution network using bilevel optimization

This paper proposes a bilevel optimization problem to model the planning of a distribution network that allows us to take into account how decisions made at the distribution stage of the supply chain can affect and be affected by decisions made at the manufacturing stage. Usually, the distribution network design problem decides on the opening of depots and the distribution from the depots to customers only and pays no attention to the manufacturing process itself. By way of example, the paper discusses the implications of formulating a bilevel model to integrate distribution and manufacturing, maintaining the hierarchy existing in the decision process. The resulting model is a bilevel mixed integer optimization problem. Hence, only small instances can be optimally solved in an acceptable computing time. In order to be able to solve the optimization model for realistic large systems, a metaheuristic approach based on evolutionary algorithms is developed. The algorithm combines the use of an evolutionary algorithm to control the supply of depots with optimization techniques to determine the delivery from depots to customers and the supply from manufacturing plants to depots. A computational experiment is carried out to assess the efficiency and robustness of the algorithm.     

Interactive fuzzy goal programming for multi-objective transportation problems

This paper presents an interactive fuzzy goal programming approach to determine the preferred compromise solution for the multi-objective transportation problem. The proposed approach considers the imprecise nature of the input data by implementing the minimum operator and also assumes that each objective function has a fuzzy goal. The approach focuses on minimizing the worst upper bound to obtain an efficient solution which is close to the best lower bound of each objective function. The solution procedure controls the search direction via updating both the membership values and the aspiration levels. An important characteristic of the approach is that the decision maker's role is concentrated only in evaluating the efficient solution to limit the influences of his/her incomplete knowledge about the problem domain. In addition, the proposed approach can be applied to solve other multi-objective decision making problems. The performance of this solution approach is evaluated by comparing its results with that of the two existing methods in the literature.     

A market regulation bilevel problem: A case study of the Mexican petrochemical industry

In this paper, a bilevel programming model is proposed to study a problem of market regulation through government intervention. One of the main characteristics of the problem herein analyzed is that the government monopolizes the raw material in one industry, and competes in another industry with private firms for the production of commodities. Under this scheme, the government controls a state-owned firm to balance the market; that is, to minimize the difference between the produced and demanded commodities. On the other hand, a regulatory organization that coordinates private firms aims to maximize the total profit by deciding the amount of raw material bought from the a state-owned firm. Two equivalent single-level reformulations are proposed to solve the problem. The first reformulation is based on the strong duality condition of the lower level and results in a continuous non-linear model. The second reformulation resorts to the complementarity slackness optimality constraints yielding a mixed-integer linear model. Additionally, three heuristic algorithms are designed to obtain good-quality solutions with low computational effort. In this problem, the feasible region of the dual problem associated to the follower is independent from the leader’s decision. Therefore, the proposed heuristics exploit this particular characteristic of the bilevel model. Moreover, the third heuristic hybridizes the other two algorithms to enhance its performance. Extensive computational experimentation is carried out to measure the efficiency of the proposed solution methodologies. A case study based on the Mexican petrochemical industry is presented. Additional instances generated from the case study are considered to validate the robustness of the proposed heuristic algorithms. Numerical results indicate that the hybrid algorithm outperforms the other two heuristics. However, all of them demonstrate to be good alternatives for solving the problem. Additionally, optimal solutions of all the instances are obtained by using good quality solutions (given by the hybrid algorithm) as initial solutions when solving the second reformulation via a general purpose solver.     

A method combining genetic algorithm with simultaneous perturbation stochastic approximation for linearly constrained stochastic optimization problems

This paper considers the optimization of linearly constrained stochastic problem which only noisy measurements of the loss function are available. We propose a method which combines genetic algorithm (GA) with simultaneous perturbation stochastic approximation (SPSA) to solve linearly constrained stochastic problems. The hybrid method uses GA to search for optimum over the whole feasible region, and SPSA to search for optimum at local region. During the GA and SPSA search process, the hybrid method generates new solutions according to gradient projection direction, which is calculated based on active constraints. Because the gradient projection method projects the search direction into the subspace at a tangent to the active constraints, it ensures new solutions satisfy all constraints strictly. This paper applies the hybrid method to nine typical constrained optimization problems and the results coincide with the ideal solutions cited in the references. The numerical results reveal that the hybrid method is suitable for multimodal constrained stochastic optimization problem. Moreover, each solution generated by the hybrid method satisfies all linear constraints strictly.     

On multi-criteria chance-constrained capacitated single-source discrete facility location problems

This work aims at investigating multi-criteria modeling frameworks for discrete stochastic facility location problems with single sourcing. We assume that demand is stochastic and also that a service level is imposed. This situation is modeled using a set of probabilistic constraints. We also consider a minimum throughput at the facilities to justify opening them. We investigate two paradigms in terms of multi-criteria optimization: vectorial optimization and goal programming. Additionally, we discuss the joint use of objective functions that are relevant in the context of some humanitarian logistics problems. We apply the general modeling frameworks proposed to the so-called stochastic shelter site location problem. This is a problem emerging in the context of preventive disaster management. We test the models proposed using two real benchmark data sets. The results show that considering uncertainty and multiple objectives in the type of facility location problems investigated leads to solutions that may better support decision making.     

基于双层规划的交通疏散中车辆出发与交通控制综合优化

在有组织的区域性疏散中,从需求调节(即疏散车辆出发安排)和供给管理(即交通管控)两方面对疏散交通流进行合理组织,是提高疏散效率的有效途径。论文立足于疏散车辆出发组织与路网交通管控之间的双层决策关系,建立双层规划模型对集结点疏散车辆的发车频率、路线和交叉口控制参数进行综合优化,其中上层模型通过优化信号交叉口的相位绿灯时间即绿信比以降低平均延误,其决策影响到交叉口通行能力等供给特性;下层模型通过优化疏散车辆的分批出发时间与路线以压缩疏散总时间,其决策影响到交叉口流量等需求特性。设计了基于遗产算法的求解步骤,给出了一个数值算例。将模型优化方案和只从交叉口控制参数出发的单方面优化模式所得结果进行了比较,结果表明只从调整绿灯时间着手不结合车辆的出发组织,很难有效降低延误和压缩疏散时间。     

不对称信息下反恐阻止网络设计

当前，我国面临的恐怖主义威胁日益严峻。为防止境外恐怖分子潜入，政府可设计反恐阻止网络，通过在交通网络中有效地分配例如安检仪器、传感设备等阻断资源，来提前识别和拦截正在潜入的恐怖分子。特别地，考虑信息不对称情形，把阻断资源分为"公开"和"隐蔽"两种类型，并假设恐怖分子观察不到"隐蔽"阻断。主要研究政府应如何同时优化两类阻断方案，才能发挥信息优势，设置"陷阱"并降低袭击分析。首先，将该问题构造为双层规划模型，上层规划是关于政府的阻止网络设计问题，下层规划则是关于恐怖分子的袭击节点选择和入侵路径优化问题。随后，设计一类用改进遗传算法处理上层规划，并结合下层规划直接求解的混合算法。其中，改进体现于杂交算子和变异算子的设计。最后，结合喀什地区进行算例分析，并分析"隐蔽"阻断的作用机理。     

On flexible product-mix decision problems under randomness and fuzziness

This paper considers several models of product-mix decision problems and production planning problems under uncertain conditions, and shows that these are extensional and versatile models for resolving previous product-mix problems. These proposed models include randomness derived from statistical analysis based on historical data, ambiguity of decision maker's intuition and the quality of received information, and flexibility in accomplishing the original plan. Furthermore, given that the upper limit values of some constraints have flexibility, and given a decision maker's level of satisfaction, we propose a flexible product mix of problems using the theory of constraints (TOC), and develop an efficient solution method. We then provide a numerical example that compares our models with some previous basic models. Efficiency of flexibility is obtained when our proposed models are applied to several conditions, such as measurable changes from the expected value of future returns.     

基于信息共享增值机制的供应链需求均衡优化

文章将供应商、经销商追求利益最大化目标与用户需求的相互作用表述为一个双层规划问题。其中,上层规划为供应商与经销商的零售价格优化模型,下层为用户购买与需求均衡模型,分别表现为寡头、垄断、社会最优等不同信息共享机制。文章设计灵敏度分析算法和迭代方法求解和优化供应链需求均衡问题。     

Designing time-of-use tariffs in electricity retail markets using a bi-level model – Estimating bounds when the lower level problem cannot be exactly solved

Time-of-use tariffs are a pricing strategy for a product or service in which the supplier establishes time-differentiated prices. Dynamic (e.g., day-ahead) time-differentiated electricity prices can contribute to increase the retailer's profit, allow end-users to reduce the consumption costs and enhance grid efficiency.The electricity retailer and the consumer are hierarchically related. The interaction between them can be modeled by a bi-level (BL) optimization model – the retailer is the upper level decision maker and the consumer is the lower level decision maker. The retailer and the consumer have different and conflicting goals: the retailer establishes the pricing scheme to sell electricity to consumers to maximize his profit; the consumer reacts to these prices by determining the operation of the controllable loads in order to minimize the discomfort and the electricity bill.In this work, a BL optimization model incorporating shiftable, interruptible and thermostatic loads is proposed. The upper level problem is tackled by a particle swarm optimization algorithm while the lower level problem is solved by an exact mixed-integer programming solver. The inclusion of the thermostatic load in the lower level problem imposes a much higher computational burden. Therefore, it may not be possible to find the optimal lower level solution, and a sub-optimal lower level solution is infeasible to the BL problem. Considering a computational budget, this work proposes an approach to compute good quality estimates of bounds for the upper level objective function, providing the leader further information and allowing him to make sounder decisions in an adequate time frame.     

基于持续运营机会约束的竞争设施点选址研究——一种有效的实数编码遗传求解算法

竞争设施点选址是空间经济、区域发展、组合优化和系统工程的重要课题之一。本文以市场份额最大化为目标,研究了基于持续运营机会约束的竞争设施点选址问题,并给出了一种有效的实数编码遗传求解算法。在求解模型方面,首先假定运营成本是竞争设施点规模大小的函数,并对设施点持续运营概率进行机会约束,借鉴引力模型建立竞争设施点选址-设计问题的非线性混合整数规划模型。其次,考虑到选址变量和规模变量的数值类型,以及编码变换问题,设计了一种实数编码遗传求解算法。通过数值实验表明,对不同规模问题的实际计算结果,该算法可以在较短时间内获得最优解,可行解和精确解之间误差小于0.5%,相关比较分析也讨论了该算法的优越性和实用性,为竞争设施点选址问题的研究提供了不同的视角和实用求解算法。     

An ant colony algorithm for solving budget constrained and unconstrained dynamic facility layout problems

The main characteristic of today's manufacturing environments is volatility. Under a volatile environment, demand is not stable. It changes from one production period to another. To operate efficiently under such environments, the facilities must be adaptive to changing production requirements. From a layout point of view, this situation requires the solution of the dynamic layout problem (DLP). DLP is a computationally complex combinatorial optimization problem for which optimal solutions can only be found for small size problems. It is known that classical optimization procedures are not adequate for this problem. Therefore, several heuristics including taboo search, simulated annealing and genetic algorithm are applied to this problem to find a good solution. This work makes use of the ant colony optimization (ACO) algorithm to solve the DLP by considering the budget constraints. The paper makes the first attempt to show how the ACO can be applied to DLP with the budget constraints. In the paper, example applications are presented and computational experiments are performed to present suitability of the ACO to solve the DLP problems. Promising results are obtained from the solution of several test problems.     

一种策略层项目计划的双目标优化方法

针对产品开发项目管理的实际情况,对策略层计划优化方法进行研究。以工作包的工作量估算为基础,以资源投入水平和工期最小化为目标,考虑各种约束条件,提出一种策略层项目计划问题的混合整数规划问题模型。以非支配遗传算法NSGA-II为基础框架,设计了一种改进的双目标遗传算法。该算法针对问题的特点,提出了基于资源平滑的解码算法。参考NSGA-III的关键特征,对拥挤密度计算方法进行改进。通过企业实际项目案例,验证了算法的性能和所提出的策略层项目计划方法的有效性。     

On the fair optimization of cost and customer service level in a supply chain under disruption risks

This paper presents a new decision-making problem of a fair optimization with respect to the two equally important conflicting objective functions: cost and customer service level, in the presence of supply chain disruption risks. Given a set of customer orders for products, the decision maker needs to select suppliers of parts required to complete the orders, allocate the demand for parts among the selected suppliers, and schedule the orders over the planning horizon, to equitably optimize expected cost and expected customer service level. The supplies of parts are subject to independent random local and regional disruptions. The fair decision-making aims at achieving the normalized expected cost and customer service level values as much close to each other as possible. The obtained combinatorial stochastic optimization problem is formulated as a stochastic mixed integer program with the ordered weighted averaging aggregation of the two conflicting objective functions. Numerical examples and computational results, in particular comparison with the weighted-sum aggregation of the two objective functions are presented and some managerial insights are reported. The findings indicate that for the minimum cost objective the cheapest supplier is usually selected, and for the maximum service level objective a subset of most reliable and most expensive suppliers is usually chosen, whereas the equitably efficient supply portfolio usually combines the most reliable and the cheapest suppliers. While the minimum cost objective function leads to the largest expected unfulfilled demand and the expected production schedule for the maximum service level follows the customer demand with the smallest expected unfulfilled demand, the equitably efficient solution ensures a reasonable value of expected unfulfilled demand.