A remark on the princess and monster search game

We consider two zero-sum search games in which a searcher moves along a continuous trajectory in a search setQ. The probability of detection depends on the distance between the two players. The problem is open loop, i.e. neither player receives any information about the other as the game progresses. The payoff to a hider is the elapsed time before detection. Optimal mixed strategies are obtained.     

Parallel tabu search message-passing synchronous strategies for task scheduling under precedence constraints

This paper presents parallelization strategies for a tabu search algorithm for the task scheduling problem on heterogeneous processors under task precedence constraints. Parallelization relies exclusively on the decompostion of the solution space exploration. Four different parallel strategies are proposed and implemented on an asynchronous parallel machine under PVM: the master-slave model, with two different schemes for improved load balancing, and the single-program-multiple-data model, with single-token and multiple-token message passing schemes. The comparative analysis of these strategies shows that the tabu search approach for this problem is very suitable to the parallelization of the neighborhood search, with efficiency results almost always close to one for problems over a certain size.     

On the minimality of search paths under absolutely continuous univariate distributions

The linear search problem is concerned with the search for a target located randomly on a line. The target being sought for might be on either side of some starting point. A searcher makes for the target with an upper bound on his speed, using a continuous search path in which he changes his direction many times before reaching his goal. The minimality of average distance (time) from the starting point upon reaching the target is the measure of optimality of search paths. We have obtained sufficient conditions that guarantee the minimality of such search paths whenever the target has an absolutely continuous distribution.

---

Zusammenfassung Ein Objekt, das sich in zufälliger Position auf einer Strecke befindet, soll gesucht werden; der Startpunkt liegt im Inneren der Strecke. Für die Bewegungsgeschwindigkeit bei der Suche ist eine obere Schranke gegeben; der Suchpfad muß stetig sein, wobei beliebig viele Richtungsänderungen zugelassen sind. Das Ziel ist die Minimierung der erwarteten Zeit bis zum Erreichen des Objekts. Unter der Voraussetzung einer absolut stetigen Verteilung für die Position des Objekts werden hinreichende Bedingungen für die Optimalität eines Suchpfades angegeben.

     

Genetic local search the graph partitioning problem under cardinality constraints

For the graph partitioning problem under cardinality constraints, a genetic local search method is developed. At each iteration of the method, there is a set of local optima of the problem. This set is used to search for new local optima with a smaller error. The local search problem with certain polynomially searchable neighborhoods is proved to be tight PLS-complete. It is shown that, in the worst case, number of local improvements can be exponentially large for any pivoting rule. Numerical experiments are performed in the special case of edge weights equal to unity, when local search is a polynomial-time procedure. The results of the experiments indicate that the method is highly efficient and can be applied to large-scale problems.     

Dynamic programming and the backpacker''s linear search problem

A backpacker approaches a road with a marker on it, desirous of finding the marker but having only a rough idea of where it is located. It is well known among backpackers that it is best to aim either right or left of the marker, since otherwise it will not be clear which way to turn upon reaching the road. The problem of deciding exactly where to aim can be formalized as a modification of the Linear Search Problem. This paper does so, and also discusses dynamic programming as a solution method.     

Fixed-parameter algorithms for protein similarity search under mRNA structure constraints

In the context of protein engineering, we consider the problem of computing an mRNA sequence of maximal codon-wise similarity to a given mRNA (and consequently, to a given protein) that additionally satisfies some secondary structure constraints, the so-called mRNA Structure Optimization (MRSO) problem. Since MRSO is known to be APX-hard, Bongartz [D. Bongartz, Some notes on the complexity of protein similarity search under mRNA structure constraints, in: Proc. of the 30th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 2004, pp. 174–183] suggested to attack the problem using the approach of parameterized complexity. In this paper we propose three fixed-parameter algorithms that apply for several interesting parameters of MRSO. We believe these algorithms to be relevant for practical applications today, as well as for possible future applications. Furthermore, our results extend the known tractability borderline of MRSO, and provide new research horizons for further improvements of this sort.     

A Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints

We present a metaheuristic methodology for the Capacitated Vehicle Routing Problem with two-dimensional loading constraints (2L-CVRP). 2L-CVRP is a generalisation of the Capacitated Vehicle Routing Problem, in which customer demand is formed by a set of two-dimensional, rectangular, weighted items. The purpose of this problem is to produce the minimum cost routes, starting and terminating at a central depot, to satisfy the customer demand. Furthermore, the transported items must be feasibly packed into the loading surfaces of the vehicles. We propose a metaheuristic algorithm which incorporates the rationale of Tabu Search and Guided Local Search. The loading aspects of the problem are tackled using a collection of packing heuristics. To accelerate the search process, we reduce the neighbourhoods explored, and employ a memory structure to record the loading feasibility information. Extensive experiments were conducted to calibrate the algorithmic parameters. The effectiveness of the proposed metaheuristic algorithm was tested on benchmark instances and led to several new best solutions.     

Beam search heuristic to solve stochastic integer problems under probabilistic constraints

This paper proposes a Beam Search heuristic strategy to solve stochastic integer programming problems under probabilistic constraints. Beam Search is an adaptation of the classical Branch and Bound method in which at any level of the search tree only the most promising nodes are kept for further exploration, whereas the remaining are pruned out permanently. The proposed algorithm has been compared with the Branch and Bound method. The numerical results collected on the probabilistic set covering problem show that the Beam Search technique is very efficient and appears to be a promising tool to solve difficult stochastic integer problems under probabilistic constraints.     

Modeling the search for the least costly opportunity

With the continuing growth in the number of opportunities available at virtual stores over the Internet there is also a growing demand for the services of computer programs capable of scanning a large number of stores in a very short time. We assume that the cost associated with each scan is linear in the number of stores scanned, and that the resulting list of price quotes is not always satisfactory to the customer, in which case an additional scan is performed, and so on. In such a reality the customer, wishing to minimize her expected cost, must specify the requested sample size and a rule (control limit) to stop the search.     

Optimal investment and life insurance strategies under minimum and maximum constraints

We derive optimal strategies for an individual life insurance policyholder who can control the asset allocation as well as the sum insured (the amount to be paid out upon death) throughout the policy term. We first consider the problem in a pure form without constraints (except nonnegativity on the sum insured) and then in a more general form with minimum and/or maximum constraints on the sum insured. In both cases we also provide the optimal life insurance strategies in the case where risky-asset investments are not allowed (or not taken into consideration), as in basic life insurance mathematics. The optimal constrained strategies are somewhat more complex than the unconstrained ones, but the latter can serve to ease the understanding and implementation of the former.     

Computation of suboptimal randomized strategies for steering the random motion of a point under partial observation

Consider the random motion in the plane of a pointM, whose velocityv=(v ₁,v ₂) is perturbed by an ²-valued Gaussian white noise. Only noisy nonlinear observations taken on the point location (state) are available toM. The velocityv is of the formv(y)= _u (u ₁,u ₂) _y (du), wherey denotes the value of the observed signal,U is the range of the velocity, and, for eachy, _y is a probability measure on (U). Using the available observations, the pointM wishes to steer itself into a given target set by choosing a randomized strategy ={ _y :y ²}. Sufficient conditions on weak optimal randomized strategies are derived. An algorithm for computing weak suboptimal randomized strategies is suggested, and the strategies are computed for a variety of cases.This work was partially supported by a grant from Control Data.     

The eye and the fist: Optimizing search and interdiction

Interdiction operations involving search, identification, and interception of suspected objects are of great interest and high operational importance to military and naval forces as well as nation’s coast guards and border patrols. The interdiction scenario discussed in this paper includes an area of interest with multiple neutral and hostile objects moving through this area, and an interdiction force, consisting of an airborne sensor and an intercepting surface vessel or ground vehicle, whose objectives are to search, identify, track, and intercept hostile objects within a given time frame. The main contributions of this paper are addressing both airborne sensor and surface vessel simultaneously, developing a stochastic dynamic-programming model for optimizing their employment, and deriving operational insight. In addition, the search and identification process of the airborne sensor addresses both physical (appearance) and behavioral (movement pattern) signatures of a potentially hostile object. As the model is computationally intractable for real-world scenarios, we propose a simple heuristic policy, which is shown, using a bounding technique, to be quite effective. Based on a numerical case study of maritime interdiction operations, which includes several representative scenarios, we show that the expected number of intercepted hostile objects, following the heuristic decision policy, is at least 60% of the number of hostile objects intercepted following an optimal decision policy.     

A tabu search algorithm for the Open Shop problem

In this paper we consider the minimum makespan Open Shop problem without preemption. It is well-known that the case with only two machines can be optimally solved in linear time, whereas the problem with an arbitrary number of machines is NP-hard in the strong sense. We propose a tabu search algorithm for the solution of the problem which uses simple list scheduling algorithms to build the starting solutions. The algorithm is extensively tested on randomly generated instances.     

Optimal strategies for asset allocation and consumption under stochastic volatility

Selecting optimal asset allocation and consumption strategies is an important, but difficult, topic in modern finance. The dynamics is governed by a nonlinear partial differential equation. Stochastic volatility adds further complication. Even to obtain a numerical solution is challenging. Here, we develop a closed-form approximate solution. We show that our theoretical predictions for the optimal asset allocation strategy and the optimal consumption strategy are in surprisingly good agreement with the results from full numerical computations.     

Experimental studies of variable selection strategies based on constraint weights

Variable ordering heuristics that sample information before or during search in order to inform subsequent decisions have shown better performance and greater robustness than standard heuristics. One such strategy, the “weighted degree heuristic,” is based on weighting constraints according to their involvement in failure during search. A more recent approach uses “random probing” with restarting to gain information less subject to sampling bias. To date, these approaches have not been carefully analysed experimentally. In the present work, several important findings are presented, including a better delineation of the class of events that is sampled, an analysis of the importance of informed choices at the beginning of search, and a demonstration that random probing identifies sources of global contention effectively even when these are not clearly demarcated. These experiments show how empirical analysis can clarify subtle issues in the analysis of heuristic procedures for difficult search problems.     

Spline smoothing under constraints on derivatives

An efficient algorithm for computing a smoothing polynomial splines under inequality constraints on derivatives is introduced where both order and breakpoints ofs can be prescribed arbitrarily. By using the B-spline representation ofs, the original semi-infinite constraints are replaced by stronger finite ones, leading to a least squares problem with linear inequality constraints. Then these constraints are transformed into simple box constraints by an appropriate substitution of variables so that efficient standard techniques for solving such problems can be applied. Moreover, the smoothing term commonly used is replaced by a cheaply computable approximation. All matrix transformations are realized by numerically stable Givens rotations, and the band structure of the problem is exploited as far as possible.     

Asset allocation strategies in the presence of liability constraints

The performance of portfolio managers is usually assessed by comparing their allocation strategies to a benchmark portfolio. A major issue for portfolio managers of liability driven institutions is that no benchmark is given to them, although they face mid-term objectives with short term constraints. No performance attribution methodology may then be used to serve as a reference. Assessing the performance of the asset manager as an agent, represents a major stake for the institution as a principal delegating a mandate of asset management. We propose an optimal asset allocation approach taking into account liability constraints to build a benchmark. This benchmark will be used to compare the ex-post effective performance of the asset manager to the effective performance of the ex-ante optimal dynamic asset allocation.     

On the convergence of a class of algorithms using linearly independent search directions

Powell has shown that the cyclic coordinate method with exact searches may not converge to a stationary point. In this note we consider a more general class of algorithms for unconstrained minimization, and establish their convergence under the assumption that the objective function has a unique minimum along any line.     

Estimating a density under pointwise constraints on the derivatives

Suppose we want to estimate a density at a point where we know the values of its first or higher order derivatives. In this case a given kernel estimator of the density can be modified by adding appropriately weighted kernel estimators of these derivatives. We give conditions under which the modified estimators are asymptotically normal. We also determine the optimal weights. When the highest derivative is known to vanish at a point, then the bias is asymptotically negligible at that point and the asymptotic variance of the kernel estimator can be made arbitrarily small by choosing a large bandwidth.     

Conjugate duality in the optimization of the search for a target with generalized conditionally deterministic motion

A target moves in Euclideann-spaceR ⁿ according to the generalized conditionally deterministic law. The search density that accumulates on the target during its route determines the probability of detection. A necessary and sufficient condition for the search density (x, t) to be optimal is first represented, when there are two types of constraints for the search density: pointwise constraints and total-amount constraints. The second part consists of formulation of the dual problem with the aid of sensitivity parameters for the constraints. By using the dual functional, we obtain the maximal error from the minimum value of the primal objective functional for an arbitrary feasible . Finally, we study the discretized case, which is necessary for numerical calculations.