Scheduling unit-length jobs with precedence constraints of small height

We consider the problem of scheduling unit-length jobs on identical machines subject to precedence constraints. We show that natural scheduling rules fail when the precedence constraints form a collection of stars or a collection of complete bipartite graphs. We prove that the problem is in fact NP-hard on collections of stars when the input is given in a compact encoding, whereas it can be solved in polynomial time with standard adjacency list encoding. On a subclass of collections of stars and on collections of complete bipartite graphs we show that the problem can be solved in polynomial time even when the input is given in compact encoding, in both cases via non-trivial algorithms.     

On the restricted cores and the bounded core of games on distributive lattices

A game with precedence constraints is a TU game with restricted cooperation, where the set of feasible coalitions is a distributive lattice, hence generated by a partial order on the set of players. Its core may be unbounded, and the bounded core, which is the union of all bounded faces of the core, proves to be a useful solution concept in the framework of games with precedence constraints. Replacing the inequalities that define the core by equations for a collection of coalitions results in a face of the core. A collection of coalitions is called normal if its resulting face is bounded. The bounded core is the union of all faces corresponding to minimal normal collections. We show that two faces corresponding to distinct normal collections may be distinct. Moreover, we prove that for superadditive games and convex games only intersecting and nested minimal collection, respectively, are necessary. Finally, it is shown that the faces corresponding to pairwise distinct nested normal collections may be pairwise distinct, and we provide a means to generate all such collections.     

A threshold phenomenon in the Field-Noyes model of the Belousov-Zhabotinskii reaction

The Belousov-Zhabotinskii reaction is one of the most interesting and best understood chemical oscillators. It has been conjectured that certain biological phenomena have important features in common with this reaction. We investigate the Field-Noyes model of this reaction and demonstrate that there is a range of values of the stoichiometric parameter, f, over which the model exhibits “threshold phenomena.” That is, if a perturbation from the steady state exceeds a certain “threshold” value then a solution in the form of a “spike” results followed by its return to the steady state. We show that the underlying mathematical structure of this model resembles very closely the underlying mathematical structure of the Hodgkin-Huxley nerve conduction equations which exhibit the same sort of threshold phenomena.     

An Interactive Icon Index: Images of the Outer Planets

Abstract

We are interested in the exploratory analysis of large collections of complex objects. As an example, we are studying a large collection of digital images that has nearly 30,000 members. We regard each image in the collection as an individual observation. To facilitate our study we construct an index of the images in the collection. The index uses a small copy of each image (an icon or a “thumbnail”) to represent the full-size version. A large number of these thumbnails are laid out in a workstation window. We can interactively arrange and rearrange the thumbnails within the window. For example, we can sort the thumbnails by the values of a function computed from them or by the values of data associated with each of them. By the use of specialized equipment (a single-frame video disk recorder/player), we can instantly access any individual full-size image in the collection as a video image. We regard our software as an early development of statistical exploratory tools for studying collections of images and other complex objects in the same way we routinely study batches of numbers. We expect that the concept of a visual index will extend to other collections of complex objects besides images, for example, time series, functions, and text.     

Sequential heuristic for the two-dimensional bin-packing problem

A heuristic approach for the two-dimensional bin-packing problem is proposed. The algorithm is based on the sequential heuristic procedure that generates each pattern to produce some items and repeats until all items are produced. Both guillotine and non-guillotine patterns can be used. Each pattern is obtained from calling a pattern-generation procedure, where the objective is to maximize the pattern value. The item values are adjusted after the generation of each pattern using a value correction formula. The algorithm is compared with five published algorithms, using 50 groups of benchmark instances. The results indicate that the algorithm is the most efficient in improving solution quality.     

Algorithm for constructing an optimal control strategy in a nonlinear differential game with Lipschitz compactly supported payoff

For a zero-sum differential game, we consider an algorithm for constructing optimal control strategies with the use of backward minimax constructions. The dynamics of the game is not necessarily linear, the players’ controls satisfy geometric constraints, and the terminal payoff function satisfies the Lipschitz condition and is compactly supported. The game value function is computed by multilinear interpolation of grid functions. We show that the algorithm error can be arbitrarily small if the discretization step in time is sufficiently small and the discretization step in the state space has a higher smallness order than the time discretization step. We show that the algorithm can be used for differential games with a terminal set. We present the results of computations for a problem of conflict control of a nonlinear pendulum.     

Optimal techniques for class-dependent attribute discretization

Preprocessing of raw data has been shown to improve performance of knowledge discovery processes. Discretization of quantitative attributes is a key component of preprocessing and has the potential to greatly impact the efficiency of the process and the quality of its outcomes. In attribute discretization, the value domain of an attribute is partitioned into a finite set of intervals so that the attribute can be described using a small number of discrete representations. Discretization therefore involves two decisions, on the number of intervals and the placement of interval boundaries. Previous approaches for quantitative attribute discretization have used heuristic algorithms to identify partitions of the attribute value domain. Therefore, these approaches cannot be guaranteed to provide the optimal solution for the given discretization criterion and number of intervals. In this paper, we use linear programming (LP) methods to formulate the attribute discretization problem. The LP formulation allows the discretization criterion and the number of intervals to be integral considerations of the problem. We conduct experiments and identify optimal solutions for various discretization criteria and numbers of intervals.     

Regularized numerical integration of multibody dynamics with the generalized method

This paper discusses the consistent regularization property of the generalized α method when applied as an integrator to an initial value high index and singular differential-algebraic equation model of a multibody system. The regularization comes from within the discretization itself and the discretization remains consistent over the range of values the regularization parameter may take. The regularization involves increase of the smallest singular values of the ill-conditioned Jacobian of the discretization and is different from Baumgarte and similar techniques which tend to be inconsistent for poor choice of regularization parameter. This regularization also helps where pre-conditioning the Jacobian by scaling is of limited effect, for example, when the scleronomic constraints contain multiple closed loops or singular configuration or when high index path constraints are present. The feed-forward control in Kane’s equation models is additionally considered in the numerical examples to illustrate the effect of regularization. The discretization presented in this work is adopted to the first order DAE system (unlike the original method which is intended for second order systems) for its A-stability and same order of accuracy for positions and velocities.     

Third order convergent time discretization for parabolic optimal control problems with control constraints

We consider a priori error analysis for a discretization of a linear quadratic parabolic optimal control problem with box constraints on the time-dependent control variable. For such problems one can show that a time-discrete solution with second order convergence can be obtained by a first order discontinuous Galerkin time discretization for the state variable and either the variational discretization approach or a post-processing strategy for the control variable. Here, by combining the two approaches for the control variable, we demonstrate that almost third order convergence with respect to the size of the time steps can be achieved.     

Numerical integration of positive linear differential-algebraic systems

In the simulation of dynamical processes in economy, social sciences, biology or chemistry, the analyzed values often represent non-negative quantities like the amount of goods or individuals or the density of a chemical or biological species. Such systems are typically described by positive ordinary differential equations (ODEs) that have a non-negative solution for every non-negative initial value. Besides positivity, these processes often are subject to algebraic constraints that result from conservation laws, limitation of resources, or balance conditions and thus the models are differential-algebraic equations (DAEs). In this work, we present conditions under which both these properties, the positivity as well as the algebraic constraints, are preserved in the numerical simulation by Runge–Kutta or multistep discretization methods. Using a decomposition approach, we separate the dynamic and the algebraic equations of a given linear, positive DAE to give positivity preserving conditions for each part separately. For the dynamic part, we generalize the results for positive ODEs to DAEs using the solution representation via Drazin inverses. For the algebraic part, we use the consistency conditions of the discretization method to derive conditions under which this part of the approximation overestimates the exact solution and thus is non-negative. We analyze these conditions for some common Runge–Kutta and multistep methods and observe that for index-1 systems and stiffly accurate Runge–Kutta methods, positivity is conditionally preserved under similar conditions as for ODEs. For higher index problems, however, none of the common methods is suitable.     

A sparse nonlinear optimization algorithm

One of the most effective numerical techniques for solving nonlinear programming problems is the sequential quadratic programming approach. Many large nonlinear programming problems arise naturally in data fitting and when discretization techniques are applied to systems described by ordinary or partial differential equations. Problems of this type are characterized by matrices which are large and sparse. This paper describes a nonlinear programming algorithm which exploits the matrix sparsity produced by these applications. Numerical experience is reported for a collection of trajectory optimization problems with nonlinear equality and inequality constraints.The authors wish to acknowledge the insightful contributions of Dr. William Huffman.     

Local Near Sets: Pattern Discovery in Proximity Spaces

The focus of this article is on various approaches to discerning patterns in nonempty sets endowed with a proximity (nearness) relation. Patterns arise in repetitions of some form in the arrangement of the parts of a set. To simplify the steps leading to pattern discovery, an approach inspired by M. Kat?tov is used, where one proximitises certain parts of a nonempty set, rather than proximitise the whole set. In effect, this is a divide-and-conquer approach to pattern discovery. This leads to a study of patterns that are collections of near sets. An important practical outcome of this approach is the discovery of patterns in proximity spaces.     

Efficient Threshold Selection for Multivariate Total Variation Denoising

Total variation (TV) denoising is still attracting attention with theoretical and computational motivations, for its conceptual simplicity of solving a lasso-like convex problem and its good properties for preserving sharp edges and contours in objects with spatial structures like natural images, although more modern and recent techniques specifically tailored to image processing have been developed. TV induces variation-sparsity in the sense that the reconstruction is piecewise constant with a small number of jumps. A threshold parameter λ controls the number of jumps and the quality of the estimation. Since calculation of the TV estimate in high dimension is computationally intensive for a given λ, we propose to calculate the TV estimate for only two sequential λ’s. Our adaptive procedure is based on large deviation of stochastic processes and extreme value theory. We also show that TV can perform exact segmentation in dimension one, under an alternating sign condition for some prescribed threshold. We apply our procedure to denoise a collection of 1D and 2D test signals verifying empirically the effectiveness of our approach. Codes are given to reproduce our results in a provided PURL.     

Randomized post-optimization of covering arrays

The construction of covering arrays with the fewest rows remains a challenging problem. Most computational and recursive constructions result in extensive repetition of coverage. While some is necessary, some is not. By reducing the repeated coverage, metaheuristic search techniques typically outperform simpler computational methods, but they have been applied in a limited set of cases. Time constraints often prevent them from finding an array of competitive size. We examine a different approach. Having used a simple computation or construction to find a covering array, we employ a post-optimization technique that repeatedly adjusts the array in an attempt to reduce its number of rows. At every stage the array retains full coverage. We demonstrate its value on a collection of previously best known arrays by eliminating, in some cases, 10% of their rows. In the well-studied case of strength two with twenty factors having ten values each, post-optimization produces a covering array with only 162 rows, improving on a wide variety of computational and combinatorial methods. We identify certain important features of covering arrays for which post-optimization is successful.     

The effects of symmetric/asymmetric boundary conditions on the flow of an internally heated fluid

The two-dimensional flow of an internally heated fluid in a circular vessel has been investigated by using a finite-control-volume numerical model. It has been found that, when symmetry constraints are imposed along the vertical midplane of the vessel, two distinct flow patterns can he predicted for the same operating conditions, a jet-momentum-dominated pattern and buoyancy-dominated pattern. These patterns occur in an operating region where momentum and buoyancy forces are of comparable magnitude. However, when the symmetry constraints are removed and the full vessel cross section is modeled, only the buoyancy-dominated pattern is observed. Results for the two cases are described and possible reasons for the differences in behavior are discussed.     

Generating a Random Collection of Discrete Joint Probability Distributions Subject to Partial Information

In this paper, we develop a practical and flexible methodology for generating a random collection of discrete joint probability distributions, subject to a specified information set, which can be expressed as a set of linear constraints (e.g., marginal assessments, moments, or pairwise correlations). Our approach begins with the construction of a polytope using this set of linear constraints. This polytope defines the set of all joint distributions that match the given information; we refer to this set as the “truth set.” We then implement a Monte Carlo procedure, the Hit-and-Run algorithm, to sample points uniformly from the truth set. Each sampled point is a joint distribution that matches the specified information. We provide guidelines to determine the quality of this sampled collection. The sampled points can be used to solve optimization models and to simulate systems under different uncertainty scenarios.     

Reduced Dynamics of the Non-holonomic Whipple Bicycle

Though the bicycle is a familiar object of everyday life, modeling its full nonlinear three-dimensional dynamics in a closed symbolic form is a difficult issue for classical mechanics. In this article, we address this issue without resorting to the usual simplifications on the bicycle kinematics nor its dynamics. To derive this model, we use a general reduction-based approach in the principal fiber bundle of configurations of the three-dimensional bicycle. This includes a geometrically exact model of the contacts between the wheels and the ground, the explicit calculation of the kernel of constraints, along with the dynamics of the system free of any external forces, and its projection onto the kernel of admissible velocities. The approach takes benefits of the intrinsic formulation of geometric mechanics. Along the path toward the final equations, we show that the exact model of the bicycle dynamics requires to cope with a set of non-symmetric constraints with respect to the structural group of its configuration fiber bundle. The final reduced dynamics are simulated on several examples representative of the bicycle. As expected the constraints imposed by the ground contacts, as well as the energy conservation, are satisfied, while the dynamics can be numerically integrated in real time.     

Multiple Imputation by Ordered Monotone Blocks With Application to the Anthrax Vaccine Research Program

Multiple imputation (MI) has become a standard statistical technique for dealing with missing values. The CDC Anthrax Vaccine Research Program (AVRP) dataset created new challenges for MI due to the large number of variables of different types and the limited sample size. A common method for imputing missing data in such complex studies is to specify, for each of J variables with missing values, a univariate conditional distribution given all other variables, and then to draw imputations by iterating over the J conditional distributions. Such fully conditional imputation strategies have the theoretical drawback that the conditional distributions may be incompatible. When the missingness pattern is monotone, a theoretically valid approach is to specify, for each variable with missing values, a conditional distribution given the variables with fewer or the same number of missing values and sequentially draw from these distributions. In this article, we propose the “multiple imputation by ordered monotone blocks” approach, which combines these two basic approaches by decomposing any missingness pattern into a collection of smaller “constructed” monotone missingness patterns, and iterating. We apply this strategy to impute the missing data in the AVRP interim data. Supplemental materials, including all source code and a synthetic example dataset, are available online.     

On The Relationships of Cluster Measures and Distributions of Distances in Compact Metric Spaces

A compact metric space with a bounded Borel measure is considered. Any measurable set of diameter not exceeding r is called r-cluster. The existence of a collection consisting of a fixed number of 2r-clusters possessing the following properties is investigated: the clusters are located at the distance r from each other and the collection measure (the total measure of the clusters in the collection) is close to the measure of the entire space. It is proved that there exists a collection with a maximum measure among such collections. The concept of r-parametric discretization of the distribution of distances into short, medium, and long distances is defined. In terms of this discretization, a lower bound on the measure of the maximum-measure collection is obtained.     

Coupled nonlinear oscillators and the symmetries of animal gaits

Summary Animal locomotion typically employs several distinct periodic patterns of leg movements, known as gaits. It has long been observed that most gaits possess a degree of symmetry. Our aim is to draw attention to some remarkable parallels between the generalities of coupled nonlinear oscillators and the observed symmetries of gaits, and to describe how this observation might impose constraints on the general structure of the neural circuits, i.e. central pattern generators, that control locomotion. We compare the symmetries of gaits with the symmetry-breaking oscillation patterns that should be expected in various networks of symmetrically coupled nonlinear oscillators. We discuss the possibility that transitions between gaits may be modeled as symmetry-breaking bifurcations of such oscillator networks. The emphasis is on general model-independent features of such networks, rather than on specific models. Each type of network generates a characteristic set of gait symmetries, so our results may be interpreted as an analysis of the general structure required of a central pattern generator in order to produce the types of gait observed in the natural world. The approach leads to natural hierarchies of gaits, ordered by symmetry, and to natural sequences of gait bifurcations. We briefly discuss how the ideas could be extended to hexapodal gaits.