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     

Exact algorithms and bounds for the dynamic assignment interdiction problem

We study a multi‐stage dynamic assignment interdiction (DAI) game in which two agents, a user and an attacker, compete in the underlying bipartite assignment graph. The user wishes to assign a set of tasks at the minimum cost, and the attacker seeks to interdict a subset of arcs to maximize the user's objective. The user assigns exactly one task per stage, and the assignment costs and interdiction impacts vary across stages. Before any stage commences in the game, the attacker can interdict arcs subject to a cardinality constraint. An interdicted arc can still be used by the user, but at an increased assignment cost. The goal is to find an optimal sequence of assignments, coupled with the attacker's optimal interdiction strategy. We prove that this problem is strongly NP‐hard, even when the attacker can interdict only one arc. We propose an exact exponential‐state dynamic‐programming algorithm for this problem as well as lower and upper bounds on the optimal objective function value. Our bounds are based on classical interdiction and robust optimization models, and on variations of the DAI game. We examine the efficiency of our algorithms and the quality of our bounds on a set of randomly generated instances. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 373–387, 2017     

All Counterinsurgency is Local: Counterinsurgency and Rebel Legitimacy

Abstract

Although the concept of legitimacy is central to Western counterinsurgency theory, most discourse in this area black-boxes the concept. It hence remains under-specified in many discussions of counterinsurgency. Fortunately, recent research on rebel governance and legitimacy contributes to our understanding of the problems faced by counterinsurgents who want to boost state legitimacy while undermining that of the rebels. Taken together, this research illustrates that a rational choice approach to legitimacy is simplistic; that micro-level factors ultimately drive legitimacy dynamics; and that both cooption of existing legitimate local elites and their replacement from the top–down is unlikely to succeed. Western counterinsurgency doctrine has failed to grasp the difficulties this poses for it.     

An efficient SPH methodology for modelling mechanical characteristics of particulate composites

Particulate composites are one of the widely used materials in producing numerous state-of-the-art components in biomedical, automobile, aerospace including defence technology. Variety of modelling techniques have been adopted in the past to model mechanical behaviour of particulate composites. Due to their favourable properties, particle-based methods provide a convenient platform to model failure or fracture of these composites. Smooth particle hydrodynamics (SPH) is one of such methods which demonstrate excellent potential for modelling failure or fracture of particulate composites in a Lagrangian setting. One of the major challenges in using SPH method for modelling composite materials depends on accurate and efficient way to treat interface and boundary conditions. In this paper, a master-slave method based multi-freedom constraints is proposed to impose essential boundary conditions and interfacial displacement constraints in modelling mechanical behaviour of composite materials using SPH method. The proposed methodology enforces the above constraints more accurately and requires only smaller condition number for system stiffness matrix than the procedures based on typical penalty function approach. A minimum cut-off value-based error criteria is employed to improve the compu-tational efficiency of the proposed methodology. In addition, the proposed method is further enhanced by adopting a modified numerical interpolation scheme along the boundary to increase the accuracy and computational efficiency. The numerical examples demonstrate that the proposed master-slave approach yields better accuracy in enforcing displacement constraints and requires approximately the same computational time as that of penalty method.     

A search game with a protector

A classic problem in Search Theory is one in which a searcher allocates resources to the points of the integer interval [1, n] in an attempt to find an object which has been hidden in them using a known probability function. In this paper we consider a modification of this problem in which there is a protector who can also allocate resources to the points; allocating these resources makes it more difficult for the searcher to find an object. We model the situation as a two‐person non‐zero‐sum game so that we can take into account the fact that using resources can be costly. It is shown that this game has a unique Nash equilibrium when the searcher's probability of finding an object located at point i is of the form (1 − exp (−λ_ix_i)) exp (−μ_iy_i) when the searcher and protector allocate resources x_i and y_i respectively to point i. An algorithm to find this Nash equilibrium is given. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47:85–96, 2000     

Solving partially observable agent‐intruder games with an application to border security problems

In this paper, we introduce partially observable agent‐intruder games (POAIGs). These games model dynamic search games on graphs between security forces (an agent) and an intruder given possible (border) entry points and high value assets that require protection. The agent faces situations with dynamically changing, partially observable information about the state of the intruder and vice versa. The agent may place sensors at selected locations, while the intruder may recruit partners to observe the agent's movement. We formulate the problem as a two‐person zero‐sum game, and develop efficient algorithms to compute each player's optimal strategy. The solution to the game will help the agent choose sensor locations and design patrol routes that can handle imperfect information. First, we prove the existence of ?‐optimal strategies for POAIGs with an infinite time horizon. Second, we introduce a Bayesian approximation algorithm to identify these ?‐optimal strategies using belief functions that incorporate the imperfect information that becomes available during the game. For the solutions of large POAIGs with a finite time horizon, we use a solution method common to extensive form games, namely, the sequence form representation. To illustrate the POAIGs, we present several examples and numerical results.