随机容错设施选址问题的原始-对偶近似算法

研究两阶段随机容错设施选址问题,其中需要服务的顾客在第二阶段出现（在第一阶段不知道）．两个阶段中每个设施的开设费用可以不同,设施的开设依赖于阶段和需要服务的顾客集合（称为场景）．并且在出现的场景里的每个顾客都有相同的连接需求,即每个顾客需要由r个不同的设施服务．给定所有可能的场景及相应的概率,目标是在两个阶段分别选取开设的设施集合,将出现场景的顾客连接到r个不同的开设设施上,使得包括设施费用和连接费用的总平均费用最小．根据问题的特定结构,给出了原始。对偶（组合）3-近似算法．     

Assigning cooperating UAVs to simultaneous tasks on consecutive targets using genetic algorithms

A problem of assigning multiple agents to simultaneously perform cooperative tasks on consecutive targets is posed as a new combinatorial optimization problem. The investigated scenario consists of multiple ground moving targets prosecuted by a team of unmanned aerial vehicles (UAVs). The team of agents is heterogeneous, with each UAV carrying designated sensors and all but one carry weapons as well. To successfully prosecute each target it needs to be simultaneously tracked by two UAVs and attacked by a third UAV carrying a weapon. Only for small-sized scenarios involving not more than a few vehicles and targets the problem can be solved in sufficient time using classical combinatorial optimization methods. For larger-sized scenarios the problem cannot be solved in sufficient time using these methods due to timing constraints on the simultaneous tasks and the coupling between task assignment and path planning for each UAV. A genetic algorithm (GA) is proposed for efficiently searching the space of feasible solutions. A matrix representation of the chromosomes simplifies the encoding process and the application of the genetic operators. To further simplify the encoding, the chromosome is composed of sets of multiple genes, each corresponding to the entire set of simultaneous assignments on each target. Simulation results show the viability of the proposed assignment algorithm for different sized scenarios. The sensitivity of the performance to variations in the GA tuning parameters is also investigated.     

Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion

In this paper a class of bottleneck combinatorial optimization problems with uncertain costs is discussed. The uncertainty is modeled by specifying a discrete scenario set containing a finite number of cost vectors, called scenarios. In order to choose a solution the Ordered Weighted Averaging aggregation operator (OWA for short) is applied. The OWA operator generalizes traditional criteria in decision making under uncertainty such as the maximum, minimum, average, median, or Hurwicz criterion. New complexity and approximation results in this area are provided. These results are general and remain valid for many problems, in particular for a wide class of network problems.     

App开发者质量投资和定价策略研究

本文考虑了由两个App开发者和一个下载平台商所构成的二级App供应链,在开发者间存在价格竞争和质量竞争的情况下,区分开发者竞争、开发者合作、供应链集中决策以及混合竞争四种不同的情景,建立了开发者质量投资和定价决策模型,分析了四种情景下开发者的均衡策略,并通过数值仿真进一步探讨了价格竞争程度和质量竞争程度对不同情境下均衡结果的影响。研究表明,高能力开发者的最优质量投资水平以及最优App价格均高于低能力开发者;价格竞争程度和质量竞争程度对非合作情形下的最优策略影响显著,对合作情形下的最优策略影响不显著;此外,App供应链总利润的高低取决于开发者与平台商之间合作的紧密程度。     

A randomized algorithm for the min-max selecting items problem with uncertain weights

This paper deals with the min-max version of the problem of selecting p items of the minimum total weight out of a set of n items, where the item weights are uncertain. The discrete scenario representation of uncertainty is considered. The computational complexity of the problem is explored. A randomized algorithm for the problem is then proposed, which returns an O(ln K)-approximate solution with a high probability, where K is the number of scenarios. This is the first approximation algorithm with better than K worst case ratio for the class of min-max combinatorial optimization problems with unbounded scenario set.     

Scenario-based portfolio selection of investment projects with incomplete probability and utility information

In the selection of investment projects, it is important to account for exogenous uncertainties (such as macroeconomic developments) which may impact the performance of projects. These uncertainties can be addressed by examining how the projects perform across several scenarios; but it may be difficult to assign well-founded probabilities to such scenarios, or to characterize the decision makers’ risk preferences through a uniquely defined utility function. Motivated by these considerations, we develop a portfolio selection framework which (i) uses set inclusion to capture incomplete information about scenario probabilities and utility functions, (ii) identifies all the non-dominated project portfolios in view of this information, and (iii) offers decision support for rejection and selection of projects. The proposed framework enables interactive decision support processes where the implications of additional probability and utility information or further risk constraints are shown in terms of corresponding decision recommendations.     

System/scenario duality—a supporting equivalence

The two well-known strategic toolsets of scenarios and systems thinking possess a structural mutuality. The latter focuses on future states, whereas the former focuses on the mechanisms that create those possible futures. An ensemble of scenarios for strategic use should exhibit a homogeneity in its underlying behavioural assumptions while, self-evidently, illustrating variations on those assumptions in terms of the outcomes captured by the scenarios. Thus, in order to create a suitable scenario ensemble (for strategic hypothesising, assessment of candidate policies, risk appraisal, etc) there needs to exist a stable system assumption common to all of the scenarios. The purpose of this paper is to explore the nature of this duality between coherence in a scenario ensemble and the underlying system representation and to illustrate a procedure for utilising this duality to improve scenario and system model building. This is approached from two directions. First, the contribution of explicit system mechanisms (dominant loops) in characterising and creating coherence in scenario ensembles is discussed. Second, the dual problem, that of the extent to which an existing coherent ensemble of scenarios can throw light on the dominant underlying system assumptions, is explored. The conclusions of the paper are that there is use in mobilising this duality of representation, this being illustrated by a brief, multi-informant case study of the futures of the business school industry of the UK. The explication and analysis of the case study shows the procedure in use.     

Routes to chaos in continuous mechanical systems: Part 2. Modelling transitions from regular to chaotic dynamics

In second part of the paper both classical and novel scenarios of transition from regular to chaotic dynamics of dissipative continuous mechanical systems are studied. A detailed analysis allowed us to detect the already known classical scenarios of transition from periodic to chaotic dynamics, and in particular the Feigenbaum scenario. The Feigenbaum constant was computed for all continuous mechanical objects studied in the first part of the paper. In addition, we illustrate and discuss different and novel scenarios of transition of the analysed systems from regular to chaotic dynamics, and we show that the type of scenario depends essentially on excitation parameters.     

Generating Scenarios of Division as Sharing and Grouping: A Study of Japanese Elementary and University Students

Elementary school students learn two types of division scenarios: partitive and quotitive. Previous researchers have assumed that the partitive scenario is easier because it reflects the everyday notion of sharing, whereas the quotitive scenario, which represents grouping, is more difficult and is understood gradually in the course of mathematics learning. However, this assumption has not been adequately investigated in empirical studies. The present study examines the assumption in a cross-sectional study. Participants were 336 elementary school students (98 in Grade 3, 82 in Grade 4, 88 in Grade 5, and 68 in Grade 6) and 70 university students who performed two tasks. In the preference task, they generated a division scenario of any type consistent with a given numerical equation. In the problem-posing task, they generated a division scenario consistent with both a numerical equation and a picture representing a partitive or quotitive scenario. On the preference task, students at all grade levels preferred the partitive to the quotitive scenario, and this preference increased with students’ grade level. On the problem-posing task, younger students (Grades 3, 4, and 5) had equivalent success in the partitive and quotitive scenarios, but older students (Grade 6 and university) found the partitive scenario to be easier than the quotitive. Implications for mathematics education are discussed.     

Fair resource allocation for different scenarios of demands

This paper considers a resource allocation problem, which objective is to treat fairly all the system users. Usually the requests cannot be entirely predicted, but the manager can forecast the request evolution, this leading to a set of possible scenarios. Such a problem arises for instance in network bandwidth allocation as well as in storage space management. It also appears in the management of computer systems, such as computational grids or in cloud computing, when teams share a common pool of machines. Problems of fair resource sharing arise among users with equal access right but with different needs.Here the problem is tackled by a multi-criteria model, where one criterion is associated to one scenario. A solution is a policy, which provides an allocation for each scenario. An algorithm is proposed and analysed that lists all solutions which are Pareto optimal with regard to the different possible user request scenarios. The algorithm is used offline, but can be adapted, with some additional hypothesis, to be used online.     

Simple dynamic location problem with uncertainty: a primal-dual heuristic approach

Abstract

In this paper, the simple dynamic facility location problem is extended to uncertain realizations of the potential locations for facilities and the existence of customers as well as fixed and variable costs. With limited knowledge about the future, a finite and discrete set of scenarios is considered. The decisions to be made are where and when to locate the facilities, and how to assign the existing customers over the whole planning horizon and under each scenario, in order to minimize the expected total costs. Whilst assignment decisions can be scenario dependent, location decisions have to take into account all possible scenarios and cannot be changed according to each scenario in particular. We first propose a mixed linear programming formulation for this problem and then we present a primal-dual heuristic approach to solve it. The heuristic was tested over a set of randomly generated test problems. The computational results are provided.     

Government formation in a two dimensional policy space

Given any allocation of parliament seats among parties, we characterize all the stable government configurations (supported by at least a majority of the parliament) in terms of winning coalitions and policy outcomes. We consider a two dimensional policy space and we assume that there are four parties that care mainly about holding office, and only instrumentally about policy. We find that for any distribution of seats in the parliament only two scenarios are possible: either there is a party that is a member of almost all equilibrium coalitions (dominant party scenario) or there is a party that is never a member of an equilibrium coalition (dominated party scenario). We characterize the key party for each possible scenario and we show that it is sufficient that the key party has intense preferences over one the issues to guarantee the formation of a stable government coalition.     

Monte Carlo scenario generation for retail loan portfolios

Monte Carlo simulation is a common method for studying the volatility of market traded instruments. It is less employed in retail lending, because of the inherent nonlinearities in consumer behaviour. In this paper, we use the approach of Dual-time Dynamics to separate loan performance dynamics into three components: a maturation function of months-on-books, an exogenous function of calendar date, and a quality function of vintage origination date. The exogenous function captures the impacts from the macroeconomic environment. Therefore, we want to generate scenarios for the possible futures of these environmental impacts. To generate such scenarios, we must go beyond the random walk methods most commonly applied in the analysis of market-traded instruments. Retail portfolios exhibit autocorrelation structure and variance growth with time that requires more complex modelling. This paper is aimed at practical application and describes work using ARMA and ARIMA models for scenario generation, rules for selecting the correct model form given the input data, and validation methods on the scenario generation. We find when the goal is capturing the future volatility via Monte Carlo scenario generation, that model selection does not follow the same rules as for forecasting. Consequently, tests more appropriate to reproducing volatility are proposed, which assure that distributions of scenarios have the proper statistical characteristics. These results are supported by studies of the variance growth properties of macroeconomic variables and theoretical calculations of the variance growth properties of various models. We also provide studies on historical data showing the impact of training length on model accuracy and the existence of differences between macroeconomic epochs.     

On scenario aggregation to approximate robust combinatorial optimization problems

As most robust combinatorial min–max and min–max regret problems with discrete uncertainty sets are NP-hard, research in approximation algorithm and approximability bounds has been a fruitful area of recent work. A simple and well-known approximation algorithm is the midpoint method, where one takes the average over all scenarios, and solves a problem of nominal type. Despite its simplicity, this method still gives the best-known bound on a wide range of problems, such as robust shortest path or robust assignment problems. In this paper, we present a simple extension of the midpoint method based on scenario aggregation, which improves the current best K-approximation result to an \((\varepsilon K)\)-approximation for any desired \(\varepsilon > 0\). Our method can be applied to min–max as well as min–max regret problems.     

Worst-case robust decisions for multi-period mean–variance portfolio optimization

In this paper, we extend the multi-period mean–variance optimization framework to worst-case design with multiple rival return and risk scenarios. Our approach involves a min–max algorithm and a multi-period mean–variance optimization framework for the stochastic aspects of the scenario tree. Multi-period portfolio optimization entails the construction of a scenario tree representing a discretised estimate of uncertainties and associated probabilities in future stages. The expected value of the portfolio return is maximized simultaneously with the minimization of its variance. There are two sources of further uncertainty that might require a strengthening of the robustness of the decision. The first is that some rival uncertainty scenarios may be too critical to consider in terms of probabilities. The second is that the return variance estimate is usually inaccurate and there are different rival estimates, or scenarios. In either case, the best decision has the additional property that, in terms of risk and return, performance is guaranteed in view of all the rival scenarios. The ex-ante performance of min–max models is tested using historical data and backtesting results are presented.     

Second-order scenario approximation and refinement in optimization under uncertainty

When solving scenario-based stochastic programming problems, it is imperative that the employed solution methodology be based on some form of problem decomposition: mathematical, stochastic, or scenario decomposition. In particular, the scenario decomposition resulting from scenario approximations has perhaps the least tendency to be computationally tedious due to increases in the number of scenarios. Scenario approximations discussed in this paper utilize the second-moment information of the given scenarios to iteratively construct a (relatively) small number of representative scenarios that are used to derive bounding approximations on the stochastic program. While the sizes of these approximations grow only linearly in the number of random parameters, their refinement is performed by exploiting the behavior of the value function in the most effective manner. The implementation SMART discussed here demonstrates the aptness of the scheme for solving two-stage stochastic programs described with a large number of scenarios.This paper was presented at the IFIP Workshop onStochastic Programming: Algorithms and Models, Lillehammer, Norway, January 1994.     

An approach to the automatic abstracting of Russian texts

A new method of the automatic abstracting of Russian texts which takes account of their functional style is considered. The texts are broken up into five groups and, for each group, its own scenario of constructing the abstract is developed. A general adjustable algorithm embodying the possibilities of all the scenarios developed is described.     

Airline network revenue management by multistage stochastic programming

A multistage stochastic programming approach to airline network revenue management is presented. The objective is to determine seat protection levels for all itineraries, fare classes, points of sale of the airline network and all dcps of the booking horizon such that the expected revenue is maximized. While the passenger demand and cancelation rate processes are the stochastic inputs of the model, the stochastic protection level process represents its output and allows to control the booking process. The stochastic passenger demand and cancelation rate processes are approximated by a finite number of tree structured scenarios. The scenario tree is generated from historical data using a stability-based recursive scenario reduction scheme. Numerical results for a small hub-and-spoke network are reported. This research is supported by the DFG Research Center Matheon “Mathematics for key technologies” in Berlin.     

A test suite for the evaluation of mixed multi-unit combinatorial auctions

Mixed Multi-Unit Combinatorial Auctions extend and generalize all the preceding types of combinatorial auctions. In this paper, we try to make headway on the practical application of MMUCAs by: (1) providing an algorithm to generate artificial data that is representative of the sort of scenarios a winner determination algorithm is likely to encounter; and (2) subsequently assessing the performance of an Integer Programming implementation of MMUCA in CPLEX.