Selecting mixed-effects models based on a generalized information criterion

The generalized information criterion (GIC) proposed by Rao and Wu [A strongly consistent procedure for model selection in a regression problem, Biometrika 76 (1989) 369-374] is a generalization of Akaike's information criterion (AIC) and the Bayesian information criterion (BIC). In this paper, we extend the GIC to select linear mixed-effects models that are widely applied in analyzing longitudinal data. The procedure for selecting fixed effects and random effects based on the extended GIC is provided. The asymptotic behavior of the extended GIC method for selecting fixed effects is studied. We prove that, under mild conditions, the selection procedure is asymptotically loss efficient regardless of the existence of a true model and consistent if a true model exists. A simulation study is carried out to empirically evaluate the performance of the extended GIC procedure. The results from the simulation show that if the signal-to-noise ratio is moderate or high, the percentages of choosing the correct fixed effects by the GIC procedure are close to one for finite samples, while the procedure performs relatively poorly when it is used to select random effects.     

Cone contraction and reference point methods for multi-criteria mixed integer optimization

Interactive approaches employing cone contraction for multi-criteria mixed integer optimization are introduced. In each iteration, the decision maker (DM) is asked to give a reference point (new aspiration levels). The subsequent Pareto optimal point is the reference point projected on the set of admissible objective vectors using a suitable scalarizing function. Thereby, the procedures solve a sequence of optimization problems with integer variables. In such a process, the DM provides additional preference information via pair-wise comparisons of Pareto optimal points identified. Using such preference information and assuming a quasiconcave and non-decreasing value function of the DM we restrict the set of admissible objective vectors by excluding subsets, which cannot improve over the solutions already found. The procedures terminate if all Pareto optimal solutions have been either generated or excluded. In this case, the best Pareto point found is an optimal solution. Such convergence is expected in the special case of pure integer optimization; indeed, numerical simulation tests with multi-criteria facility location models and knapsack problems indicate reasonably fast convergence, in particular, under a linear value function. We also propose a procedure to test whether or not a solution is a supported Pareto point (optimal under some linear value function).     

Monodromization and Difference Equations with Meromorphic Periodic Coefficients

We consider a system of two first-order difference equations in the complex plane. We assume that the matrix of the system is a 1-periodic meromorphic function having two simple poles per period and bounded as Im z → ±∞. We prove the existence and uniqueness of minimal meromorphic solutions, i.e., solutions having simultaneously a minimal set of poles and minimal possible growth as Im z → ±∞. We consider the monodromy matrix representing the shift-byperiod operator in the space of meromorphic solutions and corresponding to a basis built of two minimal solutions. We check that it has the same functional structure as the matrix of the initial system of equations and, in particular, is a meromorphic periodic function with two simple poles per period. This implies that the initial equation is invariant with respect to the monodromization procedure, that is, a natural renormalization procedure arising when trying to extend the Floquet–Bloch theory to difference equations defined on the real line or complex plane and having periodic coefficients. Our initial system itself arises after one renormalization of a self-adjoint difference Schrödinger equation with 1-periodic meromorphic potential bounded at ±i∞ and having two poles per period.     

Ordinal optimization based metaheuristic algorithm for optimal inventory policy of assemble-to-order systems

Assemble-to-order (ATO) systems refer to a manufacturing process in which a customer must first place an order before the ordered item is manufactured. An ATO system that operates under a continuous-review base-stock policy can be formulated as a stochastic simulation optimization problem (SSOP) with a huge search space, which is known as NP-hard. This work develops an ordinal optimization (OO) based metaheuristic algorithm, abbreviated to OOMH, to determine a near-optimal design (target inventory level) in ATO systems. The proposed approach covers three main modules, which are meta-modeling, exploration, and exploitation. In the meta-modeling module, the extreme learning machine (ELM) is used as a meta-model to estimate the approximate objective value of a design. In the exploration module, the elite teaching-learning-based optimization (TLBO) approach is utilized to select N candidate designs from the entire search space, where the fitness of a design is evaluated using the ELM. In the exploitation module, the sequential ranking-and-selection (R&S) scheme is used to optimally allocate the computing resource and budget for effective selecting the critical designs from the N candidate designs. Finally, the proposed algorithm is applied to two general ATO systems. The large ATO system comprises 12 items on eight products and the moderately sized ATO system is composed of eight items on five products. Test results that are obtained using the OOMH approach are compared with those obtained using three heuristic methods and a discrete optimization-via-simulation (DOvS) algorithm. Analytical results reveal that the proposed method yields solutions of much higher quality with a much higher computational efficiency than the three heuristic methods and the DOvS algorithm.     

Maximum likelihood estimation for noncausal autoregressive processes

We discuss a maximum likelihood procedure for estimating parameters in possibly noncausal autoregressive processes driven by i.i.d. non-Gaussian noise. Under appropriate conditions, estimates of the parameters that are solutions to the likelihood equations exist and are asymptotically normal. The estimation procedure is illustrated with a simulation study for AR(2) processes.     

Efficient comparison of constrained systems using dormancy

We consider the problem of finding the best simulated system under a primary performance measure, while also satisfying stochastic constraints on secondary performance measures. We improve upon existing constrained selection procedures by allowing certain systems to become dormant, halting sampling for those systems as the procedure continues. A system goes dormant when it is found inferior to another system whose feasibility has not been determined, and returns to contention only if its superior system is eliminated. If found feasible, the superior system will eliminate the dormant system. By making systems dormant, we avoid collecting unnecessary observations from inferior systems. The paper also proposes other modifications, and studies the impact and benefits of our approaches (compared to similar constrained selection procedures) through experimental results and asymptotic approximations. Additionally, we discuss the difficulties associated with procedures that use sample means of unequal, random sample sizes, which commonly occurs within constrained selection and optimization-via-simulation.     

An approximate dynamic programming approach for the vehicle routing problem with stochastic demands

This paper examines approximate dynamic programming algorithms for the single-vehicle routing problem with stochastic demands from a dynamic or reoptimization perspective. The methods extend the rollout algorithm by implementing different base sequences (i.e. a priori solutions), look-ahead policies, and pruning schemes. The paper also considers computing the cost-to-go with Monte Carlo simulation in addition to direct approaches. The best new method found is a two-step lookahead rollout started with a stochastic base sequence. The routing cost is about 4.8% less than the one-step rollout algorithm started with a deterministic sequence. Results also show that Monte Carlo cost-to-go estimation reduces computation time 65% in large instances with little or no loss in solution quality. Moreover, the paper compares results to the perfect information case from solving exact a posteriori solutions for sampled vehicle routing problems. The confidence interval for the overall mean difference is (3.56%, 4.11%).     

Computing small solutions of Burgers' equation backwards in time

We construct and analyze an algorithm for the numerical computation of Burgers' equation for preceding times, given an a priori bound for the solution and an approximation to the terminal data. The method is based on the “backward beam equation” coupled with an iterative procedure for the solution of the nonlinear problem via a sequence of linear problems. We also present the results of several numerical experiments. It turns out that the procedure converges “asymptotically,” i.e., in the same manner in which an asymptotic expansion converges. This phenomenon seems related to the “destruction of information,” at t = 0, which is typical in backwards dissipative equations. We derive a priori stability estimates for the analytic backwards problem, and we observe that in many numerical experiments, the distance backwards in time where significant accuracy can be attained is much larger than would be expected on the basis of such estimates. The method is useful for small solutions. Problems where steep gradients occur require considerably more precision in measurement. The algorithm is applicable to other semilinear problems.     

Mixed graph edge coloring

We are interested in coloring the edges of a mixed graph, i.e., a graph containing unoriented and oriented edges. This problem is related to a communication problem in job-shop scheduling systems. In this paper we give general bounds on the number of required colors and analyze the complexity status of this problem. In particular, we provide NP-completeness results for the case of outerplanar graphs, as well as for 3-regular bipartite graphs (even when only 3 colors are allowed, or when 5 colors are allowed and the graph is fully oriented). Special cases admitting polynomial-time solutions are also discussed.     

Approximate analysis of load-dependent generally distributed queuing networks with low service time variability

In this paper, we present an approximate method for solution of load-dependent, closed queuing networks having general service time distributions with low variability. The proposed technique is an extension of Marie’s (1980) method. In the methodology, conditional throughputs are obtained by an iterative procedure. The iterations are repeated until an invalid result is detected or no improvements are found. We demonstrate the performance of the technique with 10 different examples. On average, the solutions have 5% or lower deviations when compared to simulation results.     

Global solutions of the Navier–Stokes equations for isentropic flow with large external potential force

We prove the global-in-time existence of weak solutions to the Navier–Stokes equations of compressible isentropic flow in three space dimensions with adiabatic exponent γ ≥ 1. Initial data and solutions are small in L ² around a non-constant steady state with densities being positive and essentially bounded. No smallness assumption is imposed on the external forces when γ = 1. A great deal of information about partial regularity and large-time behavior is obtained.     

Efficient automatic simulation of parallel computation on networks of workstations

Andrews et al. [Automatic method for hiding latency in high bandwidth networks, in: Proceedings of the ACM Symposium on Theory of Computing, 1996, pp. 257-265; Improved methods for hiding latency in high bandwidth networks, in: Proceedings of the Eighth Annual ACM Symposium on Parallel Algorithms and Architectures, 1996, pp. 52-61] introduced a number of techniques for automatically hiding latency when performing simulations of networks with unit delay links on networks with arbitrary unequal delay links. In their work, they assume that processors of the host network are identical in computational power to those of the guest network being simulated. They further assume that the links of the host are able to pipeline messages, i.e., they are able to deliver P packets in time O(P+d) where d is the delay on the link.In this paper we examine the effect of eliminating one or both of these assumptions. In particular, we provide an efficient simulation of a linear array of homogeneous processors connected by unit-delay links on a linear array of heterogeneous processors connected by links with arbitrary delay. We show that the slowdown achieved by our simulation is optimal. We then consider the case of simulating cliques by cliques; i.e., a clique of heterogeneous processors with arbitrary delay links is used to simulate a clique of homogeneous processors with unit delay links. We reduce the slowdown from the obvious bound of the maximum delay link to the average of the link delays. In the case of the linear array we consider both links with and without pipelining. For the clique simulation the links are not assumed to support pipelining.The main motivation of our results (as was the case with Andrews et al.) is to mitigate the degradation of performance when executing parallel programs designed for different architectures on a network of workstations (NOW). In such a setting it is unlikely that the links provided by the NOW will support pipelining and it is quite probable the processors will be heterogeneous. Combining our result on clique simulation with well-known techniques for simulating shared memory PRAMs on distributed memory machines provides an effective automatic compilation of a PRAM algorithm on a NOW.     

Temporally regularized direct numerical simulation

Experience with fluid-flow simulation suggests that, in some instances, under-resolved direct numerical simulation (DNS), without a residual-stress model per se but with artificial damping of small scales to account for energy lost in the cascade from resolved to unresolved scales, may be as reliable as simulations based on more complex models of turbulence. One efficient and versatile manner to selectively damp under-resolved spatial scales is by a relaxation regularization, e.g. Stolz and Adams [S. Stolz, N.A. Adams, An approximate deconvolution procedure for large eddy simulation, Phys. Fluids II (1999) 1699-1701]. We consider the analogous approach based on time scales, time filtering and damping of under-resolved temporal features. The paper explores theoretical and practical aspects of temporally damped fluid-flow simulations. We prove existence of solutions to the resulting continuum model. We also establish the effect of the damping of under-resolved temporal features as the energy balance and dissipation and prove that the time fluctuations → 0 in a precise sense. The method is then demonstrated to obtain both steady-state and time-dependent coarse-grid solutions of the Navier-Stokes equations.     

A particle method for some parabolic equations

We present a quasi-Monte-Carlo particle simulation of some multidimensional linear parabolic equations with constant coefficients. We approximate the elliptic operator in space by a finite-difference operator. We discretize time into intervals of length Δt. The discrete representation of the solution at time t_n = nΔt is a sum of Dirac delta measures. Using the explicit Euler scheme, the resulting approximation at time t_n+1 is recovered by a quasi-Monte-Carlo integration. We make use of a technique involving renumbering the simulated particles in every time step. We state and prove a convergence theorem for the method. Experimental results are presented for some model problems. The results suggest that the quasi-Monte-Carlo simulation tends to give more accurate solutions than a Monte-Carlo simulation, when the correct renumbering technique is used. Other choices can result in significant loss of efficiency.     

Undesirable facility location with minimal covering objectives

An undesirable facility is to be located within some feasible region of any shape in the plane or on a planar network. Population is supposed to be concentrated at a finite number n of points. Two criteria are taken into account: a radius of influence to be maximised, indicating within which distance from the facility population disturbance is taken into consideration, and the total covered population, i.e. lying within the influence radius from the facility, which should be minimised. Low complexity polynomial algorithms are derived to determine all nondominated solutions, of which there are only O(n³) for a fixed feasible region or O(n²) when locating on a planar network. Once obtained, this information allows almost instant answers and a trade-off sensitivity analysis to questions such as minimising the population within a given radius (minimal covering problem) or finding the largest circle not covering more than a given total population.     

Error propagation when approximating multi-solitons: The KdV equation as a case study

The paper studies the influence of the time discretizations when simulating some phenomena involving more than one solitary wave. Taking the KdV equation as a case study, we obtain some conditions on the numerical method in order to get a more correct simulation of multi-soliton solutions. They are related to the evolution of the conserved quantities of the problem through the numerical integration. It is shown that, when approximating N-solitons, a method that preserves N invariants of the problem shows a better time propagation of the error than that of a general scheme. As a consequence of this, the simulation of some physical parameters that characterize the waves is more suitable when using conservative integrators. We also show how these results can be extended to the approximation to multi-solitons of any equation of the KdV hierarchy and, more generally, other integrable equations.     

The Perron method for p-harmonic functions in metric spaces

We use the Perron method to construct and study solutions of the Dirichlet problem for p-harmonic functions in proper metric measure spaces endowed with a doubling Borel measure supporting a weak (1,q)-Poincaré inequality (for some 1?q<p). The upper and lower Perron solutions are constructed for functions defined on the boundary of a bounded domain and it is shown that these solutions are p-harmonic in the domain. It is also shown that Newtonian (Sobolev) functions and continuous functions are resolutive, i.e. that their upper and lower Perron solutions coincide, and that their Perron solutions are invariant under perturbations of the function on a set of capacity zero. We further study the problem of resolutivity and invariance under perturbations for semicontinuous functions. We also characterize removable sets for bounded p-(super)harmonic functions.     

Max Flow and Min Cut with bounded-length paths: complexity, algorithms, and approximation

We consider the “flow on paths” versions of Max Flow and Min Cut when we restrict to paths having at most B arcs, and for versions where we allow fractional solutions or require integral solutions. We show that the continuous versions are polynomial even if B is part of the input, but that the integral versions are polynomial only when B ≤ 3. However, when B ≤ 3 we show how to solve the problems using ordinary Max Flow/Min Cut. We also give tight bounds on the integrality gaps between the integral and continuous objective values for both problems, and between the continuous objective values for the bounded-length paths version and the version allowing all paths. We give a primal–dual approximation algorithm for both problems whose approximation ratio attains the integrality gap, thereby showing that it is the best possible primal–dual approximation algorithm.     

A combined procedure for discrete simulation–optimization problems based on the simulated annealing framework

This paper addresses the problem of optimizing a function over a finite or countable infinite set of alternatives, whenever the objective function cannot be evaluated exactly, but has to be estimated via simulation. We present an iterative method, based on the simulated annealing framework, for solving such discrete stochastic optimization problems. In the proposed method, we combine the robustness of this metaheuristic method with a statistical procedure for comparing the solutions that are generated. The focus of our work is on devising an effective procedure rather than addressing theoretical issues. In fact, in our opinion, although significant progresses have been made in studying the convergence of a number of simulation–optimization algorithms, at present there is no procedure able to consistently provide good results in a reasonable amount of time. In addition, we present a parallelization strategy for allocating simulation runs on computing resources.     

Asymptotic description of stochastic neural networks. I. Existence of a large deviation principle

We study the asymptotic law of a network of interacting neurons when the number of neurons becomes infinite. The dynamics of the neurons is described by a set of stochastic differential equations in discrete time. The neurons interact through the synaptic weights that are Gaussian correlated random variables. We describe the asymptotic law of the network when the number of neurons goes to infinity. Unlike previous works which made the biologically unrealistic assumption that the weights were i.i.d. random variables, we assume that they are correlated. We introduce the process-level empirical measure of the trajectories of the solutions into the equations of the finite network of neurons and the averaged law (with respect to the synaptic weights) of the trajectories of the solutions into the equations of the network of neurons. The result ( Theorem 3.1 below) is that the image law through the empirical measure satisfies a large deviation principle with a good rate function. We provide an analytical expression of this rate function in terms of the spectral representation of certain Gaussian processes.