Skip to main content
main-content

Über dieses Buch

The NATO Advanced Research Workshop (ARW) "Algorithms and Model Formulations in Mathematical Programming" was held at Chr. Michelsen Institute in Bergen, Norway, from June 15 to June 19, 1987. The ARW was organized on behalf of the Committee on Algorithms (COAL) of the Mathematical Programming Society (MPS). Co-directors were Jan Telgen (Van Dien+Co Organisatie, Utrecht, The Netherlands) and Roger J-B Wets (The University of California at Davis, USA). 43 participants from 11 countries attended the ARW. The workshop was organized such that each day started with a - minute keynote presentation, followed by a 45-minute plenary discussion. The first part of this book contains the contributions of the five keynote speakers. The plenary discussions were taped, and the transcripts given to the keynote speakers. They have treated the transcripts differently, some by working the discussions into their papers, others by adding a section which sums up the discussions. The plenary discussions were very interesting and stimulating due to active participation of the audience. The five keynote speakers were asked to view the topic of the workshop, the interaction between algorithms and model formulations, from different perspectives. On the first day of the workshop Professor Alexander H.G. Rinnooy Kan (Erasmus University, Rotterdam, The Netherlands) put the theme into a larger context by his talk "Mathematical programming as an intellectual activity". This is an article of importance to any mathematical programmer who is interested in his field's history and present state.

Inhaltsverzeichnis

Frontmatter

Modeling and Strong Linear Programs for Mixed Integer Programmings

Modeling and Strong Linear Programs for Mixed Integer Programming

Mixed integer programming modeling is considered from two points of view: getting the model correctly generated in an understandable form, and formulating or reformulating the model so that the problem can be solved. For the former considerations, a relational approach is presented. For the latter, three techniques are discussed: preprocessing, constraint generation, and column generation. For all three techniques, mixed integer problems are considered. For column generation, two problem classes (cutting stock and crew scheduling) for which column generation techniques are classical, are presented in a unified framework and then clustering problems are discussed in the same framework. In the constraint generation section, some constraints based on mixed 0–1 implication graphs are presented.

Ellis L. Johnson

Advances in Nonlinear Network Models and Algorithms

Advances in Nonlinear Network Models and Algorithms

Network models with nonlinear objectives occur in numerous economic, engineering and management applications. These areas are described, along with highly specialized nonlinear programming algorithms for solving the resulting large-scale problems. It is shown that nonlinear network models can be handled efficiently using serial or vector processing computers. Extensions to stochastic programs are discussed.

John M. Mulvey

Mathematical Programming as an Intellectual Activity

Mathematical Programming as an Intellectual Activity

For every scientific discipline, a process of reappraisal and evaluation of the discipline as a whole forms a natural topic for informal discussion among scientists. These discussions — typically held between lectures or after dinner — might focus on the promise held out by a new development, on the tenacity of certain venerable subareas within the discipline or on the growth (or decline) of prominent research groups. In every case, the discussion is part of a natural mechanism through which a scientific community strives for some consensus on what the state of the discipline is and where it might be heading next.

A. H. G. Rinnooy Kan

The Aggregation Principle in Scenario Analysis and Stochastic Optimization

The Aggregation Principle in Scenario Analysis and Stochastic Optimization

Most systems that need to be controlled or analyzed involve some level of uncertainty about the value to assign to some of the parameters, if not about the actual layout of certain subcomponents of the system. In many situations not much is lost by assigning “reasonable” values to these parameters or by choosing a particular design. In other instances ignoring uncertainty may very well lead to totally misleading solutions that would invalidate any of the implications one may wish to draw from the analysis.

Roger J-B Wets

Methods for Large-Scale Linear Programming

Methods for Large-Scale Linear Programming

The problem we shall address is how to solve the linear programming problem, as stated in the following standard form: where A is an m x n matrix (m < n). The equation Ax = b describes the general constraints, and the inequalities x > 0 are called bound constraints. The essential aim is to find which of the bounds are binding at a solution—i.e., which variables x j are exactly zero.

Walter Murray

Extended Abstracts

Frontmatter

Resource Constrained Assignment Problems

In many applications it is necessary to find a minimum weight assignment that satisfies one or several additional resource constraints. For example, consider the problem of assigning persons to jobs where each assignment utilizes at least two scarce resources and the resource utilization is dependent on the person and the type of task. A practical situation where the above might occur is a slaughter house where the “cutters” are assigned to different cut patterns. In this case the resources are the time, the cost and the productivity measured in terms of quality and amount of the end products.

Ronny Aboudi, Kurt Jörnsten

The Resource Constrained Spanning Tree Problem: Alternative Modelling and Algorithmic Approaches

The problem of determining a minimal spanning tree subject to side constraints, arises frequently as a subproblem of the general network design problem, specially in the design of computer communication networks and pipeline systems.

Jaime Barceló, Kurt Jörnsten, Sakis Migdalas

Constructive Dual Methods for Non-Linear Discrete Programing Problems

Recently a constructive duality theory for integer linear programming has been suggested, Bárcia (1985) and (1986). In this paper we generalize the previous theory for the case of non-linear discrete programming and present an algorithm for the case of quadratic 0-1 problems.

P. Bárcia, J. D. Coelho

A Decomposition Based Procedure for Production Scheduling in Job-Shops with Negligible Setup Times

In short term planning of production in a discrete parts manufacturing system, a major problem is to decide on the maximum number of prespecified items that can be produced with limited shared resources, when all the items have a demand dependence in the form of bill-of- materials. The inventory carrying costs and the variation in the unit production costs from period to period become relatively unimportant in case of short planning horizons (such as one month, with periods taken to be one shift). When the total number of interacting items (such as raw materials, semifinished parts, subassemblies, finished goods, etc. ) is in the order of thousands, with considerable number of shared resources (such as machines, work centres, etc. ), the resulting model has a very large number of constraints and variables. Inclusion of the setup costs (or setup times), because of the introduced nonconvexity, makes the solution of the mathematical program infeasible from practical and computational viewpoint for short term planning purposes. Even the exclusion of the setup costs results in a large scale linear program.

Öner S. Benli

An Example of a Declarative Approach to Model Creation

Model creation tools are often closely coupled to the target mathematical structures. In the case of constrained optimisation, model creation is normally via the concepts of matrix or linear algebra, and thus perhaps only indirectly related to the objects and concepts of the problem domain. A translation from problem structure to mathematical structure is necessary.

Iain Buchanan, K. I. M. McKinnon

Optimal Solution of the Local Delivery Problem Through Minimum K-Trees

The local delivery problem has been extensively studied and is a classic in the field of vehicle routing and scheduling. This talk will describe a recently developed optimization algorithm for this problem which exploits a connection between the local delivery problem and minimum K-trees. I will first set the stage for this discussion by reviewing the enormous activity in the vehicle routing area that has occured during the last decade in both academia and industry. I will focus in particular on projects in which I have been involved at Air Products and Chemicals, DuPont and Exxon that produced implemented routing models and algorithms with significant economic benefits. Altough all of these algorithms are heuristics (as has been the focus of almost all past research in this area), I will indicate why the time is now ripe to consider optimization approaches.

Marshall L. Fisher

AMPL: A Mathematical Programing Language

Practical large-scale mathematical programming involves more than just the minimization or maximization of an objective function subject to constraint equations and inequalities. Considerable effort must be expended to correctly formulate the underlying model, and to generate the data structures required by an optimizing algorithm.

Robert Fourer, David M. Gay, Brian W. Kernighan

Multiperiod Linear Stochastic Programming and a Forestry Application

A new algorithm is given to solve the multiperiod stochastic linear programming problem

Gus Gassmann

A Multi-Period Network Design Problem: Model and Solution Techniques

We give a brief description of a part of a project initiated in the spring of 1985 at the Chr. Michelsen Institute. The aim was to develop a long term planning model for the sequencing of petroleum production activities on the Norwegian shelf. The emphasis of the model is on the development of transport systems for petroleum products from the producing fields to gas customers and oil terminals onshore.

Åsa Hallefjord

Finite-Dimensional Variational and Quasivariational Inequalities: Algorithmic Developments and Applications in Socio-Eoonomic Planning

Over the past several years the f inite-dimensional variational inequality problem has been well studied from the perspectives of computation, sensitivity analysis and application. This paper will briefly review the variational inequality literature and will also discuss the finite dimensional quasivariational inequality problem from the above mentioned perspectives. In particular, three recent results will be discussed in detail. First, an acceleration step for the nonlinear Jacobi and projection algorithms will be presented along with empirical results. Second, a special case of the quasivariational inequality problem which arises in pseudo-Nash or social equilibria games is studied in detail. Characterizations of the solutions of such problems and their relationships with variational inequality solution are presented along with some results on the stability and sensitivity of these solutions. Finally, the theory and empirical validation of a restricted simplicial decomposition algorithm for large-scale, linearly-constrained variational inequalities will be described.

Patrick T. Harker

Stochastic Equilibrium Programming for Dynamic Oligopolistic Markets

The aim of this paper is to clarify the relationship between the stochastic programming and dynamic programming approaches for the modelling of dynamic equilibria in a class of uncertain systems.

A. Haurie, Y. Smeers, G. Zaccour

A Dynamic Approach to Oligopolistic Market Equilibrium

We provide an algorithm for computing Cournot-Nash equilibria in multi-commodity markets involving finitely many producers. The algorithm amounts to follow a certain dynamical system all the way to its steady state which happens to be a non-cooperative equilibrium. The dynamics arise quite naturally as follows: Let each producer continuously adjust his planned production, if desired, as a response to the current aggregate supply. In doing so he is completely guided by myopic profit considerations. We show, under broad hypothesis on the market structure, that this adjustment process is globally, asymptotically convergent to a Nash equilibrium.

Adi Ben-Israel, Sjur D. Flåm

Estimated Parameters in Mathematical Programming: Modelling and Statistical Issues

Frequently it happens that the parameters needed to define a mathematical program are not precisely known, but can be estimated by sampling or derived from historical data. To be honest, the modeller should treat such parameters as uncertain. This is simple to state but raises profound modelling, algorithmic and analytical issues.

Alan J. King

Modelling for Parallel Optimization

As a result of the development of both research and commercial multiprocessors and multi-computers capable of implementing parallel algorithms for optimization, there has been a renewed interest in both theoretical and computational aspects of such techniques. From a modelling viewpoint, it becomes important to formulate the problem in such a manner that it can be decomposed into quasi-independent subproblems that are suited to the computer architecture on which it will be solved. One key issue in this regard is the granularity of the computation, i.e. the sizes of the ‘pieces’ that will be dealt with in parallel. For example, in a traffic assignment problem, one has the option of defining commodities (and hence subproblems) by origin-destination pair og by origin. The latter approach is less traditional, but gives rise to larger sub-problems that are better suited to a computing environment in which communication between processors is relatively expensive. Thus, one method of dealing with granularity is to seek to modify an existing model in such a way as to facilitate the decomposition of the problem into subproblems of appropriate size. A related issue is whether one will initialize the decomposition process by using intrinsic structures available a priori from the model (such as commodities or time periods) or exploit the previous solution of a related problem (which may, for example, allow a tentative geographic decomposition of the area covered by the model), or employ a heuristic splitting procedure based on the current problem data and then dynamically modify the structure of the decomposition as needed during the course of the solution process. It is clear that in order to reduce the amount of information exchange and to accelerate the solution process, it is desirable to partition the model in a manner that is suited to the machine architecture and reflects as much as possible a partition related to an optimal solution. These topics will be addressed in the context of research on large-scale nonlinear and generalized networks. We will describe computational experience with two parallel computing systems at the Computer Sciences Department of the University of Wisconsin: the CRYSTAL multicomputer, a loosely-coupled token-ring network of 20 VAX 11/750’s, and the Sequent Balance 21000, a commercial shared-memory multiprocessor with 8 processors.

Robert R. Meyer

Long-Term Hydro-Thermal Coordination of Electricity Generation Through Multicommodity Network Flows

Besides classical methods, such as dynamic programming, network flow techniques have been extensively used to solve the problem of short term hydro-thermal coordination of electricity generation. Nonlinear flows in a replicated network, can adequately model the hydraulic generation of a system of reservoirs, which complements thermal generations in satisfying known forecasts of each hourly demand. Side constraints or penalty functions must be used, at each time interval, to prevent excessive or insufficient hydro-power generation.

Narcis Nabona

Equilibration Operators for the Solution of Constrained Matrix Problem

The problem of determining a set of coefficients of a matrix which collectively satisfy certain constraints has become known as the constraively Matrix Problem. It has been widely studied because of its frequent appearance as a “core” problem in diverse applications. These include estimation of input-output tables in the regional sciences, of contingency tables in statistics, origin-destination flows in traffic analysis, and social -national accounts in economics.

A. Nagurney, A. G. Robinson

A General Dynamic Network Spatial Price Equilibrium Model with Gains and Losses

The spatial price equilibrium models of Samuelson, and Takayama and Judge have provided the basic framework for the study of a variety of applications in the fields of agriculture, regional science, and energy markets. The central issue in such studies is the computation of the equilibrium regional production, consumption, and interregional commodity flow patterns.

Anna Nagurney

Incorporating the Concept of Internal Rate of Return in Linear and Integer Programming Models

The use of an internal rate of return (IRR) measure is cammon in financial problems. Over the past decade the measure has been enjoying an increased usage in the new municipal debt issue market. Nauss (Management Science, July 1986) developed a procedure to minimize the IRR for competitive bids for new issues of municipal debt. While this problem was generally viewed as being a nonlinear integer program, it was shown that the problem could be linearized so that an integer linear program resulted. The linearization is possible because there is only one change in the sign of the cash flows over time. This assures that only one real root for the IRR exists. A special purpose branch and bound algorithm was developed to solve the problem in a matter of seconds so that it could be used in actual applications.

Robert M. Nauss

Procedures for Solving Bottleneck Generalized Assignment Problems

We discuss bottleneck (or minimax) versions of the generalized assignment problem. The basic problem involves the assignment of a number of jobs to a number of agents such that each job is performed by a unique agent, and capacity limitations on the agents are not exceeded. Two versions of the bottleneck generalized problem (BGAP) are defined. The first of these is called the Task BGAP and has as its objective the minimization of the maximum of the costs of the assignments that are made. The second version is referred to as the Agent BGAP and has as its objective the minimization of the maximum of the total costs assigned to each agent.

Alan W. Neebe, Joseph B. Mazzola

Weighted Matching in Chess Tournaments

In many chess tournaments the number of players is much larger than the number of rounds to be played. In such tournaments the pairing for a round depends on the results in earlier rounds. Many different systems have been constructed for these pairings. Two oommonly used systems are the Monrad system and the Swiss system though there exist a number of different variants of these two systems.

Snjólfur Olafsson

Decentralized Optimization for Structured Linear Programming Models

This paper deals with methods for solving linear programming models with a primal or dual block-angular structure. A more general exposition of these methods can be found in [1]. For a primal block- angular structure the method is called the dual basis decomposition method.

Cornelis van de Panne

Transport Planning in Airborne Operations

One of the most complex problems in military planning is that of transport in tactical airborne operations. It differs from transportation problems in several important aspects: it is time- dependent; it is multi-cxxnmodity with interrelations among commodities; it is capacity-constrained in a complicated manner; and, above all; it incorporates some severe military-tactical constraints. Some of these features can be found in scheduling problems, but even when viewed this way the planning process is very complex.

Adir Pridor

A Hierarchical Approach to the Placement Problem

This paper concerns the problem of placing components on a circuit board, in such a way that a predefined set of objectives is optimized. The layout of integrated circuits motivated the use of hierarchical techniques as a means of dealing with increasing circuit complexity. A fully hierarchical approach to the placement problem is here described, based on a tree structure which embodies an adopted set of circuit properties and objective functions. The tree structure represents the relative positions of a hierarchy of blocks of components on the board surface.

Maria Rosália Dinis Rodrigues

Optimisation of Oil Depletion Strategy to Satisfy Long-Term Objectives

The problem of deterrnining how fast to extract oil from oil fields is a complicated one involving reservoir engineering, economic and political factors. Reservoir engineering simulations can be used to determine good ways of extracting the oil but they cannot do more than evaluate the economic consequences. By contrast, conventional MP models are unable to represent the behaviour of the oil reservoirs sufficiently accurately to be credible. A technique is presented for combining the accuracy of reservoir engineering simulations and the optimisation of the MP approach within the framework of a MP model.

R. V. Simons

Approaches to Optimizing Fuel Consumption in Cars

One of the most important problems which the automotive industry faces is that of reducing fuel consumption, in view of the increasing cost of energy and the need to save oil for more sophisticated uses, while keeping pollutants emissions as low as possible, in view of the resulting health and environmental problems. Reduction of fuel consumption can be obtained working on different features of the car, including type of engine, aerodynamical design, used materials and optimal operations of the engine. In this work we shall be concerned with the last approach, which can result in a 5-20% saving on fuel, depending on which parameters are optimized. Mathematically, the problem can be formulated as follows: let s(t) be the value of a vector of state parameters (typically speed and power) at time t; then one has to choose optimal values of control parameters u(t), typically spark advance angle, air-fuel ratio and possibly transmission ratio, in such a way that the total fuel consumption on a certain cycle (EPA or European cycle) be minimized subject to constraints, of legal type, on the total amount of certain emitted pollutants (typically co, NOx HC) during the cycle and of course to drivebility constraints. The resulting problem is formally an optimal control problem, which is in practice discretized and thus reduced to a mathematical programming problem, of the nonlinear type and of moderately large dimensions (the number of independent variables is in practice about fifty, with about twice that number of constraints).

Emilio Spedicato

Equilibrium Definitions in Simulated Annealing: A Computational Experiment

Recently simulated annealing, a probabilistic heuristic motivated by an analogy between statistical mechanics and combinatorial optimization, has been used to obtain good solutions to various combinatorial problems. The method minimizes a function f(s) whose arguments are the elements of a finite set S of feasible configurations (or solutions when applied to a combinatorial optimization problem) by a sequence of actions called local exchanges. All exchanges which improve f are accepted where as exchanges which increase f are accepted with a probability depending on a parameter called the temperature. At a given temperature level, a sequence of local exchanges, the so called inner loop iterations, are executed until the system reaches an equilibrium. The number of temperature levels and the way the temperature is lowered is called the annealing schedule.

Karl Spälti

Decomposition in Integer Programming

The objective is to discuss the constnjction of models for multilevel structures with the additional inclusion of integrality constraints.

Jørgen Tind

Computational Geometry and Low Dimensional Linear Programs

Many areas (robotics, pattern recognition, computer graphics etc. ) offer problems requiring efficient computation of elementary planar geometric objects, e.g. the convex hull of a set, the intersectionof a line and a convex polytcpe, the distance between two line segments. Computational geometry, applying computer science methodology to such geometrical problems (see e.g. [3], [4]), has provided important algorithms and complexity results, typically under specific assumptions on the data structure.

Henry Wolkowicz, Adi Ben-Israel

Backmatter

Weitere Informationen