Refine
Year of publication
Document Type
- Report (179)
- Preprint (19)
- Doctoral Thesis (4)
- Course Material (2)
- Working Paper (1)
Language
- English (205) (remove)
Has Fulltext
- yes (205)
Keywords
- numerical upscaling (7)
- Integer programming (4)
- hub location (4)
- Darcy’s law (3)
- Heston model (3)
- Lagrangian mechanics (3)
- effective heat conductivity (3)
- facility location (3)
- non-Newtonian flow in porous media (3)
- poroelasticity (3)
Faculty / Organisational entity
- Fraunhofer (ITWM) (205) (remove)
In the literature, there are at least two equivalent two-factor Gaussian models for the instantaneous short rate. These are the original two-factor Hull White model (see [3]) and the G2++ one by Brigo and Mercurio (see [1]). Both these models first specify a time homogeneous two-factor short rate dynamics and then by adding a deterministic shift function '(·) fit exactly the initial term structure of interest rates. However, the obtained results are rather clumsy and not intuitive which means that a special care has to be taken for their correct numerical implementation.
In this paper we study the possibilities of sharing profit in combinatorial procurement auctions and exchanges. Bundles of heterogeneous items are offered by the sellers, and the buyers can then place bundle bids on sets of these items. That way, both sellers and buyers can express synergies between items and avoid the well-known risk of exposure (see, e.g., [3]). The reassignment of items to participants is known as the Winner Determination Problem (WDP). We propose solving the WDP by using a Set Covering formulation, because profits are potentially higher than with the usual Set Partitioning formulation, and subsidies are unnecessary. The achieved benefit is then to be distributed amongst the participants of the auction, a process which is known as profit sharing. The literature on profit sharing provides various desirable criteria. We focus on three main properties we would like to guarantee: Budget balance, meaning that no more money is distributed than profit was generated, individual rationality, which guarantees to each player that participation does not lead to a loss, and the core property, which provides every subcoalition with enough money to keep them from separating. We characterize all profit sharing schemes that satisfy these three conditions by a monetary flow network and state necessary conditions on the solution of the WDP for the existence of such a profit sharing. Finally, we establish a connection to the famous VCG payment scheme [2, 8, 19], and the Shapley Value [17].
Determination of interaction between MCT1 and CAII via a mathematical and physiological approach
(2008)
The enzyme carbonic anhydrase isoform II (CAII), catalysing the hydration and dehydration of CO2, enhances transport activity of the monocarboxylate transporter isoform I (MCT1, SLC16A1) expressed in Xenopus oocytes by a mechanism that does not require CAII catalytic activity (Becker et al. (2005) J. Biol. Chem., 280). In the present study, we have investigated the mechanism of the CAII induced increase in transport activity by using electrophysiological techniques and a mathematical model of the MCT1 transport cycle. The model consists of six states arranged in cyclic fashion and features an ordered, mirror-symmetric, binding mechanism were binding and unbinding of the proton to the transport protein is considered to be the rate limiting step under physiological conditions. An explicit rate expression for the substrate °ux is derived using model reduction techniques. By treating the pools of intra- and extracellular MCT1 substrates as dynamic states, the time dependent kinetics are obtained by integration using the derived expression for the substrate °ux. The simulations were compared with experimental data obtained from MCT1-expressing oocytes injected with di®erent amounts of CAII. The model suggests that CAII increases the e®ective rate constants of the proton reactions, possibly by working as a proton antenna.
The level-set method has been recently introduced in the field of shape optimization, enabling a smooth representation of the boundaries on a fixed mesh and therefore leading to fast numerical algorithms. However, most of these algorithms use a Hamilton-Jacobi equation to connect the evolution of the level-set function with the deformation of the contours, and consequently they cannot create any new holes in the domain (at least in 2D). In this work, we propose an evolution equation for the level-set function based on a generalization of the concept of topological gradient. This results in a new algorithm allowing for all kinds of topology changes.
This report discusses two approaches for a posteriori error indication in the linear elasticity solver DDFEM: An indicator based on the Richardson extrapolation and Zienkiewicz-Zhu-type indicator. The solver handles 3D linear elasticity steady-state problems. It uses own input language to describe the mesh and the boundary conditions. Finite element discretization over tetrahedral meshes with first or second order shape functions (hierarchical basis) has been used to resolve the model. The parallelization of the numerical method is based on the domain decomposition approach. DDFEM is highly portable over a set of parallel computer architectures supporting the MPI-standard.
The rotational spinning of viscous jets is of interest in many industrial applications, including pellet manufacturing [4, 14, 19, 20] and drawing, tapering and spinning of glass and polymer fibers [8, 12, 13], see also [15, 21] and references within. In [12] an asymptotic model for the dynamics of curved viscous inertial fiber jets emerging from a rotating orifice under surface tension and gravity was deduced from the three-dimensional free boundary value problem given by the incompressible Navier-Stokes equations for a Newtonian fluid. In the terminology of [1], it is a string model consisting of balance equations for mass and linear momentum. Accounting for inner viscous transport, surface tension and placing no restrictions on either the motion or the shape of the jet’s center-line, it generalizes the previously developed string models for straight [3, 5, 6] and curved center-lines [4, 13, 19]. Moreover, the numerical results investigating the effects of viscosity, surface tension, gravity and rotation on the jet behavior coincide well with the experiments of Wong et.al. [20].
The optimal design of rotational production processes for glass wool manufacturing poses severe computational challenges to mathematicians, natural scientists and engineers. In this paper we focus exclusively on the spinning regime where thousands of viscous thermal glass jets are formed by fast air streams. Homogeneity and slenderness of the spun fibers are the quality features of the final fabric. Their prediction requires the computation of the fuidber-interactions which involves the solving of a complex three-dimensional multiphase problem with appropriate interface conditions. But this is practically impossible due to the needed high resolution and adaptive grid refinement. Therefore, we propose an asymptotic coupling concept. Treating the glass jets as viscous thermal Cosserat rods, we tackle the multiscale problem by help of momentum (drag) and heat exchange models that are derived on basis of slender-body theory and homogenization. A weak iterative coupling algorithm that is based on the combination of commercial software and self-implemented code for ow and rod solvers, respectively, makes then the simulation of the industrial process possible. For the boundary value problem of the rod we particularly suggest an adapted collocation-continuation method. Consequently, this work establishes a promising basis for future optimization strategies.
This work deals with the modeling and simulation of slender viscous jets exposed to gravity and rotation, as they occur in rotational spinning processes. In terms of slender-body theory we show the asymptotic reduction of a viscous Cosserat rod to a string system for vanishing slenderness parameter. We propose two string models, i.e. inertial and viscous-inertial string models, that differ in the closure conditions and hence yield a boundary value problem and an interface problem, respectively. We investigate the existence regimes of the string models in the four-parametric space of Froude, Rossby, Reynolds numbers and jet length. The convergence regimes where the respective string solution is the asymptotic limit to the rod turn out to be disjoint and to cover nearly the whole parameter space. We explore the transition hyperplane and derive analytically low and high Reynolds number limits. Numerical studies of the stationary jet behavior for different parameter ranges complete the work.
This paper analyzes and solves a patient transportation problem arising in several large hospitals. The aim is to provide an efficient and timely transport service to patients between several locations on a hospital campus. Transportation requests arrive in a dynamic fashion and the solution methodology must therefore be capable of quickly inserting new requests in the current vehicle routes. Contrary to standard dial-a-ride problems, the problem under study contains several complicating constraints which are specific to a hospital context. The paper provides a detailed description of the problem and proposes a two-phase heuristic procedure capable of handling its many features. In the first phase a simple insertion scheme is used to generate a feasible solution, which is improved in the second phase with a tabu search algorithm. The heuristic procedure was extensively tested on real data provided by a German hospital. Results show that the algorithm is capable of handling the dynamic aspect of the problem and of providing high quality solutions. In particular, it succeeded in reducing waiting times for patients while using fewer vehicles.
Within this paper we review image distortion measures. A distortion measure is a criterion that assigns a "quality number" to an image. We distinguish between mathematical distortion measures and those distortion measures in-cooperating a priori knowledge about the imaging devices ( e.g. satellite images), image processing algorithms or the human physiology. We will consider representative examples of different kinds of distortion measures and are going to discuss them.
Test rig optimization
(2014)
Designing good test rigs for fatigue life tests is a common task in the auto-
motive industry. The problem to find an optimal test rig configuration and
actuator load signals can be formulated as a mathematical program. We in-
troduce a new optimization model that includes multi-criteria, discrete and
continuous aspects. At the same time we manage to avoid the necessity to
deal with the rainflow-counting (RFC) method. RFC is an algorithm, which
extracts load cycles from an irregular time signal. As a mathematical func-
tion it is non-convex and non-differentiable and, hence, makes optimization
of the test rig intractable.
The block structure of the load signals is assumed from the beginning.
It highly reduces complexity of the problem without decreasing the feasible
set. Also, we optimize with respect to the actuators’ positions, which makes
it possible to take torques into account and thus extend the feasible set. As
a result, the new model gives significantly better results, compared with the
other approaches in the test rig optimization.
Under certain conditions, the non-convex test rig problem is a union of
convex problems on cones. Numerical methods for optimization usually need
constraints and a starting point. We describe an algorithm that detects each
cone and its interior point in a polynomial time.
The test rig problem belongs to the class of bilevel programs. For every
instance of the state vector, the sum of functions has to be maximized. We
propose a new branch and bound technique that uses local maxima of every
summand.
Robust Reliability of Diagnostic Multi-Hypothesis Algorithms: Application to Rotating Machinery
(1998)
Damage diagnosis based on a bank of Kalman filters, each one conditioned on a specific hypothesized system condition, is a well recognized and powerful diagnostic tool. This multi-hypothesis approach can be applied to a wide range of damage conditions. In this paper, we will focus on the diagnosis of cracks in rotating machinery. The question we address is: how to optimize the multi-hypothesis algorithm with respect to the uncertainty of the spatial form and location of cracks and their resulting dynamic effects. First, we formulate a measure of the reliability of the diagnostic algorithm, and then we discuss modifications of the diagnostic algorithm for the maximization of the reliability. The reliability of a diagnostic algorithm is measured by the amount of uncertainty consistent with no-failure of the diagnosis. Uncertainty is quantitatively represented with convex models.
The objective of this paper is to bridge the gap between location theory and practice. To meet this objective focus is given to the development of software capable of addressing the different needs of a wide group of users. There is a very active community on location theory encompassing many research fields such as operations research, computer science, mathematics, engineering, geography, economics and marketing. As a result, people working on facility location problems have a very diverse background and also different needs regarding the software to solve these problems. For those interested in non-commercial applications (e. g. students and researchers), the library of location algorithms (LoLA can be of considerable assistance. LoLA contains a collection of efficient algorithms for solving planar, network and discrete facility location problems. In this paper, a detailed description of the functionality of LoLA is presented. In the fields of geography and marketing, for instance, solving facility location problems requires using large amounts of demographic data. Hence, members of these groups (e. g. urban planners and sales managers) often work with geographical information too s. To address the specific needs of these users, LoLA was inked to a geographical information system (GIS) and the details of the combined functionality are described in the paper. Finally, there is a wide group of practitioners who need to solve large problems and require special purpose software with a good data interface. Many of such users can be found, for example, in the area of supply chain management (SCM). Logistics activities involved in strategic SCM include, among others, facility location planning. In this paper, the development of a commercial location software tool is also described. The too is embedded in the Advanced Planner and Optimizer SCM software developed by SAP AG, Walldorf, Germany. The paper ends with some conclusions and an outlook to future activities.
We propose a constraint-based approach for the two-dimensional rectangular packing problem with orthogonal orientations. This problem is to arrange a set of rectangles that can be rotated by 90 degrees into a rectangle of minimal size such that no two rectangles overlap. It arises in the placement of electronic devices during the layout of 2.5D System-in-Package integrated electronic systems. Moffitt et al. [8] solve the packing without orientations with a branch and bound approach and use constraint propagation. We generalize their propagation techniques to allow orientations. Our approach is compared to a mixed-integer program and we provide results that outperform it.
In this paper we develop a network location model that combines the characteristics of ordered median and gradual cover models resulting in the Ordered Gradual Covering Location Problem (OGCLP). The Gradual Cover Location Problem (GCLP) was specifically designed to extend the basic cover objective to capture sensitivity with respect to absolute travel distance. Ordered Median Location problems are a generalization of most of the classical locations problems like p-median or p-center problems. They can be modeled by using so-called ordered median functions. These functions multiply a weight to the cost of fulfilling the demand of a customer which depends on the position of that cost relative to the costs of fulfilling the demand of the other customers. We derive Finite Dominating Sets (FDS) for the one facility case of the OGCLP. Moreover, we present efficient algorithms for determining the FDS and also discuss the conditional case where a certain number of facilities are already assumed to exist and one new facility is to be added. For the multi-facility case we are able to identify a finite set of potential facility locations a priori, which essentially converts the network location model into its discrete counterpart. For the multi-facility discrete OGCLP we discuss several Integer Programming formulations and give computational results.
The Discrete Ordered Median Problem (DOMP) generalizes classical discrete location problems, such as the N-median, N-center and Uncapacitated Facility Location problems. It was introduced by Nickel [16], who formulated it as both a nonlinear and a linear integer program. We propose an alternative integer linear programming formulation for the DOMP, discuss relationships between both integer linear programming formulations, and show how properties of optimal solutions can be used to strengthen these formulations. Moreover, we present a specific branch and bound procedure to solve the DOMP more efficiently. We test the integer linear programming formulations and this branch and bound method computationally on randomly generated test problems.
In this paper, a stochastic model [5] for the turbulent fiber laydown in the industrial production of nonwoven materials is extended by including a moving conveyor belt. In the hydrodynamic limit corresponding to large noise values, the transient and stationary joint probability distributions are determined using the method of multiple scales and the Chapman-Enskog method. Moreover, exponential convergence towards the stationary solution is proven for the reduced problem. For special choices of the industrial parameters, the stochastic limit process is an Ornstein{Uhlenbeck. It is a good approximation of the fiber motion even for moderate noise values. Moreover, as shown by Monte{Carlo simulations, the limiting process can be used to assess the quality of nonwoven materials in the industrial application by determining distributions of functionals of the process.
Radiation therapy planning is always a tight rope walk between dangerous insufficient dose in the target volume and life threatening overdosing of organs at risk. Finding ideal balances between these inherently contradictory goals challenges dosimetrists and physicians in their daily practice. Today’s planning systems are typically based on a single evaluation function that measures the quality of a radiation treatment plan. Unfortunately, such a one dimensional approach cannot satisfactorily map the different backgrounds of physicians and the patient dependent necessities. So, too often a time consuming iteration process between evaluation of dose distribution and redefinition of the evaluation function is needed. In this paper we propose a generic multi-criteria approach based on Pareto’s solution concept. For each entity of interest - target volume or organ at risk a structure dependent evaluation function is defined measuring deviations from ideal doses that are calculated from statistical functions. A reasonable bunch of clinically meaningful Pareto optimal solutions are stored in a data base, which can be interactively searched by physicians. The system guarantees dynamical planning as well as the discussion of tradeoffs between different entities. Mathematically, we model the upcoming inverse problem as a multi-criteria linear programming problem. Because of the large scale nature of the problem it is not possible to solve the problem in a 3D-setting without adaptive reduction by appropriate approximation schemes. Our approach is twofold: First, the discretization of the continuous problem is based on an adaptive hierarchical clustering process which is used for a local refinement of constraints during the optimization procedure. Second, the set of Pareto optimal solutions is approximated by an adaptive grid of representatives that are found by a hybrid process of calculating extreme compromises and interpolation methods.
This work presents a new framework for Gröbner basis computations with Boolean polynomials. Boolean polynomials can be modeled in a rather simple way, with both coefficients and degree per variable lying in {0, 1}. The ring of Boolean polynomials is, however, not a polynomial ring, but rather the quotient ring of the polynomial ring over the field with two elements modulo the field equations x2 = x for each variable x. Therefore, the usual polynomial data structures seem not to be appropriate for fast Gröbner basis computations. We introduce a specialized data structure for Boolean polynomials based on zero-suppressed binary decision diagrams (ZDDs), which is capable of handling these polynomials more efficiently with respect to memory consumption and also computational speed. Furthermore, we concentrate on high-level algorithmic aspects, taking into account the new data structures as well as structural properties of Boolean polynomials. For example, a new useless-pair criterion for Gröbner basis computations in Boolean rings is introduced. One of the motivations for our work is the growing importance of formal hardware and software verification based on Boolean expressions, which suffer – besides from the complexity of the problems – from the lack of an adequate treatment of arithmetic components. We are convinced that algebraic methods are more suited and we believe that our preliminary implementation shows that Gröbner bases on specific data structures can be capable to handle problems of industrial size.
In this work we extend the multiscale finite element method (MsFEM)
as formulated by Hou and Wu in [14] to the PDE system of linear elasticity.
The application, motivated from the multiscale analysis of highly heterogeneous
composite materials, is twofold. Resolving the heterogeneities on
the finest scale, we utilize the linear MsFEM basis for the construction of
robust coarse spaces in the context of two-level overlapping Domain Decomposition
preconditioners. We motivate and explain the construction
and present numerical results validating the approach. Under the assumption
that the material jumps are isolated, that is they occur only in the
interior of the coarse grid elements, our experiments show uniform convergence
rates independent of the contrast in the Young's modulus within the
heterogeneous material. Elsewise, if no restrictions on the position of the
high coefficient inclusions are imposed, robustness can not be guaranteed
any more. These results justify expectations to obtain coefficient-explicit
condition number bounds for the PDE system of linear elasticity similar to
existing ones for scalar elliptic PDEs as given in the work of Graham, Lechner
and Scheichl [12]. Furthermore, we numerically observe the properties
of the MsFEM coarse space for linear elasticity in an upscaling framework.
Therefore, we present experimental results showing the approximation errors
of the multiscale coarse space w.r.t. the fine-scale solution.
For the numerical simulation of a mechanical multibody system (MBS), dynamical loads are needed as input data, such as a road profile. With given input quantities, the equations of motion of the system can be integrated. Output quantities for further investigations are calculated from the integration results. In this paper, we consider the corresponding inverse problem: We assume, that a dynamical system and some reference output signals are given. The general task is to derive an input signal, such that the system simulation produces the desired reference output. We present the state-of-the-art method in industrial applications, the iterative learning control method (ILC) and give an application example from automotive industry. Then, we discuss three alternative methods based on optimal control theory for differential algebraic equations (DAEs) and give an overview of their general scheme.
Input loads are essential for the numerical simulation of vehicle multibody system
(MBS)- models. Such load data is called invariant, if it is independent of the specific system under consideration. A digital road profile, e.g., can be used to excite MBS models of different
vehicle variants. However, quantities efficiently obtained by measurement such as wheel forces
are typically not invariant in this sense. This leads to the general task to derive invariant loads
on the basis of measurable, but system-dependent quantities. We present an approach to derive
input data for full-vehicle simulation that can be used to simulate different variants of a vehicle
MBS model. An important ingredient of this input data is a virtual road profile computed by optimal control methods.
It is well-known that some of the classical location problems with polyhedral gauges can be solved in polynomial time by finding a finite dominating set, i.e. a finite set of candidates guaranteed to contain at least one optimal location. In this paper it is first established that this result holds for a much larger class of problems than currently considered in the literature. The model for which this result can be proven includes, for instance, location problems with attraction and repulsion, and location-allocation problems. Next, it is shown that the approximation of general gauges by polyhedral ones in the objective function of our general model can be analyzed with regard to the subsequent error in the optimal objective value. For the approximation problem two different approaches are described, the sandwich procedure and the greedy algorithm. Both of these approaches lead - for fixed epsilon - to polynomial approximation algorithms with accuracy epsilon for solving the general model considered in this paper.
A new approach is proposed to model and simulate numerically heterogeneous catalysis in rarefied gas flows. It is developed to satisfy all together the following points: i) describe the gas phase at the microscopic scale, as required in rarefied flows, ii) describe the wall at the macroscopic scale, to avoid prohibitive computational costs and consider not only crystalline but also amorphous surfaces, iii) reproduce on average macroscopic laws correlated with experimental results and iv) derive ana- lytic models in a systematic and exact way. The problem is stated in the general framework of a non static flow in the vicinity of a catalytic and non porous surface (without ageing). It is shown that the exact and systematic resolution method based on the Laplace transform, introduced previously by the author to model collisions in the gas phase, can be extended to the present problem. The proposed approach is applied to the modelling of the Eley-Rideal and Langmuir-Hinshelwood recombinations, assuming that the coverage is locally at equilibrium. The models are developed considering one atomic species and extended to the gen eral case of several atomic species. Numerical calculations show that the models derived in this way reproduce with accuracy behaviours observed experimentally.
The performance of oil filters used in the automotive industry can be significantly improved, especially when computer simulation is an essential component of the design process. In this paper, we consider parallel numerical algorithms for solving mathematical models describing the process of filtration, filtering out solid particles from liquid oil. The Navier-Stokes-Brinkmann system of equations is used to describe the laminar flow of incompressible isothermal oil. The space discretization in the complicated filter geometry is based on the finite-volume method. Special care is taken for an accurate approximation of velocity and pressure on the interface between the fluid and the porous media. The time discretization used here is a proper modification of the fractional time step discretization (cf. Chorin scheme) of the Navier-Stokes equations, where the Brinkmann term is considered at both, prediction and correction substeps. A data decomposition method is used to develop a parallel algorithm, where the domain is distributed among processors by using a structured reference grid. The MPI library is used to implement the data communication part of the algorithm. A theoretical model is proposed for the estimation of the complexity of the given parallel algorithm and a scalability analysis is done on the basis of this model. Results of computational experiments are presented, and the accuracy and efficiency of the parallel algorithm is tested on real industrial geometries.
In this paper we consider numerical algorithms for solving a system of nonlinear PDEs arising in modeling of liquid polymer injection. We investigate the particular case when a porous preform is located within the mould, so that the liquid polymer flows through a porous medium during the filling stage. The nonlinearity of the governing system of PDEs is due to the non-Newtonian behavior of the polymer, as well as due to the moving free boundary. The latter is related to the penetration front and a Stefan type problem is formulated to account for it. A finite-volume method is used to approximate the given differential problem. Results of numerical experiments are presented. We also solve an inverse problem and present algorithms for the determination of the absolute preform permeability coefficient in the case when the velocity of the penetration front is known from measurements. In both cases (direct and inverse problems) we emphasize on the specifics related to the non-Newtonian behavior of the polymer. For completeness, we discuss also the Newtonian case. Results of some experimental measurements are presented and discussed.
The capacitated single-allocation hub location problem revisited: A note on a classical formulation
(2009)
Denote by G = (N;A) a complete graph where N is the set of nodes and A is the set of edges. Assume that a °ow wij should be sent from each node i to each node j (i; j 2 N). One possibility is to send these °ows directly between the corresponding pairs of nodes. However, in practice this is often neither e±cient nor costly attractive because it would imply that a link was built between each pair of nodes. An alternative is to select some nodes to become hubs and use them as consolidation and redistribution points that altogether process more e±ciently the flow in the network. Accordingly, hubs are nodes in the graph that receive tra±c (mail, phone calls, passengers, etc) from di®erent origins (nodes) and redirect this tra±c directly to the destination nodes (when a link exists) or else to other hubs. The concentration of tra±c in the hubs and its shipment to other hubs lead to a natural decrease in the overall cost due to economies of scale.
In this paper, an extension to the classical capacitated single-allocation hub location problem is studied in which the size of the hubs is part of the decision making process. For each potential hub a set of capacities is assumed to be available among which one can be chosen. Several formulations are proposed for the problem, which are compared in terms of the bound provided by the linear programming relaxation. Di®erent sets of inequalities are proposed to enhance the models. Several preprocessing tests are also presented with the goal of reducing the size of the models for each particular instance. The results of the computational experiments performed using the proposed models are reported.
The scope of this paper is to enhance the model for the own-company stockholder (given in Desmettre, Gould and Szimayer (2010)), who can voluntarily performance-link his personal wealth to his management success by acquiring stocks in the own-company whose value he can directly influence via spending work effort. The executive is thereby characterized by a parameter of risk aversion and the two work effectiveness parameters inverse work productivity and disutility stress. We extend the model to a constant absolute risk aversion framework using an exponential utility/disutility set-up. A closed-form solution is given for the optimal work effort an executive will apply and we derive the optimal investment strategies of the executive. Furthermore, we determine an up-front fair cash compensation applying an indifference utility rationale. Our study shows to a large extent that the results previously obtained are robust under the choice of the utility/disutility set-up.
We develop a framework for analyzing an executive’s own-company stockholding and work effort preferences. The executive, characterized by risk aversion and work effectiveness parameters, invests his personal wealth without constraint in the financial market, including the stock of his own company whose value he can directly influence with work effort. The executive’s utility-maximizing personal investment and work effort strategy is derived in closed-form, and an indifference utility rationale is demonstrated to determine his required compensation. Our results have implications for the practical and theoretical assessment of executive quality and the benefits of performance contracting. Assuming knowledge of the company’s non-systematic risk, our executive’s unconstrained own-company investment identifies his work effectiveness (i.e. quality), and also reflects work effort that establishes a base-level that performance contracting should seek to exceed.
We consider a highly-qualified individual with respect to her choice between two distinct career paths. She can choose between a mid-level management position in a large company and an executive position within a smaller listed company with the possibility to directly affect the company’s share price. She invests in the financial market includ- ing the share of the smaller listed company. The utility maximizing strategy from consumption, investment, and work effort is derived in closed form for logarithmic utility. The power utility case is discussed as well. Conditions for the individual to pursue her career with the smaller listed company are obtained. The participation constraint is formulated in terms of the salary differential between the two posi- tions. The smaller listed company can offer less salary. The salary shortfall is offset by the possibility to benefit from her work effort by acquiring own-company shares. This gives insight into aspects of optimal contract design. Our framework is applicable to the pharma- ceutical and financial industry, and the IT sector.
This report describes the calibration and completion of the volatility cube in the SABR model. The description is based on a project done for Assenagon GmbH in Munich. However, we use fictitious market data which resembles realistic market data. The problem posed by our client is formulated in section 1. Here we also motivate why this is a relevant problem. The SABR model is briefly reviewed in section 2. Section 3 discusses the calibration and completion of the volatility cube. An example is presented in section 4. We conclude by suggesting possible future research in section 5.
In this work we use the Parsimonious Multi–Asset Heston model recently developed in [Dimitroff et al., 2009] at Fraunhofer ITWM, Department Financial Mathematics, Kaiserslautern (Germany) and apply it to Quanto options. We give a summary of the model and its calibration scheme. A suitable transformation of the Quanto option payoff is explained and used to price Quantos within the new framework. Simulated prices are given and compared to market prices and Black–Scholes prices. We find that the new approach underprices the chosen options, but gives better results than the Black–Scholes approach, which is prevailing in the literature on Quanto options.
We present two heuristic methods for solving the Discrete Ordered Median Problem (DOMP), for which no such approaches have been developed so far. The DOMP generalizes classical discrete facility location problems, such as the p-median, p-center and Uncapacitated Facility Location problems. The first procedure proposed in this paper is based on a genetic algorithm developed by Moreno Vega [MV96] for p-median and p-center problems. Additionally, a second heuristic approach based on the Variable Neighborhood Search metaheuristic (VNS) proposed by Hansen & Mladenovic [HM97] for the p-median problem is described. An extensive numerical study is presented to show the efficiency of both heuristics and compare them.
In this paper we propose a general approach solution method for the single facility ordered median problem in the plane. All types of weights (non-negative, non-positive, and mixed) are considered. The big triangle small triangle approach is used for the solution. Rigorous and heuristic algorithms are proposed and extensively tested on eight different problems with excellent results.
Safety and reliability requirements on the one side and short development cycles, low costs and lightweight design on the other side are two competing aspects of truck engineering. For safety critical components essentially no failures can be tolerated within the target mileage of a truck. For other components the goals are to stay below certain predefined failure rates. Reducing weight or cost of structures often also reduces strength and reliability. The requirements on the strength, however, strongly depend on the loads in actual customer usage. Without sufficient knowledge of these loads one needs large safety factors, limiting possible weight or cost reduction potentials. There are a lot of different quantities influencing the loads acting on the vehicle in actual usage. These ‘influencing quantities’ are, for example, the road quality, the driver, traffic conditions, the mission (long haulage, distribution or construction site), and the geographic region. Thus there is a need for statistical methods to model the load distribution with all its variability, which in turn can be used for the derivation of testing specifications.
We present a unified approach of several boundary conditions for lattice Boltzmann models. Its general framework is a generalization of previously introduced schemes such as the bounce-back rule, linear or quadratic interpolations, etc. The objectives are two fold: first to give theoretical tools to study the existing boundary conditions and their corresponding accuracy; secondly to design formally third- order accurate boundary conditions for general flows. Using these boundary conditions, Couette and Poiseuille flows are exact solution of the lattice Boltzmann models for a Reynolds number Re = 0 (Stokes limit). Numerical comparisons are given for Stokes flows in periodic arrays of spheres and cylinders, linear periodic array of cylinders between moving plates and for Navier-Stokes flows in periodic arrays of cylinders for Re < 200. These results show a significant improvement of the overall accuracy when using the linear interpolations instead of the bounce-back reflection (up to an order of magnitude on the hydrodynamics fields). Further improvement is achieved with the new multi-reflection boundary conditions, reaching a level of accuracy close to the quasi-analytical reference solutions, even for rather modest grid resolutions and few points in the narrowest channels. More important, the pressure and velocity fields in the vicinity of the obstacles are much smoother with multi-reflection than with the other boundary conditions. Finally the good stability of these schemes is highlighted by some simulations of moving obstacles: a cylinder between flat walls and a sphere in a cylinder.
Flow of non-Newtonian fluid in saturated porous media can be described by the continuity equation and the generalized Darcy law. Efficient solution of the resulting second order nonlinear elliptic equation is discussed here. The equation is discretized by a finite volume method on a cell-centered grid. Local adaptive refinement of the grid is introduced in order to reduce the number of unknowns. A special implementation approach is used, which allows us to perform unstructured local refinement in conjunction with the finite volume discretization. Two residual based error indicators are exploited in the adaptive refinement criterion. Second order accurate discretization of the fluxes on the interfaces between refined and non-refined subdomains, as well as on the boundaries with Dirichlet boundary condition, are presented here, as an essential part of the accurate and efficient algorithm. A nonlinear full approximation storage multigrid algorithm is developed especially for the above described composite (coarse plus locally refined) grid approach. In particular, second order approximation of the fluxes around interfaces is a result of a quadratic approximation of slave nodes in the multigrid - adaptive refinement (MG-AR) algorithm. Results from numerical solution of various academic and practice-induced problems are presented and the performance of the solver is discussed.
On a Multigrid Adaptive Refinement Solver for Saturated Non-Newtonian Flow in Porous Media A multigrid adaptive refinement algorithm for non-Newtonian flow in porous media is presented. The saturated flow of a non-Newtonian fluid is described by the continuity equation and the generalized Darcy law. The resulting second order nonlinear elliptic equation is discretized by a finite volume method on a cell-centered grid. A nonlinear full-multigrid, full-approximation-storage algorithm is implemented. As a smoother, a single grid solver based on Picard linearization and Gauss-Seidel relaxation is used. Further, a local refinement multigrid algorithm on a composite grid is developed. A residual based error indicator is used in the adaptive refinement criterion. A special implementation approach is used, which allows us to perform unstructured local refinement in conjunction with the finite volume discretization. Several results from numerical experiments are presented in order to examine the performance of the solver.
In this paper, we propose multi-level Monte Carlo(MLMC) methods that use ensemble level mixed multiscale methods in the simulations of multi-phase flow and transport. The main idea of ensemble level multiscale methods is to construct local multiscale basis functions that can be used for any member of the ensemble. We consider two types of ensemble level mixed multiscale finite element methods, (1) the no-local-solve-online ensemble level method (NLSO) and (2) the local-solve-online ensemble level method (LSO). Both mixed multiscale methods use a number of snapshots of the permeability media to generate a multiscale basis.
As a result, in the offline stage, we construct multiple basis functions for
each coarse region where basis functions correspond to different realizations.
In the no-local-solve-online ensemble level method one uses the whole set of pre-computed basis functions to approximate the solution for an arbitrary realization. In the local-solve-online ensemble level method one uses the pre-computed functions to construct a multiscale basis for a particular realization. With this basis the solution corresponding to this
particular realization is approximated in LSO mixed MsFEM. In both approaches
the accuracy of the method is related to the number of snapshots computed based on different realizations that one uses to pre-compute a
multiscale basis. We note that LSO approaches share similarities with reduced basis methods [11, 21, 22].
In multi-level Monte Carlo methods ([14, 13]), more accurate (and expensive) forward simulations are run with fewer samples while less accurate(and inexpensive) forward simulations are run with a larger number of samples. Selecting the number of expensive and inexpensive simulations carefully, one can show that MLMC methods can provide better accuracy
at the same cost as MC methods. In our simulations, our goal is twofold. First, we would like to compare NLSO and LSO mixed MsFEMs. In particular, we show that NLSO
mixed MsFEM is more accurate compared to LSO mixed MsFEM. Further, we use both approaches in the context of MLMC to speed-up MC
calculations. We present basic aspects of the algorithm and numerical
results for coupled flow and transport in heterogeneous porous media.
Simulation of multibody systems (mbs) is an inherent part in developing and design of complex mechanical systems. Moreover, simulation during operation gained in importance in the recent years, e.g. for HIL-, MIL- or monitoring applications. In this paper we discuss the numerical simulation of multibody systems on different platforms. The main section of this paper deals with the simulation of an established truck model [9] on different platforms, one microcontroller and two real-time processor boards. Additional to numerical C-code the latter platforms provide the possibility to build the model with a commercial mbs tool, which is also investigated. A survey of different ways of generating code and equations of mbs models is given and discussed concerning handling, possible limitations as well as performance. The presented benchmarks are processed under terms of on-board real time applications. A further important restriction, caused by the real-time requirement, is a fixed integration step size. Whence, carefully chosen numerical integration algorithms are necessary, especially in the case of closed loops in the model. We investigate linearly-implicit time integration methods with fixed step size, so-called Rosenbrock methods, and compare them with respect to their accuracy and performance on the tested processors.
The modelling of hedge funds poses a difficult problem since the available reported data sets are often small and incomplete. We propose a switching regression model for hedge funds, in which the coefficients are able to switch between different regimes. The coefficients are governed by a Markov chain in discrete time. The different states of the Markov chain represent different states of the economy, which influence the performance of the independent variables. Hedge fund indices are chosen as regressors. The parameter estimation for the switching parameter as well as for the switching error term is done through a filtering technique for hidden Markov models developed by Elliott (1994). Recursive parameter estimates are calculated through a filter-based EM-algorithm, which uses the hidden information of the underlying Markov chain. Our switching regression model is applied on hedge fund series and hedge fund indices from the HFR database.
Traditional methods fail for the purpose of simulating the complete flow process in urban areas as a consequence of heavy rainfall and as required by the European Standard EN-752 since the bi-directional coupling between sewer and surface is not properly handled. The methodology, developed in the BMBF/ EUREKA-project RisUrSim, solves this problem by carrying out the runoff on the basis of shallow water equations solved on high-resolution surface grids. Exchange nodes between the sewer and the surface, like inlets and manholes, are located in the computational grid and water leaving the sewer in case of surcharge is further distributed on the surface. So far, it has been a problem to get the dense topographical information needed to build models suitable for hydrodynamic runoff calculation in urban areas. Recent airborne data collection methods like laser scanning, however, offer a great chance to economically gather densely sampled input data. This paper studies the potential of such laser-scan data sets for urban water hydrodynamics.
Finite difference discretizations of 1D poroelasticity equations with discontinuous coefficients are analyzed. A recently suggested FD discretization of poroelasticity equations with constant coefficients on staggered grid, [5], is used as a basis. A careful treatment of the interfaces leads to harmonic averaging of the discontinuous coefficients. Here, convergence for the pressure and for the displacement is proven in certain norms for the scheme with harmonic averaging (HA). Order of convergence 1.5 is proven for arbitrary located interface, and second order convergence is proven for the case when the interface coincides with a grid node. Furthermore, following the ideas from [3], modified HA discretization are suggested for particular cases. The velocity and the stress are approximated with second order on the interface in this case. It is shown that for wide class of problems, the modified discretization provides better accuracy. Second order convergence for modified scheme is proven for the case when the interface coincides with a displacement grid node. Numerical experiments are presented in order to illustrate our considerations.
Two-level domain decomposition preconditioner for 3D flows in anisotropic highly heterogeneous porous media is presented. Accurate finite volume discretization based on multipoint flux approximation (MPFA) for 3D pressure equation is employed to account for the jump discontinuities of full permeability tensors. DD/MG type preconditioner for above mentioned problem is developed. Coarse scale operator is obtained from a homogenization type procedure. The influence of the overlapping as well as the influence of the smoother and cell problem formulation is studied. Results from numerical experiments are presented and discussed.
An efficient approach for calculating the effective heat conductivity for a class of industrial composite materials, such as metal foams, fibrous glass materials, and the like, is discussed. These materials, used in insulation or in advanced heat exchangers, are characterized by a low volume fraction of the highly conductive material (glass or metal) having a complex, network-like structure and by a large volume fraction of the insulator (air). We assume that the composite materials have constant macroscopic thermal conductivity tensors, which in principle can be obtained by standard up-scaling techniques, that use the concept of representative elementary volumes (REV), i.e. the effective heat conductivities of composite media can be computed by post-processing the solutions of some special cell problems for REVs. We propose, theoretically justify, and numerically study an efficient approach for calculating the effective conductivity for media for which the ratio of low and high conductivities satisfies 1. In this case one essentially only needs to solve the heat equation in the region occupied by the highly conductive media. For a class of problems we show, that under certain conditions on the microscale geometry, the proposed approach produces an upscaled conductivity that is O() close to the exact upscaled permeability. A number of numerical experiments are presented in order to illustrate the accuracy and the limitations of the proposed method. Applicability of the presented approach to upscaling other similar problems, e.g. flow in fractured porous media, is also discussed.
A number of water flow problems in porous media are modelled by Richards’ equation [1]. There exist a lot of different applications of this model. We are concerned with the simulation of the pressing section of a paper machine. This part of the industrial process provides the dewatering of the paper layer by the use of clothings, i.e. press felts, which absorb the water during pressing [2]. A system of nips are formed in the simplest case by rolls, which increase sheet dryness by pressing against each other (see Figure 1). A lot of theoretical studies were done for Richards’ equation (see [3], [4] and references therein). Most articles consider the case of x-independent coefficients. This simplifies the system considerably since, after Kirchhoff’s transformation of the problem, the elliptic operator becomes linear. In our case this condition is not satisfied and we have to consider nonlinear operator of second order. Moreover, all these articles are concerned with the nonstationary problem, while we are interested in the stationary case. Due to complexity of the physical process our problem has a specific feature. An additional convective term appears in our model because the porous media moves with the constant velocity through the pressing rolls. This term is zero in immobile porous media. We are not aware of papers, which deal with such kind of modified steady Richards’ problem. The goal of this paper is to obtain the stability results, to show the existence of a solution to the discrete problem, to prove the convergence of the approximate solution to the weak solution of the modified steady Richards’ equation, which describes the transport processes in the pressing section. In Section 2 we present the model which we consider. In Section 3 a numerical scheme obtained by the finite volume method is given. The main part of this paper is theoretical studies, which are given in Section 4. Section 5 presents a numerical experiment. The conclusion of this work is given in Section 6.
In this paper, a combined approach to damage diagnosis of rotors is proposed. The intention is to employ signal-based as well as model-based procedures for an improved detection of size and location of the damage. In a first step, Hilbert transform signal processing techniques allow for a computation of the signal envelope and the instantaneous frequency, so that various types of non-linearities due to a damage may be identified and classified based on measured response data. In a second step, a multi-hypothesis bank of Kalman Filters is employed for the detection of the size and location of the damage based on the information of the type of damage provided by the results of the Hilbert transform.
A new stability preserving model reduction algorithm for discrete linear SISO-systems based on their impulse response is proposed. Similar to the Padé approximation, an equation system for the Markov parameters involving the Hankel matrix is considered, that here however is chosen to be of very high dimension. Although this equation system therefore in general cannot be solved exactly, it is proved that the approximate solution, computed via the Moore-Penrose inverse, gives rise to a stability preserving reduction scheme, a property that cannot be guaranteed for the Padé approach. Furthermore, the proposed algorithm is compared to another stability preserving reduction approach, namely the balanced truncation method, showing comparable performance of the reduced systems. The balanced truncation method however starts from a state space description of the systems and in general is expected to be more computational demanding.
To a network N(q) with determinant D(s;q) depending on a parameter vector q Î Rr via identification of some of its vertices, a network N^ (q) is assigned. The paper deals with procedures to find N^ (q), such that its determinant D^ (s;q) admits a factorization in the determinants of appropriate subnetworks, and with the estimation of the deviation of the zeros of D^ from the zeros of D. To solve the estimation problem state space methods are applied.
The problem discussed in this paper is motivated by the new recycling directiveWEEE of the EC. The core of this law is, that each company which sells electrical or electronic equipment in a European country has the obligation to recollect and recycle an amount of returned items which is proportional to its market share. To assign collection stations to companies, in Germany for one product type a territory design approach is planned. However, in contrast to classical territory design, the territories should be geographically as dispersed as possible to avoid that a company, resp. its logistics provider responsible for the recollection, gains a monopoly in some region. First, we identify an appropriate measure for the dispersion of a territory. Afterwards, we present a first mathematical programming model for this new problem as well as a solution method based on the GRASP methodology. Extensive computational results illustrate the suitability of the model and assess the effectiveness of the heuristic.
In this expository article, we give an introduction into the basics of bootstrap tests in general. We discuss the residual-based and the wild bootstrap for regression models suitable for applications in signal and image analysis. As an illustration of the general idea, we consider a particular test for detecting differences between two noisy signals or images which also works for noise with variable variance. The test statistic is essentially the integrated squared difference between the signals after denoising them by local smoothing. Determining its quantile, which marks the boundary between accepting and rejecting the hypothesis of equal signals, is hardly possible by standard asymptotic methods whereas the bootstrap works well. Applied to the rows and columns of images, the resulting algorithm not only allows for the detection of defects but also for the characterization of their location and shape in surface inspection problems.
In soil mechanics assumption of only vertical subsidence is often invoked and this leads to the one-dimensional model of poroelasticity. The classical model of linear poroelasticity is obtained by Biot [1], detailed derivation can be found e.g., in [2]. This model is applicable also to modelling certain processes in geomechanics, hydrogeology, petroleum engineering (see, e.g., [3, 8], in biomechanics (e.g., [9, 10]), in filtration (e.g., filter cake formation, see [15, 16, 17]), in paper manufacturing (e.g., [11, 12]), in printing (e.g., [13]), etc. Finite element and finite difference methods were applied by many authors for numerical solution of the Biot system of PDEs, see e.g. [3, 4, 5] and references therein. However, as it is wellknown, the standard FEM and FDM methods are subject to numerical instabilities at the first time steps. To avoid this, discretization on staggered grid was suggested in [4, 5]. A single layer deformable porous medium was considered there. This paper can be viewed as extension of [4, 5] to the case of multilayered deformable porous media. A finite volume discretization to the interface problem for the classical one-dimensional Biot model of consolidation process is applied here. Following assumptions are supposed to be valid: each of the porous layers is composed of incompressible solid matrix, it is homogeneous and isotropic. Furthermore, one of two following assumptions is valid: porous medium is not completely saturated and fluid is incompressible or porous medium is completely saturated and fluid is slightly compressible. The reminder of the paper is organised as follows. Next section presents the mathematical model. Third section is devoted to the dicsretization of the continuous problem. Fourth section contains the results from the numerical experiments.
In this paper, a new mixed integer mathematical programme is proposed for the application of Hub Location Problems (HLP) in public transport planning. This model is among the few existing ones for this application. Some classes of valid inequalities are proposed yielding a very tight model. To solve instances of this problem where existing standard solvers fail, two approaches are proposed. The first one is an exact accelerated Benders decomposition algorithm and the latter a greedy neighborhood search. The computational results substantiate the superiority of our solution approaches to existing standard MIP solvers like CPLEX, both in terms of computational time and problem instance size that can be solved. The greedy neighborhood search heuristic is shown to be extremely efficient.
In this paper, we are going to propose the first mathematical model for Multi- Period Hub Location Problems (MPHLP). We apply this mixed integer program- ming model on public transport planning and call it Multi-Period Hub Location Problem for Public Transport (MPHLPPT). In fact, HLPPT model proposed earlier by the authors is extended to include more facts and features of the real-life application. In order to solve instances of this problem where existing standard solvers fail, a solution approach based on a greedy neighborhood search is developed. The computational results substantiate the efficiency of our solution approach to solve instances of MPHLPPT.
Free Surface Lattice-Boltzmann Method To Model The Filling Of Expanding Cavities By Bingham Fluids
(2001)
The filling process of viscoplastic metal alloys and plastics in expanding cavities is modelled using the lattice Boltzmann method in two and three dimensions. These models combine the regularized Bingham model for viscoplastic with a free-interface algorithm. The latter is based on a modified immiscible lattice Boltzmann model in which one species is the fluid and the other one is considered as vacuum. The boundary conditions at the curved liquid-vacuum interface are met without any geometrical front reconstruction from a first-order Chapman-Enskog expansion. The numerical results obtained with these models are found in good agreement with available theoretical and numerical analysis.
Lattice Boltzmann Model for Free-Surface flow and Its Application to Filling Process in Casting
(2002)
A generalized lattice Boltzmann model to simulate free-surface is constructed in both two and three dimensions. The proposed model satisfies the interfacial boundary conditions accurately. A distinctive feature of the model is that the collision processes is carried out only on the points occupied partially or fully by the fluid. To maintain a sharp interfacial front, the method includes an anti-diffusion algorithm. The unknown distribution functions at the interfacial region are constructed according to the first order Chapman-Enskog analysis. The interfacial boundary conditions are satisfied exactly by the coefficients in the Chapman-Enskog expansion. The distribution functions are naturally expressed in the local interfacial coordinates. The macroscopic quantities at the interface are extracted from the least-square solutions of a locally linearized system obtained from the known distribution functions. The proposed method does not require any geometric front construction and is robust for any interfacial topology. Simulation results of realistic filling process are presented: rectangular cavity in two dimensions and Hammer box, Campbell box, Sheffield box, and Motorblock in three dimensions. To enhance the stability at high Reynolds numbers, various upwind-type schemes are developed. Free-slip and no-slip boundary conditions are also discussed.
The direction splitting approach proposed earlier in [6], aiming at the efficient solution of Navier-Stokes equations, is extended and adopted here to solve the Navier-Stokes-Brinkman equations describing incompressible flows in plain and in porous media. The resulting pressure equation is a perturbation of the
incompressibility constrained using a direction-wise factorized operator as proposed in [6]. We prove that this approach is unconditionally stable for the unsteady Navier-Stokes-Brinkman problem. We also provide numerical illustrations of the method's accuracy and efficiency.
In this paper we present and investigate a stochastic model for the lay-down of fibers on a conveyor belt in the production process of nonwovens. The model is based on a stochastic differential equation taking into account the motion of the ber under the influence of turbulence. A reformulation as a stochastic Hamiltonian system and an application of the stochastic averaging theorem lead to further simplications of the model. Finally, the model is used to compute the distribution of functionals of the process that might be helpful for the quality assessment of industrial fabrics.
To simulate the influence of process parameters to the melt spinning process a fiber model is used and coupled with CFD calculations of the quench air flow. In the fiber model energy, momentum and mass balance are solved for the polymer mass flow. To calculate the quench air the Lattice Boltzmann method is used. Simulations and experiments for different process parameters and hole configurations are compared and show a good agreement.
Abstract. The stationary, isothermal rotational spinning process of fibers is considered. The investigations are concerned with the case of large Reynolds (± = 3/Re ¿ 1) and small Rossby numbers (\\\" ¿ 1). Modelling the fibers as a Newtonian fluid and applying slender body approximations, the process is described by a two–point boundary value problem of ODEs. The involved quantities are the coordinates of the fiber’s centerline, the fluid velocity and viscous stress. The inviscid case ± = 0 is discussed as a reference case. For the viscous case ± > 0 numerical simulations are carried out. Transfering some properties of the inviscid limit to the viscous case, analytical bounds for the initial viscous stress of the fiber are obtained. A good agreement with the numerical results is found. These bounds give strong evidence, that for ± > 3\\\"2 no physical relevant solution can exist. A possible interpretation of the above coupling of ± and \\\" related to the die–swell phenomenon is given.
In the present paper a kinetic model for vehicular traffic leading to multivalued fundamental diagrams is developed and investigated in detail. For this model phase transitions can appear depending on the local density and velocity of the flow. A derivation of associated macroscopic traffic equations from the kinetic equation is given. Moreover, numerical experiments show the appearance of stop and go waves for highway traffic with a bottleneck.
Industrial analog circuits are usually designed using numerical simulation tools. To obtain a deeper circuit understanding, symbolic analysis techniques can additionally be applied. Approximation methods which reduce the complexity of symbolic expressions are needed in order to handle industrial-sized problems. This paper will give an overview to the field of symbolic analog circuit analysis. Starting with a motivation, the state-of-the-art simplification algorithms for linear as well as for nonlinear circuits are presented. The basic ideas behind the different techniques are described, whereas the technical details can be found in the cited references. Finally, the application of linear and nonlinear symbolic analysis will be shown on two example circuits.
We examine the feasibility polyhedron of the uncapacitated hub location problem (UHL) with multiple allocation, which has applications in the fields of air passenger and cargo transportation, telecommunication and postal delivery services. In particular we determine the dimension and derive some classes of facets of this polyhedron. We develop some general rules about lifting facets from the uncapacitated facility location (UFL) for UHL and projecting facets from UHL to UFL. By applying these rules we get a new class of facets for UHL which dominates the inequalities in the original formulation. Thus we get a new formulation of UHL whose constraints are all facet–defining. We show its superior computational performance by benchmarking it on a well known data set.
Given a public transportation system represented by its stops and direct connections between stops, we consider two problems dealing with the prices for the customers: The fare problem in which subsets of stops are already aggregated to zones and "good" tariffs have to be found in the existing zone system. Closed form solutions for the fare problem are presented for three objective functions. In the zone problem the design of the zones is part of the problem. This problem is NP hard and we therefore propose three heuristics which prove to be very successful in the redesign of one of Germany's transportation systems
This paper details models and algorithms which can be applied to evacuation problems. While it concentrates on building evacuation many of the results are applicable also to regional evacuation. All models consider the time as main parameter, where the travel time between components of the building is part of the input and the overall evacuation time is the output. The paper distinguishes between macroscopic and microscopic evacuation models both of which are able to capture the evacuees' movement over time. Macroscopic models are mainly used to produce good lower bounds for the evacuation time and do not consider any individual behavior during the emergency situation. These bounds can be used to analyze existing buildings or help in the design phase of planning a building. Macroscopic approaches which are based on dynamic network flow models (minimum cost dynamic flow, maximum dynamic flow, universal maximum flow, quickest path and quickest flow) are described. A special feature of the presented approach is the fact, that travel times of evacuees are not restricted to be constant, but may be density dependent. Using multicriteria optimization priority regions and blockage due to fire or smoke may be considered. It is shown how the modelling can be done using time parameter either as discrete or continuous parameter. Microscopic models are able to model the individual evacuee's characteristics and the interaction among evacuees which influence their movement. Due to the corresponding huge amount of data one uses simulation approaches. Some probabilistic laws for individual evacuee's movement are presented. Moreover ideas to model the evacuee's movement using cellular automata (CA) and resulting software are presented. In this paper we will focus on macroscopic models and only summarize some of the results of the microscopic approach. While most of the results are applicable to general evacuation situations, we concentrate on building evacuation.
For some decades radiation therapy has been proved successful in cancer treatment. It is the major task of clinical radiation treatment planning to realise on the one hand a high level dose of radiation in the cancer tissue in order to obtain maximum tumour control. On the other hand it is obvious that it is absolutely necessary to keep in the tissue outside the tumour, particularly in organs at risk, the unavoidable radiation as low as possible. No doubt, these two objectives of treatment planning high level dose in the tumour, low radiation outside the tumour have a basically contradictory nature. Therefore, it is no surprise that inverse mathematical models with dose distribution bounds tend to be infeasible in most cases. Thus, there is need for approximations compromising between overdosing the organs at risk and underdosing the target volume. Differing from the currently used time consuming iterative approach, which measures deviation from an ideal (non-achievable) treatment plan using recursively trial-and-error weights for the organs of interest, we go a new way trying to avoid a priori weight choices and consider the treatment planning problem as a multiple objective linear programming problem: with each organ of interest, target tissue as well as organs at risk, we associate an objective function measuring the maximal deviation from the prescribed doses. We build up a data base of relatively few efficient solutions representing and approximating the variety of Pareto solutions of the multiple objective linear programming problem. This data base can be easily scanned by physicians looking for an adequate treatment plan with the aid of an appropriate online tool.
Finding "good" cycles in graphs is a problem of great interest in graph theory as well as in locational analysis. We show that the center and median problems are NP hard in general graphs. This result holds both for the variable cardinality case (i.e. all cycles of the graph are considered) and the fixed cardinality case (i.e. only cycles with a given cardinality p are feasible). Hence it is of interest to investigate special cases where the problem is solvable in polynomial time. In grid graphs, the variable cardinality case is, for instance, trivially solvable if the shape of the cycle can be chosen freely. If the shape is fixed to be a rectangle one can analyse rectangles in grid graphs with, in sequence, fixed dimension, fixed cardinality, and variable cardinality. In all cases a com plete characterization of the optimal cycles and closed form expressions of the optimal objective values are given, yielding polynomial time algorithms for all cases of center rectangle problems. Finally, it is shown that center cycles can be chosen as rectangles for small cardinalities such that the center cycle problem in grid graphs is in these cases completely solved.
In this paper, we present a novel multicriteria decision support system (MCDSS), called knowCube, consisting of components for knowledge organization, generation, and navigation. Knowledge organization rests upon a database for managing qualitative and quantitative criteria, together with add-on information. Knowledge generation serves filling the database via e.g. identification, optimization, classification or simulation. For “finding needles in haycocks”, the knowledge navigation component supports graphical database retrieval and interactive, goal-oriented problem solving. Navigation “helpers” are, for instance, cascading criteria aggregations, modifiable metrics, ergonomic interfaces, and customizable visualizations. Examples from real-life projects, e.g. in industrial engineering and in the life sciences, illustrate the application of our MCDSS.
Bringing robustness to patient flow management through optimized patient transports in hospitals
(2007)
Intra-hospital transports are often required for diagnostic or therapeutic reasons. Depending on the hospital layout, transportation between nursing wards and service units is either provided by ambulances or by trained personnel who accompany patients on foot. In many large German hospitals, the patient transport service is poorly managed and lacks workflow coordination. This contributes to higher hospital costs (e.g. when a patient is not delivered to the operating room on time) and to patient inconvenience due to longer waiting times. We have designed a computer-based planning system - Opti-TRANS c - that supports all phases of the transportation flow, ranging from travel booking, dispatching transport requests to monitoring and reporting trips in real-time. The methodology developed to solve the underlying optimization problem - a dynamic dial-a-ride problem with hospital-specific constraints - draws on fast heuristic methods to ensure the efficient and timely provision of transports. We illustrate the strong impact of Opti-TRANS c on the daily performance of the patient transportation service of a large German hospital. The major benefits obtained with the new tool include streamlined transportation processes and workflow, significant savings and improved patient satisfaction. Moreover, the new planning system has contributed to increase awareness among hospital staff about the importance of implementing efficient logistics practices.
In this paper, we discuss approaches related to the explicit modeling of human beings in software development processes. While in most older simulation models of software development processes, esp. those of the system dynamics type, humans are only represented as a labor pool, more recent models of the discrete-event simulation type require representations of individual humans. In that case, particularities regarding the person become more relevant. These individual effects are either considered as stochastic variations of productivity, or an explanation is sought based on individual characteristics, such as skills for instance. In this paper, we explore such possibilities by recurring to some basic results in psychology, sociology, and labor science. Various specific models for representing human effects in software process simulation are discussed.
In this article, we consider the problem of planning inspections and other tasks within a software development (SD) project with respect to the objectives quality (no. of defects), project duration, and costs. Based on a discrete-event simulation model of SD processes comprising the phases coding, inspection, test, and rework, we present a simplified formulation of the problem as a multiobjective optimization problem. For solving the problem (i.e. finding an approximation of the efficient set) we develop a multiobjective evolutionary algorithm. Details of the algorithm are discussed as well as results of its application to sample problems.
During the recent years, multiobjective evolutionary algorithms have matured as a flexible optimization tool which can be used in various areas of reallife applications. Practical experiences showed that typically the algorithms need an essential adaptation to the specific problem for a successful application. Considering these requirements, we discuss various issues of the design and application of multiobjective evolutionary algorithms to real-life optimization problems. In particular, questions on problem-specific data structures and evolutionary operators and the determination of method parameters are treated. As a major issue, the handling of infeasible intermediate solutions is pointed out. Three application examples in the areas of constrained global optimization (electronic circuit design), semi-infinite programming (design centering problems), and discrete optimization (project scheduling) are discussed.
With the ever-increasing significance of software in our everyday lives, it is vital to afford reliable software quality estimates. Typically, quantitative software quality analyses rely on either statistical fault prediction methods (FPMs) or stochastic software reliability growth models (SRGMs). Adopting solely FPMs or SRGMs, though, may result in biased predictions that do not account for uncertainty in the distinct prediction methods; thus rendering the prediction less reliable. This paper identifies flaws of the individual prediction methods and suggests a hybrid prediction approach that combines FPMs and SRGMs. We adopt FPMs for initially estimating the expected number of failures for fi- nite failure SRGMs. Initial parameter estimates yield more accurate reliability predictions until sufficient failures are observed that enable stable parameter estimates in SRGMs. Being at the equilibrium level of FPM and SRGM pre- dictions we suggest combining the competing prediction methods with respect to the principle of heterogeneous redundancy. That is, we propose using the in- dividual methods separately and combining their predictions. In this paper we suggest Bayesian model averaging (BMA) for combining the different methods. The hybrid approach allows early reliability estimates and encourages higher confidence in software quality predictions.
In the Finite-Volume-Particle Method (FVPM), the weak formulation of a hyperbolic conservation law is discretized by restricting it to a discrete set of test functions. In contrast to the usual Finite-Volume approach, the test functions are not taken as characteristic functions of the control volumes in a spatial grid, but are chosen from a partition of unity with smooth and overlapping partition functions (the particles), which can even move along prescribed velocity fields. The information exchange between particles is based on standard numerical flux functions. Geometrical information, similar to the surface area of the cell faces in the Finite-Volume Method and the corresponding normal directions are given as integral quantities of the partition functions. After a brief derivation of the Finite-Volume-Particle Method, this work focuses on the role of the geometric coefficients in the scheme.
We derive a new class of particle methods for conservation laws, which are based on numerical flux functions to model the interactions between moving particles. The derivation is similar to that of classical Finite-Volume methods; except that the fixed grid structure in the Finite-Volume method is substituted by so-called mass packets of particles. We give some numerical results on a shock wave solution for Burgers equation as well as the well-known one-dimensional shock tube problem.
This paper discusses a numerical subgrid resolution approach for solving the Stokes-Brinkman system of equations, which is describing coupled ow in plain and in highly porous media. Various scientic and industrial problems are described by this system, and often the geometry and/or the permeability vary on several scales. A particular target is the process of oil ltration. In many complicated lters, the lter medium or the lter element geometry are too ne to be resolved by a feasible computational grid. The subgrid approach presented in the paper is aimed at describing how these ne details are accounted for by solving auxiliary problems in appropriately chosen grid cells on a relatively coarse computational grid. This is done via a systematic and a careful procedure of modifying and updating the coecients of the Stokes-Brinkman system in chosen cells. This numerical subgrid approach is motivated from one side from homogenization theory, from which we borrow the formulations for the so called cell problem, and from the other side from the numerical upscaling approaches, such as Multiscale Finite Volume, Multiscale Finite Element, etc. Results on the algorithm's eciency, both in terms of computational time and memory usage, are presented. Comparison with solutions on full ne grid (when possible) are presented in order to evaluate the accuracy. Advantages and limitations of the considered subgrid approach are discussed.
This paper concerns numerical simulation of flow through oil filters. Oil filters consist of filter housing (filter box), and a porous filtering medium, which completely separates the inlet from the outlet. We discuss mathematical models, describing coupled flows in the pure liquid subregions and in the porous filter media, as well as interface conditions between them. Further, we reformulate the problem in fictitious regions method manner, and discuss peculiarities of the numerical algorithm in solving the coupled system. Next, we show numerical results, validating the model and the algorithm. Finally, we present results from simulation of 3-D oil flow through a real car filter.
In this work, some model reduction approaches for performing simulations
with a pseudo-2D model of Li-ion battery are presented. A full pseudo-2D model of processes in Li-ion batteries is presented following
[3], and three methods to reduce the order of the full model are considered. These are: i) directly reduce the model order using proper
orthogonal decomposition, ii) using fractional time step discretization in order to solve the equations in decoupled way, and iii) reformulation
approaches for the diffusion in the solid phase. Combinations of above
methods are also considered. Results from numerical simulations are presented, and the efficiency and the accuracy of the model reduction approaches are discussed.
Abstract. An efficient approach to the numerical upscaling of thermal conductivities of fibrous media, e.g. insulation materials, is considered. First, standard cell problems for a second order elliptic equation are formulated for a proper piece of random fibrous structure, following homogenization theory. Next, a graph formed by the fibers is considered, and a second order elliptic equation with suitable boundary conditions is solved on this graph only. Replacing the boundary value problem for the full cell with an auxiliary problem with special boundary conditions on a connected subdomain of highly conductive material is justified in a previous work of the authors. A discretization on the graph is presented here, and error estimates are provided. The efficient implementation of the algorithm is discussed. A number of numerical experiments is presented in order to illustrate the performance of the proposed method.
Abstract — Various advanced two-level iterative methods are studied numerically and compared with each other in conjunction with finite volume discretizations of symmetric 1-D elliptic problems with highly oscillatory discontinuous coefficients. Some of the methods considered rely on the homogenization approach for deriving the coarse grid operator. This approach is considered here as an alternative to the well-known Galerkin approach for deriving coarse grid operators. Different intergrid transfer operators are studied, primary consideration being given to the use of the so-called problemdependent prolongation. The two-grid methods considered are used as both solvers and preconditioners for the Conjugate Gradient method. The recent approaches, such as the hybrid domain decomposition method introduced by Vassilevski and the globallocal iterative procedure proposed by Durlofsky et al. are also discussed. A two-level method converging in one iteration in the case where the right-hand side is only a function of the coarse variable is introduced and discussed. Such a fast convergence for problems with discontinuous coefficients arbitrarily varying on the fine scale is achieved by a problem-dependent selection of the coarse grid combined with problem-dependent prolongation on a dual grid. The results of the numerical experiments are presented to illustrate the performance of the studied approaches.
We present a two-scale finite element method for solving Brinkman’s and Darcy’s equations. These systems of equations model fluid flows in highly porous and porous media, respectively. The method uses a recently proposed discontinuous Galerkin FEM for Stokes’ equations byWang and Ye and the concept of subgrid approximation developed by Arbogast for Darcy’s equations. In order to reduce the “resonance error” and to ensure convergence to the global fine solution the algorithm is put in the framework of alternating Schwarz iterations using subdomains around the coarse-grid boundaries. The discussed algorithms are implemented using the Deal.II finite element library and are tested on a number of model problems.
Iterative solution of large scale systems arising after discretization and linearization of the unsteady non-Newtonian Navier–Stokes equations is studied. cross WLF model is used to account for the non-Newtonian behavior of the fluid. Finite volume method is used to discretize the governing system of PDEs. Viscosity is treated explicitely (e.g., it is taken from the previous time step), while other terms are treated implicitly. Different preconditioners (block–diagonal, block–triangular, relaxed incomplete LU factorization, etc.) are used in conjunction with advanced iterative methods, namely, BiCGStab, CGS, GMRES. The action of the preconditioner in fact requires inverting different blocks. For this purpose, in addition to preconditioned BiCGStab, CGS, GMRES, we use also algebraic multigrid method (AMG). The performance of the iterative solvers is studied with respect to the number of unknowns, characteristic velocity in the basic flow, time step, deviation from Newtonian behavior, etc. Results from numerical experiments are presented and discussed.
In this work the problem of fluid flow in deformable porous media is studied. First, the stationary fluid-structure interaction (FSI) problem is formulated in terms of incompressible Newtonian fluid and a linearized elastic solid. The flow is assumed to be characterized by very low Reynolds number and is described by the Stokes equations. The strains in the solid are small allowing for the solid to be described by the Lame equations, but no restrictions are applied on the magnitude of the displacements leading to strongly coupled, nonlinear fluid-structure problem. The FSI problem is then solved numerically by an iterative procedure which solves sequentially fluid and solid subproblems. Each of the two subproblems is discretized by finite elements and the fluid-structure coupling is reduced to an interface boundary condition. Several numerical examples are presented and the results from the numerical computations are used to perform permeability computations for different geometries.
The paper production is a problem with significant importance for the society
and it is a challenging topic for scientific investigations. This study is concerned
with the simulations of the pressing section of a paper machine. A two-dimensional
model is developed to account for the water flow within the pressing zone. Richards’
type equation is used to describe the flow in the unsaturated zone. The dynamic capillary
pressure–saturation relation proposed by Hassanizadeh and co-workers (Hassanizadeh
et al., 2002; Hassanizadeh, Gray, 1990, 1993a) is adopted for the paper
production process.
The mathematical model accounts for the co-existence of saturated and unsaturated
zones in a multilayer computational domain. The discretization is performed
by the MPFA-O method. The numerical experiments are carried out for parameters
which are typical for the production process. The static and dynamic capillary
pressure–saturation relations are tested to evaluate the influence of the dynamic
capillary effect.
This work presents the dynamic capillary pressure model (Hassanizadeh, Gray, 1990, 1993a) adapted for the needs of paper manufacturing process simulations. The dynamic capillary pressure-saturation relation is included in a one-dimensional simulation model for the pressing section of a paper machine. The one-dimensional model is derived from a two-dimensional model by averaging with respect to the vertical direction. Then, the model is discretized by the finite volume method and solved by Newton’s method. The numerical experiments are carried out for parameters typical for the paper layer. The dynamic capillary pressure-saturation relation shows significant influence on the distribution of water pressure. The behaviour of the solution agrees with laboratory experiments (Beck, 1983).
A numerical upscaling approach, NU, for solving multiscale elliptic problems is discussed. The main components of this NU are: i) local solve of auxil- iary problems in grid blocks and formal upscaling of the obtained re sults to build a coarse scale equation; ii) global solve of the upscaled coarse scale equation; and iii) reconstruction of a fine scale solution by solving local block problems on a dual coarse grid. By its structure NU is similar to other methods for solving multiscale elliptic problems, such as the multiscale finite element method, the multiscale mixed finite element method, the numerical subgrid upscaling method, heterogeneous multiscale method, and the multiscale finite volume method. The difference with those methods is in the way the coarse scale equation is build and solved, and in the way the fine scale solution is reconstructed. Essential components of the presented here NU approach are the formal homogenization in the coarse blocks and the usage of so called multipoint flux approximation method, MPFA. Unlike the usual usage as MPFA as a discretiza- tion method for single scale elliptic problems with tensor discontinuous coefficients, we consider its usage as a part of a numerical upscaling approach. The main aim of this paper is to compare NU with the MsFEM. In particular, it is shown that the resonance effect, which limits the application of the Multiscale FEM, does not appear, or it is significantly relaxed, when the presented here numerical upscaling approach is applied.
Approximation property of multipoint flux approximation (MPFA) approach for elliptic equations with discontinuous full tensor coefficients is discussed here. Finite volume discretization of the above problem is presented in the case of jump discontinuities for the permeability tensor. First order approximation for the fluxes is proved. Results from numerical experiments are presented and discussed.
Calculating effective heat conductivity for a class of industrial problems is discussed. The considered composite materials are glass and metal foams, fibrous materials, and the like, used in isolation or in advanced heat exchangers. These materials are characterized by a very complex internal structure, by low volume fraction of the higher conductive material (glass or metal), and by a large volume fraction of the air. The homogenization theory (when applicable), allows to calculate the effective heat conductivity of composite media by postprocessing the solution of special cell problems for representative elementary volumes (REV). Different formulations of such cell problems are considered and compared here. Furthermore, the size of the REV is studied numerically for some typical materials. Fast algorithms for solving the cell problems for this class of problems, are presented and discussed.
A non-linear multigrid solver for incompressible Navier-Stokes equations, exploiting finite volume discretization of the equations, is extended by adaptive local refinement. The multigrid is the outer iterative cycle, while the SIMPLE algorithm is used as a smoothing procedure. Error indicators are used to define the refinement subdomain. A special implementation approach is used, which allows to perform unstructured local refinement in conjunction with the finite volume discretization. The multigrid - adaptive local refinement algorithm is tested on 2D Poisson equation and further is applied to a lid-driven flows in a cavity (2D and 3D case), comparing the results with bench-mark data. The software design principles of the solver are also discussed.
The desire to simulate more and more geometrical and physical features of technical structures and the availability of parallel computers and parallel numerical solvers which can exploit the power of these machines have lead to a steady increase in the number of grid elements used. Memory requirements and computational time are too large for usual serial PCs. An a priori partitioning algorithm for the parallel generation of 3D nonoverlapping compatible unstructured meshes based on a CAD surface description is presented in this paper. Emphasis is given to practical issues and implementation rather than to theoretical complexity. To achieve robustness of the algorithm with respect to the geometrical shape of the structure authors propose to have several or many but relatively simple algorithmic steps. The geometrical domain decomposition approach has been applied. It allows us to use classic 2D and 3D high-quality Delaunay mesh generators for independent and simultaneous volume meshing. Different aspects of load balancing methods are also explored in the paper. The MPI library and SPMD model are used for parallel grid generator implementation. Several 3D examples are shown.
An algorithm for automatic parallel generation of three-dimensional unstructured computational meshes based on geometrical domain decomposition is proposed in this paper. Software package build upon proposed algorithm is described. Several practical examples of mesh generation on multiprocessor computational systems are given. It is shown that developed parallel algorithm enables us to reduce mesh generation time significantly (dozens of times). Moreover, it easily produces meshes with number of elements of order 5 · 107, construction of those on a single CPU is problematic. Questions of time consumption, efficiency of computations and quality of generated meshes are also considered.
Inspired by Kirchhoff’s kinetic analogy, the special Cosserat theory of rods is formulatedin the language of Lagrangian mechanics. A static rod corresponds to an abstract Lagrangian system where the energy density takes the role of the Lagrangian function. The equilibrium equations are derived from a variational principle. Noether’s theorem relates their first integrals to frame-indifference, isotropy and uniformity. These properties can be formulated in terms of Lie group symmetries. The rotational degrees of freedom, present in the geometrically exact beam theory, are represented in terms of orthonormal director triads. To reduce the number of unknowns, Lagrange multipliers associated with the orthonormality constraints are eliminated using null-space matrices. This is done both in the continuous and in the discrete setting. The discrete equilibrium equations are used to compute discrete rod configurations, where different types of boundary conditions can be handled.
A theory of discrete Cosserat rods is formulated in the language of discrete Lagrangian mechanics. By exploiting Kirchho's kinetic analogy, the potential energy density of a rod is a function on the tangent bundle of the conguration manifold and thus formally corresponds to the Lagrangian function of a dynamical system. The equilibrium equations are derived from a variational principle using a formulation that involves null{space matrices. In this formulation, no Lagrange multipliers are necessary to enforce orthonormality of the directors. Noether's theorem relates rst integrals of the equilibrium equations to Lie group actions on the conguration bundle, so{called symmetries. The symmetries relevant for rod mechanics are frame{indierence, isotropy and uniformity. We show that a completely analogous and self{contained theory of discrete rods can be formulated in which the arc{length is a discrete variable ab initio. In this formulation, the potential energy density is dened directly on pairs of points along the arc{length of the rod, in analogy to Veselov's discrete reformulation of Lagrangian mechanics. A discrete version of Noether's theorem then identies exact rst integrals of the discrete equilibrium equations. These exact conservation properties confer the discrete solutions accuracy and robustness, as demonstrated by selected examples of application. Copyright c 2010 John Wiley & Sons, Ltd.
A general approach to the construction of discrete equilibrium dis- tributions is presented. Such distribution functions can be used to set up Kinetic Schemes as well as Lattice Boltzmann methods. The general principles are also applied to the construction of Chapman Enskog dis- tributions which are used in Kinetic Schemes for compressible Navier Stokes equations.
The relation between the Lattice Boltzmann Method, which has re- cently become popular, and the Kinetic Schemes, which are routinely used in Computational Fluid Dynamics, is explored. A new discrete velocity model for the numerical solution of Navier-Stokes equations for incom- pressible uid ow is presented by combining both the approaches. The new scheme can be interpreted as a pseudo-compressibility method and, for a particular choice of parameters, this interpretation carries over to the Lattice Boltzmann Method.
Territory design and districting may be viewed as the problem of grouping small geographic areas into larger geographic clusters called territories in such a way that the latter are acceptable according to relevant planning criteria. The availability of GIS on computers and the growing interest in Geo-Marketing leads to an increasing importance of this area. Despite the wide range of applications for territory design problems, when taking a closer look at the models proposed in the literature, a lot of similarities can be noticed. Indeed, the models are many times very similar and can often be, more or less directly, carried over to other applications. Therefore, our aim is to provide a generic application-independent model and present efficient solution techniques. We introduce a basic model that covers aspects common to most applications. Moreover, we present a method for solving the general model which is based on ideas from the field of computational geometry. Theoretical as well as computational results underlining the efficiency of the new approach will be given. Finally, we show how to extend the model and solution algorithm to make it applicable for a broader range of applications and how to integrate the presented techniques into a GIS.
Territory design may be viewed as the problem of grouping small geographic areas into larger geographic clusters called territories in such a way that the latter are acceptable according to relevant planning criteria. In this paper we review the existing literature for applications of territory design problems and solution approaches for solving these types of problems. After identifying features common to all applications we introduce a basic territory design model and present in detail two approaches for solving this model: a classical location–allocation approach combined with optimal split resolution techniques and a newly developed computational geometry based method. We present computational results indicating the efficiency and suitability of the latter method for solving large–scale practical problems in an interactive environment. Furthermore, we discuss extensions to the basic model and its integration into Geographic Information Systems.
In this paper we consider short term storage systems. We analyze presorting strategies to improve the effiency of these storage systems. The presorting task is called Batch PreSorting Problem (BPSP). The BPSP is a variation of an assigment problem, i.e., it has an assigment problem kernel and some additional constraints. We present different types of these presorting problems, introduce mathematical programming formulations and prove the NP-completeness for one type of the BPSP. Experiments are carried out in order to compare the different model formulations and to investigate the behavior of these models.