Aircraft weapon budgeting

This article considers the problem of allocating a fixed budget among alternative air-to-ground weapons. The weapon-budgeting problem is high-dimensional, involving all feasible combinations of aircraft, weapons, and targets. The decision maker's utility function is defined over kills of the various target types, but it is unrealistic to expect him to write down the mathematical formula for this function. The article suggests two procedures for reducing the dimension of the maximization problem and operating without exact knowledge of the utility function. The first procedure uses successive linear approximations to generate the set of “efficient” or undominated weapon allocations. The second procedure applies separability restrictions to the utility function, thereby reducing the overall maximization problem to a sequence of low-dimensional subproblems.     

A finite algorithm for concave minimization over a polyhedron

We present a new algorithm for solving the problem of minimizing a nonseparable concave function over a polyhedron. The algorithm is of the branch-and-bound type. It finds a globally optimal extreme point solution for this problem in a finite number of steps. One of the major advantages of the algorithm is that the linear programming subproblems solved during the branch-and-bound search each have the same feasible region. We discuss this and other advantages and disadvantages of the algorithm. We also discuss some preliminary computational experience we have had with our computer code for implementing the algorithm. This computational experience involved solving several bilinear programming problems with the code.     

New algorithms for (Q,r) systems with complete backordering using a fill-rate criterion

We present an algorithm which determines optimal parameter values for order quantity-reorder point systems with complete backordering. The service level is measured as fraction of demand satisfied directly from shelf, also known as “fill-rate.” This algorithm differs from existing algorithms because an exact cost function is used rather than an approximation. We also present a new heuristic algorithm, which is more efficient computationally than the optimal procedure and provides excellent results. Results of extensive computational experience also are reported.     

A penalty for concave minimization derived from the tuy cutting plane

A wide variety of optimization problems have been approached with branch-and-bound methodology, most notably integer programming and continuous nonconvex programming. Penalty calculations provide a means to reduce the number of subproblems solved during the branch-and-bound search. We develop a new penalty based on the Tuy cutting plane for the nonconvex problem of globally minimizing a concave function over linear constraints and continuous variables. Computational testing with a branch-and-bound algorithm for concave minimization indicates that, for the problems solved, the penalty reduces solution time by a factor ranging from 1.2 to 7.2. © 1994 John Wiley & Sons, Inc.     

An exact ceiling point algorithm for general integer linear programming

We present an algorithm called the exact ceiling point algorithm (XCPA) for solving the pure, general integer linear programming problem (P). A recent report by the authors demonstrates that, if the set of feasible integer solutions for (P) is nonempty and bounded, all optimal solutions for (P) are “feasible 1-ceiling points,” roughly, feasible integer solutions lying on or near the boundary of the feasible region for the LP-relaxation associated with (P). Consequently, the XCPA solves (P) by implicitly enumerating only feasible 1-ceiling points, making use of conditional bounds and “double backtracking.” We discuss the results of computational testing on a set of 48 problems taken from the literature.     

A branch‐and‐price algorithm for parallel machine scheduling with time windows and job priorities

This paper presents a branch‐and‐price algorithm for scheduling n jobs on m nonhomogeneous parallel machines with multiple time windows. An additional feature of the problem is that each job falls into one of ρ priority classes and may require two operations. The objective is to maximize the weighted number of jobs scheduled, where a job in a higher priority class has “infinitely” more weight or value than a job in a lower priority class. The methodology makes use of a greedy randomized adaptive search procedure (GRASP) to find feasible solutions during implicit enumeration and a two‐cycle elimination heuristic when solving the pricing subproblems. Extensive computational results are presented based on data from an application involving the use of communications relay satellites. Many 100‐job instances that were believed to be beyond the capability of exact methods, were solved within minutes. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Transportation type problems with quantity discounts

It is known to be real that the per unit transportation cost from a specific supply source to a given demand sink is dependent on the quantity shipped, so that there exist finite intervals for quantities where price breaks are offered to customers. Thus, such a quantity discount results in a nonconvex, piecewise linear functional. In this paper, an algorithm is provided to solve this problem. This algorithm, with minor modifications, is shown to encompass the “incremental” quantity discount and the “fixed charge” transportation problems as well. It is based upon a branch-and-bound solution procedure. The branches lead to ordinary transportation problems, the results of which are obtained by utilizing the “cost operator” for one branch and “rim operator” for another branch. Suitable illustrations and extensions are also provided.     

(0, 1) hyperbolic programming problems

In the first part of this paper we study the unconstrained {0, 1} hyperbolic programming problem treated in [1]. We describe a new algorithm for this problem which produces an optimal solution by scanning just once the set of fractions to be analysed. This algorithm shows better computing performance than the one described in [1]. In the second part we study the {0, 1} hyperbolic programming problem with constraints given by inequalities on nondeereasing pseudo-boolean functions. We describe a “branch and bound” type algorithm for this problem.     

Decomposing inventory routing problems with approximate value functions

We present a time decomposition for inventory routing problems. The methodology is based on valuing inventory with a concave piecewise linear function and then combining solutions to single‐period subproblems using dynamic programming techniques. Computational experiments show that the resulting value function accurately captures the inventory's value, and solving the multiperiod problem as a sequence of single‐period subproblems drastically decreases computational time without sacrificing solution quality. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Steady-state approximation of a multiechelon multi-indentured repairable-item inventory system with a single repair facility

We model a two-echelon multi-indentured repairable-item inventory system where each “base” has a maximum number of identical online machines, and each machine consists of several module types. Machine failures are due to module failures and occur according to an exponential distribution. When a machine fails, the failed module is replaced by an identical spare module if one is available. Otherwise, the module is backordered. All failed modules go to a single “depot” repair facility which consists of a finite number of identical repairmen who are able to repair any module type in an exponentially distributed time, although the repair rates for different module types may differ. The principal contribution of this article is an approximation algorithm for calculating the steady-state characteristics of the system. In comparison with simulation results, the algorithm is quite accurate and computationally efficient. © 1993 John Wiley & Sons, Inc.     

An algorithm and new penalties for concave integer minimization over a polyhedron

We present a branch-and-bound algorithm for globally minimizing a concave function over linear constraints and integer variables. Concave cost functions and integer variables arise in many applications, such as production planning, engineering design, and capacity expansion. To reduce the number of subproblems solved during the branch-and-bound search, we also develop a framework for computing new and existing penalties. Computational testing indicates that penalties based on the Tuy cutting plane provide large decreases in solution time for some problems. A combination of Driebeek-Tomlin and Tuy penalties can provide further decreases in solution time. © 1994 John Wiley & Sons, Inc.     

Interdiction models for delaying adversarial attacks against critical information technology infrastructure

Information technology (IT) infrastructure relies on a globalized supply chain that is vulnerable to numerous risks from adversarial attacks. It is important to protect IT infrastructure from these dynamic, persistent risks by delaying adversarial exploits. In this paper, we propose max‐min interdiction models for critical infrastructure protection that prioritizes cost‐effective security mitigations to maximally delay adversarial attacks. We consider attacks originating from multiple adversaries, each of which aims to find a “critical path” through the attack surface to complete the corresponding attack as soon as possible. Decision‐makers can deploy mitigations to delay attack exploits, however, mitigation effectiveness is sometimes uncertain. We propose a stochastic model variant to address this uncertainty by incorporating random delay times. The proposed models can be reformulated as a nested max‐max problem using dualization. We propose a Lagrangian heuristic approach that decomposes the max‐max problem into a number of smaller subproblems, and updates upper and lower bounds to the original problem via subgradient optimization. We evaluate the perfect information solution value as an alternative method for updating the upper bound. Computational results demonstrate that the Lagrangian heuristic identifies near‐optimal solutions efficiently, which outperforms a general purpose mixed‐integer programming solver on medium and large instances.     

A descent approach to solving the complementary programming problem

In recent years, much attention has focused on mathematical programming problems with equilibrium constraints. In this article we consider the case where the constraints are complementarity constraints. Problems of this type arise, for instance, in the design of traffic networks. We develop here a descent algorithm for this problem that will converge to a local optimum in a finite number of iterations. The method involves solving a sequence of subproblems that are linear programs. Computational tests comparing our algorithm with the branch-and-bound algorithm in [7] bear out the efficacy of our method. When solving large problems, there is a definite advantage to coupling both methods. A local optimum incumbent provided by our algorithm can significantly reduce the computational effort required by the branch-and-bound algorithm.     

Maximizing the ratio of two convex functions over a convex set

The purpose of this article is to present an algorithm for globally maximizing the ratio of two convex functions f and g over a convex set X. To our knowledge, this is the first algorithm to be proposed for globally solving this problem. The algorithm uses a branch and bound search to guarantee that a global optimal solution is found. While it does not require the functions f and g to be differentiable, it does require that subgradients of g can be calculated efficiently. The main computational effort of the algorithm involves solving a sequence of subproblems that can be solved by convex programming methods. When X is polyhedral, these subproblems can be solved by linear programming procedures. Because of these properties, the algorithm offers a potentially attractive means for globally maximizing ratios of convex functions over convex sets. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Robust shortest path problems with two uncertain multiplicative cost coefficients

We consider a robust shortest path problem when the cost coefficient is the product of two uncertain factors. We first show that the robust problem can be solved in polynomial time by a dual‐variable enumeration with shortest path problems as subproblems. We also propose a path enumeration approach using a K ‐shortest paths finding algorithm that may be efficient in many real cases. An application in hazardous materials transportation is discussed, and the solution methods are illustrated by numerical examples. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Weak order stability under risk

The assessment of a Bernoulli utility function is often accomplished by an approximation process which makes use of ever more information on the preference as it is elicited from a decision maker. Simultaneous approximations of the utility function and the underlying distributions are generally not sufficient for the expectations to converge to the expected value of the respective limits. We give various sufficient stability conditions for the expected utility. All these conditions contain some “uniformness”. © 1995 John Wiley & Sons, Inc.     

Production to order and off‐line inspection when the production process is partially observable

This study combines inspection and lot‐sizing decisions. The issue is whether to INSPECT another unit or PRODUCE a new lot. A unit produced is either conforming or defective. Demand need to be satisfied in full, by conforming units only. The production process may switch from a “good” state to a “bad” state, at constant rate. The proportion of conforming units in the good state is higher than in the bad state. The true state is unobservable and can only be inferred from the quality of units inspected. We thus update, after each inspection, the probability that the unit, next candidate for inspection, was produced while the production process was in the good state. That “good‐state‐probability” is the basis for our decision to INSPECT or PRODUCE. We prove that the optimal policy has a simple form: INSPECT only if the good‐state‐probability exceeds a control limit. We provide a methodology to calculate the optimal lot size and the expected costs associated with INSPECT and PRODUCE. Surprisingly, we find that the control limit, as a function of the demand (and other problem parameters) is not necessarily monotone. Also, counter to intuition, it is possible that the optimal action is PRODUCE, after revealing a conforming unit. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

“Effing” the military: a political misunderstanding of management

The use of commercial business management techniques is widespread in all government departments, including the Ministry of Defence. This article examines the use of popular management techniques in the Armed Forces and argues that their application is misplaced. It looks at what the “effs” – “efficiency” and “effectiveness” – mean in the business world and to the Armed Forces. It compares the definitions both in business and the Armed Forces and finds that there are few, if any, situations where the same measurements can be applied. Whilst many management techniques are suited for business, the function of the Armed Forces and its output cannot be measured in the same way, complicated by the different metrics of “efficiency” in peace and in war. This difference may not be clearly understood by some politicians, or indeed by some senior military personnel. Using examples from some of the most popular management techniques such as “Lean” and “Agile” it is possible to see that their use might actually diminish the capabilities of the Armed Forces when it comes to performing their principal role – the use of force to achieve political objectives.     

An exact branch‐and‐price algorithm for multitasking scheduling on unrelated parallel machines

We consider the multitasking scheduling problem on unrelated parallel machines to minimize the total weighted completion time. In this problem, each machine processes a set of jobs, while the processing of a selected job on a machine may be interrupted by other available jobs scheduled on the same machine but unfinished. To solve this problem, we propose an exact branch‐and‐price algorithm, where the master problem at each search node is solved by a novel column generation scheme, called in‐out column generation, to maintain the stability of the dual variables. We use a greedy heuristic to obtain a set of initial columns to start the in‐out column generation, and a hybrid strategy combining a genetic algorithm and an exact dynamic programming algorithm to solve the pricing subproblems approximately and exactly, respectively. Using randomly generated data, we conduct numerical studies to evaluate the performance of the proposed solution approach. We also examine the effects of multitasking on the scheduling outcomes, with which the decision maker can justify making investments to adopt or avoid multitasking.     

Application of generalized benders decomposition to a nonlinear distribution system design problem

The Benders decomposition method has been successfully applied to a classic multistage, multiproduct distribution-system design problem with fixed and linear variable costs. In other applications, however, distribution-center variable throughput costs often show nonlinearity due to economies of scale. This article extends the standard problem formulation to a nonlinear distribution-system design problem and incorporates the generalized Benders decomposition method in an efficient solution algorithm. Approximate dual prices are generated by solving linear instead of concave subproblems. Thereafter these prices are adjusted to induce a more accurate representation of the concave cost function before they are incorporated in the Benders cuts, which are used to generate new binary solutions. The computational results are encouraging.