Geometric Modelling, Numerical Simulation, and Optimization

SINTEF is a contract research institute organized as a private non-profit foundation in Norway. For more than 50 years, SINTEF has performed basic and applied research in cooperation with Norwegian and international academic, industrial, and public partners. You are very welcome to learn more about the SINTEF group and our activities and aims at our home page http://www.sintef.no. SINTEF Applied Mathematics is a small, yet dynamic department within SINTEF. Currently we are about thirty full-time employees in addition to advisers, post docs, PhD students, and other affiliates.

The purpose of this tutorial paper is twofold. Firstly it can serve as an introduction to CAD shape modeling in general. Secondly it can be read as an introduction-by-example to the concept of an ontology. In computer science, an ontology is a rigorous conceptual model of a specific domain. Such models are useful in various contexts such as advanced information retrieval, knowledge sharing, web agents, natural language processing and simulation and modeling. There is an ongoing effort in the EU-funded Network of Excellence AIM@SHAPE to develop ontologies formalizing various aspects of digital shapes, by creating several domain-specific ontologies and by integrating them into a general common ontology. As a part of this effort, an ontology for CAD model information based on the STEP 42 standard has been proposed. This article presents the establishment of this particular ontology as an introductory example.

An approach for calculating intersections between parametric surfaces based on long experience in developing intersection algorithms for industrial use, is presented. In addition two novel methods that help improve quality and performance of intersection algorithms are described:

We discuss some challenges faced by neuroscientists with respect to 3D geometry reconstruction, modelling and visualization. We have developed a toolbox based on implicit representation of geometry, distributed computing and an easy to deploy and maintain graphical Java3D based interface. We describe the principles underlying this toolbox and provide an outline of the problems and suggested solutions related to a specific project, Neuroinf [18], which is a collaboration between research groups in biomedical science, informatics, and mathematics at the participating institutions. Public access to these tools will be announced on the web page.

Using graphics hardware for general-purpose computations (GPGPU) has for selected applications shown a performance increase of more than one order of magnitude compared to traditional CPU implementations. The intent of this paper is to give an introduction to the use of graphics hardware as a computational resource. Understanding the architecture of graphics hardware is essential to comprehend GPGPU-programming. This paper first addresses the fixed functionality graphics pipeline, and then explains the architecture and programming model of programmable graphics hardware. As the CPU is instruction driven, while a graphics processing unit (GPU) is data stream driven, a good CPU algorithm is not necessarily well suited for GPU implementation. We will illustrate this with some commonly used GPU algorithms. The paper winds up with examples of GPGPU-research at SINTEF within simulation, visualization, image processing, and geometry processing.

We demonstrate a ray tracing type technique for rendering algebraic surfaces using programmable graphics hardware (GPUs). Our approach allows for real-time exploration and manipulation of arbitrary real algebraic surfaces, with no pre-processing step, except that of a possible change of polynomial basis.

The algorithm is based on the blossoming principle of trivariate Bernstein-Bézier functions over a tetrahedron. By computing the blossom of the function describing the surface with respect to each ray, we obtain the coefficients of a univariate Bernstein polynomial, describing the surface’s value along each ray. We then use Bézier subdivision to find the first root of the curve along each ray to display the surface. These computations are performed in parallel for all rays and executed on a GPU.

The material contained here is to a large extent motivated by the so-called Draupner “New Year Wave”, an extreme wave event that was recorded at the Draupner E platform in the central North Sea on January 1st 1995 [4], [5]. This location has an essentially uniform depth of 70 m. The platform is of jacket type and is not expected to modify the wave field in any significant way. The platform had been given a foundation of a novel type, and for this reason was instrumented with a large number of sensors measuring environmental data, structural and foundation response. We are particularly interested in measurements taken by a down looking laser-based wave sensor, recording surface elevation at a speed of 2.1333 Hz during 20 minutes of every hour. The full 20 minute time series recorded starting at 1520 GMT is shown in Figure 1 and a close-up of the extreme wave event is shown in Figure 2. To remove any doubt that the measurements are of good quality, Figure 3 shows an even finer close-up with the individual measurements indicated. It is clear that the extreme wave is not an isolated erroneous measurement. The minimum distance between the sensor and the water surface was 7.4 m.

The paper has two main themes: The first theme is to give the reader an introduction to modern methods for systems of conservation laws. To this end, we start by introducing two classical schemes, the Lax-Friedrichs scheme and the Lax-Wendroff scheme. Using a simple example, we show how these two schemes fail to give accurate approximations to solutions containing discontinuities. We then introduce a general class of semi-discrete finite-volume schemes that are designed to produce accurate resolution of both smooth and nonsmooth parts of the solution. Using this special class we wish to introduce the reader to the basic principles used to design modern high-resolution schemes. As examples of systems of conservation laws, we consider the shallow-water equations for water waves and the Euler equations for the dynamics of an ideal gas.

The second theme in the paper is how programmable graphics processor units (GPUs or graphics cards) can be used to efficiently compute numerical solutions of these systems. In contrast to instruction driven micro-processors (CPUs), GPUs subscribe to the data-stream-based computing paradigm and have been optimised for high throughput of large data streams. Most modern numerical methods for hyperbolic conservation laws are explicit schemes defined over a grid, in which the unknowns at each grid point or in each grid cell can be updated independently of the others. Therefore such methods are particularly attractive for implementation using data-stream-based processing.

Even though the art of reservoir simulation has evolved through more than four decades, there is still a substantial research activity that aims toward faster, more robust, and more accurate reservoir simulators. Here we attempt to give the reader an introduction to the mathematics and the numerics behind reservoir simulation. We assume that the reader has a basic mathematical background at the undergraduate level and is acquainted with numerical methods, but no prior knowledge of the mathematics or physics that govern the reservoir flow process is needed. To give the reader an intuitive understanding of the equations that model filtration through porous media, we start with incompressible single-phase flow and move step-by-step to the black-oil model and compressible two-phase flow. For each case, we present a basic numerical scheme in detail, before we discuss a few alternative schemes that reflect trends in state-of-the-art reservoir simulation. Two and three-dimensional test cases are presented and discussed. Finally, for the most basic methods we include simple Matlab codes so that the reader can easily implement and become familiar with the basics of reservoir simulation.

Flow in petroleum reservoirs occurs on a wide variety of physical scales. This poses a continuing challenge to modelling and simulation of reservoirs since fine-scale effects often have a profound impact on flow patterns on larger scales. Resolving all pertinent scales and their interaction is therefore imperative to give reliable qualitative and quantitative simulation results. To overcome the problem of multiple scales it is customary to use some kind of upscaling or homogenisation procedure, in which the reservoir properties are represented by some kind of averaged properties and the flow is solved on a coarse grid. Unfortunately, most upscaling techniques give reliable results only for a limited range of flow scenarios. Increased demands for reservoir simulation studies have therefore led researchers to develop more rigorous multiscale methods that incorporate subscale effects more directly.

In the first part of the paper, we give an overview of some of the many scales that are considered important for flow simulations. Next, we present and discuss several upscaling approaches that have played a role in the history of reservoir simulation. In the final part, we present some more recent approaches for modelling scales in the flow simulations based upon the multiscale paradigm. We conclude with a discussion of benefits and disadvantages of using multiscale methods, rather than using traditional upscaling techniques, in reservoir simulation.

In the present chapter a short review is given of the mathematical formulation relevant for geophysical flow modelling, and in addition computational examples are shown for some specific flow cases. These examples are described in some detail in order to illustrate useful methods to handle such problems in practice. The emphasis is on more local geophysical flows, including stratified flow over variable topography.

Solving the Vehicle Routing Problem (VRP) is a key to efficiency in transportation and supply chain management. The VRP is an NP-hard problem that comes in many guises. The VRP literature contains thousands of papers, and VRP research is regarded as one of the great successes of OR. Vehicle routing decision support tools provide substantial savings in society every day, and an industry of routing tool vendors has emerged. Exact methods of today cannot consistently solve VRP instances with more than 50–100 customers in reasonable time, which is generally a small number in real-life applications. For industrial problem sizes, and if one aims at solving a variety of VRP variants, approximation methods is the only viable approach. There is still a need for VRP research, particularly for large-scale instances and complex, rich VRP variants. In this chapter, we give a brief general introduction to the VRP. We then describe how industrial requirements motivate extensions to the basic, rather idealized VRP models that have received most attention in the research community, and how such extensions can be made. At SINTEF Applied Mathematics, industrial variants of the VRP have been studied since 1995. Our efforts have led to the development of a generic VRP solver that has been commercialized through a spin-off company. We give a description of the underlying, rich VRP model and the selected uniform algorithmic approach, which is based on metaheuristics. Finally, results from computational experiments are presented. In conclusion, we point to important issues in further VRP research.

The Long-Term Forest Treatment Scheduling Problem (LTFTSP) is the task of allocating treatments in a forest such that both sustainability and economic outcome is maximized. Solving such problems is demanded in more and more countries and the task is increasingly more complex because one must adhere to local legislation, environmental issues, and public interests. To be able to handle most aspects of the LTFTSP with adjacency constraints (which is the problem we solve), a rich, spatial model which is parameterized, is required. We present a model defined on discrete land units and time points, where the treatments to perform are parameterized. Many of the most commonly used criteria in the form of constraints and objective components in long-term forestry scheduling are included. Such criteria may be defined for the complete forest region in question, or for specific sub-regions.

The complexity of the model requires a robust solution method. We have selected a heuristic approach based on Tabu Search. An initial solution is constructed by composition of economically optimal schedules for each land unit. This solution is made feasible by a greedy heuristic. The initial solution is iteratively improved by Tabu Search. Two different types of move are used in the Tabu Search procedure: Shifting a treatment to another time point, and exchanging one treatment program for another treatment program.

The solution method is implemented in the software tool Ecoplan. Empirical results have been produced for a 1,541 stand case from Norway. The results show that when more than one objective is included in the objective function, the quality of the solution with respect to the individual objectives may be considerably reduced. Some of the quality loss, especially with regards to the “old forest” objective component may be explained by the initial state of the forest.

This paper discusses segmentation and reconstruction problems using a integer linear programming approach. These problems have important applications in remote sensing, medical image analysis and industrial inspection. We focus on methods that produce optimal or near-optimal solutions for the corresponding optimization problems. We show that for the two problems one may use similar ideas in both modeling and solution methods. These methods are based on Lagrangian decomposition and dynamic programming for certain subproblems (associated with lines in the image). Some computational experiences are also reported.

During the last half decade, the metal industry has been in a harsh situation seeing their profit margins squeezed to an extreme. Many companies have been forced to close down furnaces and plants. To help a major metal producing company manage this process, we developed a strategic mixed integer programming model. The main decisions addressed by the model involve the future plant structure and production capacities, the production portfolio at each plant and the by-product production. Here, we present the underlying MIP-model and give computational results. In addition, we show how the valuable by-product production can have impact on the optimal supply chain design.

In this paper we give an introduction to modelling the natural gas value chain including production, transportation, processing, contracts, and markets. The presentation gives insight in the complexity of planning in the natural gas supply chain and how optimization can help decision makers in a natural gas company coordinate the different activities. We present an integrated view from the perspective of an upstream company. The paper starts with decribing how to model natural gas transportation and storage, and at the end we present a stochastic portfolio optimization model for the natural gas value chain in a liberalized market.