CiteULike: Tag optimization

Proving the Correctness of Optimising Destructive and Non-destructive Reads over Tuple Spaces

Rocco De Nicola — 2007-04-21T19:09:13-00:00

(2000), pp. 66-80.

. In this paper we describe the proof of an optimisation that can be applied to tuple space based run-time systems (as used in Linda). The optimisation allows, under certain circumstances, for a tuple that has been destructively removed from a shared tuple space (for example, by a Linda in) to be returned as the result for a non-destructive read (for example, a Linda rd) for a different process. The optimisation has been successfully used in a prototype run-time system. 1 Introduction...

A comparison of spatial design methods for correlated observations

Werner Müller — 2006-12-14T02:38:37-00:00

Environmetrics, Vol. 16, No. 5. (2005), pp. 495-505.

Random fields are frequently used to model spatial environmental processes. Optimum design theory for regression experiments is consequently employed to assess and construct monitoring networks for these processes. However, straightforward application of much of this theory is not possible, since the typical assumption of independent errors is violated. In the present article I intend to give an overview on design methods that attempt to cope with the problem, amongst them two recently developed approaches. For a comparison the techniques will be applied to the design of a water-quality monitoring network in the Südliche Tullnerfeld in Lower Austria. Copyright © 2005 John Wiley & Sons, Ltd.

Hybrid Wireless-Optical Broadband-Access Network (WOBAN): A Review of Relevant Challenges

S Sarkar — 2008-05-05T13:25:44-00:00

Lightwave Technology, Journal of, Vol. 25, No. 11. (2007), pp. 3329-3340.

The hybrid wireless-optical broadband-access network (WOBAN) is a promising architecture for future access networks. Recently, the wireless part of WOBAN has been gaining increasing attention, and early versions are being deployed as municipal access solutions to eliminate the wired drop to every wireless router at customer premises. This architecture saves on network deployment cost because the fiber need not penetrate each end-user, and it extends the reach of emerging optical-access solutions, such as passive optical networks. This paper first presents an architecture and a vision for the WOBAN and articulates why the combination of wireless and optical presents a compelling solution that optimizes the best of both worlds. While this discussion briefly touches upon the business drivers, the main arguments are based on technical and deployment considerations. Consequently, the rest of this paper reviews a variety of relevant research challenges, namely, network setup, network connectivity, and fault-tolerant behavior of the WOBAN. In the network setup, we review the design of a WOBAN where the back end is a wired optical network, the front end is managed by a wireless connectivity, and, in between, the tail ends of the optical part [known as optical network unit (ONU)] communicate directly with wireless base stations (known as ldquogateway routersrdquo). We outline algorithms to optimize the placement of ONUs in a WOBAN and report on a survey that we conducted on the distribution and types of wireless routers in the Wildhorse residential neighborhood of North Davis, CA. Then, we examine the WOBAN's routing properties (network connectivity), discuss the pros and cons of various routing algorithms, and summarize the idea behind fault-tolerant design of such hybrid networks.

An Introduction to the Conjugate Gradient Method Without the Agonizing Pain

Jonathan Shewchuk — 2005-07-25T18:32:17-00:00

(1994)

Numerical Recipes: The Art of Scientific Computing

William Press — 2007-06-13T05:09:04-00:00

(01 August 2007)

Co-authored by four leading scientists from academia and industry, Numerical Recipes Third Edition starts with basic mathematics and computer science and proceeds to complete, working routines. Widely recognized as the most comprehensive, accessible and practical basis for scientific computing, this new edition incorporates more than 400 Numerical Recipes routines, many of them new or upgraded. The executable C++ code, now printed in color for easy reading, adopts an object-oriented style particularly suited to scientific applications. The whole book is presented in the informal, easy-to-read style that made earlier editions so popular. Find more information at <a href = "http://www.nr.com">www.nr.com or <a href = "http://www.cambridge.org/numericalrecipes">www.cambridge.org/numericalrecipes. New key features: <ul> <li>2 new chapters, 25 new sections, 25% longer than Second Edition</li> <li>Thorough upgrades throughout the text</li> <li>Over 100 completely new routines and upgrades of many more.</li> <li>New Classification and Inference chapter, including Gaussian mixture models, HMMs, hierarchical clustering, Support Vector Machines</li><li>New Computational Geometry chapter covers KD trees, quad- and octrees, Delaunay triangulation, and algorithms for lines, polygons, triangles, and spheres</li> <li>New sections include interior point methods for linear programming, Monte Carlo Markov Chains, spectral and pseudospectral methods for PDEs, and many new statistical distributions</li> <li>An expanded treatment of ODEs with completely new routines</li> </ul> Plus comprehensive coverage of <ul> <li>linear algebra, interpolation, special functions, random numbers, nonlinear sets of equations, optimization, eigensystems, Fourier methods and wavelets, statistical tests, ODEs and PDEs, integral equations, and inverse theory</li> </ul> And much, much more! For more information, or to buy the book, visit <a href = "http://www.cambridge.org/numericalrecipes">www.cambridge.org/numericalrecipes. For support, or to subscribe to an online version, please visit <a href = "http://www.nr.com">www.nr.com.

Numerik linearer Gleichungssysteme: Direkte und iterative Verfahren (Springer-Lehrbuch)

Christian Kanzow — 2008-03-28T16:13:50-00:00

(15 September 2004)

Dieses Buch gibt eine umfassende Darstellung der wichtigsten Verfahren zur numerischen Lösung von linearen Gleichungssystemen. Es benötigt zum Verständnis nur sehr geringe mathematische Vorkenntnisse, wie sie meist schon nach einem einsemestrigen Kurs in einem mathematischen oder ingenieurwissenschaftlichen Studiengang vorliegen. Aus diesem Grunde wendet sich das Buch nicht nur an Studierende der Mathematik, Wirtschaftsmathematik oder Technomathematik, sondern auch an den Natur- und Ingenieurwissenschaftler, der in vielen praktischen Anwendungen mit der Lösung von linearen Gleichungssystemen konfrontiert wird. Inhaltlich beschäftigt sich das Buch sowohl mit den direkten als auch den iterativen Verfahren. Dabei wird großer Wert auf eine sorgfältige Herleitung dieser Verfahren gelegt. Ausserdem enthält das Buch sehr detaillierte Pseudocodes, mit deren Hilfe sich die jeweiligen Verfahren in einer beliebigen Programmiersprache sofort auf dem Computer realisieren lassen. Im Einzelnen werden folgende Themenkreise behandelt: Direkte Verfahren für lineare Gleichungssysteme, Orthogonalisierungsverfahren für lineare Ausgleichsprobleme, Splitting-Methoden, CG-, GMRES- und zahlreiche weitere Krylov-Raum-Methoden, Mehrgitterverfahren.

Efficient Linear System Solvers for Mesh Processing

Mario Botsch — 2008-03-27T12:37:39-00:00

Mathematics of Surfaces XI (2005), pp. 62-83.

The use of polygonal mesh representations for freeform geometry enables the formulation of many important geometry processing tasks as the solution of one or several linear systems. As a consequence, the key ingredient for efficient algorithms is a fast procedure to solve linear systems. A large class of standard problems can further be shown to lead more specifically to sparse, symmetric, and positive definite systems, that allow for a numerically robust and efficient solution. In this paper we discuss and evaluate the use of sparse direct solvers for such kind of systems in geometry processing applications, since in our experiments they turned out to be superior even to highly optimized multigrid methods, but at the same time were considerably easier to use and implement. Although the methods we present are well known in the field of high performance computing, we observed that they are in practice surprisingly rarely applied to geometry processing problems.

Optimization by Simulated Annealing

S Kirkpatrick — 2007-07-12T12:09:29-00:00

Science, Vol. 220, No. 4598. (13 May 1983), pp. 671-680.

There is a deep and useful connection between statistical mechanics (the behavior of systems with many degrees of freedom in thermal equilibrium at a finite temperature) and multivariate or combinatorial optimization (finding the minimum of a given function depending on many parameters). A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems. This connection to statistical mechanics exposes new information and provides an unfamiliar perspective on traditional optimization problems and methods. 10.1126/science.220.4598.671

SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization

Philip Gill — 2008-06-20T04:27:18-00:00

SIAM Review, Vol. 47, No. 1. (2005), pp. 99-131.

An Adaptive Nonlinear Least-Squares Algorithm

John Dennis — 2007-01-05T08:16:03-00:00

ACM Trans. Math. Softw., Vol. 7, No. 3. (September 1981), pp. 348-368.

An efficient method for finding the minimum of a function of several variables without calculating derivatives

MJD Powell — 2006-12-19T12:33:28-00:00

The Computer Journal, Vol. 7, No. 2. (1 February 1964), pp. 155-162.

A simple variation of the well-known method of minimizing a function of several variables by changing one parameter at a time is described. This variation is such that when the procedure is applied to a quadratic form, it causes conjugate directions to be chosen, so the ultimate rate of convergence is fast when the method is used to minimize a general function. A further variation completes the method, and its ensures that the convergence rate from a bad approximation to a minimum is always efficient. Practical applications of the procedure have proved to be very satisfactory, and numerical examples are given in which functions of up to twenty variables are minimized. 10.1093/comjnl/7.2.155

Hierarchical Topology Optimization Problems In Three-Dimensions

Giuseppe Derose — 2005-08-22T19:38:25-00:00

Hierarchical Topology Optimization Problems In Three-Dimensions By Giuseppe C. A. DeRose Jr. Hierarchical topology optimization is introduced as a mechanism to reduce computational resources needed to solve large scale, 3-dimensional problems. In hierarchical topology optimization, octree data structures are used to describe a given design during the optimization process. Using a sequence of hierarchically described models, increasingly detailed descriptions of the optimal shape are...

Metaheuristics in combinatorial optimization: Overview and conceptual comparison

Christian Blum — 2005-09-04T16:24:11-00:00

ACM Comput. Surv., Vol. 35, No. 3. (September 2003), pp. 268-308.

The degree of participation concept in ad hoc networks

Y Iraqi — 2006-01-17T22:02:58-00:00

Computers and Communication, 2003. (ISCC 2003). Proceedings. Eighth IEEE International Symposium on (2003), pp. 197-202 vol.1.

The paper introduces the novel concept of degree-of-participation (DP) in mobile ad hoc networks. The degree-of-participation concept allows nodes in the ad hoc network to express the level of involvement they are willing to give to the forwarding process. The paper also introduces a DP-based routing scheme for mobile ad hoc networks. Performance evaluations show that the degree-of-participation allows a more resource-aware forwarding process.

Maximum Entropy Distributions between Upper and Lower Bounds

Ali Abbas — 2006-04-18T02:24:37-00:00

AIP Conference Proceedings, Vol. 803, No. 1. (2005), pp. 25-42.

We discuss the formulation of discrete maximum entropy problems given upper and lower bounds on moments and probabilities. We show that with bounds on discrete probabilities, and bounds on cumulative probabilities, the solution is invariant to any additive concave objective function. This observation simplifies the analysis of the problem and unifies the solution of several generalized entropy expressions. We use this invariance result to provide an exact graphical solution to the maximum entropy distribution between upper and lower cumulative probability bounds. We also discuss the maximum entropy joint distribution with bounds on marginal probabilities and provide a graphical solution to the problem using properties of the entropy expression.

Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

Benjamin Recht — 2007-08-30T03:43:55-00:00

(28 Jun 2007)

The affine rank minimization problem consists of finding a matrix of minimum rank that satisfies a given system of linear equality constraints. Such problems have appeared in the literature of a diverse set of fields including system identification and control, Euclidean embedding, and collaborative filtering. Although specific instances can often be solved with specialized algorithms, the general affine rank minimization problem is NP-hard. In this paper, we show that if a certain restricted isometry property holds for the linear transformation defining the constraints, the minimum rank solution can be recovered by solving a convex optimization problem, namely the minimization of the nuclear norm over the given affine space. We present several random ensembles of equations where the restricted isometry property holds with overwhelming probability. The techniques used in our analysis have strong parallels in the compressed sensing framework. We discuss how affine rank minimization generalizes this pre-existing concept and outline a dictionary relating concepts from cardinality minimization to those of rank minimization.

Convexity, Surrogate Functions and Iterative Optimization in Multi-class Logistic Regression Models

Zhihua Zhang — 2005-10-21T05:37:37-00:00

(2004)

In this paper, we propose a family of surrogate maximization (SM) algorithms for multi-class logistic regression models (also called conditional exponential models). An SM algorithm aims at turning an otherwise intractable maximization problem into a tractable one by iterating two steps. The S-step computes a tractable surrogate function to substitute the original objective function, and the M-step seeks to maximize this surrogate function. We apply SM algorithms to logistic regression models, leading to the standard SM, generalized SM, gradient SM, and quadratic SM algorithms. Compared with Newton's method, these SM algorithms dramatically save computational costs when either the dimensionality or number of data samples is huge. Finally, we demonstrate the efcacy of these SM algorithms and compare their empirical performance on text categorization.

Convex Optimization

Stephen Boyd — 2005-04-18T19:00:14-00:00

(08 March 2004)

Convex optimization problems arise frequently in many different fields. A comprehensive introduction to the subject, this book shows in detail how such problems can be solved numerically with great efficiency. The focus is on recognizing convex optimization problems and then finding the most appropriate technique for solving them. The text contains many worked examples and homework exercises and will appeal to students, researchers and practitioners in fields such as engineering, computer science, mathematics, statistics, finance, and economics.

Discriminative training via linear programming

KA Papineni — 2005-10-20T17:21:16-00:00

Acoustics, Speech, and Signal Processing, 1999. ICASSP '99. Proceedings., 1999 IEEE International Conference on, Vol. 2 (1999), pp. 561-564 vol.2.

This paper presents a linear programming approach to discriminative training. We first define a measure of discrimination of an arbitrary conditional probability model on a set of labeled training data. We consider maximizing discrimination on a parametric family of exponential models that arises naturally in the maximum entropy framework. We show that this optimization problem is globally convex in Rn, and is moreover piecewise linear on Rn. We propose a solution that involves solving a series of linear programming problems. We provide a characterization of global optimizers. We compare this framework with those of minimum classification error and maximum entropy

Why natural gradient?

S Amari — 2005-11-30T06:03:02-00:00

Acoustics, Speech, and Signal Processing, 1998. ICASSP '98. Proceedings of the 1998 IEEE International Conference on, Vol. 2 (1998), pp. 1213-1216 vol.2.

Gradient adaptation is a useful technique for adjusting a set of parameters to minimize a cost function. While often easy to implement, the convergence speed of gradient adaptation can be slow when the slope of the cost function varies widely for small changes in the parameters. In this paper, we outline an alternative technique, termed natural gradient adaptation, that overcomes the poor convergence properties of gradient adaptation in many cases. The natural gradient is based on differential geometry and employs knowledge of the Riemannian structure of the parameter space to adjust the gradient search direction. Unlike Newton's method, natural gradient adaptation does not assume a locally-quadratic cost function. Moreover, for maximum likelihood estimation tasks, natural gradient adaptation is asymptotically Fisher-efficient. A simple example illustrates the desirable properties of natural gradient adaptation

Grafting: fast, incremental feature selection by gradient descent in function space

Simon Perkins — 2005-11-22T17:56:36-00:00

J. Mach. Learn. Res., Vol. 3 (2003), pp. 1333-1356.

On "Natural" Learning and Pruning in Multilayered Perceptrons

T Heskes — 2005-11-29T07:18:06-00:00

Neural Computation, Vol. 12, No. 4. (1 April 2000), pp. 881-901.

Several studies have shown that natural gradient descent for on-line learning is much more efficient than standard gradient descent. In this article, we derive natural gradients in a slightly different manner and discuss implications for batch-mode learning and pruning, linking them to existing algorithms such as Levenberg-Marquardt optimization and optimal brain surgeon. The Fisher matrix plays an important role in all these algorithms. The second half of the article discusses a layered approximation of the Fisher matrix specific to multilayered perceptrons. Using this approximation rather than the exact Fisher matrix, we arrive at much faster "natural" learning algorithms and more robust pruning procedures.

A new class of quasi-Newtonian methods for optimal learning in MLP-networks

A Bortoletti — 2005-11-29T05:20:26-00:00

Neural Networks, IEEE Transactions on, Vol. 14, No. 2. (2003), pp. 263-273.

In this paper, we present a new class of quasi-Newton methods for an effective learning in large multilayer perceptron (MLP)-networks. The algorithms introduced in this work, named LQN, utilize an iterative scheme of a generalized BFGS-type method, involving a suitable family of matrix algebras L. The main advantages of these innovative methods are based upon the fact that they have an O(nlogn) complexity per step and that they require O(n) memory allocations. Numerical experiences, performed on a set of standard benchmarks of MLP-networks, show the competitivity of the LQN methods, especially for large values of n.

Efficient Block Training of Multilayer Perceptrons

A Navia-Vazquez — 2005-11-29T05:02:19-00:00

Neural Computation, Vol. 12, No. 6. (1 June 2000), pp. 1429-1447.

The attractive possibility of applying layerwise block training algorithms to multilayer perceptrons MLP, which offers initial advantages in computational effort, is refined in this article by means of introducing a sensitivity correction factor in the formulation. This results in a clear performance advantage, which we verify in several applications. The reasons for this advantage are discussed and related to implicit relations with second-order techniques, natural gradient formulations through Fisher's information matrix, and sample selection. Extensions to recurrent networks and other research lines are suggested at the close of the article.

Approximation algorithms for geometric shortest path problems

Lyudmil Aleksandrov — 2005-08-20T07:16:53-00:00

(2000), pp. 286-295.

The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems

Josiah Carlson — 2005-08-18T03:37:00-00:00

(16 Aug 2005)

We consider problems in which we are given a rooted tree as input, and must find a subtree with the same root, optimizing some objective function of the nodes in the subtree. When this function is the sum of constant node weights, the problem is trivially solved in linear time. When the objective is the sum of weights that are linear functions of a parameter, we show how to list all optima for all possible parameter values in O(n log n) time; this parametric optimization problem can be used to solve many bicriterion optimizations problems, in which each node has two values xi and yi associated with it, and the objective function is a bivariate function f(SUM(xi),SUM(yi)) of the sums of these two values. A special case, when f is the ratio of the two sums, is the Weighted Maximum-Mean Subtree Problem, or equivalently the Fractional Prize-Collecting Steiner Tree Problem on Trees; for this special case, we provide a linear time algorithm for this problem when all weights are positive, improving a previous O(n log n) solution, and prove that the problem is NP-complete when negative weights are allowed.

Optimization on Lie manifolds and pattern recognition

Nagabhushana Prabhu — 2005-11-08T08:46:43-00:00

Pattern Recognition, Vol. 38, No. 12. (December 2005), pp. 2286-2300.

Several pattern recognition problems can be reduced in a natural way to the problem of optimizing a nonlinear function over a Lie manifold. However, optimization on Lie manifolds involves, in general, a large number of nonlinear equality constraints and is hence one of the hardest optimization problems. We show that exploiting the special structure of Lie manifolds allows one to devise a method for optimizing on Lie manifolds in a computationally efficient manner. The new method relies on the differential geometry of Lie manifolds and the underlying connections between Lie groups and their associated Lie algebras. We describe an application of the new Lie group method to the problem of diagnosing malignancy in the cytological extracts of breast tumors. The diagnosis method that we present has a mean sensitivity of 98.086% and a predictive index of 0.0602, making it the most accurate and reliable diagnostic method reported thus far.

Learning Statistical Structure for Object Detection

H Schneiderman — 2006-07-11T12:54:25-00:00

(2003)

Many classes of images exhibit sparse structuring of statistical dependency. Each variable has strong statistical dependency with a small number of other variables and negligible dependency with the remaining ones. Such structuring makes it possible to construct a powerful classifier by only representing the stronger dependencies among the variables. In particular, a seminaive Bayes classifier compactly represents sparseness. A semi-naive Bayes classifier decomposes the input variables into...

Including Group-By in Query Optimization

Surajit Chaudhuri — 2007-05-15T08:34:53-00:00

(1994), pp. 354-366.

Sequential parameter optimization

T Bartz-Beielstein — 2007-02-13T10:48:33-00:00

Evolutionary Computation, 2005. The 2005 IEEE Congress on, Vol. 1 (2005), pp. 773-780.

Sequential parameter optimization is a heuristic that combines classical and modern statistical techniques to improve the performance of search algorithms. To demonstrate its flexibility, three scenarios are discussed: (1) no experience how to choose the parameter setting of an algorithm is available, (2) a comparison with other algorithms is needed, and (3) an optimization algorithm has to be applied effectively and efficiently to a complex real-world optimization problem. Although sequential parameter optimization relies on enhanced statistical techniques such as design and analysis of computer experiments, it can be performed algorithmically and requires basically the specification of the relevant algorithm's parameters.

Updating Quasi-Newton Matrices with Limited Storage

Jorge Nocedal — 2007-05-08T20:41:45-00:00

Mathematics of Computation, Vol. 35, No. 151. (1980), pp. 773-782.

We study how to use the BFGS quasi-Newton matrices to precondition minimization methods for problems where the storage is critical. We give an update formula which generates matrices using information from the last m iterations, where m is any number supplied by the user. The quasi-Newton matrix is updated at every iteration by dropping the oldest information and replacing it by the newest information. It is shown that the matrices generated have some desirable properties. The resulting algorithms are tested numerically and compared with several well-known methods.

A comparison of algorithms for maximum entropy parameter estimation

Robert Malouf — 2006-10-25T09:41:12-00:00

(2002), pp. 1-7.

Query optimization

Yannis Ioannidis — 2006-06-16T22:09:13-00:00

ACM Computing Surveys, Vol. 28, No. 1. (1996), pp. 121-123.

Introduction Imagine yourself standing in front of an exquisite buffet filled with numerous delicacies. Your goal is to try them all out, but you need to decide in what order. What exchange of tastes will maximize the overall pleasure of your palate? Although much less pleasurable and subjective, that is the type of problem that query optimizers are called to solve. Given a query, there are many plans that a database management system (DBMS) can follow to process it and produce its answer....

Simulating pathological gait using the enhanced linear inverted pendulum model

T Komura — 2005-10-11T13:18:37-00:00

Biomedical Engineering, IEEE Transactions on, Vol. 52, No. 9. (2005), pp. 1502-1513.

In this paper, we propose a new method to simulate human gait motion when muscles are weakened. The method is based on the enhanced version of three-dimensional linear inverted pendulum model that is used for generation of gait in robotics. After the normal gait motion is generated by setting the initial posture and the parameters that decide the trajectories of the center of mass and angular momentum, the muscle to be weakened is specified. By minimizing an objective function based on the force exerted by the specified muscle during the motion, the set of parameters that represent the pathological gait was calculated. Since the number of parameters to describe the motion is small in our method, the optimization process converges much more quickly than in previous methods. The effects of weakening the gluteus medialis, the gluteus maximus, and vastus were analyzed. Important similarities were noted when comparing the predicted pendulum motion with data obtained from an actual patient.

Condition-based maintenance optimization by means of genetic algorithms and Monte Carlo simulation

Marzio Marseguerra — 2006-06-02T14:57:04-00:00

Reliability Engineering & System Safety, Vol. 77, No. 2. (1 August 2002), pp. 151-165.

Efficient maintenance policies are of fundamental importance in system engineering because of their fallbacks into the safety and economics of plants operation. When the condition of a system, such as its degradation level, can be continuously monitored, a Condition[hyphen]Based Maintenance (CBM) policy can be implemented, according to which the decision of maintaining the system is taken dynamically on the basis of the observed condition of the system.In this paper, we consider a continuously monitored multi[hyphen]component system and use a Genetic Algorithm (GA) for determining the optimal degradation level beyond which preventive maintenance has to be performed. The problem is framed as a multi[hyphen]objective search aiming at simultaneously optimizing two typical objectives of interest, profit and availability. For a closer adherence to reality, the predictive model describing the evolution of the degrading system is based on the use of Monte Carlo (MC) simulation. More precisely, the flexibility offered by the simulation scheme is exploited to model the dynamics of a stress[hyphen]dependent degradation process in load[hyphen]sharing components and to account for limitations in the number of maintenance technicians available. The coupled (GA[plus ]MC) approach is rendered particularly efficient by the use of the ‘drop[hyphen]by[hyphen]drop’ technique, previously introduced by some of the authors, which allows to effectively drive the combinatorial search towards the most promising solutions.

Maintenance optimisation from a decision theoretical point of view

Jorn Vatn — 2006-06-02T14:45:09-00:00

Reliability Engineering & System Safety, Vol. 58, No. 2. (November 1997), pp. 119-126.

Maintenance optimisation is rarely discussed from a decision theoretical point of view. It is believed that maintenance programmes may benefit from using decision theory in a more formal manner. In decision theory there is a sharp line of demarcation between establishing requirements and preferences on one side, and methods for seeking an optimal solution in accordance with the requirements and preferences on the other side. We discuss requirements and preferences concerning maintenance, and how to model these by value and utility functions. Next we discuss how to choose the optimum set of maintenance actions. Influence diagrams are introduced to visualise the relation between maintenance actions, system characteristics and value functions. Finally an illustrative example is given.

An overall model for maintenance optimization

Jorn Vatn — 2006-06-02T14:34:23-00:00

Reliability Engineering & System Safety, Vol. 51, No. 3. (March 1996), pp. 241-257.

This paper presents an approach for identifying the optimal maintenance schedule for the components of a production system. Safety, health and environment objectives, maintenance costs and costs of lost production are all taken into consideration, and maintenance is thus optimized with respect to multiple objectives. Such a global approach to maintenance optimization requires expertise from various fields, e.g., decision theory, risk analysis and reliability and maintenance modelling. Further, a close co-operation between management, maintenance personnel and analysts is required to achieve a successful result. In the past this has been a major obstacle to the extensive use of proper maintenance optimization methods in practice, and techniques to promote the communication between the involved parties of the optimization process is an essential element in the suggested approach. A simple step by step presentation of the required modelling is provided. Contrary to most current methods of RCM (Reliability Centered Maintenance), the approach is based on an analytic model, and therefore gives a sound framework for carrying out a proper maintenance optimization. The approach is also flexible as it can be carried out at various levels of detail, e.g., adopted to available resources and to the managements willingness to give detailed priorities with respect to objectives on safety vs production loss.

Minimizing multimodal functions of continuous variables with the “simulated annealing” algorithm

A Corana — 2006-05-17T21:20:23-00:00

ACM Trans. Math. Softw., Vol. 13, No. 3. (September 1987), pp. 262-280.

The Ant System: Optimization by a colony of cooperating agents

Marco Dorigo — 2007-04-11T04:57:26-00:00

IEEE Transactions on Systems, Man, and Cybernetics Part B: Cybernetics, Vol. 26, No. 1. (1996), pp. 29-41.

An analogy with the way ant colonies function has suggested the definition of a new computational paradigm, which we call Ant System. We propose it as a viable new approach to stochastic combinatorial optimization. The main characteristics of this model are positive feedback, distributed computation, and the use of a constructive greedy heuristic. Positive feedback accounts for rapid discovery of good solutions, distributed computation avoids premature convergence, and the greedy heuristic...

Scheduling of discrete event systems using mixed integer linear programming

A Kobetski — 2008-04-17T11:05:10-00:00

Discrete Event Systems, 2006 8th International Workshop on (2006), pp. 76-81.

To remain competitive, the modern industry strive for flexibility. Recently, a method for automatic generation of control code from a 3D simulation model of a flexible manufacturing system was developed. Finite automata and supervisory control theory (SCT) were used to guarantee the required behaviour of the system. This paper moves one step further. A method for automatic conversion between deterministic finite automata and mixed integer linear programming (MILP) formulation is presented. This allows to efficiently combine SCT and MILP to automatically generate time-optimal, collision-free and non-blocking working schedules.

The semantics of future and its use in program optimization

Cormac Flanagan — 2004-12-17T23:46:18-00:00

(1995), pp. 209-220.

Attribute grammars as a functional programming paradigm

Thomas Johnsson — 2005-09-13T07:31:28-00:00

(1987), pp. 154-173.

Tree Transducer Composition as Program Transformation

Janis Voigtländer — 2005-09-12T06:47:36-00:00

(2005)

Nonstrict, purely functional programming languages offer a high potential for the modularization of software. But beside their advantages with respect to reliability and reusability, modularly specified programs often have the disadvantage of low execution efficiency, caused in particular by the creation and consumption of structured intermediate results. One possible approach to cure this conflict is the automatic, semantics-preserving optimization of programs, for which purely functional languages are again particularly suited due to their mathematical foundation. This dissertation studies a specific transformation for the elimination of intermediate results (for so called deforestation) regarding its impact on the program efficiency under nonstrict evaluation. The formal framework is provided by concepts from the theory of tree transducers. One special feature of the transformation under consideration is the successful handling of accumulating parameters, which find frequent use in functional programs. The core of the thesis is the derivation of effectively decidable, syntactic conditions on the original program under which the transformed program is to be preferred over it with respect to efficiency.

Usage Counting Analysis for Lazy Functional Languages

GW Hamilton — 2005-09-30T12:46:59-00:00

Information and Computation, Vol. 146, No. 2. (1 November 1998), pp. 100-137.

If it can be determined at compile-time how many times values will be used within lazy functional programs, a number of useful optimisations can be performed. For example, call-by-need parameter passing can be converted to call-by-name, and in-place updating and compile-time garbage collection can be performed. In this paper, it is shown how this usage counting information can be obtained by static analysis. This analysis is not itself a major contribution of this paper; similar analyses have been defined before. The major contributions of this paper are that it provides a framework against which this analysis can be proved correct for a lazy functional language, and the analysis is proved to be correct with respect to this framework. The framework for proving the correctness of the analysis is provided by defining a store semantics which counts the number of times values are used.

Functional array fusion

Manuel Chakravarty — 2005-09-09T11:42:39-00:00

Vol. 36, No. 10. (October 2001), pp. 205-216.

Comparison of Deforestation Techniques for Functional Programs and for Tree Transducers

A Kühnemann — 2005-09-16T12:12:39-00:00

Vol. 1722 (November 1999), pp. 114-130.

Using Circular Programs to Deforest in Accumulating Parameters

Janis Voigtländer — 2005-09-09T08:58:16-00:00

Higher-Order and Symbolic Computation, Vol. 17, No. 1 - 2. (March 2004), pp. 129-163.

This paper presents a functional program transformation that removes intermediate data structures in compositions of two members of a class of recursive functions with accumulating parameters. To avoid multiple traversals of the input data structure, the composition algorithm produces circular programs that make essential use of lazy evaluation and local recursion. The resulting programs are simplified using a post-processing phase sketched in the paper. The presented transformation, called lazy composition, is compared with related transformation techniques both on a qualitative level and based on runtime measurements. An alternative use of higher-orderedness instead of circularity is also briefly explored.

Composition of functions with accumulating parameters

Janis Voigtländer — 2005-08-29T12:01:01-00:00

Journal of Functional Programming, Vol. 14, No. 3. (May 2004), pp. 317-363.

Many functional programs with accumulating parameters are contained in the class of macro tree transducers. We present a program transformation technique that can be used to solve the efficiency problems due to creation and consumption of intermediate data structures in compositions of such functions, where classical deforestation techniques fail. To do so, given two macro tree transducers under appropriate restrictions, we construct a single macro tree transducer that implements the composition of the two original ones. The imposed restrictions are more liberal than those in the literature on macro tree transducer composition, thus generalising previous results.

Concatenate, reverse and map vanish for free

Janis Voigtländer — 2005-04-22T05:25:13-00:00

SIGPLAN Notices, Vol. 37, No. 9. (October 2002), pp. 14-25.

We introduce a new transformation method to eliminate intermediate data structures occurring in functional programs due to repeated list concatenations and other data manipulations (additionally exemplified with list reversal and mapping of functions over lists). The general idea is to uniformly abstract from data constructors and manipulating operations by means of rank-2 polymorphic combinators that exploit algebraic properties of these operations to provide an optimized implementation. The correctness of transformations is proved by using the free theorems derivable from parametric polymorphic types.

Using circular programs to deforest in accumulating parameters

Janis Voigtländer — 2005-09-09T08:42:28-00:00

(September 2002), pp. 126-137.

Functional languages allow a modular programming style by function composition, which however can lead to inefficient runtime behavior due to production and consumption of intermediate results. We present a new mechanizable transformation technique for removing intermediate data structures in the composition of two functions from a class of recursive functions with accumulating parameters, for which classical deforestation techniques fail. In order to avoid multiple traversals of the input data structure, the composition algorithm produces circular programs that make essential use of lazy evaluation and local recursion. The resulting programs are simplified using a post-processing phase presented in the paper.