Reformulations in mathematical programming: automatic symmetry detection and exploitation

If a mathematical program has many symmetric optima, solving it via Branch-and-Bound techniques often yields search trees of disproportionate sizes; thus, finding and exploiting symmetries is an important task. We propose a method for automatically finding the formulation group of any given Mixed-Integer Nonlinear Program, and for reformulating the problem by means of static symmetry breaking constraints. The reformulated problem—which is likely to have fewer symmetric optima—can then be solved via standard Branch-and-Bound codes such as CPLEX (for linear programs) and Couenne (for nonlinear programs). Our computational results include formulation group tables for the MIPLib3, MIPLib2003, GlobalLib and MINLPLib instance libraries and solution tables for some instances in the aforementioned libraries.     

Modelling and evaluation of time aspects in business processes

There is a need for modelling and performance evaluation techniques and tools for a fast and reliable design of workflow systems. This paper introduces a modelling methodology based on coloured stochastic Petri nets. It allows the integration of control flow, organizational, information related and timing aspects in one modelling framework. The processing delays include stochastic distributions in addition to deterministic times. Several workflows and the effects of constrained shared resources needed for different tasks can easily be described and analysed together. Control flow and organizational aspects are modelled separately in resource and workflow models. These models are automatically compiled into one model, which can then be used for qualitative analysis or performance evaluation. The proposed modelling and evaluation method is supported by the software tool TimeNET. An application example shows its use.     

Stochastic Simulation and Monte Carlo methods applied to the assessment of hydro-thermal generating system operation

Summary Simulation can be defined as a numerical technique for conducting experiments on a digital computer, which involves certain types of mathematical and logical models that describe the behaviour of a system over extended periods of real time. Simulation is, in a wide sense, a technique for performing sampling experiments on a model of the system. Stochastic simulation implies experimenting with the model over time including sampling stochastic variates from probability distributions. This paper describes the main concepts of the application of Stochastic Simulation and Monte Carlo methods to the analysis of the operation of electric energy systems, in particular to hydro-thermal generating systems. These techniques can take into account virtually all contingencies inherent in the operation of the system. Also, the operating policies that have an important effect on the performance of these systems can be realistically represented.     

Overview: Data Assimilation and Model Reduction

For the very large systems that arise in the environmental sciences, the available data are not sufficient to initiate a complex computational forecasting model. The technique of data assimilation enables measured observations (over time) to be combined with model predictions to generate accurate estimates of the system states – both current and future. An overview of data assimilation is presented here and the major types of assimilation method for treating very large nonlinear systems are described. Novel numerical assimilation techniques based on model reduction methods from control theory are then presented. The benefits of these techniques are demonstrated in a practical application from atmosphere and ocean modelling. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Near optimality of stochastic control in systems with unknown parameter processes

Stochastic control for systems with an unknown parameter is considered in this paper. The underlying problem is to minimize a functional subject to a system described by a singularly perturbed differential equation with an unknown parameter process driven by fast fluctuating random disturbances. This problem arises in the context of stochastic adaptive control, adaptive signal processing, and failure-prone manufacturing systems. Due to the nature of the wide-bandwidth noise processes, identifying the parameter process for eacht is very hard since the driving noise changes very rapidly. An alternative approach is used, and an auxiliary control problem is introduced to overcome the difficulties. By means of weak convergence methods and comparison control techniques, nearly optimal controls are obtained.This research was supported in part by the National Science Foundation under Grant DMS-9022139 and DMS-9224372.     

Nonlinear Filters and Operators and the Constant-Gain Extended Kalman Filter

Stochastic optimal control and estimation in nonlinear systemsis considered using a function-space approach. A condition underwhich nonlinear estimators are nondivergent is determined andthe stability of nonlinear systems which employ such estimatorsis established. The paper extends the contribution by Safanovand Athens and also offers alternative or more detailed proofswhere their work is discussed. The results are valuable practicallyand applications are demonstrated in examples.     

An upper bound on the cycle time of a stochastic marked graph using incomplete information on the transition firing time distributions

Stochastic marked graphs, a special class of stochastic timed Petri nets, are used for modelling and analyzing decision-free dynamic systems with uncertainties in timing. The model allows evaluating the performance of such systems under a cyclic process. Given the probabilistic characteristics of the transition times, the cycle time of the system can be determined from the initial marking. In this contribution, we compute an upper bound on the cycle time of a stochastic marked graph in case the probabilistic characteristics of the transition times are not fully specified.     

Gauss噪声扰动下的FitzHugh-Nagumo系统的随机稳定性

在Gauss噪声扰动下FitzHugh-Nagumo系统的随机稳定性是该文的研究目的．通过研究随机FitzHugh-Nagumo系统的动力学行为, 证明其存在唯一的、具有指数混合速度的不变测度．最后, 考察当噪声趋于0时不变测度的渐近行为．     

Adaptive step size numerical integration for stochastic differential equations with discontinuous drift and diffusion

Numerical Algorithms - Stochastic hybrid systems (SHSs) are a modelling framework for a cyber-physical system (CPS), used to simulate, validate, and verify safety critical controllers under...     

Multistep stochastic mirror descent for risk-averse convex stochastic programs based on extended polyhedral risk measures

We consider risk-averse convex stochastic programs expressed in terms of extended polyhedral risk measures. We derive computable confidence intervals on the optimal value of such stochastic programs using the Robust Stochastic Approximation and the Stochastic Mirror Descent (SMD) algorithms. When the objective functions are uniformly convex, we also propose a multistep extension of the Stochastic Mirror Descent algorithm and obtain confidence intervals on both the optimal values and optimal solutions. Numerical simulations show that our confidence intervals are much less conservative and are quicker to compute than previously obtained confidence intervals for SMD and that the multistep Stochastic Mirror Descent algorithm can obtain a good approximate solution much quicker than its nonmultistep counterpart.     

Choice of modelling technique for evaluating health care interventions

Economic evaluation, such as cost effectiveness analysis, provides a method for comparing healthcare interventions. These evaluations often use modelling techniques such as decision trees, Markov processes and discrete event simulations (DES). With the aid of examples from coronary heart disease, the use of these techniques in different health care situations is discussed. Guidelines for the choice of modelling technique are developed according to the characteristics of the health care intervention.The choice of modelling technique is shown to depend on the acceptance of the modelling technique, model ‘error’, model appropriateness, dimensionality and ease and speed of model development. Generally decision trees are suitable for acute interventions but they cannot model recursion and Markov models are suitable for simple chronic interventions. It is further recommended that population based models be used in order to provide health care outcomes for the likely cost, health benefits and cost effectiveness of the intervention. The population approach will complicate the construction of the model. DES will allow the modeller to construct more complex, dynamic and accurate systems but these may involve a corresponding increase in development time and expense. The modeller will need to make a judgement on the necessary complexity of the model in terms of interaction of individuals and model size and whether queuing for resources, resource constraints or the interactions between individuals are significant issues in the health care system.     

A Markov Type Model for Systems with Tolerable Down Times

This paper provides a modelling framework for the use of non-homogeneous Markovian techniques for components and systems, where the sojourn time at a state, or a class of states, may be limited by a given value. This approach is useful, for example, to build component models with constant repair times, and to model systems or components with tolerable down times. Tolerable down time models have appeared in the field of Boolean techniques for 10 years. A systematic Markovian approach applied to systems composed of several components, allows the interdependencies among the components to be precisely treated, which may cause large conservativeness, if the Boolean modelling technique is applied.     

Solving the optimal network problem

A heuristic method for solving the optimal network problem is proposed and shown to yield high quality results. Solution methods based on Branch-and-Bound techniques are also considered in some detail. The effects of making various approximations, when calculating lower bounds, is discussed and the concept of forced moves introduced.The various methods are applied to a series of problems which include networks with link construction cost not proportional to length and with trip demands tij not all equal.     

Centre manifolds for stochastic evolution equations

Stochastic invariant manifolds are crucial in modelling the dynamical behaviour of dynamical systems under uncertainty. Under the assumption of exponential trichotomy, existence and smoothness of centre manifolds for a class of stochastic evolution equations with linearly multiplicative noise are proved. The exponential attraction and approximation to centre manifolds are also discussed.     

Modelling a general standby system and evaluation of its performance

Redundancy or standby is a technique that has been widely applied to improving system reliability and availability in system design. In this paper, a general method for modelling standby system is proposed and system performance measures are derived. It is shown that the proposed general standby system includes the cases of cold, hot and warm standby systems with units of exponential distribution, which were studied in the literature, as special cases. An optimal allocation problem for a standby system is also discussed. Copyright © 2007 John Wiley & Sons, Ltd.     

Bayesian enhanced strategic decision making for reliability

Successful strategies for maintenance and replacement require good decisions. We might wish to determine how often to perform preventive maintenance, or the optimal time to replace a system. Alternatively, our interest might be in selecting a threshold to adopt for action under condition monitoring, or in choosing suitable warranty schemes for our products. Stochastic reliability models involving unknown parameters are often used to answer such questions. In common with other problems in operational research, some applications of maintenance and replacement are notorious for their lack of data. We present a general review and some new ideas for improving decisions by adopting Bayesian methodology to allow for the uncertainty of model parameters. These include recommendations for specifying suitable prior distributions using predictive elicitation and simple methods for Bayesian simulation. Practical demonstrations are given to illustrate the potential benefits of this approach.     

Reformulation in mathematical programming: An application to quantum chemistry

This paper concerns the application of reformulation techniques in mathematical programming to a specific problem arising in quantum chemistry, namely the solution of Hartree-Fock systems of equations, which describe atomic and molecular electronic wave functions based on the minimization of a functional of the energy. Their traditional solution method does not provide a guarantee of global optimality and its output depends on a provided initial starting point. We formulate this problem as a multi-extremal nonconvex polynomial programming problem, and solve it with a spatial Branch-and-Bound algorithm for global optimization. The lower bounds at each node are provided by reformulating the problem in such a way that its convex relaxation is tight. The validity of the proposed approach was established by successfully computing the ground-state of the helium and beryllium atoms.     

Simulation in manufacturing and business: A review

This paper reports the results of a review of simulation applications published within peer-reviewed literature between 1997 and 2006 to provide an up-to-date picture of the role of simulation techniques within manufacturing and business. The review is characterised by three factors: wide coverage, broad scope of the simulation techniques, and a focus on real-world applications. A structured methodology was followed to narrow down the search from around 20,000 papers to 281. Results include interesting trends and patterns. For instance, although discrete event simulation is the most popular technique, it has lower stakeholder engagement than other techniques, such as system dynamics or gaming. This is highly correlated with modelling lead time and purpose. Considering application areas, modelling is mostly used in scheduling. Finally, this review shows an increasing interest in hybrid modelling as an approach to cope with complex enterprise-wide systems.     

Optimization on sparse random hypergraphs and spin glasses

We establish that in the large degree limit, the value of certain optimization problems on sparse random hypergraphs is determined by an appropriate Gaussian optimization problem. This approach was initiated in Dembo et al. (2016) for extremal cuts of graphs. The usefulness of this technique is further illustrated by deriving the optimal value for Max q‐cut on graphs, Max XORSAT on Erdős–Rényi hypergraphs, and the min‐bisection the min‐bisection for the Stochastic Block Model.     

A hybrid data mining/simulation approach for modelling outpatient no-shows in clinic scheduling

This paper considers the outpatient no-show problem faced by a rural free clinic located in the south-eastern United States. Using data mining and simulation techniques, we develop sequencing schemes for patients, in order to optimize a combination of performance measures used at the clinic. We utilize association rule mining (ARM) to build a model for predicting patient no-shows; and then use a set covering optimization method to derive three manageable sets of rules for patient sequencing. Simulation is used to determine the optimal number of patients and to evaluate the models. The ARM technique presented here results in significant improvements over models that do not employ rules, supporting the conjecture that, when dealing with noisy data such as in an outpatient clinic, extracting partial patterns, as is done by ARM, can be of significant value for simulation modelling.