Depth-first heuristic search for the job shop scheduling problem

We evaluate two variants of depth-first search algorithms and consider the classic job shop scheduling problem as a test bed. The first one is the well-known branch-and-bound algorithm proposed by P. Brucker et al. which uses a single chronological backtracking strategy. The second is a variant that uses partially informed depth-first search strategy instead. Both algorithms use the same heuristic estimation; in the first case, it is only used for pruning states that cannot improve the incumbent solution, whereas in the second it is also used to sort the successors of an expanded state. We also propose and analyze a new heuristic estimation which is more informed and more time consuming than that used by Brucker’s algorithm. We conducted an experimental study over well-known instances showing that the proposed partially informed depth-first search algorithm outperforms the original Brucker’s algorithm.     

Heuristic Search Algorithms for the Minimum Volume Ellipsoid

Abstract

A method of robust estimation of multivariate location and shape that has attracted a lot of attention recently is Rousseeuw's minimum volume ellipsoid estimator (MVE). This estimator has a high breakdown point but is difficult to compute successfully. In this article, we apply methods of heuristic search to this problem, including simulated annealing, genetic algorithms, and tabu search, and compare the results to the undirected random search algorithm that is often cited. Heuristic search provides several effective algorithms that are far more computationally efficient than random search. Furthermore, random search, as currently implemented, is shown to be ineffective for larger problems.     

混合整数线性模型方差分量的Bayes估计

本文研究了混合整数线性模型方差分量在无信息先验分布和有信息先验分布下Bayes估计，给出了混合整数线性模型方差分量无信息和：有信息先验分布下的极大后验估计和最佳Bayes估计。     

Multistart method with estimation scheme for global satisfycing problems

We present a multistart method for solving global satisfycing problems. The method uses data generated by linearly converging local algorithms to estimate the cost value at the local minimum to which the local search is converging. When the estimate indicates that the local search is converging to a value higher than the satisfycing value, the local search is interrupted and a new local search is initiated from a randomly generated point. When the satisfycing problem is difficult and the estimation scheme is fairly accurate, the new method is superior over a straightforward adaptation of classical multistart methods.     

Incorporating scatter search and threshold accepting in finding maximum likelihood estimates for the multinomial probit model

This paper presents a procedure that incorporates scatter search and threshold accepting to find the maximum likelihood estimates for the multinomial probit (MNP) model. Scatter search, widely used in optimization-related studies, is a type of evolutionary algorithm that uses a small set of solutions as the selection pool for mating and generating new solutions to search for a globally optimal solution. Threshold accepting is applied to the scatter search to improve computational efficiency while maintaining the same level of solution quality. A set of numerical experiments, based on synthetic data sets with known model specifications and error structures, were conducted to test the effectiveness and efficiency of the proposed framework. The results indicated that the proposed procedure enhanced performance in terms of likelihood function value and computational efficiency for MNP model estimation as compared to the original scatter search framework.     

Optimal solution for novel grey polynomial prediction model

The grey prediction model, as a time-series analysis tool, has been used in various fields only with partly known distribution information. The grey polynomial model is a novel method to solve the problem that the original sequence is in accord with a more general trend rather than the special homogeneous or non-homogeneous trend, but how to select the polynomial order still needs further study. In this paper the tuned background coefficient is introduced into the grey polynomial model and then the algorithmic framework for polynomial order selection, background coefficient search and parameter estimation is proposed. The quantitative relations between the affine transformation of accumulating sequence and the parameter estimates are deduced. The modeling performance proves to be independent of the affine transformation. The numerical example and application are carried out to assess the modeling efficiency in comparison with other conventional models.     

On the minimum volume simplex enclosure problem for estimating a linear mixing model

We describe the minimum volume simplex enclosure problem (MVSEP), which is known to be a global optimization problem, and further investigate its multimodality. The problem is a basis for several (unmixing) methods that estimate so-called endmembers and fractional values in a linear mixing model. We describe one of the estimation methods based on MVSEP. We show numerically that using nonlinear optimization local search leads to the estimation results aimed at. This is done using examples, designing instances and comparing the outcomes with a maximum volume enclosing simplex approach which is used frequently in unmixing data.     

A perfect example for the BFGS method

Consider the BFGS quasi-Newton method applied to a general non-convex function that has continuous second derivatives. This paper aims to construct a four-dimensional example such that the BFGS method need not converge. The example is perfect in the following sense: (a) All the stepsizes are exactly equal to one; the unit stepsize can also be accepted by various line searches including the Wolfe line search and the Arjimo line search; (b) The objective function is strongly convex along each search direction although it is not in itself. The unit stepsize is the unique minimizer of each line search function. Hence the example also applies to the global line search and the line search that always picks the first local minimizer; (c) The objective function is polynomial and hence is infinitely continuously differentiable. If relaxing the convexity requirement of the line search function; namely, (b) we are able to construct a relatively simple polynomial example.     

Successive direction extraction for estimating the central subspace in a multiple-index regression

In this paper we propose a dimension reduction method for estimating the directions in a multiple-index regression based on information extraction. This extends the recent work of Yin and Cook [X. Yin, R.D. Cook, Direction estimation in single-index regression, Biometrika 92 (2005) 371-384] who introduced the method and used it to estimate the direction in a single-index regression. While a formal extension seems conceptually straightforward, there is a fundamentally new aspect of our extension: We are able to show that, under the assumption of elliptical predictors, the estimation of multiple-index regressions can be decomposed into successive single-index estimation problems. This significantly reduces the computational complexity, because the nonparametric procedure involves only a one-dimensional search at each stage. In addition, we developed a permutation test to assist in estimating the dimension of a multiple-index regression.     

Oracle inequalities for the stochastic differential equations

This paper is a survey of recent results on the adaptive robust non parametric methods for the continuous time regression model with the semi-martingale noises with jumps. The noises are modeled by the Lévy processes, the Ornstein–Uhlenbeck processes and semi-Markov processes. We represent the general model selection method and the sharp oracle inequalities methods which provide the robust efficient estimation in the adaptive setting. Moreover, we present the recent results on the improved model selection methods for the nonparametric estimation problems.     

Algorithms for index tracking

The problem of selecting a portfolio of securities to trackthe performance of a given index is formulated in mathematicalprogramming terms. Optimal weights for given sets of includedsecurities are obtained using linear complementarity algorithms,and various methods of search among neighbouring sets of securitiesare considered. The problem of local optima is considered, andvarious methods, including simulated annealing, are suggestedfor overcoming this. The solution depends on estimation of thecovariance matrix and expected returns for the constituent securities;tracking of the FT-SE 100-share index for the calendar year1988 is solved using various estimation techniques.     

Discrete search and estimation

This paper is a theoretical study of an overlap between search theory and estimation in such a way, that a class of minimum variance estimation problems is described and analyzed by search theory concepts. To a certain extent this assimilates the two theories.     

Adaptive sample size and importance sampling in estimation-based local search for the probabilistic traveling salesman problem

The probabilistic traveling salesman problem is a paradigmatic example of a stochastic combinatorial optimization problem. For this problem, recently an estimation-based local search algorithm using delta evaluation has been proposed. In this paper, we adopt two well-known variance reduction procedures in the estimation-based local search algorithm: the first is an adaptive sampling procedure that selects the appropriate size of the sample to be used in Monte Carlo evaluation; the second is a procedure that adopts importance sampling to reduce the variance involved in the cost estimation. We investigate several possible strategies for applying these procedures to the given problem and we identify the most effective one. Experimental results show that a particular heuristic customization of the two procedures increases significantly the effectiveness of the estimation-based local search.     

Performance of a genetic algorithm for the graph partitioning problem

The performance of the genetic algorithm (GA) for the graph partitioning problem (GPP) is investigated by comparison with standard heuristics on well-known benchmark graphs. In general, there is a case where a practical performance of a conventional genetic approach, which performs only simple operations without a local search strategy, is not sufficient. However, it is known that a combination of GA and local search can produce better solutions. From this practice, we incorporate a simple local search algorithm into the GA. In particular, the search ability of the GA is compared with standard heuristics such as multistart local search and simulated annealing, which use the same neighborhood structure of the simple local search, for solving the GPP. Experimental results show that the GA performs better than its competitors.     

Two-Stage Nested Partitions Method for Stochastic Optimization

We address the problem of optimizing over a large but finite set when the objective function does not have an analytical expression and is evaluated using noisy estimation. Building on the recently proposed nested partitions method for stochastic optimization, we develop a new approach that combines this random search method and statistical selection for guiding the search. We prove asymptotic convergence and analyze the finite time behavior of the new approach. We also report extensive numerical results to illustrate the benefits of the new approach.     

Nearest neighbor conditional estimation for Harris recurrent Markov chains

This paper is concerned with consistent nearest neighbor time series estimation for data generated by a Harris recurrent Markov chain on a general state space. It is shown that nearest neighbor estimation is consistent in this general time series context, using simple and weak conditions. The results proved here, establish consistency, in a unified manner, for a large variety of problems, e.g. autoregression function estimation, and, more generally, extremum estimators as well as sequential forecasting. Finally, under additional conditions, it is also shown that the estimators are asymptotically normal.     

A Monte Carlo Filtering Approach for Estimating the Term Structure of Interest Rates

We develop new methodology for estimation of general class of term structure models based on a Monte Carlo filtering approach. We utilize the generalized state space model which can be naturally applied to the estimation of the term structure models based on the Markov state processes. It is also possible to introduce measurement errors in the general way without any bias. Moreover, the Monte Carlo filter can be applied even to the models in which the zero-coupon bonds' prices can not be analytically obtained. As an example, we apply the method to LIBORs (London Inter Bank Offered Rates) and interest rates swaps in the Japanese market and show the usefulness of our approach.     

A real time algorithm for the location search of discontinuous conductivities with one measurement

We consider an inverse problem for finding the anomaly of discontinuous electrical conductivity by one current‐voltage observation. We develop a real time algorithm for determining the location of the anomaly. This new idea is based on the observation of the pattern of a simple weighted combination of the input current and the output voltage. Combined with the size estimation result, this algorithm gives a good initial guess for Newton‐type schemes. We give the rigorous proof for the location search algorithm. Both the mathematical analysis and its numerical implementation indicate our location search algorithm is very fast, stable and efficient. © 2001 John Wiley & Sons, Inc.     

On the general problem of mean estimation

Mean estimation for a random function is considered in its most general context, including both the case of infinite dimensional mean and exact estimation. The existence theorem for the best linear unbiased estimates is established. The general definition of the pseudobest estimate is given; necessary and sufficient conditions for the efficiency of the pseudobest estimates are obtained. As an application the problem of the periodic trend estimation is considered.     

Branch and win: OR tree search algorithms for solving combinatorial optimisation problems

Currently, most combinatorial optimisation problems have to be solved, if the optimum solution is sought, using general techniques to explore the space of feasible solutions and, more specifically, through exploratory enumerative procedures in trees and search graphs. We propose Branch and Win, a general formulation for understanding and synthesising the different tree search procedures that have been presented in the literature of operations research as well as in that of artificial intelligence. Several general ideas are also presented, whose application allows designing new hybrid search algorithms, in order to implement the procedure.