Solution of Differential--Algebraic Systems Using Diagonally Implicit Runge--Kutta Methods

Diagonally Implicit Runge—Kutta (DIRK) methods are developedand applied to differential—algebraic systems arisingfrom dynamic process simulation. In particular, an embeddedfamily of DIRK methods is developed for implementation as avariable-step variable-order algorithm. The methods developedallow easy assessment of local solution error as well as theability to change the order of approximation. The stabilityproperties of the methods are chosen to make them suitable foruse on stiff systems. Some important aspects of implementation of DIRK methods arediscussed within the context of the solution of differential—algebraicsystems. The performance of this algorithm is compared withan alternative variable-order approach based on "triples" whichallows the patching together of several fixed-order formulae.The results indicate that the fully embedded DIRK algorithmis generally more efficient than the algorithm based on "triples".Areas of further investigation in the context of differential—algebraicsystems are outlined.     

A Finite-element Front-tracking Enthalpy Method for Stefan Problems

A finite-element front-tracking method, which avoids explicittreatment of the jump condition on the phase boundary, is proposed.This method is based on the discretization of a weak enthalpyformulation with isoparametric space—time finite elements.A one-dimensional two-phase problem and a two-dimensional one-phaseproblem are solved by this method. Then the method is appliedto a generalized Stefan problem—the spot-welding problemand extended to the alloy-solidification problem. Numerical experiments show that this method is convergent andunconditionally stable and that second-order convergence canbe expected if the biquadratic elements are used for one-dimensionalproblems. The effectiveness of this method is, in particular,shown in solving the last two problems.     

Initial-Boundary Value Problems for the Korteweg-de Vries Equation

Exact and approximate solutions of the initial—boundaryvalue problem for the Korteweg—de Vries equation on thesemi-infinite line are found. These solutions are found forboth constant and time-dependent boundary values. The form ofthe solution is found to depend markedly on the specific boundaryand initial value. In particular, multiple solutions and nonsteadysolutions are possible. The analytical solutions are comparedwith numerical solutions of the Korteweg—de Vries equationand are found to be in good agreement.     

Coevolutionary-based Mechanisms for Network Anomaly Detection

The paper presents an approach based on the principles of immune systems applied to the anomaly detection problem. Flexibility and efficiency of the anomaly detection system are achieved by building a model of the network behavior based on the self–nonself space paradigm. Covering both self and nonself spaces by hyperrectangular structures is proposed. The structures corresponding to self-space are built using a training set from this space. The hyperrectangular detectors covering nonself space are created using a niching genetic algorithm. A coevolutionary algorithm is proposed to enhance this process. The results of experiments show a high quality of intrusion detection, which outperform the quality of the recently proposed approach based on a hypersphere representation of the self-space.      

Scheduling fixtures for New Zealand Cricket

^** Email: m.wright{at}lancaster.ac.uk This paper describes the problem faced every year by New ZealandCricket in scheduling the principal inter-regional fixtures.This is a combinatorial optimization problem with few constraintsbut many objectives, which are described in detail. A techniqueknown as Subcost-Guided Simulated Annealing is used to solvethis problem, producing one or more schedules of high quality.One particular feature of the problem requires great care—thedetermination of adequate neighbourhoods for such a tightlyconstrained problem, where most simple changes lead to infeasibility.The approach adopted is to use a complex and unorthodox definitionof a perturbation, each one leading to several possible neighbouringsolutions which are generated by means of a tree search procedure.The system will be used in practice for the 2003–2004cricket season and beyond.     

Whiteboard math movies

In this article, we discuss whiteboard math movies (a.k.a. mathcasts)and their applications to mathematics education. A whiteboardmath (wbm) movie is a screen recording of writing plus voiceand/or text explaining a mathematical concept or solving a problem.The movie is then produced to Flash movie format and distributedvia CD or Internet. The wbm movies are the ultimate in asynchronouslearning—providing a simple and inexpensive means of interactionat the teacher–student, teacher–teacher, student–teacherand student–student level. With wbm movies both the creatorand the viewer get to see and hear the mathematical thinkingstep-by-step. They get the process and not just the result andthey can have it when and as many times as they want. We talkabout how Tim Fahlberg came up with this idea over 8 years agoand describe the developments in technology—that are atleast partially the result of our team's work—that nowmake wbm movie making a cost-efficient, effective and even afun way of truly learning mathematics.     

Advanced Genetic Programming Based Machine Learning

A Genetic Programming based approach for solving classification problems is presented in this paper. Classification is understood as the act of placing an object into a set of categories, based on the object’s properties; classification algorithms are designed to learn a function which maps a vector of object features into one of several classes. This is done by analyzing a set of input-output examples (“training samples”) of the function. Here we present a method based on the theory of Genetic Algorithms and Genetic Programming that interprets classification problems as optimization problems: Each presented instance of the classification problem is interpreted as an instance of an optimization problem, and a solution is found by a heuristic optimization algorithm. The major new aspects presented in this paper are advanced algorithmic concepts as well as suitable genetic operators for this problem class (mainly the creation of new hypotheses by merging already existing ones and their detailed evaluation). The experimental part of the paper documents the results produced using new hybrid variants of Genetic Algorithms as well as investigated parameter settings. Graphical analysis is done using a novel multiclass classifier analysis concept based on the theory of Receiver Operating Characteristic curves. The work described in this paper was done within the Translational Research Project L282 “GP-Based Techniques for the Design of Virtual Sensors” sponsored by the Austrian Science Fund (FWF).     

A portfolio of purchase contracts--an example of solving large-scale dynamic programming on parallel computers

The curse of dimensionality means that, though many stochasticsequential decision problems can be modelled as dynamic-programmingproblems, their memory requirements and large solution timesmake them impracticable to solve on most serial computers. Thispaper looks at an example of such a problem—the optimalportfolio of purchase contracts—whichwas solved usinga parallel computer and a LAN of workstations. It concentrateson two questions related to the solution of this problem.     

A note on the regularity of reduced models obtained by nonlocal quasi-continuum-like approaches

The paper investigates model reduction techniques that are based on a nonlocal quasi-continuum-like approach. These techniques reduce a large optimization problem to either a system of nonlinear equations or another optimization problem that are expressed in a smaller number of degrees of freedom. The reduction is based on the observation that many of the components of the solution of the original optimization problem are well approximated by certain interpolation operators with respect to a restricted set of representative components. Under certain assumptions, the “optimize and interpolate” and the “interpolate and optimize” approaches result in a regular nonlinear equation and an optimization problem whose solutions are close to the solution of the original problem, respectively. The validity of these assumptions is investigated by using examples from potential-based and electronic structure-based calculations in Materials Science models. A methodology is presented for using quasi-continuum-like model reduction for real-space DFT computations in the absence of periodic boundary conditions. The methodology is illustrated using a basic Thomas–Fermi–Dirac case study.     

Stochastic local search for large-scale instances of the haplotype inference problem by pure parsimony

Haplotype Inference is a challenging problem in bioinformatics that consists in inferring the basic genetic constitution of diploid organisms on the basis of their genotype. This information allows researchers to perform association studies for the genetic variants involved in diseases and the individual responses to therapeutic agents. A notable approach to the problem is to encode it as a combinatorial problem (under certain hypotheses, such as the pure parsimony criterion) and to solve it using off-the-shelf combinatorial optimization techniques. The main methods applied to Haplotype Inference are either simple greedy heuristic or exact methods (Integer Linear Programming, Semidefinite Programming, SAT and pseudo-boolean encoding) that, at present, are adequate only for moderate size instances. In this paper, we present and discuss an approach based on the combination of local search metaheuristics and a reduction procedure based on an analysis of the problem structure. Some relevant design issues are first described, then a family of local search metaheuristics is defined to tackle the Haplotype Inference. Results on common Haplotype Inference benchmarks show that the approach achieves a good trade-off between solution quality and execution time.     

Existence and optimal control for periodic parabolic equations with nonlocal terms

Motivated by models which have been proposed for some problemsin mathematical biology and fisheries management and elsewhere,we consider a nonlinear periodic parabolic problem and an associatedcost functional J. A key feature of our problem is the presenceof a nonlocal term which—as we show by direct example—rendersthe standard mono-tonicity methods invalid. We therefore employtopological methods to deal both with existence of solutionsand of minima of J over the Control set. Some considerationsare also presented on related systems and on the question ofuniqueness.     

Covering a polygonal region by rectangles

The problem of covering a compact polygonal region, called target region, with a finite family of rectangles is considered. Tools for mathematical modeling of the problem are provided. Especially, a function, called Γ-function, is introduced which indicates whether the rectangles with respect to their configuration form a cover of the target region or not. The construction of the Γ-function is similar to that of Φ-functions which have been proved to be an efficient tool for packing problems. A mathematical model of the covering problem based on the Γ-function is proposed as well as a solution strategy. The approach is illustrated by an example and some computational results are presented.     

Performance analysis of automatic assembly systems with in-line parallel stations

An automatic assembly system—a key tool for mass production—isgenerally composed of a number of workstations and a transportsystem. One common problem associated with automatic assemblysystems is that some assembly operations may have relativelylong cycle times. As a consequence, productivity, which is determinedby the operations with the longest cycle time, can be reducedsignificantly. Therefore a special form of parallel workstationknown as an in-line parallel (tandem-gated) station was developedto improve the performance of an automatic assembly system.In this design, stations working in parallel are installed ina serial structure and perform identical operations. Thus, morethan one assembly may be processed simultaneously—a typeof design especially beneficial when a stage requires a longoperation cycle time. A typical example is a computer assemblysystem which performs long inspection operations to ensure thatthe quality level of each product is up to the acceptance level. In this paper, we describe a simulation study of the performancecharacteristics of this type of system, with a statistical analysisof each decision factor. Phenomena affecting the performanceof in-line parallel stations, identified by the assistance ofthe computer graphical display, will then be discussed. An analyticalmodel based on these phenomena identified is then developed.The results generated by the analytical model developed arevalidated by comparisons with the simulation results. Finally,guidelines for optimization of buffer size are presented.     

Global Error Estimation with Runge--Kutta Methods

An analysis of global error estimation for Runge—Kuttasolutions of ordinary differential equations is presented. Thebasic technique is that of Zadunaisky in which the global erroris computed from a numerical solution of a neighbouring problemrelated to the main problem by some method of interpolation.It is shown that Runge—Kutta formulae which permit validglobal error estimation using low-degree interpolation can bedeveloped, thus leading to more accurate and computationallyconvenient algorithms than was hitherto expected. Some specialRunge—Kutta processes up to order 4 are presented togetherwith numerical results.     

A fuzzy goal programming and meta heuristic algorithms for solving integrated production: distribution planning problem

Integrated production–distribution planning is one of the most important issues in supply chain management (SCM). We consider a supply chain (SC) network to consist of a manufacturer, with multiple plants, products, distribution centers (DCs), retailers and customers. A multi-objective linear programming problem for integrating production–distribution, which considers various simultaneously conflicting objectives, is developed. The decision maker’s imprecise aspiration levels of goals are incorporated into the model using a fuzzy goal programming approach. Due to complexity of the considered problem we propose three meta-heuristics to tackle the problem. A simple genetic algorithm and a particle swarm optimization (PSO) algorithm with a new fitness function, and an improved hybrid genetic algorithm are developed. In order to show the efficiency of the proposed methods, two classes of problems are considered and their instances are solved using all methods. The obtained results show that the improved hybrid genetic algorithm gives us the best solutions in a reasonable computational time.     

Numerical analysis of the dispersion of electroelastic waves in a cylinder whose physical properties have a longitudinal axis of symmetry

We develop a numerical method of analyzing the dispersion of electroelastic waves in a hollow circular cylinder. The method is based on the reduction of the wave problem to a spectral problem for a system of ordinary differential equations. This system is solved numerically. The roots of the dispersion equation are determined by the method of bisection. The practical convergence of the algorithm is shown using a specific example. One figure. Bibliography: 3 titles. Translated fromTeoreticheskaya i Prikladnaya Mekhanika, No. 28, 1998, pp. 151–156.     

Stochastic vendor selection problem: chance-constrained model and genetic algorithms

We study a vendor selection problem in which the buyer allocates an order quantity for an item among a set of suppliers such that the required aggregate quality, service, and lead time requirements are achieved at minimum cost. Some or all of these characteristics can be stochastic and hence, we treat the aggregate quality and service as uncertain. We develop a class of special chance-constrained programming models and a genetic algorithm is designed for the vendor selection problem. The solution procedure is tested on randomly generated problems and our computational experience is reported. The results demonstrate that the suggested approach could provide managers a promising way for studying the stochastic vendor selection problem. The authors would like to thank the referees for providing constructive comments that led to an improved version of the paper. Also, this research was partially supported by grants from National Natural Science Foundation (60776825)—China, 863 Programs (2007AA11Z208)—China, Doctorate Foundation (20040004012)—China, Villanova University Research Sabbatical Fall 2006, and the National Science Foundation (0332490)—USA.     

Two-level evolutionary approach to the survivable mesh-based transport network topological design

The complete topology design problem of survivable mesh-based transport networks is to address simultaneously design of network topology, working path routing, and spare capacity allocation based on span-restoration. Each constituent problem in the complete design problem could be formulated as an Integer Programming (IP) and is proved to be NP\mathcal{NP} -hard. Due to a large amount of decision variables and constraints involved in the IP formulation, to solve the problem directly by exact algorithms (e.g. branch-and-bound) would be impractical if not impossible. In this paper, we present a two-level evolutionary approach to address the complete topology design problem. In the low-level, two parameterized greedy heuristics are developed to jointly construct feasible solutions (i.e., closed graph topologies satisfying all the mesh-based network survivable constraints) of the complete problem. Unlike existing “zoom-in”-based heuristics in which subsets of the constraints are considered, the proposed heuristics take all constraints into account. An estimation of distribution algorithm works on the top of the heuristics to tune the control parameters. As a result, optimal solution to the considered problem is more likely to be constructed from the heuristics with the optimal control parameters. The proposed algorithm is evaluated experimentally in comparison with the latest heuristics based on the IP software CPLEX, and the “zoom-in”-based approach on 28 test networks problems. The experimental results demonstrate that the proposed algorithm is more effective in finding high-quality topologies than the IP-based heuristic algorithm in 21 out of 28 test instances with much less computational costs, and performs significantly better than the “zoom-in”-based approach in 19 instances with the same computational costs.     

Two storage inventory model in a mixed environment

Multi-item inventory models with two storage facility and bulk release pattern are developed with linearly time dependent demand in a finite time horizon under crisp, stochastic and fuzzy-stochastic environments. Here different inventory parameters—holding costs, ordering costs, purchase costs, etc.—are assumed as probabilistic or fuzzy in nature. In particular cases stochastic and crisp models are derived. Models are formulated as profit maximization principle and three different approaches are proposed for solution. In the first approach, fuzzy extension principle is used to find membership function of the objective function and then it’s Graded Mean Integration Value (GMIV) for different optimistic levels are taken as equivalent stochastic objectives. Then the stochastic model is transformed to a constraint multi-objective programming problem using Stochastic Non-linear Programming (SNLP) technique. The multi-objective problems are transferred to single objective problems using Interactive Fuzzy Satisfising (IFS) technique. Finally, a Region Reducing Genetic Algorithm (RRGA) based on entropy has been developed and implemented to solve the single objective problems. In the second approach, the above GMIV (which is stochastic in nature) is optimized with some degree of probability and using SNLP technique model is transferred to an equivalent single objective crisp problem and solved using RRGA. In the third approach, objective function is optimized with some degree of possibility/necessity and following this approach model is transformed to an equivalent constrained stochastic programming problem. Then it is transformed to an equivalent single objective crisp problem using SNLP technique and solved via RRGA. The models are illustrated with some numerical examples and some sensitivity analyses have been presented.     

A fully subjective approach to modelling inspection maintenance

The fully subjective, or fully Bayesian approach discussed in this paper provides straightforward means of presenting uncertainty related to future events to decision makers. This approach is described in the context of an inspection maintenance decision problem, and is contrasted with the classical probabilistic approach that assumes the existence of true probabilities and probability distributions which have to be estimated. Key features of the fully subjective approach are discussed, including integration of engineering judgements, uncertainty treatment and type of performance measures to be used. An example related to the problem of identifying “optimal” inspection intervals for an extrusion press is used to illustrate the principles described.