Robust shortest path planning and semicontractive dynamic programming

In this article, we consider shortest path problems in a directed graph where the transitions between nodes are subject to uncertainty. We use a minimax formulation, where the objective is to guarantee that a special destination state is reached with a minimum cost path under the worst possible instance of the uncertainty. Problems of this type arise, among others, in planning and pursuit‐evasion contexts, and in model predictive control. Our analysis makes use of the recently developed theory of abstract semicontractive dynamic programming models. We investigate questions of existence and uniqueness of solution of the optimality equation, existence of optimal paths, and the validity of various algorithms patterned after the classical methods of value and policy iteration, as well as a Dijkstra‐like algorithm for problems with nonnegative arc lengths.© 2016 Wiley Periodicals, Inc. Naval Research Logistics 66:15–37, 2019     

On the polyhedral structure of two‐level lot‐sizing problems with supplier selection

In this article, we study a two‐level lot‐sizing problem with supplier selection (LSS), which is an NP‐hard problem arising in different production planning and supply chain management applications. After presenting various formulations for LSS, and computationally comparing their strengths, we explore the polyhedral structure of one of these formulations. For this formulation, we derive several families of strong valid inequalities, and provide conditions under which they are facet‐defining. We show numerically that incorporating these valid inequalities within a branch‐and‐cut framework leads to significant improvements in computation. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 647–666, 2017     

A practical organizational efficiency measure

There is often a call in any organization to make the system ‘more efficient’. This document describes a novel framework for measuring organizational efficiency at the microeconomic level. We show how this framework can be used to monitor an organization using data typically available in extant performance management frameworks. This is most useful in large organizations with eclectic outputs where resources may be too constrained to perform industry-level analyses, such as data envelope analysis, to infer efficiency. This method helps illuminate how the factors of an organization’s internal practices can affect its efficient use of resources.     

Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem

The reformulation‐linearization technique (RLT) is a methodology for constructing tight linear programming relaxations of mixed discrete problems. A key construct is the multiplication of “product factors” of the discrete variables with problem constraints to form polynomial restrictions, which are subsequently linearized. For special problem forms, the structure of these linearized constraints tends to suggest that certain classes may be more beneficial than others. We examine the usefulness of subsets of constraints for a family of 0–1 quadratic multidimensional knapsack programs and perform extensive computational tests on a classical special case known as the 0–1 quadratic knapsack problem. We consider RLT forms both with and without these inequalities, and their comparisons with linearizations derived from published methods. Interestingly, the computational results depend in part upon the commercial software used. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Intellectual spring cleaning: it’s time for a military “Do Not Read” list; and some sources that should be on that list

Military reading lists, intended to promote professional reading and in turn enhance education and develop critical thinking skills and sound judgement, recommend key texts to military personnel. This is a noble intent but the lists themselves, while generally good, are not flawless. Critiques of military reading lists often focus on what sources they are missing. This article offers its own critique but from a different perspective. It does so by analysing why some sources, which have become outdated, are based on faulty or incomplete research, have been thoroughly disproven, or some combination of the above, nevertheless linger on military reading lists. It then offers a short list of such sources, which it recommends be either removed from existing reading lists or accompanied by other sources that place the original source in appropriate historical context. Where applicable, it also recommends alternative sources that provide insights into the same subject matter. In so doing, this article is intended generate debate and to assist militaries to achieve a better balance between evaluation, induction and retention of valid knowledge on one hand, and rejection of outdated or flawed knowledge on the other.     

Optimal service rates of a service facility with perishable inventory items

In this paper we optimally control service rates for an inventory system of service facilities with perishable products. We consider a finite capacity system where arrivals are Poisson‐distributed, lifetime of items have exponential distribution, and replenishment is instantaneous. We determine the service rates to be employed at each instant of time so that the long‐run expected cost rate is minimized for fixed maximum inventory level and capacity. The problem is modelled as a semi‐Markov decision problem. We establish the existence of a stationary optimal policy and we solve it by employing linear programming. Several numerical examples which provide insight to the behavior of the system are presented. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 464–482, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10021     

Two‐stage component test plans for testing the reliability of a series system

A system reliability is often evaluated by individual tests of components that constitute the system. These component test plans have advantages over complete system based tests in terms of time and cost. In this paper, we consider the series system with n components, where the lifetime of the i‐th component follows exponential distribution with parameter λ_i. Assuming test costs for the components are different, we develop an efficient algorithm to design a two‐stage component test plan that satisfies the usual probability requirements on the system reliability and in addition minimizes the maximum expected cost. For the case of prior information in the form of upper bounds on λ_i's, we use the genetic algorithm to solve the associated optimization problems which are otherwise difficult to solve using mathematical programming techniques. The two‐stage component test plans are cost effective compared to single‐stage plans developed by Rajgopal and Mazumdar. We demonstrate through several numerical examples that our approach has the potential to reduce the overall testing costs significantly. © 2002 John Wiley & Sons, Inc. Naval Research Logistics, 49: 95–116, 2002; DOI 10.1002/nav.1051     

Dominating sets for rectilinear center location problems with polyhedral barriers

In planar location problems with barriers one considers regions which are forbidden for the siting of new facilities as well as for trespassing. These problems are important since they model various actual applications. The resulting mathematical models have a nonconvex objective function and are therefore difficult to tackle using standard methods of location theory even in the case of simple barrier shapes and distance functions. For the case of center objectives with barrier distances obtained from the rectilinear or Manhattan metric, it is shown that the problem can be solved in polynomial time by identifying a dominating set. The resulting genuinely polynomial algorithm can be combined with bound computations which are derived from solving closely connected restricted location and network location problems. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 647–665, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10038     

Investment in production resource flexibility: An empirical investigation of methods for planning under uncertainty

We examine several methods for evaluating resource acquisition decisions under uncertainty. Traditional methods may underestimate equipment benefit when part of this benefit comes from decision flexibility. We develop a new, practical method for resource planning under uncertainty, and show that this approach is more accurate than several commonly used methods. We successfully applied our approach to an investment problem faced by a major firm in the aviation information industry. Our recommendations were accepted and resulted in estimated annual savings in excess of $1 million (US). © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

Waiting time distributions for transient bulk queues with general vehicle dispatching strategies

A numerical approach is presented for determining the waiting time distribution in a transient bulk-arrival, bulk-service queue. Vehicle departures from the queue are governed by a general dispatch strategy that includes holding with a variable release function and vehicle cancellations. The waiting time distribution of a customer (in a group) arriving at a given point in time is calculated by simulating the process in discrete time and determining at each step the probability the customer has left the system. The dispatch strategies require knowing the total length of the queue as well as the position a customer holds in the queue. An exact approach is compared to an accurate approximation which is 50 to 100 times faster. Comparisons are made with other approaches in the context of steady-state systems.