 |
|
||||||||||
Publications 2000 and earlier
2000
| Agent-Based Management Systems in Logistics | |
| Authors | Jens Henoch, Heinz Ulrich |
| Abstract | In logistics of today's economy we have to deal with distributed systems. To support the demanding management task the multi-agent approach offers promising perspectives. For human organizations a socio-technical system is to be handled. The theory of organizational cybernetics provides basic knowledge about structure- theoretic foundations to reach organizational fitness. For the design of management systems based on a multi-agent concept, we try to adopt as much as possible of the insight valid for human based socio-technical systems to the agent world. We particularly focus on identifying the main characteristics for designing management systems in order to achieve the ability to master a system in a dynamic environment evolving in a short and long-term horizon. |
| Reference | I.Timm et al., ed., Proceedings of the ECAI 2000 Workshop 13 "Agent Technologies and Their Application Scenarios in Logistics", 2000 |
| Download | |
| HIDES: Towards an Agent-Based Simulator | |
| Authors | Jens Henoch, Heinz ULrich |
| Abstract | The simulation platform HIDES is particularly designed for the simulation of logistics systems. The most important characteristics of this discrete-event simulator are the reference model for logistics systems providing a small number of simple generic elements as modeling basis and the strict separation of physical and logical level in the modeling process. The planning and control task in logistics is of increasing complexity, hence distributed solution approaches, as the multi-agent concept, offer promising perspectives. For developing purposes a test-bed for agent-based simulation is conceived by adding a third level to the simulator kernel, the management level. This management level comprises a management system including an agent community, where agents are in charge of the operational tasks in the logistics system. |
| Reference | Christoph Urban, ed., Proceedings of the Workshop 2000 on Agent Based Simulation, SCS European Publishing House, May, 2000 |
| Download | PDF, PS, PS.gz |
| Modelling Dependence with Copulas and Applications to Risk Management | |
| Author | Filip Lindskog |
| Abstract | The dependence between random variables is completely described by their joint distribution. However, dependence and marginal behaviour can be separated. The copula of a multivariate distribution can be considered to be the part describing the dependence structure. Furthermore, strictly increasing transformations of the underlying random variables result in the transformed variables having the same copula. Hence copulas are invariant under strictly increasing transformations of the margins. This provides a way of studying scale-invariant measures of associations and also a starting point for construction of multivariate distributions. Scale-invariant measures of association such as Kendall's tau and Spearman's rho only depend on the copula and are thus invariant under strictly increasing transformations of the margins, which means that we can apply arbitrary continuous margins to our chosen copula leaving among other things the measures of association unchanged. Tail dependence and Kendall's tau and Spearman's rho are presented and evaluated for a large number of copula families. Among these copula families are families suitable for modelling extreme events, which are highly relevant as a basis for risk models in insurance and finance. The multivariate normal distribution and linear correlation are the basis of most models used to model dependence. Even though this distribution has a wide range of dependence it is quite seldom suitable for modelling real world situations in insurance and finance. We will show that using a model based on the multivariate normal distribution without knowledge of its limitations can prove very dangerous. Linear correlation is a natural measure of dependence in the context of the normal distribution. However, it should be noted that it is not invariant under strictly increasing transformations of the marginals and can be misleading as a measure of dependence. The problem of simulating dependent data arises naturally in Monte Carlo approaches to risk management. One main aim of this talk is to show that when addressing this problem knowledge of copulas and copula based dependence concepts is important, and also the usefulness of copula ideas in this approach to risk management. Another main aim of this talk is the construction of multivariate extensions of bivariate copula families. In particular we focus on multivariate extensions with a flexible and wide range of dependence for which efficient algorithms for random variate generation are presented. |
| Download | PDF, PS, PS.gz |
| The Analytic Center Quadratic Cut Method for Strongly Monotone Variational Inequality Problems | |
| Authors | Hans-Jakob Lüthi, Benno Büeler |
| Abstract | Convergence of an algorithm for strongly monotone variational inequality problems (VIPs) is investigated. At each iteration, the algorithm adds a quadratic cut through the analytic center of the consequently shrinking convex set. It is shown that the convergence of analytic centers converges to the unique solution in O(1/sqrt(k)), where k is the number of iterations. |
| Reference | SIAM J. on Optimization, Vol. 10, No.2, pp. 415-426, 2000 |
| Download | PDF, PS, PS.gz |
| Cocircuit graphs and efficient orientation reconstruction in oriented matroids. | |
| Authors | E. Babson, L. Finschi and K. Fukuda |
| Abstract |
We consider the cocircuit graph GM of an oriented matroid M, which is the 1-skeleton of the cell complex formed by the span of the cocircuits of M. As a result of Cordovil, Fukuda, and Guedes de Oliveira, the isomorphism class of M is not determined by GM, but it is determined if M is uniform and the vertices in GM are paired if they are associated to negative cocircuits; furthermore the reorientation class of an oriented matroid M with rank(M) >= 2 is determined by GM if every vertex in GM is labeled by the zero support of the associated cocircuit. In this paper we show that the isomorphism class of a uniform oriented matroid is determined by the cocircuit graph, and we present polynomial algorithms which provide constructive proofs to all these results. Furthermore it is shown that the correctness of the input of the algorithms can be verified in polynomial time. |
| Download | PDF, PS, PS.gz |
1999
| The parallel search bench zram and its applications | |
| Authors |
A. Brüngger, A. Marzetta, K. Fukuda, and J. Nievergelt |
| Abstract |
Distributed and parallel computation is, on the one hand, the cheapest way to increase raw computing power. Turning parallelism into a useful tool for solving new problems, on the other hand, presents formidable challenges to computer science. We believe that parallel computation will spread among general users mostly through the ready availability of convenient and powerful program libraries. In contrast to general-purpose languages, a program library is specialized towards a well-defined class of problems and algorithms. This narrow focus permits developers to optimize algorithms, once and for all, for parallel computers of a variety of common architectures. This paper presents ZRAM, a portable parallel library of exhaustive search algorithms, as a case study that proves the feasibility of achieving simultaneously the goals of portability, efficiency, and convenience of use. Examples of massive computations successfully performed with the help of ZRAM illustrate its capabilities and use. The Role of Computing Power for Combinatorial Search For half a century since computers came into existence, the goal of finding elegant and efficient algorithms to solve "simple" (well-defined and well-structured) problems has dominated algorithm design. Over the same time period, both processing and storage capacity of computers have increased roughly by a factor of 106. The next few decades may well give us a similar rate of growth in raw computing power, due to various factors such as continuing miniaturization, parallel and distributed computing. If a quantitative change of orders of magnitude leads to qualitative changes, where will the latter take place? |
| Download | PDF, PS, PS.gz |
| Frontier Analysis in Air Pollution | |
| Author | Eleni Pratsini |
| Abstract | Carbon containing aerosol is the most abundant particulate air pollutant species. It causes poor visibility and can be toxic. Tracing its origins is an important step in environmental management and control. This study analyzes the carbon concentrations at Duarte, CA (a suburban site near Los Angeles) and in Lennox, CA (a site next to a Los Angeles freeway). Concentrations inside a tunnel are also available and used to derive a motor vehicle emission profile. A new approach is proposed for calculating the motor vehicle contribution to organic carbon and the amount of background carbon found at the two sites. Regression analysis provides insight in the formation of organic carbon and frontier analysis is used to calculate the motor vehicle contribution to organic carbon and the amount of background carbon in the atmosphere. The information obtained from this analysis can be used in the regulation of motor vehicle emissions and in air pollution control. |
| Download | PDF, PS, PS.gz |
| Simulating Alternative Production Schedules with Variable Technology | |
| Authors | Eleni Pratsini, Neil B. Marks, Timothy C. Krehbiel |
| Abstract | This article studies different sequencing and inventory rules in a manufacturing environment with nonlinear technological coefficients and stochastic demand. Multiple products require setup on a single machine and setup time and setup cost decrease with repeated setups. Furthermore, setup operations for different products have common components and an item can be benefited by a setup operation of another item. The single-level, multi-item lot size model is used to model the production environment. The learning curve is used to represent this decrease in setup time with repeated setups. The learning transmission between items affects the scheduling of the products and the resulting model considers simultaneous decisions about lot sizing and sequencing in a nonlinear formulation with a stochastic component. The problem is formulated and a simple production policy is simulated. Two sequencing rules and four inventory rules are examined. A simulation experiment of 6400 runs is studied and the results are analyzed. |
| Download | PDF, PS, PS.gz |
| Introduction to Dynamic Financial Analysis | |
| Author | Roger Kaufmann |
| Abstract | In the last years we have witnessed growing interest in a discipline called Dynamic Financial Analysis (DFA). This phrase seems to be much more in use in the US and Canada than in Continental Europe. Moreover it is applied almost exclusively to nonlife insurance whereas a quite similar concept in life insurance is still called Asset Liability Management. We neither want to explain the difference between these two concepts nor do we want to introduce highly sophisticated modules of a DFA. There are some DFA models in place, mostly in the US. Our goal is to present an introduction into this field by giving an outline of common characteristics of different DFA models and by setting up a model framework for different modules of a DFA. We show how these modules can be constructed and related into an efficient risk management platform. An explicit DFA example is presented. |
| Download | PDF, PS, PS.gz |
| Coherent Allocation of Risk Capital | |
| Author | Michel Denault |
| Abstract | The allocation problem stems from the diversification effect observed in risk measurements of financial portfolios: the sum of the risk measures of many portfolios is typically larger than the risk of all portfolios taken together. The allocation problem is to apportion this "diversification advantage" to the portfolios in a fair manner, to obtain new, firm-internal risk evaluations of the portfolios. Our approach is axiomatic, in the sense that we first establish the (arguably) necessary properties of an allocation scheme, and then study schemes that fulfill the properties. Important results from the area of game theory find a direct application, and are used here. |
| Download | PDF, PS, PS.gz |
| A Survey and Some Generalizations of Bessel Processes | |
| Authors | Anja Göing-Jaeschke, Marc Yor, Marie Curie |
| Abstract | Bessel processes play an important role in financial mathematics because of their strong relation to financial processes like geometric Brownian motion or CIR processes. We are interested in the first time Bessel processes and more generally, radial Ornstein-Uhlenbeck processes hit a given barrier. We give explicit expressions of the Laplace transforms of first hitting times by (squared) radial Ornstein-Uhlenbeck processes, i.e., CIR processes. As a natural extension we study squared Bessel processes and squared Ornstein-Uhlenbeck processes with negative dimensions or negative starting points and derive their properties. |
| Download | PDF, PS, PS.gz |
| Optimization Over k-set Polytopes and Efficient k-set Enumeration | |
| Authors | A. Andrzejak, K. Fukuda |
| Abstract | We present two versions of an algorithm based on the reverse search technique for enumerating all k-sets of a point set in Rd. The key elements include the notion of a k-set polytope and the optimization of a linear function over a k-set polytope. |
| Download | PDF, PS, PS.gz |
| Process Simulation to Evaluate Steep Terrain Harvesting Systems | |
| Authors | Karl Stampfer, Jens Henoch |
| Abstract | To secure the competitiveness of forestry on steep slopes, harvesting systems must be further developed in a systematic, efficient and goal orientated manner. The common "trial and error" method is associated with high development costs. This brings about the question, how can forest harvesting systems be cost-effectively analysed and optimised in the future. A successful concept is the use of computer simulation. A simulation model prototype for steep terrain forestry systems has been developed. With the simulation environment HaSyS (Harvesting System Simulator) various harvesting systems (chainsaw, walking harvester, and tracked harvester in combination with cable systems) can be analysed. For the first time, the interaction effect of thinning intensity and the productive system was modelled. The simulation model allows productivity prediction to be made dependant on system, terrain and stand variables. Productivity comparisons between different working systems have shown that through mechanisation of timber harvesting not only the felling and cross-cutting, but that also the cable extraction can be rationalised. |
| Reference | Landwards, The Institution of Agricultural Engineers, Volume 54, No 3, 1999 |
| Download | PDF, PS, PS.gz |
1998
| The Analytic Center Quadratic Cut Method (ACQCM) for Strongly Monotone Variational Inequality Problems with Approximate Centers | |
| Authors | Hans-Jakob Lüthi, Benno Büeler |
| Abstract | For strongly monotone variational inequality problems (VIPs) convergence of an algorithm is investigated which, at each iteration k, adds a quadratic cut through an approximate analytic center xk of the consequently shrinking convex body. First it is shown that the sequence of xk converges to the unique solution x* of the VIP an O(1/sqrt(k)). As an interesting detail note that - for increasingly accurate analytic centers - the complexity constants converge to the quantities obtained for ACQCM with exact centers. Secondly we show that the arithmetic complexity to update from xk to xk+1 after inserting a quadratic cut through xk is bounded by a constant number of Newton iterations plus O(n ln ln [zeta k2/epsilon3]), where n is the space dimension, epsilon is the final solution accuracy ||xk - x*||, and zeta depends on some problem-specific constants only. |
| Download | PS, PS.gz |
| A Simulation Platform for Multiagent Systems in Logistics | |
| Author | Heinz Ulrich |
| Abstract | The challenges in today's global economy are flexibility and fast reactions to customer requests. To cope with these requirements there is a need for intelligent adaptive planning and control systems. The multiagent approach offer favorable prospects for adequate solutions. A simulation platform for the development of multiagent systems in logistics is presented. Logistics is viewed as socio-technical which enables to take into account human resources within the design process explicitly according their importance. This simulation platform is based on the discrete-event simulation environment HIDES developed at our institute. The modeling basis of the simulation is a reference model of logistics comprising few specific basic elements to be used according to a well-defined syntactical structure. To realize multiagent systems a particular management level is added, where the agents and the interfaces to human resources are located. The platform is intended to provide a substantial support for developing multiagent systems. |
| Download | PDF, PS, PS.gz |
| Towards a Unified Framework for Randomized Pivoting Algorithms in Linear Programming | |
| Authors | L. Finschi, K. Fukuda, H.-J. Lüthi |
| Abstract | We study linear programming (LP) algorithms. Of particular interest are bounds for the number of elementary arithmetic operations necessary to solve a linear program. The best bounds that depend only on the sizes of a basis and a nonbasis have been found for a family of randomized pivoting algorithms. However, the original descriptions and analyses of these algorithms use several different geometric and abstract settings. In this paper we present a unified framework in which we describe two known algorithms as special simplex methods and analyse their complexities and differences. |
| Download | PDF, PS, PS.gz |
1997
| Approximation of P&L Distributions | |
| Authors | Prof. Karl Frauendorfer, Pierre-Yves Moix, Olivier Schmid |
| Abstract | Former investigation (Approximation of Profit-and-Loss Distributions, Part I introduces the application of the barycentric approximation methodology for evaluating profit-and-loss distributions numerically. Although, convergence of the quantiles is ensured by the weak convergence of the discrete measures, as proclaimed in Part I, recent numerical results have indicated that the approximations of the profit-and-loss distribution are less practical when the portfolio gets a reasonable complexity. This experience has revealed that the weak convergence of the probability measures appears not to be strong enough for evaluating quantiles numerically in a satisfactory way. Thereupon, the authors have focused on information offered by the barycentric approximation but still unused in the algorithmic procedure of Part I. It has been realized that the dual to the derived discrete probability measure helps evaluate the profit-and-loss distribution in a better way. In this Part II, the barycentric approximation technique is outlined and benchmarked with the intention to focus on the dual viewpoint for simplicial refinement. This technique poses no assumption on the risk factor space, except that the variance-covariance matrix of the risk factors exist. Therefore, it is applicable for general multivariate or empirical distributions. Furthermore, the technique provides approximation of the risk profile as well as of the risk factor distribution. Beforehand, various test environments are specified which help illustrate the sensitivity of value-at-risk numbers. These environments are characterized by the probability measure P of the risk factors and a risk profile g which represents the payoff structure of some portfolio. The corresponding numerical results illustrate the sensitivity of value-at-risk with respect to market volatility and correlation of risk factors. This provides information on the model risk one is exposed to within the value-at-risk approach. |
| Download | PDF, PS, PS.gz |
| Some Generalizations of Bessel Processes | |
| Author | Anja Göing |
| Download | PDF, PS, PS.gz |
| Factors at Risk | |
| Authors | Hans-Jakob Lüthi, Gerold Studer |
| Abstract | The identification of scenarios which have a particularly low or high P&L helps to get a better understanding of the portfolio's risk exposure. Therefore, the notions of safe (resp. dangerous) regions are introduced, which represent sets where the P&L is greater (resp. less) than a given critical level. In order to describe such sets in an easily interpretable way, one-dimensional intervals are used. Such intervals can be determined by solving a sequence of restricted maximum loss problems. |
| Download | PDF, PS, PS.gz |
| Modelling an International Market of CO2 Emission Permits | |
| Authors | O. Bahn, B. Büeler, S. Kypreos, H.-J. Lüthi |
| Abstract | Many countries have developed energy models (such as MARKAL-MACRO-MM) to as sess their energy policies, in particular concerning the curbing of their carbon dioxide (CO2) emissions. To integrate national MM models, we propose a multi-regional MAR KAL-MACRO (3M) model. It enables one to study an international cooperation to curb jointly CO2 emissions through a market of emission permits (certificate). Furthermore, from a decision support perspective, the 3M model can be used to integrate aspects of ecological sustainability (in relation to the climate change issue), economic welfare, efficient resource use and technological innovation. To solve 3M, we have used two alternative mathematical methods. We have implemented both in parallel on a network of independent workstations. As a numerical application, we study the cooperation of three European countries (the Netherlands, Sweden and Switzerland) to curb jointly their CO2 emissions. |
| Reference | Int. J. of Global Energy Issues, Vol. 12, No 1-6, pp. 283-291. |
| Download | PDF, PS, PS.gz |
| Exact Volume Computation for Polytopes: A Practical Study | |
| Authors | B. Büeler, A. Enge, K. Fukuda |
| Download | PS, PS.gz |
1996
| Quadratic Maximum Loss for Risk Measurement of Portfolios | |
| Authors | Hans-Jakob Lüthi, Gerold Studer |
| Abstract | Effective risk management requires adequate risk measurement. A basic problem herein is the quantification of market risks: what is the overall effect on a portfolio if market rates change? The first chapter gives a brief review of the standard risk measure "Value-At-Risk" (VAR) and introduces the concept of "Maximum Loss" (ML) as a method for identifying the worst case in a given scenario space, called "Trust Region". Next, a technique for calculating efficiently ML for quadratic functions is described; the algorithm is based on the Levenberg-Marquardt theorem, which reduces the high dimensional optimization problem to a one dimensional root finding. Following this, the idea of the "Maximum Loss Path" is presented: repetitive calculation of ML for a growing trust region leads to a sequence of worst cases, which form a complete path. Similarly, the paths of "Maximum Profit" (MP) and "Expected Value" (EV) can be determined; the comparison of them permits judgements on the quality of portfolios. These concepts are also applicable to non-quadratic portfolios by using "Dynamic Approximations", which replace arbitrary profit and loss functions with a sequence of quadratic functions. Finally, the idea of "Maximum Loss Distribution" is explained. The distributions of ML and MP can be obtained directly from the ML and MP paths. They lead to lower and upper bounds of VAR and allow statements about the spread of ML and MP. |
| Download | PDF, PS, PS.gz |
| Estimation in Financial Models | |
| Author | Anja Göing |
| Abstract | Over the last few years various new derivative instruments have emerged in financial markets leading to a demand for versatile estimation methods for relevant model parameters. Typical examples include volatility, covariances and correlations. In this paper we give a survey on statistical estimation methods for both discrete as well as continuous time stochastic models. |
| Download | PDF, PS, PS.gz |
| Innovation by Simulation Using the Example of an Automated Work Cell | |
| Authors | H.-J. Lüthi, Willi Dürig, Heinz Ulrich |
| Abstract | This article describes the use of the HIDES simulation framework within the context of a planning and control system for an automated work cell. Because of the dynamic co mplexity of the planning task, this system must be able to monitor itself, and to react as independently as possible to changing external circumstances. In order to achie ve this, the planning task is distributed among a number of virtual intelligent agents. Each one of these agents supports a clearly de,ned task, has its own problem-solvi ng strategies, and can request assistance from other agents. Simulation plays an important part in this system. It is used by the agents to monitor their own solution str ategies, and to assess the future consequences of their decisions. |
| Download | PS, PS.gz |
1995
| Approximation of P&L Distributions | |
| Authors | Prof. Karl Frauendorfer, Pierre-Yves Moix, Olivier Schmid |
| Abstract | Value functions (risk profiles) of financial instruments and the real distributions of risk factors are not available in analytically closed forms. These components have to be approximated. In this work, a new approach for risk measurement is introduced. The underlying methodology is based on the utilization of extremal measures for approximating the P&L distribution. A special class of "extremal measures" is employed which exploits the monotonicity of price sensitivities entailed by convexity. Clearly, in case the value functions have monotonous derivatives, the payoff-functions are convex or concave depending on whether a position is held short or long. The incorporated extremal measures provide approximations for both risk factor distribution and risk profiles, and allow for deriving an adequate approximation of the P&L distributions, in particual for appealing VaR-estimates. The basics of this approach are presented and first numerical results are tested against the currently apllied VaR-approaches and the simulation benchmarks established earlier in Allen. |
| Download | PDF, PS, PS.gz |
| Value At Risk and Maximum Loss Optimization | |
| Author | Gerold Studer |
| Abstract |
A very condensed overview of risk measurement methods is given and the different techniques are classified. The risk measure "Value At Risk" (VAR) is presented from a new point of view and a general definition of VAR is derived. Next, "Maximum Loss" (ML) is formulated as a mathematical optimization problem and its modelling is described. The techniques for calculating ML for linear and quadratic risk profiles are presented. Some theoretical relations between VAR and ML are demonstrated: ML is presented as a general framework including Delta-Normal VAR as well as Wilson's Delta-Gamma approach. It is also proven that ML is a worst case measure which is always more conservative than VAR. |
| Download | PDF, PS, PS.gz |
| Intelligent, Adaptive Planning and Control of Logistic Processes | |
| Authors | Heinz Ulrich, Willi Dürig |
| Abstract | Modern information and communicationtechnology provides new promising facilities to support the management of logistic processes in manufacturing industry. In today's global worldwide economy flexibility and fast reactions to customer requirements is asked. This is aparticular challenge for the management of logistics where planning and control systems need the capacity of dynamic adaptation and self-control which implies intelligence within the process. Our approach to achieve this goal is the distribution of the decision tasks to several virtual intelligent agents. Each agent supports a clearly discernible task, has its own specific problem solving strategies and is able to ask for services of other agents. Simulation plays a crucial role in this planning system and is used by the agents to revise their planning strategies and tode termine the future consequences of their decisions. |
| Download | PS, PS.gz |
1994
| The Contribution of Simulation for the Management of an Automated Work Cell | |
| Authors | Heinz Ulrich, Willi Dürig |
| Abstract | The high productivity of an automated work-cell can only be taken advantage of, if there is a sufficient solution for its inherent management task. This task comprises very demanding decisions within this work-process for its design, planning and control, in particular in respect of the dynamic complexity of the system and of the required short response time. An adequate computer support in this decision process is indispensable. As important method in this context simulation is discussed as to its methodological aspects and its possible range of application based on successful projects realized in practice. |
| Download | PDF, PS, PS.gz |
1993
| A Highly Interactive Discrete Event Simulator designed for Systems in Logistics | |
| Authors | A. Graber, D. Mutaaga, H. Ulrich, D. Schweizer, A. Zimmermann |
| Abstract |
Simulation is considered to be a method to improveplanning and control efficiency in the field of logistics. In our view no existing simulation tool meets the basicrequirements sufficiently. We therefore developed a new simulator with the following characteristics: * Simulation principles: General purpose discrete event simulator. * Modeling basis: Meta model comprising few specific basic elements to be used according to a well-defined syntactical structure. * Modeling principle: A separation of material flow and information flow is enforced. Logically consistent hierarchical structures are provided. * Implementation: Realization in an object-oriented language (Smalltalk-80) * Working environment: Highly interactive modeling process to be performed in a man-machine-dialogue. Flexible visualization of the simulation model and the simulation results are provided. A brief summary of our experiences in simulation is given. Of our approach to develop an adequate simulator, we describe some basic elements as well as one specific application. |
| Download | PDF, PS, PS.gz |
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne
graphische Elemente dargestellt. Die Funktionalität der
Website ist aber trotzdem gewährleistet. Wenn Sie diese
Website regelmässig benutzen, empfehlen wir Ihnen, auf
Ihrem Computer einen aktuellen Browser zu installieren. Weitere
Informationen finden Sie auf
folgender
Seite.
Important Note:
The content in this site is accessible to any browser or
Internet device, however, some graphics will display correctly
only in the newer versions of Netscape. To get the most out of
our site we suggest you upgrade to a newer browser.
More
information
