Twenty-five years of applied mathematical programming and modelling

Computational Management Science -     

Nonnormal deterministic equivalents and a transformation in stochastic mathematical programming

This paper considers random variables of the continuous type in a stochastic programming problem and presents (1) a general approach to the development of deterministic equivalents of constraints to be satisfied within certain probability limits, and (2) a deterministic transformation of a stochastic programming problem with random variables in the objective function. Deterministic equivalents are developed for constraints containing uniform random variables, but the approach used can be applied to other types of continuous random variables, as well. When the random variables appear in the objective function, a deterministic transformation of the stochastic programming problem is obtained to yield a closed-form solution without resort to a Monte Carlo computer simulation. Extension of this approach to stochastic problems with discrete random variables and integer decision variables is discussed briefly. A numerical example is presented.     

A decomposition-based crash-start for stochastic programming

In this paper we propose a crash-start technique for interior point methods applicable to multi-stage stochastic programming problems. The main idea is to generate an initial point for the interior point solver by decomposing the barrier problem associated with the deterministic equivalent at the second stage and using a concatenation of the solutions of the subproblems as a warm-starting point for the complete instance. We analyse this scheme and produce theoretical conditions under which the warm-start iterate is successful. We describe the implementation within the OOPS solver and the results of the numerical tests we performed.     

A language for nonlinear programming problems

An algebraic-like language for nonlinear programming problems is described. The rationale for the computation of the function values, gradients, and scond partial derivatives of the functions from their algebraic representation is developed. Each function is translated into an explicit factorable form or hierarchical representation which is used interpretively to compute the function value, gradient, and second partials of the function at each point for which such values are required. Computational efficiency is achieved by computing the matrix of second partials as the sum of a set of vector outer products, the vectors having resulted from the gradient computation, plus a diagonal matrix. An experimental computer program which implements the language and ties it to SUMT is described. In the experience with this program the computer times required have ranged from 4 to 30 times those times required by computer solutions to the same problems by using analyst-prepared programs to compute the function values, gradients, and second partial derivatives. A program based on a compiler approach to implementing the language, rather than the interpretative approach of the experimental program, will probably result in computer times between one and two times those required by using analyst-prepared programs.     

Use of stochastic and mathematical programming in?portfolio theory and practice

Standard finance portfolio theory draws graphs and writes equations usually with no constraints and frequently in the univariate case. However, in reality, there are multivariate random variables and multivariate asset weights to determine with constraints. Also there are the effects of transaction costs on asset prices in the theory and calculation of optimal portfolios in the static and dynamic cases. There we use various stochastic programming, linear complementary, quadratic programming and nonlinear programming problems. This paper begins with the simplest problems and builds the theory to the more complex cases and then applies it to real financial asset allocation problems, hedge funds and professional racetrack betting. This paper is based on a keynote lecture at the APMOD conference in Madrid in June 2006. It was also presented at the London Business School. Many thanks are due to APMOD organizers Antonio Alonso-Ayuso, Laureano Escudero, and Andres Ramos for inviting me and for excellent hospitality in Madrid. Thanks are also due to my teachers at Berkeley who got me on the right track on stochastic and mathematical programming, especially Olvi Mangasarian, Roger Wets and Willard Zangwill, and my colleagues and co-authors on portfolio theory in finance and horseracing, especially Chanaka Edirishinge, Donald Hausch, Jarl Kallberg, Victor Lo, Leonard MacLean, Raymond Vickson and Yonggan Zhao.     

A mathematical framework for stochastic climate models

There has been a recent burst of activity in the atmosphere‐ocean sciences community in utilizing stable linear Langevin stochastic models for the unresolved degrees of freedom in stochastic climate prediction. Here a systematic mathematical strategy for stochastic climate modeling is developed, and some of the new phenomena in the resulting equations for the climate variables alone are explored. The new phenomena include the emergence of both unstable linear Langevin stochastic models for the climate mean variables and the need to incorporate both suitable nonlinear effects and multiplicative noise in stochastic models under appropriate circumstances. All of these phenomena are derived from a systematic self‐consistent mathematical framework for eliminating the unresolved stochastic modes that is mathematically rigorous in a suitable asymptotic limit. The theory is illustrated for general quadratically nonlinear equations where the explicit nature of the stochastic climate modeling procedure can be elucidated. The feasibility of the approach is demonstrated for the truncated equations for barotropic flow with topography. Explicit concrete examples with the new phenomena are presented for the stochastically forced three‐mode interaction equations. The conjecture of Smith and Waleffe [Phys. Fluids 11 (1999), 1608–1622] for stochastically forced three‐wave resonant equations in a suitable regime of damping and forcing is solved as a byproduct of the approach. Examples of idealized climate models arising from the highly inhomogeneous equilibrium statistical mechanics for geophysical flows are also utilized to demonstrate self‐consistency of the mathematical approach with the predictions of equilibrium statistical mechanics. In particular, for these examples, the reduced stochastic modeling procedure for the climate variables alone is designed to reproduce both the climate mean and the energy spectrum of the climate variables. © 2001 John Wiley & Sons, Inc.     

A management system for decompositions in stochastic programming

This paper presents two contributions: A set of routines that manipulate instances of stochastic programming problems in order to make them more amenable for different solution approaches; and a development environment where these routines can be accessed and in which the modeler can examine aspects of the problem structure. The goal of the research is to reduce the amount of work, time, and cost involved in experimenting with different solution methods.     

A stochastic programming model for aggregate production planning

This paper looks at a problem of production planning at the level of the work centre, rather than of the individual machine. The approach is based on methodology which combines aspects of decision analysis with mathematical programming procedures.A model is developed which can take into account various real life factors in the planning phase, including delaying production, and the probability of production being scrapped, or of extra work being required. An extension to the multiple objective situation is outlined, and some computational results are reported.     

A stochastic programming model for water resource planning

A framework is offered for the evaluation of electricity generation and water supply for agricultural irrigation. This assessment is conducted through the construction of an appropriate stochastic optimization model. A recursive least squares algorithm is incorporated in the model which enables more accurate estimation of model parameters.     

A stochastic programming approach for multi-period portfolio optimization

This paper extends previous work on the use of stochastic linear programming to solve life-cycle investment problems. We combine the feature of asset return predictability with practically relevant constraints arising in a life-cycle investment context. The objective is to maximize the expected utility of consumption over the lifetime and of bequest at the time of death of the investor. Asset returns and state variables follow a first-order vector auto-regression and the associated uncertainty is described by discrete scenario trees. To deal with the long time intervals involved in life-cycle problems we consider a few short-term decisions (to exploit any short-term return predictability), and incorporate a closed-form solution for the long, subsequent steady-state period to account for end effects.     

A weak duality theorem for stochastic linear programming

Summary A linear programming problem is said to be stochastic if one or more of the coefficients in the objective function or the system of constraints or resource availabilities is known only by its probability distribution. A distinction is usually made between two related approaches to stochastic linear programming, the active and passive approach respectively. An extension of the duality theorem of non-stochastic or deterministic programming problem has been attempted in this paper in the area of stochastic linear programming in its two approaches. The method of proof is based on the idea that since the parameter space defined by a stochastic linear programme is the topological product of the real line with itself, it forms a first countable topological space. Using a set of distinct and selected points in the parameter space the concepts of feasibility, optimality and duality are extended to stochastic linear programming problems of arbitrary dimensionality. Based on the non-singular regions of the parameter space of a stochastic linear programming problem the theorem utilizes the conditions of convergence of the sequence of distinct and selected points in the parameter space to a limit point and thereby generalizes the duality theorem in the stochastic case. Furthermore it is shown that the regions of feasibility of the active and passive approaches of stochastic linear programming may be different, so that on this basis it may be possible to establish some inequality relations for the optimal solutions defined for the respective feasible regions.

---

Zusammenfassung Ein lineares Programmproblem wird stochastisch genannt, wenn ein oder mehrere Koeffizienten der Zielfunktion oder des Systems der Beschränkungen oder der verfügbaren Ressourcen nur durch ihre Wahrscheinlichkeitsverteilung bekannt sind. Gewöhnlich wird zwischen zwei verwandten Verfahren für das stochastische lineare Programmieren unterschieden, dem aktiven und dem passiven Verfahren.In der vorliegenden Arbeit wird versucht, das für nichtstochastische oder deterministische Programmprobleme gültige Dualitätstheorem unter Berücksichtigung beider Verfahrensweisen auf den Bereich des stochastischen linearen Programmierens auszudehnen. Der Beweis gründet sich auf den Gedanken, daß der Parameterraum einen abzählbaren topologischen Raum bildet, da er — durch ein stochastisches lineares Programm definiert — das topologische Produkt der reellen Achse mit sich selbst ist. Unter Benutzung einer Menge von verschiedenen und ausgewählten Punkten im Parameterraum werden die Begriffe der Zulässigkeit, der Optimalität und der Dualität auf stochastische lineare Programmprobleme beliebiger Dimension ausgedehnt. Auf der Grundlage nichtsingulärer Bereiche des Parameterraumes eines stochastischen linearen Programmproblems benutzt das Theorem die Bedingungen für die Konvergenz einer Folge verschiedener und ausgewählter Punkte des Parameterraumes nach einem Grenzpunkt und verallmeinert damit das Dualitätstheorem für den stochastischen Fall. Weiter wird gezeigt, daß die Zulässigkeitsbereiche der aktiven und passiven Verfahren des stochastischen linearen Programmierens verschieden sein können, so daß es möglich sein kann, gewisse Ungleichungen für die optimalen Lösungen aufzustellen, die für die entsprechenden zulässigen Bereiche definiert sind.

     

A core language for fuzzy answer set programming

A number of different Fuzzy Answer Set Programming (FASP) formalisms have been proposed in the last years, which all differ in the language extensions they support. In this paper we investigate the expressivity of these frameworks. Specifically we show how a variety of constructs in these languages can be implemented using a considerably simpler core language. These simulations are important as a compact and simple language is easier to implement and to reason about, while an expressive language offers more options when modeling problems.     

Stability and sensitivity-analysis for stochastic programming

Stability and sensitivity studies for stochastic programs have been motivated by the problem of incomplete information about the true probability measure through which the stochastic program is formulated and in connection with the development and evaluation of algorithms. The first part of this survey paper briefly introduces and compares different approaches and points out the contemporary efforts to remove and weaken assumptions that are not realistic (e.g., strict complementarity conditions). The second part surveys recent results on qualitative and quantitative stability with respect to the underlying probability measure and describes the ways and means of statistical sensitivity analysis based on Gâteaux derivatives. The last section comments on parallel statistical sensitivity results obtained in the parametric case, i.e., for probability measures belonging to a parametric family indexed by a finite dimensional vector parameter.     

Isetl: A programming language for learning mathematics

This paper gives a brief history of the development of an approach to help students learn mathematical concepts at the post-secondary level. The method uses ISETL, a programming language derived from SETL, to implement instruction whose design is based on an emerging theory of learning. Examples are given of uses of this pedagogical strategy in abstract algebra, calculus, and mathematical induction. © 1996 John Wiley & Sons, Inc.     

A mathematical programming approach for determining oligopolistic market equilibrium

During the past several years it has become increasingly common to use mathematical programming methods for deriving economic equilibria of supply and demand. Well-defined approaches exist for the case of a single firm (monopoly) and for the case of many firms (perfect competition). In this paper a certain family of convex programs is formulated to determine equilibria for the case of a few firms (oligopoly). Solutions to this family of convex programs are shown to be Nash equilibria in the formal sense ofN person games. This equivalence leads to a mathematical programming-based algorithm for determining an oligopolistic market equilibrium.     

Newton-type methods for stochastic programming

Stochastic programming is concerned with practical procedures for decision making under uncertainty, by modelling uncertainties and risks associated with decision in a form suitable for optimization. The field is developing rapidly with contributions from many disciplines such as operations research, probability and statistics, and economics. A stochastic linear program with recourse can equivalently be formulated as a convex programming problem. The problem is often large-scale as the objective function involves an expectation, either over a discrete set of scenarios or as a multi-dimensional integral. Moreover, the objective function is possibly nondifferentiable. This paper provides a brief overview of recent developments on smooth approximation techniques and Newton-type methods for solving two-stage stochastic linear programs with recourse, and parallel implementation of these methods. A simple numerical example is used to signal the potential of smoothing approaches.     

An examination for mathematical modelling

First year mathematics degree students at Leicester Polytechnic attend a course in mathematical modelling. The aim is to introduce the students to mathematical modelling concepts and to model development. Work is set and marked during the course and this forms a vital part of the students' assessment. In addition to this, however, the students are assessed by means of a three hour examination at the end of the year. This examination is significantly different from the normal ‘five out of eight’ type. The philosophy and organization of the examination are discussed in this paper. An example of a particular examination, that for June 1986, is included as an appendix to illustrate the points made in the discussion.