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.     

Control with a Guide in the Guarantee Optimization Problem under Functional Constraints on the Disturbance

A motion control problem for a dynamic system under disturbances is considered on a finite time interval. There are compact geometric constraints on the values of the control and disturbance. The equilibrium condition in the small game is not assumed. The aim of the control is to minimize a given terminal performance index. The guaranteed result optimization problem is posed in the context of the game-theoretical approach. In the case when realizations of the disturbance belong to some a priori unknown compact subset of L₁ (the space of functions that are Lebesgue summable with the norm), we propose a new discrete-time control procedure with a guide. The proximity between the motions of the system and the guide is provided by the dynamic reconstruction of the disturbance. The quality of the control process is achieved by using an optimal counter-strategy in the guide. Conditions on the equations of motion under which this procedure ensures an optimal guaranteed result in the class of quasi-strategies are given. The scheme of the proof makes it possible to estimate the deviation of the realized value of the performance index from the value of the optimal result depending on the discretization parameter. Illustrative examples are given.     

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.     

Asymptotic Joint Normality of Counts of Uncorrelated Motifs in Recursive Trees

We study the fringe of random recursive trees, by analyzing the joint distribution of the counts of uncorrelated motifs. Our approach allows for finite and countably infinite collections. To be able to deal with the collection when it is infinitely countable, we use measure-theoretic themes. Each member of a collection of motifs occurs a certain number of times on the fringe. We show that these numbers, under appropriate normalization, have a limiting joint multivariate normal distribution. We give a complete characterization of the asymptotic covariance matrix. The methods of proof include contraction in a metric space of distribution functions to a fixed-point solution (limit distribution). We discuss two examples: the finite collection of all possible motifs of size four, and the infinite collection of rooted stars. We conclude with remarks to compare fringe-analysis with matching motifs everywhere in the tree.     

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.     

A Priori Error Estimates for State-Constrained Semilinear Parabolic Optimal Control Problems

We consider the finite element discretization of semilinear parabolic optimization problems subject to pointwise in time constraints on mean values of the state variable. In order to control the feasibility violation induced by the discretization, error estimates for the semilinear partial differential equation are derived. Based upon these estimates, it can be shown that any local minimizer of the semilinear parabolic optimization problems satisfying a weak second-order sufficient condition can be approximated by the discretized problem. Rates for this convergence in terms of temporal and spatial discretization mesh sizes are provided. In contrast to other results in numerical analysis of optimization problems subject to semilinear parabolic equations, the analysis can work with a weak second-order condition, requiring growth of the Lagrangian in critical directions only. The analysis can then be conducted relying solely on the resulting quadratic growth condition of the continuous problem, without the need for similar assumptions on the discrete or time semidiscrete setting.     

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.