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

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

The computational complexity of bilevel assignment problems

In bilevel optimization problems there are two decision makers, the leader and the follower, who act in a hierarchy. Each decision maker has his own objective function, but there are common constraints. This paper deals with bilevel assignment problems where each decision maker controls a subset of edges and each edge has a leader’s and a follower’s weight. The edges selected by the leader and by the follower need to form a perfect matching. The task is to determine which edges the leader should choose such that his objective value which depends on the follower’s optimal reaction is maximized. We consider sum- and bottleneck objective functions for the leader and follower. Moreover, if not all optimal reactions of the follower lead to the same leader’s objective value, then the follower either chooses an optimal reaction which is best (optimistic rule) or worst (pessimistic rule) for the leader. We show that all the variants arising if the leader’s and follower’s objective functions are sum or bottleneck functions are NP-hard if the pessimistic rule is applied. In case of the optimistic rule the problem is shown to be NP-hard if at least one of the decision makers has a sum objective function.     

A robust approach for modeling limited observability in bilevel optimization

Many applications of bilevel optimization contain a leader facing a follower whose reaction deviates from the one expected by the leader due to some kind of bounded rationality. We consider bilinear bilevel problems with follower's response uncertainty due to limited observability regarding the leader's decision and exploit robust optimization to model the decision making of the follower. We show that the robust counterpart of the lower level allows to tackle the problem via the lower level's KKT conditions.     

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.     

Asset allocation with distorted beliefs and transaction costs

In this paper we study the problem of the optimal portfolio selection with transaction costs for a decision-maker who is faced with Knightian uncertainty. The decision-maker’s portfolio consists of one risky and one risk-free asset, and we assume that the transaction costs are proportional to the traded volume of the risky asset. The attitude to uncertainty is modeled by the Choquet expected utility. We derive optimal strategies and bounds of the no-transaction region for both optimistic and pessimistic decision-makers. The no-transaction region of a pessimistic investor is narrower and its bounds lie closer to the origin than that of an optimistic trader. Moreover, under the Choquet expected utility the structure of the no-transaction region is not necessarily a closed interval as it is under the standard expected utility model.     

Hurwicz model of uncertain optimal control with jump

How to choose the optimization criterion of the objective function is an important issue for uncertain optimal control. The Hurwicz criterion is a flexible optimization criterion attempting to find the intermediate area between the extremes posed by the optimistic and pessimistic criteria. Based on uncertainty theory, in this paper, we establish a new uncertain optimal control model with jump by making use of Hurwicz criterion to optimize an uncertain objective function. By applying Bellman's principle of optimality, the principle of optimality for the proposed model is presented and then the equation of optimality is derived. Finally, an example is given to show the the effectiveness of the results obtained.     

On Intrinsic Complexity of Nash Equilibrium Problems and Bilevel Optimization

In this article we study generalized Nash equilibrium problems (GNEP) and bilevel optimization side by side. This perspective comes from the crucial fact that both problems heavily depend on parametric issues. Observing the intrinsic complexity of GNEP and bilevel optimization, we emphasize that it originates from unavoidable degeneracies occurring in parametric optimization. Under intrinsic complexity, we understand the involved geometrical complexity of Nash equilibria and bilevel feasible sets, such as the appearance of kinks and boundary points, non-closedness, discontinuity and bifurcation effects. The main goal is to illustrate the complexity of those problems originating from parametric optimization and singularity theory. By taking the study of singularities in parametric optimization into account, the structural analysis of Nash equilibria and bilevel feasible sets is performed. For GNEPs, the number of players’ common constraints becomes crucial. In fact, for GNEPs without common constraints and for classical NEPs we show that—generically—all Nash equilibria are jointly nondegenerate Karush–Kuhn–Tucker points. Consequently, they are isolated. However, in presence of common constraints Nash equilibria will constitute a higher dimensional set. In bilevel optimization, we describe the global structure of the bilevel feasible set in case of a one-dimensional leader’s variable. We point out that the typical discontinuities of the leader’s objective function will be caused by follower’s singularities. The latter phenomenon occurs independently of the viewpoint of the optimistic or pessimistic approach. In case of higher dimensions, optimistic and pessimistic approaches are discussed with respect to possible bifurcation of the follower’s solutions.     

An improved method for ranking alternatives in multiple criteria decision analysis

Scoring rules are an important disputable subject in data envelopment analysis (DEA). Various organizations use voting systems whose main object is to rank alternatives. In these methods, the ranks of alternatives are obtained by their associated weights. The method for determining the ranks of alternatives by their weights is an important issue. This problem has been the subject at hand of some authors. We suggest a three-stage method for the ranking of alternatives. In the first stage, the rank position of each alternative is computed based on the best and worst weights in the optimistic and pessimistic cases, respectively. The vector of weights obtained in the first stage is not a singleton. Hence, to deal with this problem, a secondary goal is used in the second stage. In the third stage of our method, the ranks of the alternatives approach the optimistic or pessimistic case. It is mentionable that the model proposed in the third stage is a multi-criteria decision making (MCDM) model and there are several methods for solving it; we use the weighted sum method in this paper. The model is solved by mixed integer programming. Also, we obtain an interval for the rank of each alternative. We present two models on the basis of the average of ranks in the optimistic and pessimistic cases. The aim of these models is to compute the rank by common weights.     

Preference Approach to Fuzzy Linear Inequalities and Optimizations

In this study we first present the preference structures in decision making as a generalized non-linear function. Then, we incorporate it into a fuzzy linear inequality of which the progressive and conservative manners are described by the concept of target hyperplanes. Thus, ones preference domain is said to be bounded by such soft constraint. When facing different situations, a membership function is defined as an evaluation function for incorporating ones optimistic or pessimistic attitude into this soft constraint. Once a goal is pursued, the problem is transformed into a symmetric fuzzy linear program. Based on max–min principle, an auxiliary crisp model in the form of a generalized fractional program is derived. Then, Dinkelbach-type-2 and the bisection algorithms are adopted for solution. Finally their simulation results of an uncertain production scheduling problem are reported.     

The core of an economy with a common pool resource: A partition function form approach

In this paper we consider a model of an economy with a common pool resource. Under decreasing returns to scale, it is well-known that no Nash equilibrium attains Pareto efficiency. We examine whether it is possible to achieve Pareto efficiency and avoid the tragedy of the commons through cooperation among players. For that purpose, we use the notion of a game in partition function form. Whether or not the core exists depends crucially on the expectations of each coalition regarding the coalition formation of the outsiders. If each coalition has pessimistic expectations, then the core always exists, while if it has optimistic expectations, the core may be empty. Received: January 1998/Final version: November 1998     

A note on tight extensive game forms

Associated with each extensive game form are the α- and β-effectivity functions,E _α andE _β. These functions characterize the effective capabilities which coalitions command under pessimistic and optimistic cooperative behavior respectively. A game form is said to be tight whenE _α ≡E _β, in which case pessimistic, optimistic, and intermediate types of behavior all support the same effective power. Dalkey's condition for Nash consistency, essentially perfect information, is found to be a necessary and sufficient condition for a game form to be tight.     

基于乐观抱怨值和悲观抱怨值的合作博弈最优妥协值的求解模型

基于乐观抱怨值和悲观抱怨值,通过建立二次规划模型求解(Hou,et al.,2018)定义的平衡博弈的最优妥协值,二次规划模型及求解方法比(Hou,et al.,2018)提出的字典序方法简单易操作.此外,文章进一步给出了同时满足个体合理性和群体有效性的乐观最优妥协值的求解算法.最后,通过数值实例说明文章建立的模型和方...     

An Optimization Model for Stochastic Project Networks with Cash Flows

Project networks – or PERT networks – can be characterized by random completion times of activities and positive or negative cash flows throughout the project. In these cases the decision maker’s problem consists of determining a feasible activities schedule, to maximize the project financial value, where the financial value is measured by the net present value (npv) of cash flows.The analysis of these networks is a difficult computational task for the following reason. First, suppose that a schedule is fixed using a heuristic rule. Then the expected npv is calculated. But, due to stochastic job completion times, this problem belongs to the ♯-P complete difficulty class, e.g. problems that involve finding all the Hamiltonian cycles in a network. The problem is such that evaluating one project alone is not sufficient, but the optimal one has to be selected. This involves a further increase in computational time.This paper proposes a stochastic optimization model to determine a heuristic scheduling rule, that provides an approximate solution to finding the optimal project npv. A feature of this approach is that the scheduling rule is completely deterministic and defined when the project begins. Therefore an upper bound of the expected npv, that is an optimistic estimate, can be calculated through linear programming and a lower bound, that is a pessimistic estimate, can be calculated using simulation before the project begins.     

Softening Bilevel Problems Via Two-scale Gibbs Measures

We introduce a new, and elementary, approximation method for bilevel optimization problems motivated by Stackelberg leader-follower games. Our technique is based on the notion of two-scale Gibbs measures. The first scale corresponds to the cost function of the follower and the second scale to that of the leader. We explain how to choose the weights corresponding to these two scales under very general assumptions and establish rigorous Γ-convergence results. An advantage of our method is that it is applicable both to optimistic and to pessimistic bilevel problems.

     

Two-level value function approach to non-smooth optimistic and pessimistic bilevel programs

ABSTRACT

The authors' paper in Dempe et al. [Necessary optimality conditions in pessimistic bilevel programming. Optimization. 2014;63:505–533], was the first one to provide detailed optimality conditions for pessimistic bilevel optimization. The results there were based on the concept of the two-level optimal value function introduced and analysed in Dempe et al. [Sensitivity analysis for two-level value functions with applications to bilevel programming. SIAM J. Optim. 22 (2012), 1309–1343], for the case of optimistic bilevel programs. One of the basic assumptions in both of these papers is that the functions involved in the problems are at least continuously differentiable. Motivated by the fact that many real-world applications of optimization involve functions that are non-differentiable at some points of their domain, the main goal of the current paper is to extend the two-level value function approach by deriving new necessary optimality conditions for both optimistic and pessimistic versions in bilevel programming with non-smooth data.     

模糊机会约束规划下的投资组合模型

资产的过去数据和专家对资产未来表现的判断是资产收益率的两个重要信息,本文用基于上述两个信息的可能性分布描述证券收益率的不确定性,结合可能性测度和必要性测度,建立了基于模糊机会约束规划的乐观型和悲观型投资组合模型,并且得到了各模型的最优解的解析式。最后给出了算例予以说明。     

Probabilistic prospects of Stackelberg leader and follower

In this paper, we consider the family of allm×n bimatrix games, whose payoff entries are the players' orderings of the outcomes, and count the fraction of games whose Stackelberg solution is the leader'sh ^th best outcome and the follower'sk ^th best outcome (h,k≤mn). We conclude that the average leader and follower enjoy symmetric prospects, and that the advantage lies not in the leadership role, but in the relative size of the player's strategy space.     

Solving the Shortest Path Problem with Interval Arcs

This paper presents an algorithm for the shortest path problem when the connected arcs in a transportation network are represented as interval numbers. The methodology proposed in this paper considers fuzzy preference ordering of intervals (Sengupta and Pal (2000), European Journal of Operational Research 127, 28–43) from pessimistic and optimistic decision maker’s point of view.     

On Huber's contaminated model

Huber's contaminated model is a basic model for data with outliers. This paper aims at addressing several fundamental problems about this model. We first study its identifiability properties. Several theorems are presented to determine whether the model is identifiable for various situations. Based on these results, we discuss the problem of estimating the parameters with observations drawn from Huber's contaminated model. A definition of estimation consistency is introduced to handle the general case where the model may be unidentifiable. This consistency is a strong robustness property. After showing that existing estimators cannot be consistent in this sense, we propose a new estimator that possesses the consistency property under mild conditions. Its adaptive version, which can simultaneously possess this consistency property and optimal asymptotic efficiency, is also provided. Numerical examples show that our estimators have better overall performance than existing estimators no matter how many outliers in the data.     

An inventory model for a deteriorating item with displayed stock dependent demand under fuzzy inflation and time discounting over a random planning horizon

An inventory model for a deteriorating item (seasonal product) with linearly displayed stock dependent demand is developed in imprecise environment (involving both fuzzy and random parameters) under inflation and time value of money. It is assumed that time horizon, i.e., period of business is random and follows exponential distribution with a known mean. The resultant effect of inflation and time value of money is assumed as fuzzy in nature. The particular case, when resultant effect of inflation and time value is crisp in nature, is also analyzed. A genetic algorithm (GA) is developed with roulette wheel selection, arithmetic crossover, random mutation. For crisp inflation effect, the total expected profit for the planning horizon is maximized using the above GA to derive optimal inventory decision. On the other hand when inflationary effect is fuzzy then the above expected profit is fuzzy in nature too. Since optimization of fuzzy objective is not well defined, the optimistic/pessimistic return of the expected profit is obtained using possibility/necessity measure of fuzzy event. Fuzzy simulation process is proposed to determine this optimistic/pessimistic return. Finally a fuzzy simulation based GA is developed and is used to maximize the above optimistic/pessimistic return to get optimal decision. The models are illustrated with some numerical examples and some sensitivity analyses have been presented.