Benchmarking ordering techniques for nonserial dynamic programming

Five ordering algorithms for the nonserial dynamic programming algorithm for solving sparse discrete optimization problems are compared in this paper. The benchmarking reveals that the ordering of the variables has a significant impact on the run-time of these algorithms. In addition, it is shown that different orderings are most effective for different classes of problems. Finally, it is shown that, amongst the algorithms considered here, heuristics based on maximum cardinality search and minimum fill-in perform best for solving the discrete optimization problems considered in this paper.     

New techniques for designing qualitatively independent systems

Qualitatively independent systems, a previously recognized type of combinatorial design, have been recently shown to have industrial applications involving the testing of complex systems. For these applications, even small reductions on the size of a qualitatively independent system can be significant. This article discusses some new techniques that result in reduced constructions. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 411–416, 1998     

New heuristic for the dynamic layout problem

The dynamic layout problem addresses the situation where the traffic among the various units within a facility changes over time. Its objective is to determine a layout for each period in a planning horizon such that the total of the flow and the relocation costs is minimized. The problem is computationally very hard and has begun to receive attention only recently. In this paper, we present a new heuristic scheme, based on the idea of viable layouts, which is easy to operationalize. A limited computational study shows that, depending upon how it is implemented, this scheme can be reasonably fast and can yield results that are competitive with those from other available solution methods.     

New approach for nonseparable dynamic programming problems

A general class of nonseparable dynamic problems is studied in a dynamic programming framework by introducingkth-order separability. The solution approach uses multiobjective dynamic programming as a separation strategy forkth-order separable dynamic problems. The theoretical grounding on which the optimal solution of the original nonseparable dynamic problem can be attained by a noninferior solution of the corresponding multiobjective dynamic programming problem is established. The relationship between the overall optimal Lagrangian multipliers and the stage-optimal Lagrangian multipliers and the relationship between the overall weighting vector and the stage weighting vector are explored, providing the basis for identifying the optimal solution of the original nonseparable problem from among the set of noninferior solutions generated by the envelope approach.This work was supported in part by NSF Grant No. CES-86-17984. The authors appreciate the comments from Dr. V. Chankong and the editorial work by Mrs. V. Benade and Dr. S. Hitchcock.     

New techniques for empirical processes of dependent data

We present a new technique for proving the empirical process invariance principle for stationary processes _(Xn)n≥0${\left(X_n\right)}_{n\ge 0}$. The main novelty of our approach lies in the fact that we only require the central limit theorem and a moment bound for a restricted class of functions _(f(Xn))n≥0${\left(f\left(X_n\right)\right)}_{n\ge 0}$, not containing the indicator functions. Our approach can be applied to Markov chains and dynamical systems, using spectral properties of the transfer operator. Our proof consists of a novel application of chaining techniques.     

On regularization methods based on dynamic programming techniques

In this article, we investigate the connection between regularization theory for inverse problems and dynamic programming theory. This is done by developing two new regularization methods, based on dynamic programming techniques. The aim of these methods is to obtain stable approximations to the solution of linear inverse ill-posed problems. We follow two different approaches and derive a continuous and a discrete regularization method. Regularization properties for both methods are proved as well as rates of convergence. A numerical benchmark problem concerning integral operators with convolution kernels is used to illustrate the theoretical results.     

New robust dynamic plots for regression mixture detection

The forward search is a powerful general method for detecting multiple masked outliers and for determining their effect on inferences about models fitted to data. From the monitoring of a series of statistics based on subsets of data of increasing size we obtain multiple views of any hidden structure. One of the problems of the forward search has always been the lack of an automatic link among the great variety of plots which are monitored. Usually it happens that a lot of interesting features emerge unexpectedly during the progression of the forward search only when a specific combination of forward plots is inspected at the same time. Thus, the analyst should be able to interact with the plots and redefine or refine the links among them. In the absence of dynamic linking and interaction tools, the analyst risks to miss relevant hidden information. In this paper we fill this gap and provide the user with a set of new robust graphical tools whose power will be demonstrated on several regression problems. Through the analysis of real and simulated data we give a series of examples where dynamic interaction with different “robust plots” is used to highlight the presence of groups of outliers and regression mixtures and appraise the effect that these hidden groups exert on the fitted model.     

Application of linear programming techniques for controlling linear dynamic plants in real time

The problem of controlling a linear dynamic plant in real time given its nondeterministic model and imperfect measurements of the inputs and outputs is considered. The concepts of current distributions of the initial state and disturbance parameters are introduced. The method for the implementation of disclosable loop using the separation principle is described. The optimal control problem under uncertainty conditions is reduced to the problems of optimal observation, optimal identification, and optimal control of the deterministic system. To extend the domain where a solution to the optimal control problem under uncertainty exists, a two-stage optimal control method is proposed. Results are illustrated using a dynamic plant of the fourth order.     

New techniques for cost sharing in combinatorial optimization games

Combinatorial optimization games form an important subclass of cooperative games. In recent years, increased attention has been given to the issue of finding good cost shares for such games. In this paper, we define a very general class of games, called integer minimization games, which includes the combinatorial optimization games in the literature as special cases. We then present new techniques, based on row and column generation, for computing good cost shares for these games. To illustrate the power of these techniques, we apply them to traveling salesman and vehicle routing games. Our results generalize and unify several results in the literature. The main underlying idea is that suitable valid inequalities for the associated combinatorial optimization problems can be used to derive improved cost shares.     

New techniques for the analysis of linear interval equations

The basic properties of interval matrix multiplication and several well-known solution algorithms for linear interval equations are abstracted by the concept of a sublinear map. The new concept, coupled with a systematic use of Ostrowski's comparison operator (in a form generalized to interval matrices), is used to derive quantitative information about the result of interval Gauss elimination andthe limit of various iterative schemes for the solution of linear interval equations. Moreover, optimality results are prove for (1) the use of the midpoint inverse as a preconditioning matrix, and (2) Gauss-Seidel iteration with componentwise intersection. This extends and improves results by Scheu, Krawczyk, and Alefeld and Herzberger.     

New techniques for comparing the volume functions of historical texts

Conclusions The techniques described in this paper are essentially experimental. So far, they have been tried on a limited volume of empirical material, and final verdict of applicability should await more detailed checks and calibration. Yet even preliminary results suggest that it is indeed possible to develop tests for classifying texts into dependent and independent with allowance for their volume.Translated from Problemy Ustoichivosti Stokhasticheskikh Modelei, Trudy Seminara, pp. 33–45, 1986.We are grateful to N. Ya. Rives for his considerable interest in this research and for his willing assistance with computer work. His expert help has enabled us to test a number of hypotheses and to advance new ones.     

New construction of causal tensors

We study the problem of constructing tensors satisfying the dominant property, a generalization of the dominant energy condition T_ab u^a v^b ≥ 0 for all future directed causal vectors u, v. The construction is done on the paravector subspace of the r-fold Euclidean Clifford algebra and is a generalization of the representation of superenergy tensors with complex 2-spinors. Especially, as with 2-spinors, we are able to construct causal tensors of arbitrary rank, contrary to earlier constructions using tensors or the r-fold Lorentzian Clifford algebra that only produce causal tensors of even rank. An advantage of the construction in is that several algebraic properties become trivial due to the Euclidean norm on it.     

New product advertising in dynamic oligopolies

The success of the introduction of a new product in a market is very sensitive to the marketing decision variables adopted by the firm. In the present paper we are concerned with the question of new product advertising in a heterogeneous oligopoly market consisting of N firms. A dynamic game is formulated to model strategic as well as sales interactions in such a market. Optimal advertising strategies are identified as open-loop Nash solutions.The comments of two anonymous referees are appreciated. The first author wishes to acknowledge support from NSERC (Grant No. OGP0037342).     

New bounds and constraint propagation techniques for the clique partitioning problem

This paper considers the problem of clustering the vertices of a complete edge-weighted graph. The objective is to maximize the sum of the edge weights within the clusters (also called cliques). This so-called Clique Partitioning Problem (CPP) is NP-complete, and has several real-life applications such as groupings in flexible manufacturing systems, in biology, in flight gate assignment, etc. Numerous heuristics and exact approaches as well as benchmark tests have been presented in the literature. Most exact methods use branch and bound with branching over edges. We present tighter upper bounds for each search tree node than those known from the literature, improve the constraint propagation techniques for fixing edges in each node, and present a new branching scheme. The theoretical improvements are reflected by computational tests with real-life data. Although a standard solver delivers best results on randomly generated data, the runtime of the proposed algorithm is very low when being applied to instances on object clustering.     

New Brownian bridge construction in quasi-Monte Carlo methods for computational finance

Quasi-Monte Carlo (QMC) methods have been playing an important role for high-dimensional problems in computational finance. Several techniques, such as the Brownian bridge (BB) and the principal component analysis, are often used in QMC as possible ways to improve the performance of QMC. This paper proposes a new BB construction, which enjoys some interesting properties that appear useful in QMC methods. The basic idea is to choose the new step of a Brownian path in a certain criterion such that it maximizes the variance explained by the new variable while holding all previously chosen steps fixed. It turns out that using this new construction, the first few variables are more “important” (in the sense of explained variance) than those in the ordinary BB construction, while the cost of the generation is still linear in dimension. We present empirical studies of the proposed algorithm for pricing high-dimensional Asian options and American options, and demonstrate the usefulness of the new BB.     

Stochastic dynamic lot-sizing problem using bi-level programming base on artificial intelligence techniques

Simulation is generally used to study non-deterministic problems in industry. When a simulation process finds the solution to an NP-hard problem, its efficiency is lowered, and computational costs increase. This paper proposes a stochastic dynamic lot-sizing problem with asymmetric deteriorating commodity, in which the optimal unit cost of material and unit holding cost would be determined. This problem covers a sub-problem of replenishment planning, which is NP-hard in the computational complexity theory. Therefore, this paper applies a decision system, based on an artificial neural network (ANN) and modified ant colony optimization (ACO) to solve this stochastic dynamic lot-sizing problem. In the methodology, ANN is used to learn the simulation results, followed by the application of a real-valued modified ACO algorithm to find the optimal decision variables. The test results show that the intelligent system is applicable to the proposed problem, and its performance is better than response surface methodology.     

New construction and ultraconvergence of derivative recovery operator for odd-degree rectangular elements

In this paper the ultraconvergence of the derivative for odd-degree rectangular elements is addressed. A new, discrete least-squares patch recovery technique is proposed to post-process the solution derivatives. Such recovered derivatives are shown to possess ultraconvergence by using projection type interpolation.