Variable-Number Sample-Path Optimization

The sample-path method is one of the most important tools in simulation-based optimization. The basic idea of the method is to approximate the expected simulation output by the average of sample observations with a common random number sequence. In this paper, we describe a new variant of Powell’s unconstrained optimization by quadratic approximation (UOBYQA) method, which integrates a Bayesian variable-number sample-path (VNSP) scheme to choose appropriate number of samples at each iteration. The statistically accurate scheme determines the number of simulation runs, and guarantees the global convergence of the algorithm. The VNSP scheme saves a significant amount of simulation operations compared to general purpose ‘fixed-number’ sample-path methods. We present numerical results based on the new algorithm.     

A useful transform of standard input data for a classical NP-complete problem

The archetypal symmetric travelling salesman problem can be seen in a new and interesting way, by using first a standard preparatory phase of input data, and then by applying a transform from the set D of ‘distances’ among ‘cities’ and the set B of ‘loss of optimality’.The specific form of D→B transform is introduced and discussed. In order to show in realistic terms the interest of the approach proposed, a class of ‘diffusive’ heuristic procedures operating from B is defined.An example of solution by an algorithm included in this class is completely worked out; an outline of computational tests done on the same algorithm is also given.     

An application of homotopy to solving linear programs

Consider a linear program inm inequality constraints andn nonnegative variables. An application of homotopy to the problem gives an algorithm similar to Dantzig's self-dual method. Howeve, the homotopy approach allows one to recognize several previously undescribed and potentially interesting properties. For example, the algorithm can be initiated in such a way as to produce a path which is primal-dual feasible. Moreover, one can theoretically identify an orthant with the property that if one initiates the algorithm at any point in that orthant then, after a ‘phase I’ requiring at most min{m, n} pivots, convergence is obtained in one step.     

Interpretation of fuzzy data by means of fuzzy rules with applications to speech recognition

Recently, a speech recognition methodology has been proposed which has as one of its main principles the explicit assumption of intrinsic uncertainty of the data (speech signals) and inexactness of the knowledge (acoustic phonetic, etc…) available to interpret them. The main problem presented by this methodology is that of parsing ‘fuzzy data’ by means of ‘fuzzy rules’. To solve this problem, an appropriate fuzzy parsing and interpretation scheme has been proposed. It assumes the data to be represented as strings of ‘fuzzy symbols’, defined as fuzzy sets over the appropriate set of categories, and knowledge as finite-state networks with the arcs labelled by fuzzy symbols of the same type. A formal presentation of this scheme is the main topic of this paper. Included is a brief discussion of the application to Automatic Speech Recognition, and a summary of some results obtained from an implementation example.     

Study of the plant recolonization process in a burnt heathland using a method of hierarchical classification

The reinstallation of different plant-species and their evolution during a ten-year period in a heathland after a fire accident has been studied by using the algorithm of heirarchical classification based on correlation (ABC) introduced by Tallur.¹ Classification under contiguity restraint of the set of observation points (subintervals of an experimental observation line) enables one to determine the ‘patches’ having uniform vegetation structure. Lerman's ‘local’ and ‘global’ statistics are used to condense the classification tree to its significant nodes and to choose the most significant partition. x² statistics are proposed to test whether a given patch has a ‘significant’ vegetation structure and if the association between a patch and a plant species is significant. Evolution of the horizontal structure of vegetation is studied by comparing the sets of patches obtained at successive observation dates and the corresponding dominant species.     

A tale of two algorithms

Real numbers are often a missing link in mathematical education. The standard working assumption in calculus courses is that there exists a system of ‘numbers’, extending the rational number system, adequate for measuring continuous quantities. Moreover, that such ‘numbers’ are in one-to-one correspondence with points on a ‘number line’. But typically real ‘numbers’ are not systematically presented via any constructive method. While taken for granted, they are one of the most commonly used mathematical objects. This paper proposes a geometric algorithm, extending the long division algorithm, which leads to a constructive definition of real numbers. It proceeds to describe a direct algorithm for adding ‘real numbers’. Combined use of the two algorithms enables a smooth and meaningful presentation, offering a double image (geometric and numerical) of real numbers in decimal notation. An early such presentation is of both conceptual and practical importance.     

Bits or shots in combat? The generalized Deitchman model of guerrilla warfare

We generalize Deitchman’s guerrilla warfare model to account for trade-off between intelligence (‘bits’) and firepower (‘shots’). Intelligent targeting leads to aimed fire; absence of intelligence leads to unaimed fire, dependent on targets’ density. We propose a new Lanchester-type model that mixes aimed and unaimed fire, the balance between these being determined by quality of information. We derive the model’s conserved quantity, and use it to analyze the trade-off between investments in intelligence and in firepower—for example, in counterinsurgency operations.     

A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration

This article tackles the multi-trip vehicle routing problem with time windows and limited duration. A trip is a timed route such that a succession of trips can be assigned to one vehicle. We provide an exact two-phase algorithm to solve it. The first phase enumerates possible ordered lists of clients which match the maximum trip duration criterion. The second phase uses a Branch and Price scheme to generate and choose a best set of trips so that all customers are visited. We propose a set covering formulation as the column generation master problem, where columns (variables) represent trips. The sub-problem selects appropriate timing for trips and has a pseudo-polynomial complexity. Computational results on Solomon’s benchmarks are presented. The computational times obtained with our new algorithm are much lower than the ones recently obtained in the only two studies published on this problem to date.     

A Semidefinite Programming Based Polyhedral Cut and Price Approach for the Maxcut Problem

We investigate solution of the maximum cut problem using a polyhedral cut and price approach. The dual of the well-known SDP relaxation of maxcut is formulated as a semi-infinite linear programming problem, which is solved within an interior point cutting plane algorithm in a dual setting; this constitutes the pricing (column generation) phase of the algorithm. Cutting planes based on the polyhedral theory of the maxcut problem are then added to the primal problem in order to improve the SDP relaxation; this is the cutting phase of the algorithm. We provide computational results, and compare these results with a standard SDP cutting plane scheme. Research supported in part by NSF grant numbers CCR–9901822 and DMS–0317323. Work done as part of the first authors Ph.D. dissertation at RPI.     

Hybrid projective synchronization of complex Duffing–Holmes oscillators with application to image encryption

Many works on hybrid projective synchronization (or simply ‘HPS’ for short) of nonlinear real dynamic systems have been performed, while the HPS of chaotic complex systems and its application have not been extensively studied. In this paper, the HPS of complex Duffing–Holmes oscillators with known and unknown parameters is separately investigated via nonlinear control. The adaptive control methods and explicit expressions are derived for controllers and parameters estimation law, which are respectively used to achieve HPS. These expressions on controllers are tested numerically, which are in excellent agreement with theory analysis. The proposed synchronization scheme is applied to image encryption with exclusive or (or simply ‘XOR’ for short). The related security analysis shows the high security of the encryption scheme. Concerning the complex Duffing–Holmes oscillator, we also discuss its chaotic properties via the maximum Lyapunov exponent. Copyright © 2017 John Wiley & Sons, Ltd.     

A tale of mathematical myth-making: E T Bell and the ‘arithmetization of algebra’

Throughout E T Bell’s writings on mathematics, both those aimed at other mathematicians and those for a popular audience, we find him endeavouring to promote abstract algebra generally, and the postulational method in particular. Bell evidently felt that the adoption of the latter approach to algebra (a process that he termed the ‘arithmetization of algebra’) would lend the subject something akin to the level of rigour that analysis had achieved in the nineteenth century. However, despite promoting this point of view, it is not so much in evidence in Bell’s own mathematical work. I offer an explanation for this apparent contradiction in terms of Bell’s infamous penchant for mathematical ‘myth-making’.     

Developing professional judgement with the aid of a ‘low-profile’ group support system

This paper reports positive results from an application of one type of group support system (GSS) to a training application. Reviews of the findings of other trials of GSS have been mixed, and inconclusive. We describe the results of a series of seven training sessions in a field-based application of group process support. The subjects were professionals working in various agencies concerned with the welfare of older people. A ‘low-profile’ type of group support system, based on wireless handsets, was used. This design enabled responses from each participant to be input and displayed anonymously. Each session was aimed at stimulating a dialogue focused on the reasons for differences of judgement, as displayed on a single projected feedback screen. Changes of individual judgements were recorded for subsequent analysis and comparison with already known ‘expert judgements’. Frequent changes of judgement were recorded. A significant proportion of these were related to an improvement, which could not be explained as simply the result of conforming behaviour. We propose that the mode of operation and design of a ‘low-profile’ GSS have the potential to create a learning environment by reducing personal anxieties while encouraging group-based learning with focussed conversation. We conclude that this type of GSS design is particularly suited to ‘selective’-type tasks in groups.     

A unifying approach to solve a class of rank-three programs involving linear and quadratic functions

The aim of this paper is two-fold. First, the so-called ‘optimal level solutions’ method is described in a new unifying framework with the aim to provide an algorithmic scheme able to approach various different classes of problems. Then, the ‘optimal level solutions’ method is used to solve a class of low-rank programmes involving linear and quadratic functions and having a polyhedral feasible region. In particular, the considered class of programmes covers, among all, rank-three d.c., multiplicative and fractional programmes. Some optimality conditions are used to improve the performance of the proposed algorithm.     

Optimal and heuristic algorithms for multiproduct uncapacitated facility location

We consider a generalization of the classic uncapacitated facility location problem (UFLP) in which customers require multiple products. We call this the multiproduct uncapacitated facility location problem (MUFLP). In MUFLP, in addition to a fixed cost for opening a facility, a fixed cost is incurred for each product that a facility is equipped to handle. Also, an assignment cost is incurred for satisfying a customer's requirement for a particular product at a chosen facility. We describe a branch-and-bound algorithm for MUFLP. Lower bounds are obtained by solving a UFLP subproblem for each product using a dual ascent routine. We also describe a heuristic branch-and-bound procedure in which the solutions to the subproblems at a given node might not generate a true lower bound. To generate a feasible solution, a ‘superposition’ heuristic based on solving UFLP subproblems for each product, as well as a ‘drop’ heuristic that eliminates facilities and equipment from the solution in a step-by-step manner, are given. Computational results are reported.     

Factors contributing to academic achievement: a Bayesian structure equation modelling study

In Iran, high school graduates enter university after taking a very difficult entrance exam called the Konkoor. Therefore, only the top-performing students are admitted by universities to continue their bachelor's education in statistics. Surprisingly, statistically, most of such students fall into the following categories: (1) do not succeed in their education despite their excellent performance on the Konkoor and in high school; (2) graduate with a grade point average (GPA) that is considerably lower than their high school GPA; (3) continue their master's education in majors other than statistics and (4) try to find jobs unrelated to statistics. This article employs the well-known and powerful statistical technique, the Bayesian structural equation modelling (SEM), to study the academic success of recent graduates who have studied statistics at Shahid Beheshti University in Iran. This research: (i) considered academic success as a latent variable, which was measured by GPA and other academic success (see below) of students in the target population; (ii) employed the Bayesian SEM, which works properly for small sample sizes and ordinal variables; (iii), which is taken from the literature, developed five main factors that affected academic success and (iv) considered several standard psychological tests and measured characteristics such as ‘self-esteem’ and ‘anxiety’. We then study the impact of such factors on the academic success of the target population. Six factors that positively impact student academic success were identified in the following order of relative impact (from greatest to least): ‘Teaching–Evaluation’, ‘Learner’, ‘Environment’, ‘Family’, ‘Curriculum’ and ‘Teaching Knowledge’. Particularly, influential variables within each factor have also been noted.     

Asymptotic structural characteristics of fuzzy measure and their applications

In fuzzy measure theory, as Sugeno's fuzzy measures lose additivity in general, the concept ‘almost’, which is well known in classical measure theory, splits into two different concepts, ‘almost’ and ‘pseudo-almost’. In order to replace the additivity, it is quite necessary to investigate some asymptotic behaviors of a fuzzy measure at sequences of sets which are called ‘waxing’ and ‘waning’, and to introduce some new concepts, such as ‘autocontinuity’, ‘converse-autocontinuity’ and ‘pseudo-autocontinuity’. These concepts describe some asymptotic structural characteristics of a fuzzy measure.In this paper, by means of the asymptotic structural characteristics of fuzzy measure, we also give four forms of generalization for both Egoroff's theorem, Riesz's theorem and Lebesgue's theorem respectively, and prove the almost everywhere (pseudo-almost everywhere) convergence theorem, the convergence in measure (pseudo-in measure) theorem of the sequence of fuzzy integrals. In the last two theorems, the employed conditions are not only sufficient, but also necessary.     

Reduced basis methods with adaptive snapshot computations

We use asymptotically optimal adaptive numerical methods (here specifically a wavelet scheme) for snapshot computations within the offline phase of the Reduced Basis Method (RBM). The resulting discretizations for each snapshot (i.e., parameter-dependent) do not permit the standard RB ‘truth space’, but allow for error estimation of the RB approximation with respect to the exact solution of the considered parameterized partial differential equation. The residual-based a posteriori error estimators are computed by an adaptive dual wavelet expansion, which allows us to compute a surrogate of the dual norm of the residual. The resulting adaptive RBM is analyzed. We show the convergence of the resulting adaptive greedy method. Numerical experiments for stationary and instationary problems underline the potential of this approach.     

Analysis of mathematical programming problems prior to applying the simplex algorithm

Large practical linear and integer programming problems are not always presented in a form which is the most compact representation of the problem. Such problems are likely to posses generalized upper bound(GUB) and related structures which may be exploited by algorithms designed to solve them efficiently. The steps of an algorithm which by repeated application reduces the rows, columns, and bounds in a problem matrix and leads to the freeing of some variables are first presented. The ‘unbounded solution’ and ‘no feasible solution’ conditions may also be detected by this. Computational results of applying this algorithm are presented and discussed. An algorithm to detect structure is then described. This algorithm identifies sets of variables and the corresponding constraint relationships so that the total number of GUB-type constraints is maximized. Comparisons of computational results of applying different heuristics in this algorithm are presented and discussed.     

A branch and bound algorithm for solving the multiple-choice knapsack problem

The multiple-choice knapsack problem is a binary knapsack problem with the addition of disjoint multiple-choice constraints. We describe a branch and bound algorithm based on embedding Glover and Klingman's method for the associated linear program within a depth-first search procedure. A heuristic is used to find a starting dual feasible solution to the associated linear program and a ‘pegging’ test is employed to reduce the size of the problem for the enumeration phase. Computational experience and comparisons with the code of Nauss and an algorithm of Armstrong et al. for the same problem are reported.