Skip to main content
main-content

Über dieses Buch

This title represents an ambitious undertaking, namely a broad view on the nature of intelligent decision making, which is characterized by the use of models and methods in the framework of decision support for management. With this title we want to reflect the scope of our field, but, at the same time, honor our colleague th Paul Stahly on the occasion of his 65 birthday. Paul Stahly has over decades invested his energy in developing the area of Operations Research from such a broad point of view. He has done this not only at his chairs at the HSG / University of St. Gallen and the University of Linz, but also on a broad international level as editor of ITOR and as influential member of all the Operations Research societies in the German speaking countries. He has, in particular, enriched our area by application-oriented research and industrial projects in fields such as logistics, emergency planning, [mance, and others, and he was pivotal in strengthening the cooperation between the national and international OR societies, particular in the German speaking area. VI Consequently, many colleagues who partly cooperated very closely with him, have contributed to this monograph. Some of these contributions have been presented at a colloquium in January 2001 in St. Gallen in honor of Paul Stahly. This colloquium was attended by many colleagues coming from Germany, Austria, Switzerland, Italy and even from the United States.

Inhaltsverzeichnis

Frontmatter

Research and Applied Projects at Paul Stähly’s Institute for Operations Research

Research and Applied Projects at Paul Stähly’s Institute for Operations Research

Abstract
This paper gives a short overview on the history of the Institute of Operations Research at the University St. Gallen and the research as well as applied projects initiated and supervised by Paul Stähly. Some selected projects are described in more detail.
Andreas Klose

Optimization

Frontmatter

Environmental Policy Design and the Economics of Crime: Some Analogies in Intertemporal Optimization

Abstract
Environmental planning and cost-benefit modeling in crime control shows some striking analogies. The purpose of this note is to exploit this fact in an intertemporal framework. In particular, the optimal mix of ‘prevention’ and ‘treatment’ in pollution control and illicit drug consumption is illustrated by several optimal control and dynamic game models.
Gustav Feichtinger

On Cross Decomposition for Mixed-Integer Programming

Abstract
Primal and dual decomposition procedures can lead – dependent on the structure of the problem – to efficient procedures for solving mixed—integer programming problems. Benders’ decomposition takes advantage of the primal structure of a problem by temporarily fixing the aggravating integer variables, while dual structures can be exploited by relaxing the complicating constraints in Lagrangian fashion and solving the Lagrangian dual with subgradient optimization, multiplier adjustment methods, or Dantzig-Wolfe decomposition.
Paul Wentges

Optimal and Neuro—Dynamic Programming Solutions for a Stochastic Inventory Transportation Problem

Abstract
We study the problem of shipping a set of products from a supplier to a customer in the supply chain. Each product is made available at the supplier at a given constant rate and absorbed by the customer on the basis of a given probability distribution of the customer demand. An inventory cost is charged at the supplier and at the customer if the level of the inventory is positive and a penalty cost is charged at the customer if the demand exceeds the inventory on hand. Shipments from the supplier to the customer are performed by vehicles of given capacity which generate a fixed cost per journey. The aim is to find a shipping strategy that minimizes the total expected discounted cost over an infinite horizon. This problem is a sequential decision making problem under uncertainty which belongs to the class of problems that can be solved by dynamic programming techniques. We implement the well known Policy iteration algorithm in order to obtain the optimal solution of the problem. Then, we propose two heuristic algorithms based on Neuro—dynamic programming techniques and show their effectiveness on a set of randomly generated problem instances.
L. Bertazzi, D. P. Bertsekas, M. G. Speranza

Modeling Approaches for Median Relations

Abstract
In the recent past, different tools have been developed for a more problem-oriented approach to modeling which, in turn, might shorten the problem-solving process itself. For a problem example from qualitative data analysis—determining a median relation—it is illustrated how different modeling/optimizing environments (AMPL, OPL, LPL) as well as a developer environment (ECLiPSe) support a more natural problem formulation. In this context, a brief outline of the programming paradigm of constraint logic programming is given.
Ulrich Tüshaus

A Note on the “More-for-Less” Paradox

Abstract
The more-for-less paradox, arising in some linear programming models is connected with a rather unexpected result: by increasing all or some output requirements (without reducing other outputs) we can obtain lower total cost (under ceteris paribus assumption). Using the notion of “technological” optimal structure and its analytical expression an economic interpretation of this paradox is discussed.
Mikulas Luptacik

Project Experiences and Some Principal Considerations Concerning Operations Research as an Interesting Branch of Science

Abstract
This paper first gives some considerations concerning major fields of Operations Research and addresses experiences, potential and philosophy of the field. In the second part, some hints are given to project work done at the FAW (Forschungsinstitut für anwendungsorientierte Wissensverarbeitung in Ulm, Germany). The topics concern practical applications in fields such as optimization, decision theory and knowledge management. The approaches taken are of an interdisciplinary nature and combine different levels of expertise. We demonstrate the availability of a variety of choices and applications and the interaction of methodological and managerial aspects. The paper concludes with some remarks on the Institut für Unternehmensforschung, Operations Research of the Hochschule St. Gallen and some indications to contributions of Prof. Paul Stähly, whose 65 birthday is celebrated with this paper.
T. Kämpke, F. J. Radermacher

Operations Research Models

Frontmatter

Concepts, Aims, and Problems which Modelling in OR and OOP Have in Common

Abstract
This paper is dedicated to Paul Stähly on the occassion of his 65th birthday. It reflects many private discussions between us, in particular, on modelling and the use of an appropriate programming language. Paul Stähly has always been a dedicated user of SIMULA 67, already in those days when object oriented programming (OOP) was not invented yet. He has early noticed the power of object orientation in his research area (OR). The authors of SIMULA 67 introduced classes as templates which define data structures and algorithms to be included in a particular instance (of a model). In addition, classes may be defined in terms of each other.
Jörg R. Mühlbacher

On the Use and Misuse of Holding Cost Models

Abstract
This paper considers the relationship between holding cost and discounted cash flow models. Rather than arguing for or against one of these types of models, their close relationship is underlined by interpreting the holding cost criterion as first order approximation of the discounted cash flow criterion. Various planning models, both for dynamic operations in a finite horizon and for cyclic operations in an infinite horizon are considered. It is shown that flow-oriented modelling of the holding costs avoids misinterpretations and problems with the evaluation of inventories.
Bernhard Fleischmann

From the Publisher to the Wholesalers Determination of the Number of Copies and Their Distribution among the Wholesalers

Abstract
I report about a project in press distribution. Its target is to develop a tool which automatically proposes how many copies should be printed and how they should be distributed among the 91 wholesalers. The publisher intends to use the same tool for all his different journals. In a first introductory chapter some important specialities of the commerce with press products are described. The second chapter offers a detailed description of the problem. In a third chapter the underlying model is presented. The fourth chapter deals with the mathematical methods. In the fifth chapter some results are presented. The paper ends with a short conclusion. The main technique to validate the model and to recommend the use of the model in practice is ex - post - simulation of the forecasting procedure over a long period using only data available at the time forecasts in practice had to be done.
Roland Dillmann

Scheduling Scarce Resources in Chemical Engineering

Abstract
The efficient utilization of scarce resources, such as machines or manpower, is major challenge within production planning in the chemical industry. We describe solution methods for a resource-constrained scheduling problem which arises at a production facility at BASF AG in Ludwigshafen. We have developed and implemented two different algorithms to solve this problem, a novel approach which is based upon Lagrangian relaxation, as well as a branch-andbound procedure. Since the Lagrangian approach is applicable for a whole variety of resource-constrained scheduling problems, it is of interest not only for the specific problem we describe, but is of interest also for many other industrial applications. In this paper, we describe both approaches, and also report on computational results, based upon practical problem instances as well as benchmark test sets.
Rolf H. Möhring, Marc Uetz

Short-Term Planning of Batch Plants in Process Industries

Abstract
The paper deals with short-term planning problems in process industries where final products are obtained by several successive chemical or physical transformations of raw materials using scarce multi-purpose equipment. In batch production mode, the total requirements for intermediate and final products are partitioned into batches. The production start of a batch at a given level requires the availability of all input products. We consider the problem of scheduling the production of given primary requirements for final products such that the makespan is minimized, where the batch sizes can be chosen within prescribed intervals. Further constraints arise from limited production and storage capacities as well as sequence-dependent cleaning times for processing units. We propose a new solution approach which is based on the decomposition of the short-term planning problem into computing appropriate batch sizes (batching) and the subsequent scheduling of batches on processing units (batch scheduling). The former problem is modelled and solved as a nonlinear mixed integer program, whereas the latter problem is addressed using models and methods of resource-constrained project scheduling. The solution procedure proposed (approximately) solves problems of industrial size within a reasonable amount of computing time.
Klaus Neumann, Christoph Schwindt, Norbert Trautmann

Local Search for a Travelling Salesman Problem in Production Control - A Case Study

Abstract
During the past two decades significant progress could be observed in the development of heuristic solution methods. In particular, Local Search Methods have attracted considerable interest, as they have been applied successfully to various difficult combinatorial problems in business management. However, only few articles exist in which these methods are compared to each other. The authors report some experience from a study in which classic (Descent Method) and modern (Simulated Annealing, Threshold Accepting, Great Deluge, Tabu Search) Local Search Methods have been implemented in order to solve a real-world Travelling Salesman Problem in production control. Simulated Annealing turned out to be superior to all other methods with respect to implementation requirements and solution quality. By replacing the previously implemented method the utilization of the respective production unit - which represented a bottleneck - could be increased significantly.
Gerhard Wäscher, Jörg Heuer, Volker Reschke, Petra Schwerin

Transportation Problems

Abstract
Starting from historical remarks on transportation problems and early applications we discuss the various connections between Monge matrices and transportation problems. In particular, we survey time transportation problems, algebraic transportation problems with applications in scheduling theory and minimax flow transportation problems. Finally we report on a recent case study for a large capacitated facility location model.
Rainer E. Burkard

Operational Planning and Optimization of Hub-and Spoke Transportation Networks for Area Wide Groupage Services

Abstract
Increased competition in the transport market has led to new cooperative arrangements between third-party logistics providers in the form of hub-and-spoke systems. In addition to the design problem, the operative planning task of a huband-spoke network is a challenging task for the management of such transportation networks. In particular, the transport management has to decide whether a pure hub-and spoke system should be realized, where all quantities within the transportation network flow over the hub from or to the depots, or whether a hybrid hub-and-spoke network is preferred in which direct transports also take place. Mathematical models for these operative planning tasks are developed and applied to a real case of an Austrian parcel service provider. Cost savings of the hybrid hub-and-spoke system are described.
Günther Zäpfel, Michael Wasner

Stochastic Programming: Achievements and Open Problems

Abstract
As is well known, many applied problems may be modelled as linear programs of the standard type
$$ subject{\kern 1pt} to\left. {\begin{array}{*{20}{c}} {\min {{c}^{T}}x} \\ {Ax = b} \\ {x \geqslant 0,} \\ \end{array} } \right\} $$
(1.1)
where \( A \in {{\mathbb{R}}^{{mxn}}},b \in {{\mathbb{R}}^{m}},c \in {{\mathbb{R}}^{n}} \) are fixed data and \( x \in {{\mathbb{R}}^{n}} \) is to be determined as a vector of optimal decisions satisfying the given constraints. However, as was observed already more than 40 years ago, it may also happen in applications, that modelling the linear structures as in (1.1) is justified, but not all of the data in A,b, c are fixed (and known) before the decision on x has to be taken. If those data happen to be random variables with known distributions, we face a problem of stochastic linear programming (SLP). Among the first papers discussing those problems are Beale [2], Charnes—Cooper [7], Dantzig [8], Dantzig—Madansky [9] and Tintner [33].
Peter Kall

Decision Support and Management Systems

Frontmatter

Infrastructure for Crisis-2000

A Distributed Disaster Management System
Abstract
Either nature-caused and man-made disasters seem to be occurring more frequently and are more severe, or our communication technology has advanced considerably and we are made aware more quickly and completely of disasters happening everywhere in the world. Such disasters can cause a large number of injured, dead and homeless. Some disasters are small and can be handled by the local authorities. On the other hand, some of them may be large in magnitude and spread over large geographical areas and therefore require coordination by authorities in many localities, as well as authorities of county, region, state and country levels - as in the case of very large earthquakes, coordinated worldwide distributed terrorist activities, etc.
This paper1 presents the infrastructure for CRISIS-2000 system, a worldwide distributed system for crisis management. The purpose of the system is to enable optimal management of activities and resources in handling disasters in an arbitrary large geographical area, i.e. it allocates the resources in a manner so that effects of the crises, e.g. number of fatalities and human suffering, are minimized. The system applies the most recent advances in methodologies of Operations Research, Artificial Intelligence, Information Management and Web Technology.
Nenad Marovac

Decision Making Based on Causal Graphs

Abstract
Graphs have been used since quite long in statistics as tools to represent probabilistic dependencies. The origins can be traced back to first applications in path analysis (Wright 1921). During the last decade developments took place that involved an improved understanding of the relationships between graphs and probabilities, on the one hand, and graphs and causal inference on the other (e. g. Pearl 1988, Spirtes et al. 1993). Graphical modeling has emerged as a key component of the KDD (knowledge discovery in databases) process in the way of extraction and depiction of dependencies from data. Further, graphical modelling provides a powerful symbolic machinery for causal analysis e. g. the problem of covariate selection and the assessment of causal effects in the sense of the potential response framework. If a decision maker fixes the value of a treatment variable the effects of this decision can easily be computed using the causal graph associated with this model.
Dietrich Eherler, Peter Kischka

On the Effect of the Bargaining Context on Bargaining Behaviour

Abstract
This paper analyses three and two person bargaining experiments with respect to the question of the ability of players to push through their own interests. It is shown that the success of the players strongly depends on the circumstances under which bargaining takes place.
Maximilian K. P. Jung, Ulrike Leopold-Wildburger

Income Tax Rate: Properties and Implications

Abstract
An income tax which is progressive and motivation preserving in the sense that income after tax increases with income before tax, satisfies interesting additional conditions that are somewhat surprising. This is shown without any differentiability assumptions
Wolfgang Eichhorn, Helmut Funke, Winfried Gleissner

Knowledge Management — Challenges and the “Knowing”-Implementation Strategy

Abstract
The fast globalization process of today has a strong impact on enterprises. They are confronted with the need to manage permanent change. Especially they have to build up more partnerships on a world-wide scale forming virtual enterprises. This is one reason to invest in intemet-, intranet-and extranet-technology. From an organizational view point this needed change process from old economy to new economy has to consider on the one hand side an increasing explicitness. This means the organization of an enterprise is becoming more transparent because of the use of standard processes, standard software etc. On the other hand also non-explicit mechanisms of increased self organization have to be used and thus included into the organization harmonically. Examples are business units, self responsible teams and other fractal structuring forms.
Globalization leads to a dramatic increase in innovation speed. This is a big challenge for enterprises because faster innovation also requires a faster change process. Employees have to be supported always by the most modern information-and communication technology. This requires permanent investment, organizational change and employees that are willing and able for live-long learning
Knowledge management is seen as a strategic methodology to define and set up the needed change process. To describe the knowledge management strategy, that has been developed in close partnership of FAW and its spin off company KNOWING GmbH with Prof. Dr. Paul Stähly at IfU-HSG we first explain a relatively general view onto enterprises as complex organisms. This view identifies the different aspects of knowledge management by exploiting an analogy to the functions of biological organisms. An enterprise is seen as a “body” that has to act in a permanent processof change.The enterprise can act “intelligent” because of the knowledge, embodied into it. Such a “surviving body” is orientated towards adaption to the future and knowledge management. The organizational structure supports and motivates live-long learning in a network of human resources (communities of practice) and technological components. The information networks become the enterpriser’s “nervous systerms” and are extremely powerful because they build upon information- and communication technology with its high transmission speed.
Besides strantegy aspects of knowledge management a supporting information- and communication-technology architecture are discussed as well. In assition concrete activities for a stepwise implementation of a technological support for knowledge management in enterprises are explained.
Dirk Solte

Perturbation Heuristics for Unconstrained Quadratic 0–1 Programming and an Alternate Stopping and Comparison Criterium

Abstract
Given quadratic functionfthe unconstrained quadratic zero-one programming problem consists in minimizingf (x)wherexis a zero-one vector of dimension n. This problem is NP-hard and therefore the most efficient results have been obtained by heuristics. As optimal solutions are in most cases unkown, comparisons between heuristics are usually based on the shortest time to reach the best known solution. This approach is arbitrary and depends on both problem size and computer speed. We present an alternate comparison and stopping criterium based on an approximate count evaluations of the objective function. This comparison technique will be applied on descent algorithms embedded in a multi-start heuristic scheme. Finally, some results for public instances of various sizes will be reported.
Kim Allemand, Thomas Liebling

Solving Conflicts and Sanctions: Results of an Experimental Study

Abstract
In our study we intend to gain insight into the behaviour of individuals in conflict situations which can be interpreted as sanctions. There are hardly any models of sanctions in literature which can be compared with this idea. An experiment is modelled to analyse the behaviour of individuals in a situation similar to a sequential prisoners’ dilemma. Contingent decisions give us the chance to measure punishment and sanctions.
Our approach is similar to an extended model by Bolton, Brandts and Ockenfels (1997), in order to analyse reciprocity in a single framework together with the help of a questionnaire.
In our paper we concentrate on whether the attitude towards fairness coincides with the attitude towards the application of sanctions. Further on we will observe that gender and age of the subjects participating has an influence on the degree of punishment used.
Results seem to indicate that the role assigned to each participant strongly influences her/his actions towards her/his counterpart. We suppose the reason for this behaviour is that more experienced/older individuals think more about the payoff for their competitors, while less experienced/younger individuals behave significantly more selfishly.
Our objectives are to gain more insight into behaviour in dilemma situations and also seek better explanations for individual decisions. Some of the results could help to solve problems concerned with sanctions.
Ulrike Leopold-Wildburger, Joerg H. Schütze, Alois Lafer, Markus Glawischnig, Maximilian K. P. Jung
Weitere Informationen