Smoothing algorithms for state–space models

Two-filter smoothing is a principled approach for performing optimal smoothing in non-linear non-Gaussian state–space models where the smoothing distributions are computed through the combination of ‘forward’ and ‘backward’ time filters. The ‘forward’ filter is the standard Bayesian filter but the ‘backward’ filter, generally referred to as the backward information filter, is not a probability measure on the space of the hidden Markov process. In cases where the backward information filter can be computed in closed form, this technical point is not important. However, for general state–space models where there is no closed form expression, this prohibits the use of flexible numerical techniques such as Sequential Monte Carlo (SMC) to approximate the two-filter smoothing formula. We propose here a generalised two-filter smoothing formula which only requires approximating probability distributions and applies to any state–space model, removing the need to make restrictive assumptions used in previous approaches to this problem. SMC algorithms are developed to implement this generalised recursion and we illustrate their performance on various problems.     

Students,mathematics, and technology: assessing the present – challenging the future

This paper is concerned with identifying and assessing the impacts of various technologically enriched approaches to mathematics learning. Its purpose is to address the usefulness of emerging knowledge to enhance practice, and to contribute to theorizing about technology-based learning. Hence the main drivers are intentions to identify and elaborate on obstacles, errors, and unresolved problems on the one hand, and positives and insights on the other. The paper tells a cautionary tale about expectations of technology-enhanced learning, while simultaneously uncovering a rich base from which to theorize and test new appreciations of what is involved when students, technology, and mathematics connect in learning settings. A summary assessment is that this area still very much represents work in progress, but there is now a heightened realization, at least among those not transfixed by technological blindness, that the search for ultimate answers will require much greater exploration of machine–mathematics–learner relationships.     

Partially dynamic vehicle routing—models and algorithms

In this paper we propose a framework for dynamic routing systems based on their degree of dynamism. Next, we consider its impact on solution methodology and quality. Specifically, we introduce the Partially Dynamic Travelling Repairman Problem and describe several dynamic policies to minimize routing costs. The results of our computational study indicate that increasing the dynamic level results in a linear increase in route length for all policies studied. Furthermore, a Nearest Neighbour policy performed, on the average, uniformly better than the other dispatching rules studied. Among these, a Partitioning policy produced only slightly higher average route lengths.     

Are there elimination algorithms for the permanent?

We define the class of elimination algorithms. There are algebraic algorithms for evaluating multivariate polynomials, and include as a special case Gaussian elimination for evaluating the determinant. We show how to find the linear symmetries of a polynomial, defined appropriately, and use these methods to find the linear symmetries of the permanent and determinant. We show that in contrast to the Gaussian elimination algorithm for the determinant, there is no elimination algorithm for the permanent.     

Symmetries,the current function,and exact solutions for Broadwell’s two-dimensional stationary kinetic model

We investigate the Broadwell stationary kinetic model for four velocities on a plane using the current function that satisfies a partial differential equation. For this equation, we evaluate the algebras of classical and nonclassical symmetries and then construct invariant solutions. All classes of solutions describe nonpotential flows. We consider the relation between nonclassical symmetries and previously obtained solutions.     

Influence of ensemble surrogate models and sampling strategy on the solution quality of algorithms for computationally expensive black-box global optimization problems

This paper examines the influence of two major aspects on the solution quality of surrogate model algorithms for computationally expensive black-box global optimization problems, namely the surrogate model choice and the method of iteratively selecting sample points. A random sampling strategy (algorithm SO-M-c) and a strategy where the minimum point of the response surface is used as new sample point (algorithm SO-M-s) are compared in numerical experiments. Various surrogate models and their combinations have been used within the SO-M-c and SO-M-s sampling frameworks. The Dempster–Shafer Theory approach used in the algorithm by Müller and Piché (J Glob Optim 51:79–104, 2011) has been used for combining the surrogate models. The algorithms are numerically compared on 13 deterministic literature test problems with 2–30 dimensions, an application problem that deals with groundwater bioremediation, and an application that arises in energy generation using tethered kites. NOMAD and the particle swarm pattern search algorithm (PSWARM), which are derivative-free optimization methods, have been included in the comparison. The algorithms have also been compared to a kriging method that uses the expected improvement as sampling strategy (FEI), which is similar to the Efficient Global Optimization (EGO) algorithm. Data and performance profiles show that surrogate model combinations containing the cubic radial basis function (RBF) model work best regardless of the sampling strategy, whereas using only a polynomial regression model should be avoided. Kriging and combinations including kriging perform in general worse than when RBF models are used. NOMAD, PSWARM, and FEI perform for most problems worse than SO-M-s and SO-M-c. Within the scope of this study a Matlab toolbox has been developed that allows the user to choose, among others, between various sampling strategies and surrogate models and their combinations. The open source toolbox is available from the authors upon request.     

Reliability and efficiency of algorithms for computing the significance of the Mann–Whitney test

Motivated by recent applications of the Mann–Whitney U test to large data sets we took a critical look at current methods for computing its significance. Surprisingly, we found that the two fastest and most popular tools for exact computation of the test significance, Dinneen and Blakesley’s and Harding’s, can exhibit large numerical errors even in moderately large datasets. In addition, another method proposed by Pagano and Tritchler also suffers from a similar numerical instability and can produce inaccurate results. This motivated our development of a new algorithm, mw-sFFT, for the exact computation of the Mann–Whitney test with no ties. Among the class of exact algorithms that are numerically stable, mw-sFFT has the best complexity: O(m ² n) versus O(m ² n ²) for others, where m and n are the two sample sizes. This asymptotic efficiency is also reflected in the practical runtime of the algorithm. In addition, we also present a rigorous analysis of the propagation of numerical errors in mw-sFFT to derive an error guarantee for the values computed by the algorithm. The reliability and efficiency of mw-sFFT make it a valuable tool in compuational applications and we plan to provide open-source libraries for it in C++ and Matlab.     

On the convergence of genetic algorithms – a variational approach

A variational approach is introduced to study the existence and uniqueness of stationary states and (exponential) stability of genetic algorithms with mutation and interactive selection.Mathematics Subject Classification (2000): 35J20 (90C30, 92D25, 35J60, 31C25)     

Graph homomorphisms,the Tutte polynomial and “q-state Potts uniqueness”

We establish for which weighted graphs H homomorphism functions from multigraphs G to H are specializations of the Tutte polynomial of G, answering a question of Freedman, Lovász and Schrijver.We introduce a new property of graphs called “q-state Potts uniqueness” and relate it to chromatic and Tutte uniqueness, and also to “chromatic–flow uniqueness”, recently studied by Duan, Wu and Yu.     

Maximum utility product pricing models and algorithms based on reservation price

We consider a revenue management model for pricing a product line with several customer segments under the assumption that customers’ product choices are determined entirely by their reservation prices. We highlight key mathematical properties of the maximum utility model and formulate it as a mixed-integer programming problem, design heuristics and valid cuts. We further present extensions of the models to deal with various practical issues arising in applications. Our computational experiments with real data from the tourism sector as well as with the randomly generated data show the effectiveness of our approach.     

Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem

In this paper, we propose approximate and exact algorithms for the double constrained two-dimensional guillotine cutting stock problem (DCTDC). The approximate algorithm is a two-stage procedure. The first stage attempts to produce a starting feasible solution to DCTDC by solving a single constrained two dimensional cutting problem, CDTC. If the solution to CTDC is not feasible to DCTDC, the second stage is used to eliminate non-feasibility. The exact algorithm is a branch-and-bound that uses efficient lower and upper bounding schemes. It starts with a lower bound reached by the approximate two-stage algorithm. At each internal node of the branching tree, a tailored upper bound is obtained by solving (relaxed) knapsack problems. To speed up the branch and bound, we implement, in addition to ordered data structures of lists, symmetry, duplicate, and non-feasibility detection strategies which fathom some unnecessary branches. We evaluate the performance of the algorithm on different problem instances which can become benchmark problems for the cutting and packing literature.     

Curvature invariant and generalized canonical operator models – II

In Douglas et al. (2012) [9], the authors investigated a family of quotient Hilbert modules in the Cowen–Douglas class over the unit disk constructed from classical Hilbert modules such as the Hardy and Bergman modules. In this paper we extend the results to the multivariable case of higher multiplicity. Moreover, similarity as well as isomorphism results are obtained.     

Bounds for the Least Laplacian Eigenvalue of a Signed Graph

A signed graph is a graph with a sign attached to each edge. This paper extends some fundamental concepts of the Laplacian matrices from graphs to signed graphs. In particular, the relationships between the least Laplacian eigenvalue and the unbalancedness of a signed graph are investigated.     

Discrete and geometric Branch and Bound algorithms for?medical image registration

Aiming at the development of an exact solution method for registration problems, we present two different Branch & Bound algorithms for a mixed integer programming formulation of the problem. The first B&B algorithm branches on binary assignment variables and makes use of an optimality condition that is derived from a graph matching formulation. The second, geometric B&B algorithm applies a geometric branching strategy on continuous transformation variables. The two approaches are compared for synthetic test examples as well as for 2-dimensional medical data. The results show that medium sized problem instances can be solved to global optimality in a reasonable amount of time.     

Fast algorithms for implementation of the Green’s function

This paper is devoted to new fast algorithms for implementation of the Green’s function for the Helmholtz operator in high-frequency regions in periodic and helical structures.     

Thresholded covering algorithms for robust and max–min optimization

In a two-stage robust covering problem, one of several possible scenarios will appear tomorrow and require to be covered, but costs are higher tomorrow than today. What should you anticipatorily buy today, so that the worst-case cost (summed over both days) is minimized? We consider the \(k\) -robust model where the possible scenarios tomorrow are given by all demand-subsets of size \(k\) . In this paper, we give the following simple and intuitive template for \(k\) -robust covering problems: having built some anticipatory solution, if there exists a single demand whose augmentation cost is larger than some threshold, augment the anticipatory solution to cover this demand as well, and repeat. We show that this template gives good approximation algorithms for \(k\) -robust versions of many standard covering problems: set cover, Steiner tree, Steiner forest, minimum-cut and multicut. Our \(k\) -robust approximation ratios nearly match the best bounds known for their deterministic counterparts. The main technical contribution lies in proving certain net-type properties for these covering problems, which are based on dual-rounding and primal–dual ideas; these properties might be of some independent interest. As a by-product of our techniques, we also get algorithms for max–min problems of the form: “given a covering problem instance, which \(k\) of the elements are costliest to cover?” For the problems mentioned above, we show that their \(k\) -max–min versions have performance guarantees similar to those for the \(k\) -robust problems.