Operations Research Proceedings 2003

Relaying — allowing multiple wireless hops — is a protocol extension for cellular networks conceived to improve data throughput. Its benefits have only been quantified for small example networks. For assessing its general potential, we define a complex resource allocation/scheduling problem. Several mathematical models are presented for this problem; while a time-expanded MIP approach turns out intractable, a sophisticated column generation scheme leads to good computational results. We thereby show that for selected cases relaying can increase data throughput by 30% on the average.

Many call centers provide service for customers of different classes. We analyze a queueing model of an inbound call center with two customer classes, three agent groups, and skills-based routing. In our model we assume that a waiting customer may hang up before his service begins. All times are assumed to be exponentially distributed. We describe the states and the state space of this continuous time Markov chain and develop the steady-state equations. The behavior of this system is analyzed in numerical experiments and optimal economical allocations of the agents are discussed.

Revenue Management has proven successful in a number of service in- dustries such as airlines, hotels and cruiseships. This paper examines the possibility of applying revenue management techniques to a manufacturing setting. A make- to-order company is considered which receives orders with different profit margins, processing times and due dates. The corresponding discrete markov decision pro- cess model is presented as well as a heuristic which solves large problem instances within a reasonable runtime.

We consider a Network Revenue Management Problem with uncertain demand and nested capacity control. The objective is to maximize expected revenue by setting nested booking limits b _j for all products j=1,…, n. For this setting, no closed form for the objective function is known. In this paper, we propose a method to derive upper and lower bounds on the expected revenue when nested booking limits b ₁ ,…, b _n are given.

The UMTS radio network planning problem poses the challenge of designing a cost-effective network that provides users with sufficient coverage and capacity. We describe an optimisation model for this problem that is based on comprehensive planning data of the EU project Momentum. We present heuristic mathematical methods for this realistic model, including computational results.

In this paper we present a review for the distribution planning problem. We posi- tion the contribution in a framework that classifies the related research in terms of decision levels. These are strategic, tactical and operational levels. We also tabulate the reviewed re- search in terms of model types, model characteristics, solution procedures and the decision levels.

Der vorliegende Beitrag präsentiert die Ergebnisse einer Analyse zur Wahl eines geeigneten Artikelanordnungsmusters (Längs-, Quer-, Radialan- ordnung) bei gegebenen, in der Praxis häufig anzutreffenden Problemparametern. Die numerischen Ergebnisse zeigen für ein gegebenes Lagersystem, dass die Festplatzlagerung einem chaotischen Lager vorzuziehen ist und dass durch die Wahl bestimmter Artikelanordnungsmuster in Abhängigkeit von der verwendeten Routingstrategie Vorteile durch reduzierte Kommissionierwege erzielt werden können.

We study a supply chain whose acting objects apply local control policies. The determination of the optimal order quantity is done by discret Markov decision models. The existence of the bullwhip effect is verified analytically. While analyzing the reasons of the bullwhip effect, we focus on the lack of information exchange and the uncertainty in demand. We determine the potential for improvements within the supply chain by implementing an additional information system. The shared informations are used by the discret Markov decision models to calculate the modified order quantities on every level of the supply chain.

We analyze the effect of installation-stock and echelon-stock policies on order amplification in a serial two-echelon supply chain. As orders are passed through a supply chain, order oscillations and inventory oscillations are typically amplified at each echelon. This behavior is referred to as the bullwhip effect. To analyze how different inventory policies affect order and inventory oscillations we apply linear control theory. We show that the echelon-stock policy outperforms the installation-stock policy with respect to both order and inventory oscillation

We consider a single-stage production inventory problem under periodic review with stochastic demand and stochastically proportional yield. Holding, shortage and ordering costs are assumed to be strictly proportional. The optimal ordering policy is known to be of a non-linear type. Linear approximation of this policy is a commonly used heuristic approach. Our focus is on the application of linear approximations under procurement leadtime conditions for an infinite horizon setting.

This paper is intended to give insights into the simultaneous technology choice and investment time problem within a dynamic deterministic framework consisting of a product life cycle and an availability cycle of returns. A Net Present Value approach is employed for solving the problem.

In Germany alone, inventories are estimated to be worth of more than 500 billion €. To manage these inventories, numerous inventory-control policies have been developed in the last decades. These inventory-control policies are typically derived analytically, which is often complicated and time consuming. For many relevant settings, such as complex multi-echelon models, there exist no closed-form formulae to describe the optimal solution. Optimal solutions for those problems are determined by complex algorithms that require several iteration steps. In this paper, we present an alternative approach to derive optimal or near-optimal inventory-control policies that are based on Genetic Programming (GP). GP is an algorithm related to Genetic Algorithms. It applies the principles of natural evolution to solve optimization problems. In this paper, we show how closed-form heuristics for a common inventory-control setting with periodic review can be found with GP. The advantage of GP is that inventory-control policies can be derived empirically without solving complex mathematical models.

We propose a mathematical modeling framework for supply chain network design which captures many aspects of practical problems that have not received adequate attention in the literature. The aspects considered include: dynamic planning horizon, generic supply chain structure, inventory and distribution opportunities for goods, facility configuration, budget constraints, and storage limitations. Moreover, the gradual relocation of facilities over the planning horizon is considered. A generic mathematical programming model is described in detail and several extensions are discussed.

Bei der Leistungsabstimmung von Produktionslinien in der Elektronikmontage (Leiterplattenbestückung) sind die zu bestückenden Bauelemente auf die verschiedenen Automaten innerhalb der Linie aufzuteilen. Hierbei sind sowohl die begrenzten Magazinkapazitäten als auch die technischer Restriktionen der Automaten zu beachten. Gleichzeitig sind unter Beachtung einer möglichen Mehrfachaufrüstung ausgewählter Bauelementtypen die Bestückungsoperationen auf die verschiedenen Automaten innerhalb der Linie aufzuteilen. Ziel ist der Belastungsausgleich zwischen den Automaten. Zur Lösung dieser komplexen Entscheidungsprobleme wird eine effiziente Heuristik vorgeschlagen.

We present a priority-rule based method for batch production scheduling in the process industries. The problem consists in scheduling a given set of operations on a batch plant such that the makespan is minimized. Each operation consumes given amounts of input materials at its start and produces given amounts of output materials at its completion. An initial, a maximum, and a minimum stock level are specified for each material. Some materials are perishable and thus cannot be stored. The operations may be executed on alternative processing units. Processing units require cleaning between certain operations and before any idle time. Due to the constraints on material availability and storage capacity, classical schedule-generation schemes cannot be applied to this problem. That is why we propose a new two-phase approach dealing with the two types of constraints separately.

The transportation of hazardous materials is a growing problem due to the increasing transported volumes. What differentiates hazardous material shipments from shipments of other materials is the risk associated with an accidental release of hazardous materials during transportation. A possible solution to reduce the occurrence of dangerous events is to provide travel plans that establish a fair spatial and temporal distribution of the risk. The objective of this work is to study the problem of routing and scheduling a set of hazardous materials shipments, minimizing the travel total risk while spreading the risk among different zones of the geographical region where the transportation network is defined. We propose a genetic algorithm that, given a set of dissimilar routes for every origin-destination pair, selects a route and defines a departure time for every shipment with the aim of minimizing the total risk of the travel plans. The genetic algorithm is experimentally evaluated on a set of realistic scenarios defined on a regional area.

Die Diskussion um eine leistungsfähige und auch kostengünstige Entsorgung der anfallenden Müllmengen hat sich in den vergangenen Jahren erheblich verschärft. Dies bezieht sich (u.a.) auch auf die Hausmüllentsorgung, die durch die unmittelbare Betroffenheit der privaten Haushalte, eine (kommunal-)politische Dimension beinhaltet. Diese Situation erzwingt eine stärkere Beachtung betriebswirtschaftlicher Zielsetzungen, u.a. in der Form von betriebsinternen Kostensenkungsmassnahmen. Ein wesentlicher Aspekt ist in diesem Zusammenhang die Verbesserung der Tourenplanung sowie der Personaleinsatzplanung in der Müllentsorgung. Ein möglicher Lösungsansatz für diese Problemstellung wird in den Grundzügen skizziert. Ausserdem werden die mit einer Realisierung verbundenen Randbedingungen beschrieben sowie notwendige Veränderungsprozesse aufgezeigt.

Crew pairing, the creation of anonymous lines of work, is a crucial part of the crew airline planning process. Column generation with shortest path pricing subproblem provides high quality solutions. In its basic form, the pricing subproblem relies on assumptions, such as additivity of the cost function and constraint contributions. However, it is not possible to be assume that these requirements are satisfied, particularly if the pairing system gives the user control over problem formulation and maintenance.Solutions to these challenges are proposed, based on proper granularity of the subproblem, a k-shortest paths based pricer and the application of resources to model nonadditive costs. Furthermore, a label-merging technique provides significant performance improvements.

In an earlier paper, we have demonstrated that traffic equilibria under social marginal cost tolls can be computed as local optima of a nonconvex optimization problem. The nonconvexity of this problem implies in particular that linearizations, e.g. in the Frank-Wolfe method, do not give underestimates of the optimal value. In this paper we derive the convex hull of nonconvex arc cost functions of BPR type. These convexifications can be used to get underestimates of the optimal value, or to get better search directions in the initial phase of the Frank-Wolfe method. Computational results for the Sioux Falls and Stockholm networks are reported

Während für Fahrgemeinschaften auf Langstrecken häufig einfache Vermittlungsverfahren ausreichen, kann und muss die Vermittlung von Fahrgemeinschaften auf Kurzstrecken als Online-Optimierungsproblem dargestellt werden. Ausgehend von einer Einordnung des als ganzzahliges lineares Programm formulierten Problems in ein Klassifikationsschema für Tourenplanungsprobleme werden hier heuristische und exakte Lösungsalgorithmen vorgestellt, die einerseits die Anwendbarkeit unter praktischen Online-Bedingungen ermöglichen, aber — mangels geeigneter Standard-Benchmarks — gleichzeitig auch eine Bewertung der Qualität der Lösungen erlauben.

A single machine due date assignment and scheduling problem of minimizing holding costs with no tardy jobs is considered under series-parallel and somewhat wider class of precedence constraints.

When solving crew scheduling problems by column generation, the main task is to solve the pricing problem for introducing new columns. This problem is NP-hard and usually requires more than 90% of the overall computation time in all of our experiments as well as in experiments reported in the literature. Therefore it is critical to achieve good performance in this step. This paper discusses an approach of using a cluster of computers to solve the pricing problem. Several aspects of parallelizing the pricing step are investigated and computational results are reported. The parallel algorithms are designed in such a way that they facilitate extensions and generalizations.

We consider a workforce scheduling problem that arises when scheduling the employees of a casino for a prescribed time period. Given a set of tasks for each day, we are looking for a sequence of tasks and days off for each employee. All sequences have to observe (hard) legal and contractual constraints as well as (soft) in-house restrictions. The overall objective is to minimize violations of the soft restrictions and evenly distribute attractive tasks among employees. Apart from regular employees, we have to take into account temporary employees, where each employee is characterized by a certain set of skills.First, we consider an exact solution procedure based on a minimum-cost multicommodity network flow formulation, which can be solved by means of column generation and branch-and-bound techniques. For large problem instances we propose a local search algorithm. An initial solution is obtained by successively solving several assignment problems. Two Hill Climbing procedures are used to improve the initial solution.

Web usage mining relies on web server logfile data. Parts of this data originate from web robots. This can — with repsect to the original aims of web mining — lead to contradicting decisions based on distorted results. We describe possibilities of web robot detection and give examples how, e.g., e-metrics and results of association rule algorithms can differ based on raw logfiles versus those that consist of requests of human users or web robots.

Web site visitors who look for desired items can formulate search queries which are taken by recommender systems to provide support within the underlying buying situation (e.g., enabling users to view recommended items and buy the ones they find most appropriate). Data from a large German retail online store is used to visualize products viewed most frequently together with search profiles that represent identical search queries of larger subgroups of site users. Comparisons between products viewed most frequently and those purchased most frequently can be used to improve the generation of recommendations. The results give interesting insights concerning the searching, viewing, and buying behavior of online shoppers.

Kontexteffekte können im Zusammenhang mit Neuprodukt-einfuhrungen eine entscheidende Rolle spielen. Sie wurden bislang primär in Experimenten nachgewiesen. Die vorliegenden Simulationsstudie untersucht die Leistungsfähigkeit eines neuen Ansatzes, der es erlaubt Kontexteffekte in Scanner Panel Daten zu messen.

To attract web visitors via the internet it is fundamental for all kinds of online activities to be “visible ”in the net. Visibility measurement is important for web sites: it helps to define benchmarks with respect to competition and allows to calculate visibility indices as predictors for site traffic.This paper discusses a new approach to measure online visibility (OV) and compares it with one known from the literature.We describe physical and psychological drivers of OV and suggest a measurement of OV that works automatically as a robot in the internet. Managerial implications to make web sites “smelly ”or “visible ”are also discussed.

With the rise of the internet, online brokerage emerged as a fast and cost effective way to trade securities. New competitors naturally focused on generating traffic to acquire many customers. However, in ebusiness, “natural” exit barriers (e.g., location) lose importance. As competitors are only a mouse-click away, online firms must convert first-time users into regular customers to regain acquisition costs. But what determines a customer to be committed to his online broker? And, if he can be successfully retained, what effect will that have on the company’s profits? Based on theoretical research, a generic model for the development, dimensions, and behavioral consequences of customer retention are proposed. Using causal analysis, this loyalty/dependence-model is successfully tested in online brokerage.

Product bundling describes an interdisciplinary problem of great importance. It can be used to tailor offers to the demand of consumer segments (marketing), it helps to tackle variety reduction management issues (production), it is based on consumer preferences (data analysis), and it needs combinatorial optimization as solution tool (operations research).In this paper a new profit-maximizing mixed integer product bundling formulation is presented that works well for modest problem instances. Additionally, a heuristic approach is derived that copes with the situation in a Greedy-like manner for larger problem instances by providing a sequence of monotone increasing lower bounds for the objective function of our product bundling methodology.

Im vorliegenden Beitrag wird eine Methodik zur Bestimmung der ökonomischen und ökologischen Auswirkungen von betriebsübergreifenden Energieversorgungskonzepten entwickelt und deren Einsatz an einem Praxisbeispiel aufgezeigt. Im Zentrum der Methodik steht ein gemischt-ganzzahliges Optimierungsmodell zur Identifikation der ausgabenminimalen Struktur der betriebsübergreifenden Energieversorgung. Zur Ermittlung der dafür benötigten Parameter wird ein verfahrenstechnisches Prozesssimulationsmodell genutzt und in einer der Optimierung nachgeschalteten Analyse werden die anfallenden Kosten und Erlöse mit Hilfe spieltheoretischer Verfahren unter den Partnern aufgeteilt.

Die Altersstruktur einer Bevölkerung beeinflusst die Empfänglichkeit für Infektionskrankheiten sowie für chronisch-degenerative Erkrankungen. Mit Hilfe eines System Dynamics Modells wird der epidemiologische übergang von Infektionskrankheiten zu chronisch-degenerativen Erkrankungen simuliert, so dass die Auswirkungen verschiedener Parameter (medizinischer Fortschritt, Alterung etc.) analysiert werden können.

In this paper we study a special class of bond portfolio management problems where strategic and operational as well as active and passive aspects are considered. On a strategic level a so-called reference portfolio is specified which is valid for a specific product class of bond funds (the class of Eurobond-funds for instance) for a specific period of time. On an operational level this predefined mix of assets has to be adapted by the fund managers as precisely as possible for each individual fund on a daily basis respecting all the investment guidelines which have to be fulfilled. Additional lot-size constraints, bid-ask-spreads and commission fees influence the cost of fund restructuring and the associated decision problem leads to a (high-dimensional) discrete non-linear program. We give an outline of a heuristic approach which we have applied in an ongoing decision support system (DSS) development project for a top-european private bank.

While the unconstrained portfolio optimization problem can be solved efficiently by standard algorithms, this is not the case for the portfolio optimization problem with additional real world constraints like cardinality constraints, buy-in thresholds, roundlots etc. In this paper we investigate two extensions to Evolutionary Algorithms (EA) applied to the portfolio optimization problem. First, we introduce a problem specific EA representation and then we add a local search for feasible solutions to improve the performance of the EA. All algorithms are compared on the constrained and unconstrained portfolio optimization problem.

By mid 2004, the Basel Committee on Banking Supervision (BCBS) is expected to launch its final recommendations on minimum capital requirements in the banking industry. Although there is the intention to arrive at capital charges which concur with economic intuition, the risk weight formulas proposed by the committee will lack an adequate treatment of concentration risks in credit portfolios. The question arises whether this problem can be solved without recourse to fully-fledged portfolio models. Since recent practical experience shows that the risk measure Conditional Value-at-Risk (CVaR) is particularly well suited for detecting concentrations, we develop the semi-asymptotic approach by Emmer and Tasche in the CVaR context and compare it with the capital charges recently suggested by the Basel Committee. Both approaches are based on the same Vasicek one-factor model.

Die fortwährende Anwendung von Simulationsmodellen im Geschäftsprozess der taktischen Produktionsplanung scheitert oft an der Schwierigkeit, die Modellparameter immer auf dem aktuellen Stand zu halten. Dies ist umso schwieriger, je größer die Modelle werden. Allerdings ist gerade der Einsatz solcher Simulationsmethoden bei komplexen Modellen umso wichtiger, da z.B. Auswirkungen von geänderten Produktionsraten und Produktportfolios nicht direkt erkennbar sind. In diesem Beitrag wird beschrieben, wie das auf Warteschlangennetzwerken basierende Simulationsmodell EPOS (Enterprise Production Planning and Optimization System) der IBM als integriertes Simulationsmodell in die Planungsprozesse der IBM im Bereich der Festplattenfertigung eingebettet wurde. Dabei werden die mathematischen Grundlagen, der entwickelte Geschäftsprozess sowie Erfahrungen aus der betrieblichen Praxis dargelegt.

Für die Leistungsanalyse hochautomatisierter Anlagen zur Montage elektronischer Baugruppen wurde ein objektorientiertes Simulationssystem entwickelt, das die zur Bestückung einer Leiterplatte erforderlichen Abläufe detailliert unter Berücksichtigung der kinematischen Eigenschaften der jeweiligen Bestückungsautomaten abgebildet. Die entwickelten Simulationsbausteine sind für generelle Automatenklassen konzipiert und können daher durch einfache Parametrisierungen speziellen Bestückungsautomaten angepasst werden.

We investigate a special mixed-discrete bilevel programming problem resulting from the task to compute cash-out penalties due to the supply of incorrect amounts of natural gas through large gas networks. For easier solution we move the discreteness demand from the lower to the upper levels. This clearly changes the problem and it is our aim to investigate the relations between both problems. After the move, a parametric generalized transportation problem arises in the lower level for which the formulation of conditions for the existence of an optimal solution is our first task. In the second part of the paper, requirements guaranteeing that an optimal solution of the original problem is obtained by solving the modified one as well as bounds for the optimal value of the original problem are derived.

In [3]QP-problems with strict convex objective functions / were investigated in order to detect constraints that are not active at the optimal point x*. It turned out, that simple calculations performed in parallel with an QP-solver allow a decision to delete restrictions from the problem. This might shrink down the problem size during the optimization procedure. These sufficient conditions for non activity could be generalized to the positive semi-definite case (see [4]).In the present paper it is shown that the techniques presented in [3] allow to get additional possibilities for a deletion of superfluous constraints. For this, the optimal point x₀ of the unrestricted QP-problem is suitably disturbed within some special set M(f(x*). This set is unknown in advance but a subset A(x₀) can algorithmically be generated. It is also proved, that x* is a limit point in A(x₀).

A comparison of two direct multiple shooting approaches for the solution of chemical optimization problems with DAE models of index one is presented. Differences are explained in terms of the underlying reduced SQP methods. The application to optimal control of a distillation column is used to illustrate the respective advantages.

The satisfiability (SAT) problem is a central problem in mathematical logic, computing theory, and artificial intelligence. An instance of SAT is specified by a set of boolean variables and a propositional formula in conjunctive normal form. Given such an instance, the SAT problem asks whether there is a truth assignment to the variables such that the formula is satisfied. It is well known that SAT is in general NP-complete, although several important special cases can be solved in polynomial time. Semidefinite programming (SDP) refers to the class of optimization problems where a linear function of a matrix variable X is maximized (or minimized) subject to linear constraints on the elements of X and the additional constraint that X be positive semidefinite. We focus on the application of SDP to obtain proofs of unsatisfiability. Using a new SDP relaxation for SAT, we obtain proofs of unsatisfiability for some hard instances with up to 260 variables and over 400 clauses. In particular, we can prove the unsatisfiability of the smallest unsatisfiable instance that remained unsolved during the SAT Competition 2003. This shows that the SDP relaxation is competitive with the top solvers in the competition, and that this technique has the potential to complement existing techniques for SAT.

This paper aims at describing a metric problem of finding two minimum total weight edge-disjoint Hamiltonian circuits in a graph with two weight functions. The problem is NP-hard in strong sense if the weight functions w₁ and w₂ are different or equal. We construct two approximation 0(n3) algorithms whose worstcase performance guarantees asymptotically equal 12/5 (in case of the different functions), and 9/4 (when w₁ and w₂ are equal).

In many regions farmers cultivate a number of small lots that are distributed over a wider area. This leads to high overhead costs and economically prohibits use of high tech machinery hence results in a non-favorable cost-structure of production. The classical form of land consolidation is typically too expensive and too rigid, whence consolidation based on lend-lease agreements has been suggested. In order to exploit the potential of this method specific mathematical optimization algorithms are needed, particularly since the underlying problem is NP-complete even in very restricted cases.This paper introduces a quadratic optimization model and shows its practicality for some typical regions in Northern Bavaria, Germany.

We introduce the data structure of a rooted, alternating, labelled tree and show its utility for a combinatorial solution of the weighted stable set problem in bipartite graphs via linear programming. As a by-product we obtain a weighted max-min relation. We illustrate the algorithm on grid graphs and present compu- tational results that indicate the efficiency of our method.

In this paper we investigate parametric optimization problems of the form $$ _x^{\inf } \{ F(x) - p^T x: Ax \leqslant b, x \in \mathbb{Z}^n \} $$ with F : ℝn → ℝ being differentiable and convex and p ∈ ℝn being some parameter. For this problem we consider the regions of stability, i.e. we ask for the set R(x0) of all parameters p for which a given feasible point x0 is optimal. Of special interest will be the conditions under which the sets are bounded or polyhedral.

This paper deals with the containership stowage problem. Containers are placed on the ship in a last-in-first-out manner and therefore temporary unloading and reloading in subsequent ports along the route, called shifting, is common and results in high costs. This is true, in particular, if the stowage plan is based only on stability constraints of the ship.The generating of such schedules depends on the transportation load, the technical constraints and possibilities in the ports, the ship geometry, the sequence of ports visited and some other rather technical constraints (e. g. very heavy containers or hazardous goods).We will show how this containership stowage problem can be modeled as a mixed integer programming model and discuss the computational complexity of the problem. Based on these results, solution methods are developed and some special cases are analyzed.Furthermore, as a cross reference, we draw our attention to other combinatorial problems like the three-dimensional packing problem with special precedence constraints or pile-up problems. Finally, we propose possible directions for further research.

The Sequential Ordering Problem (SOP) is a version of the Asymmetric Traveling Salesman Problem (ATSP) where precedence constraints on the vertices must also be observed. The SOP has many real life applications and it has proved to be a great challenge (there are SOPs with 40–50 vertices which have not been solved optimally yet with significant computational effort). We use novel branch&bound search algorithms with lower bounds obtained from homomorphic abstractions of the original state space. Our method is asymptotically optimal. In one instance, it has proved a solution value to be optimal for an open problem while it also has matched best known solutions quickly for many unsolved problems from the TSPLIB. Our method of deriving lower bounds is general and applies to other variants of constrained ATSPs as well.

The paper deals with a single processor scheduling problem in which the sum of values of all the jobs is maximized. The job value is characterized by a stepwise non-increasing function with one or more moments at which a change of job value occur. Establishing an order of processing of datagrams which are sent by router is a practical example of application of this problem. It is proved in the paper, that a special case of the considered problem — with a single common moment of job value change and zero value of jobs after this moment — is NP-hard. Therefore, a pseudo-polynomial time algorithm for the case with common moments of job value change is constructed. It is also constructed and experimentally tested a number of heuristic algorithms which solve the general version of the problem.

We explore Small Instance Relaxations in branch-and-cut for the TSP. For small TSP instances of up to 10 cities all facet-defining inequalities of the associated polytopes are known. To exploit this pool of inequalities, we shrink a given TSP support graph to a small graph with at most 10 vertices, search for a violated inequality in the pool, and eventually lift it to obtain a cutting-plane. A Small Instance Relaxation (SIR) is an LP relaxation strengthened by such cutting- planes. We mainly shrink k-way cuts (k ≤ 10) of weight kλ/2 to obtain promising small graphs (λ is the mincut weight). For the separation in the low-dimensional space we solve a series of QAP instances. Padberg-Rinaldi shrinking criteria, graph isomorphism detection and facet class selection are applied to avoid unnecessary QAP computations. Our computational results show the usefulness of SIRs for the TSP. We compare SIRs with local cuts by Applegate et al.

We consider a multiobjective optimization problem in which objective functions are in the form of mathematical expectation of functions depending on a random element and a constraints set can depend on the probability measure. Evidently then probability measure can be considered as a parameter of the problem. The aim of this note is to present a survey of some assertions on a stability and statistical estimates of the set of (properly) efficient points. To this end, already known results from one-objective stochastic programming theory are employed.

We consider a multi-stock market model where prices satisfy a stochastic differential equation (SDE) with instantaneous rates of return modeled as an unobserved continuous time, finite state Markov chain. The investor wishes to maximize the expected utility of terminal wealth but only the prices are available to him for his investment decisions. Thus we have a hidden Markov model (HMM) for the stock returns. Extending the results in [9] to stochastic volatility we obtain explicit optimal trading strategies in terms of the unnormalized filter of the drift process. We propose a simple volatility model in which the volatility is a function of the filter for the drift process. When applied to historical prices, the optimal strategies clearly outperform the strategies based on constant volatility.

In this note we present a policy iteration algorithm for constructing a set of efficient stationary policies containing optimal policies with respect to various criteria used for the mean variance tradeoff. This algorithm works both for the unichain and multichain models. We show that the obtained policies are optimal also in the class of Markovian (memoryless) policies.

We study the process composed from random increments occurring at random moments. Resulting compound process is therefore characterized by the intensity of random time points and by the distribution of increments. We propose a model considering the compound process as a two-dimensional random point process and expressing the mutual dependence of both components via the multiplicative hazard regression (Cox) model. The method of estimation of model components is presented and the prediction of process behaviour is studied. The application deals with the process of financial transactions and with the problem of detection of atypical trajectories.

The minimum weight design of structures made of fiber reinforced composite materials leads to a class of discrete optimization problems for which evolutionary algorithms (EAs) are well suited. Based on these algorithms the optimization tool package GEOPS has been developed at TU Dresden.For each structure generated by an EA the structural response has to be evaluated. This is often based on a finite element analysis, which results in high computational efforts for each single structure. Typical runs of EAs require the evaluation of thousands of structures. Thus, an efficient approximation of the structural response could improve the performance considerably. To achieve this aim, the use of a support vector machine (SVM) is suggested in this paper.As an example for a typical aircraft structure, a stiffened composite panel under compressive and shear loading is considered. Buckling as well as strength constraints are taken into account. The SVM is trained on geometrical and material data. Representing the design space of composite panels by ABD matrices turned out to be a valuable means for obtaining well trained SVMs.

(Probabilistische) Konditionale stellen ein Kommunikationsinstrument dar, mit dem Wissen in einer reichen Sprache vermittelt werden kann. Ziel dieses Artikels ist es aufzuzeigen, wie die Konditionalsprache erweitert werden kann, um auch Sprachgefüge mit temporalem Kontext auszudrücken. Zur Verarbeitung des Wissens dient das axiomatisch fundierte Entropieprinzip. Anhand eines Beispiels mittlerer Grösse werden die theoretischen Überlegungen in der Expertensystem-Shell SPIRIT näher illustriert.

Die im vorliegenden Beitrag angestellten Überlegungen konzentrieren sich auf die Entwicklung eines unscharfen regelbasierten Systems zur automatisierten Bewertung von Dienstplänen. Als InputGrössen des Systems modellieren wir die linguistischen Variablen Personalbedarfsdeckung und Mitarbeiterzufriedenheit mit ihren korrespondierenden linguistischen Termen. Die resultierende OutputGrösse ist die Gesamtbewertung des Dienstplanes. Ein weiteres Augenmerk gilt neben der Modellierung des unscharfen Regelsystems der Lösung des in diesem Zusammenhang stehenden Skalierungsproblems.

Evolutionary Algorithms (EA) are excellent optimization tools for complex high-dimensional multimodal problems. However, they require a very large number of problem function evaluations. In many engineering optimization problems, like high throughput material science or design optimization, a single fitness evaluation is very expensive or time consuming. Therefore, standard evolutionary computation methods are not practical for such applications. Applying models as a surrogate of the real fitness function is a quite popular approach to handle this restriction. We propose a Model Assisted Evolution Strategy (MAES), which uses a Gaussian Process (GP) approximation model. The purpose of the Gaussian Process model is to preselect the most promising solutions, which are then actually evaluated by the real problem function. To refine the preselection process the likelihood of each individual to improve the overall best found solution is determined. Numerical results from extensive simulations on high dimensional test functions and one material optimization problem are presented. MAES has a much better convergence rate and achieves better results than standard evolutionary optimization approaches with less fitness evaluations.

The paper aims at drawing attention to the potential of (qualitative) stability theory of stochastic programming for the study of asymptotic properties of statistical estimates. Making use of existing stability results, it is often possible to weaken the assumptions and to deal also with non-standard estimation problems. Thus non-unique solutions to the underlying optimization problems as well as constraints for the estimates can be taken into account and the continuity assumptions can often be replaced by semicontinuity. In this paper the focus is on consistency for constrained estimation with non-unique solutions. It will be shown how stability results obtained by the author can be employed to derived assertions on the convergence in probability of statistical estimates. The general results use the epi-convergence approach.

We formulate an optimal control capital accumulation model with an exogenously given time lag between investment and the accumulation of the capital stock to analyze the qualitative and quantitative influence of time lags to the system dynamics. Optimal investment paths for a finite time lag are shown to be cyclic as opposed to the monotone paths for instantaneous capital accumulation. Furthermore, we show how to reformulate the retarded differential equation in a suitable way so that sophisticated numerical methods for optimal control can be applied to analyze the impact of the length of the time lag. It turns out that both the frequency and the amplitude of the cycles depend on the length of the investment period.

We introduce a procurement auction model where capacity-constrained firms face a sequence of two procurement auctions, each of them in the first-price sealed-bid design. Our main findings are that the firms’ entry decisions depend on relative project completion cost levels and that equilibrium bidding in both auction stages deviates from the standard Symmetric Independent Private Value auction model (SIPV) due to opportunity costs of bidding created by possibly employed capacity. The model highlights the fact that firms with identical completion costs for the first project may differ in entry and bidding strategies. In addition, experimental data is reported in order to assess the predictive power of the model.

The World Wide Web (WWW) contains millions of hypertext pages that present nearly all kinds of information. Specific effort is required to use this information as input to subsequent computations or to aggregate values in web pages. To do so, data from webpages are extracted and stored on computers either in text files or databases. These manipulations can be better attained by using an autonomous software program instead of human personal. Here, we present a platform independent software agent called PISA (Partially Intelligent Software Agent) that extracts financial data autonomously from webpages and stores them on a local computer. Data quality has highest significance. PISA generates time series with user defined denseness. These time series have adequate quality for financial market analyses, e. g. forecasts with neural networks.

Several methods have been developed over a number of years for solving decision problems when vague and numerically imprecise information prevails. However, the DELTA method and similar methods give rise to particular bilinear programming problems that are time consuming to solve in a real-time environment. This paper presents a set of benchmark tests for non-linear programming solvers for solving this special type of problems. With two existing linear programming based algorithms, it also investigates the performance of linear programming solvers for special decision situations in decision analysis systems.

knowCube is a novel multicriteria decision support system, consisting of components for knowledge organization, generation, and navigation. Knowledge organization rests upon a data base for managing qualitative and quantitative criteria, together with add-on information. Knowledge generation serves filling the data base via e.g. identification, optimization, classification or simulation. For “finding needles in haycocks”, the knowledge navigation component supports graphical data base retrieval and interactive, goal-oriented problem solving. Navigation “helpers” are, for instance, cascading criteria aggregations, modifiable metrics, ergonomie interfaces, and customizable visualizations. Examples from real-life projects, e.g. in industrial engineering and in the life sciences, illustrate the application of knowCube.