Cyclic best first search: Using contours to guide branch‐and‐bound algorithms

The cyclic best‐first search (CBFS) strategy is a recent search strategy that has been successfully applied to branch‐and‐bound algorithms in a number of different settings. CBFS is a modification of best‐first search (BFS) that places search tree subproblems into contours which are collections of subproblems grouped in some way, and repeatedly cycles through all non‐empty contours, selecting one subproblem to explore from each. In this article, the theoretical properties of CBFS are analyzed for the first time. CBFS is proved to be a generalization of all other search strategies by using a contour definition that explores the same sequence of subproblems as any other search strategy. Further, a bound is proved between the number of subproblems explored by BFS and the number of children generated by CBFS, given a fixed branching strategy and set of pruning rules. Finally, a discussion of heuristic contour‐labeling functions is provided, and proof‐of‐concept computational results for mixed‐integer programming problems from the MIPLIB 2010 database are shown. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 64–82, 2017     

The National Movement for the Liberation of Azawad factor in the Mali crisis

Mali has been a battleground for more than a year now. While the armed conflict came in the aftermath of the Libyan crisis that left the regional security environment depleted, it also served as a catalyst for the collapse of state authority in Mali. This created conditions conducive for the proliferation of, and attacks by, radical religious armed groups in the northern regions of the country, including the Tuareg armed movement: the National Movement for the Liberation of Azawad (MNLA). But, far from being a new phenomenon, the Tuareg-led armed insurrection in the northern regions is as old as the post-colonial Malian state, and continues to pose tremendous challenges in West Africa and the Sahel region for both regional and extra-regional actors. The recent crisis in the Sahel region is seen as one of the most serious since the end of the Cold War, with anticipated dire long-term impacts on the security of the region and beyond. While attention is predominantly focused on defeating the jihadist groups that have threatened the survival of the Malian state, one must not lose sight of the fact that the ‘Tuareg Factor’, as represented by the rebellion launched by MNLA, remains critical both in terms of appreciating the deterioration of the situation and attempting to frame long-lasting solutions. The paper argues that the Tuareg's persistent recourse to rebellion against Bamako needs to be understood within a historical trajectory that takes into consideration three key parameters: firstly, the post-colonial state in Mali and its African leadership's relations with the descendants of the Tuareg communities; secondly, the amalgamation created by the so-called war on terror; and, finally, the contradictions of the democratisation process of the 1990s.¹1 This article is based on field research carried out between 2008 and 2013 on the ‘Resurgence of Tuareg-led Rebellions’.     

GLOBALIZING REAGAN'S INF TREATY

When it was concluded more than a quarter century ago, the Intermediate-Range Nuclear Forces (INF) Treaty between the United States and the Soviet Union was hailed as a disarmament watershed, eliminating entire classes of nuclear missiles from the arsenals of the arms-racing Cold War superpowers. Over the intervening decades, there have been repeated calls to convert this legacy treaty into a new international norm against nuclear and missile proliferation by broadening it into a global prohibition on ground-launched ballistic and cruise missiles with ranges between 500 and 5,500 kilometers. Indeed, variations on this proposal have been knocking around for so long and with so little success that the entire concept has come to be dismissed by many knowledgeable insiders as something of a farce. Looking beyond its inauspicious pedigree, however, this viewpoint suggests that the time is opportune for Washington to give the idea a fresh look. Drawing on a detailed review of the history of “Global INF” and an analysis of the contemporary context, the author recommends that the Obama administration consider a simple declaratory approach that promises modest initial benefits, avoids previous and foreseeable pitfalls, and plausibly lays a solid foundation for achieving significant long-term progress.     

Probabilistic a priori routing-location problems

In many routing-location models customers located at nodes of a network generate calls for service with known probabilities. The customers that request service in a particular day are served by a single server that performs a service tour visiting these customers. The order of providing service to customers for each potential list of calls is uniquely defined by some a priori fixed basic sequence of all the customers (a priori tour). The problems addressed in this article are to find an optimal home location or an optimal basic sequence for the server so as to minimize the expectation of a criterion. The following criteria are considered: the total waiting time of all the customers, the total length of the tour, the maximal waiting time of a customer, the average traveled length per customer, and the average waiting time per customer. We present polynomial-time algorithms for the location problems. For the routing problems we present lower bounds that can be calculated efficiently (in polynomial time) and used in a branch-and-bound scheme. © 1994 John Wiley & Sons, Inc.     

A dynamic-programming approach to continuous-review obsolescent inventory problems

Inventory models of modern production and service operations should take into consideration possible exogenous failures or the abrupt decline of demand resulting from obsolescence. This article analyzes continuous-review versions of the classical obsolescence problem in inventory theory. We assume a deterministic demand model and general continuous random times to obsolescence (“failure”). Using continuous dynamic programming, we investigate structural properties of the problem and propose explicit and workable solution techniques. These techniques apply to two fairly wide (and sometimes overlapping) classes of failure distributions: those which are increasing in failure rate and those which have finite support. Consequently, several specific failure processes in continuous time are given exact solutions. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 757–774, 1997     

Changing the paradigm: Simulation,now a method of first resort

Decades ago, simulation was famously characterized as a “method of last resort,” to which analysts should turn only “when all else fails.” In those intervening decades, the technologies supporting simulation—computing hardware, simulation‐modeling paradigms, simulation software, design‐and‐analysis methods—have all advanced dramatically. We offer an updated view that simulation is now a very appealing option for modeling and analysis. When applied properly, simulation can provide fully as much insight, with as much precision as desired, as can exact analytical methods that are based on more restrictive assumptions. The fundamental advantage of simulation is that it can tolerate far less restrictive modeling assumptions, leading to an underlying model that is more reflective of reality and thus more valid, leading to better decisions. Published 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 293–303, 2015     

Optimal replacement of continuously degrading systems in partially observed environments

Motivated by wind energy applications, we consider the problem of optimally replacing a stochastically degrading component that resides and operates in a partially observable environment. The component's rate of degradation is modulated by the stochastic environment process, and the component fails when it is accumulated degradation first reaches a fixed threshold. Assuming periodic inspection of the component, the objective is to minimize the long‐run average cost per unit time of performing preventive and reactive replacements for two distinct cases. The first case examines instantaneous replacements and fixed costs, while the second considers time‐consuming replacements and revenue losses accrued during periods of unavailability. Formulated and solved are mixed state space, partially observable Markov decision process models, both of which reveal the optimality of environment‐dependent threshold policies with respect to the component's cumulative degradation level. Additionally, it is shown that for each degradation value, a threshold policy with respect to the environment belief state is optimal if the environment alternates between two states. The threshold policies are illustrated by way of numerical examples using both synthetic and real wind turbine data. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 395–415, 2015