Min/max bounds for dynamic network flows

This paper presents an algorithm for determining the upper and lower bounds for arc flows in a maximal dynamic flow solution. The procedure is basically an extended application of the Ford-Fulkerson dynamic flow algorithm which also solves the minimal cost flow problem. A simple example is included. The presence of bounded optimal are flows entertains the notion that one can pick a particular solution which is preferable by secondary criteria.     

Allocation of resources to offensive strategic weapon systems

In this paper a very versatile game model is developed for use in the long range planning of our strategic force posture. This highly aggregate model yields optimal force mixes for the triad (land- and sea-based missile systems and bombers) under a variety of constraints. The model described here is a survivability model; however, it is shown how the model can still be used as a measure of overall system effectiveness. Constraints imposed on the problem include both SALT and budget limitations.     

Equivalent knapsack-type formulations of bounded integer linear programs: An alternative approach

In this paper we show that every bounded integer linear program can be transformed into an integer program involving one single linear constraint and upper and lower bounds on the variables, such that the solution space of the original problem coincides with that one of the equivalent knapsack-type problem.     

Search techniques for a nonlinear multiprocessor scheduling problem

The problem of assigning computer program modules to functionally similar processors in a distributed computer network is investigated. The modules of a program must be assigned among processors in such a way as to minimize interprocessor communication while taking advantage of affinities of certain modules to particular processors. This problem is formulated as a zero-one quadratic programming problem, but is more conveniently modeled as a directed acyclic search graph. The model is developed and a backward shortest path labeling algorithm is given that produces an assignment of program modules to processors. A non-backtracking branch-and-bound algorithm is described that uses a local neighborhood search at each stage of the search graph.     

A class of continuous nonlinear programming problems with time-delayed constraints

A general class of continuous time nonlinear problems is considered. Necessary and sufficient conditions for the existence of solutions are established and optimal solutions are characterized in terms of a duality theorem. The theory is illustrated by means of an example.     

The use of dynamic programming methodology for the solution of a class of nonlinear programming problems

This paper presents an application of a method for finding the global solution to a problem in integers with a separable objective function of a very general form. This report shows that there is a relationship between an integer problem with a separable nonlinear objective function and many constraints and a series of nonlinear problems with only a single constraint, each of which can be solved sequentially using dynamic programming. The first solution to any of the individual smaller problems that satisfies the original constraints in addition, will be the optimal solution to the multiply-constrained problem.     

Optimal interdiction policy for a flow network

This paper analyzes the problem faced by a field commander who, confronted by an enemy on N battlefields, must determine an interdiction policy for the enemy's logistics system which minimizes the amount of war material flowing through this system per unit time. The resource utilized to achieve this interdiction is subject to constraint. It can be shown that this problem is equivalent to determining the set of arcs Z* to remove subject to constraint from a directed graph G such that the resulting maximal flow is minimized. A branch and bound algorithm for the solution to this problem is described, and a numerical example is provided.     

Allocation of carrier-based attack aircraft using non-linear programming

The paper presents the formulation and several solutions of a model for allocating a fixed number of aircraft to carriers and to missions. The amount of damage that can be inflicted is maximized. A nonseparable concave nonlinear objective function expresses diminishing marginal damage. Linear constraints on aireraft, carrier space, and aircraft availability for missions are included. The model is solved using the sequential unconstrained minimization technique (SUMT). The model is presented in terms of a scenario. Several different exponential damage functions are treated, and S-shaped damage functions are discussed.     

A note on adaptive boiler tube pulling

This paper develops an adaptive algorithm for determining boiler tube pulling strategies by postulating a Beta prior on the probability that an individual tube is defective. This prior is updated according to Bayes' Rule as a result of the sample obtained during the tube pulling process.     

A note on a comparison of confidence interval techniques in truncated life tests

Several approximate procedures are available in the literature for obtaining confidence intervals for the parameter A of an exponential distribution based on time truncated samples. This paper contains the results of an empirical study comparing three of these procedures.