Generalized programming by linear approximation of the dual gradient: Equality constraints

A modified generalized programming procedure is presented for solving concave programming problems with equality constraints. The procedure constructs convenient linear approximations of the gradient of the dual and finds points where the approximating functions vanish. In the quadratic programming case, the procedure is finitely convergent. Global convergence is established for the non-quadratic case. Illustrative numerical examples are included.     

An operator theory of parametric programming for the generalized transportation problem: I. Basic theory

This paper gives a new organization of the theoretical results of the Generalized Transportation Problem with capacity constraints. A graph-theoretic approach is utilized to define the basis as a one-forest consisting of one-trees (a tree with an extra edge). Algorithmic development of the pivot-step is presented by the representation of a two-tree (a tree with two extra edges). Constructive procedures and proofs leading to an efficient computer code are provided. The basic definition of an operator theory which leads to the discussion of various operators is also given. In later papers we will present additional results on the operator theory for the generalized transportation problem based on the results in the present paper.     

A computation procedure for the exact solution of location-allocation problems with rectangular distances

A method is presented to locate and allocate p new facilities in relation to n existing facilities. Each of the n existing facilities has a requirement flow which must be supplied by the new facilities. Rectangular distances are assumed to exist between all facilities. The algorithm proceeds in two stages. In the first stage a set of all possible optimal new facility locations is determined by a set reduction algorithm. The resultant problem is shown to be equivalent to finding the p-median of a weighted connected graph. In the second stage the optimal locations and allocations are obtained by using a technique for solving the p-median problem.     

On the treatment of force-level constraints in times-equential combat problems

The treatment of force-level constraints in time-sequential combat optimization problems is illustrated by further studying the fire-programming problem of Isbell and Marlow. By using the theory of state variable inequality constraints from modern optimal control theory, sharper results are obtained on necessary conditions of optimality for an optimal fire-distribution policy (in several cases justifying conjectures made in previous analysis). This leads to simplification of the determination of the domains of controllability for extremals leading to the various terminal states of combat. (Additionally, some new results for the determination of boundary conditions for the adjoint variables in optimal control problems with state variable inequality constraints have arisen from this work.) Some further extensions of previous analysis of the fire-programming problem are also given. These clarify some key points in the solution synthesis. Some important military principles for target selection and the valuation of combat resources are deduced from the solution. As a result of this work, more general time-sequential combat optimization problems can be handled, and a more systematic solution procedure is developed.     

An operator theory of parametric programming for the transportation problem-I

This paper investigates the effect on the optimum solution of a (capacitated) transportation problem when the data of the problem (the rim conditions-i. e., the warehouse supplies and market demands-the per unit transportation costs and the upper bounds) are continuously varied as a (linear) function of a single parameter. An operator theory is developed and algorithms provided for applying rim and cost operators that effect the transformation of optimum solution associated with changes in rim conditions and unit costs. Bound operators that effect changes in upper bounds are shown to be equivalent to rim operators. The discussion in this paper is limited to basis preserving operators for which the changes in the data are such that the optimum basis structures are preserved.     

An economic model for planning strategic mobility posture

This paper describes a linear programming model used to perform cost-effectiveness analysis to determine the requirements for military strategic mobility resources. Expenditures for three classes of economic alternatives are considered: purchase of transportation resources; prepositioning of material; and augmentation of port facilities. The mix of economic alternatives that maximizes the effectiveness of the resultant transportation system is determined for a given investment level. By repeating the analysis for several levels of investment, a cost-effectiveness tradeoff curve can be developed.     

Location of facilities with rectangular distances among point and area destinations

This article is concerned with the optimal location of any number (n) of facilities in relation to any number (m) of destinations on the Euclidean plane. The criterion to be satisfied is the minimization of total weighted distances where the distances are rectangular. The destinations may be either single points, lines or rectangular areas. A gradient reduction solution procedure is described which has the property that the direction of descent is determined by the geometrical properties of the problem.     

The resource constrained project scheduling problem with multiple crashable modes: An exact solution method

We introduce a formulation and an exact solution method for a nonpreemptive resource constrained project scheduling problem in which the duration/cost of an activity is determined by the mode selection and the duration reduction (crashing) within the mode. This problem is a natural combination of the time/cost tradeoff problem and the resource constrained project scheduling problem. It involves the determination, for each activity, of its resource requirements, the extent of crashing, and its start time so that the total project cost is minimized. We present a branch and bound procedure and report computational results with a set of 160 problems. Computational results demonstrate the effectiveness of our procedure. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 107–127, 2001     

Explicit solution of partitioning problems over a 1‐dimensional parameter space

We consider a class of partitioning problems where the partitioned set is a finite set of real numbers and the objective function of a partition is a function of the vector whose coordinates are the sums of the elements in each part of the given partition (the number of such parts is assumed given). We obtain an explicit solution of such partitioning problem with polynomial complexity bounds. © John Wiley & Sons, Inc. Naval Research Logistics 47: 531–540, 2000     

Optimal scheduling of reader—systems

We consider a reader—writer system consisting of a single server and a fixed number of jobs (or customers) belonging to two classes. Class one jobs are called readers and any number of them can be processed simultaneously. Class two jobs are called writers and they have to be processed one at a time. When a writer is being processed no other writer or readers can be processed. A fixed number of readers and writers are ready for processing at time 0. Their processing times are independent random variables. Each reader and writer has a fixed waiting cost rate. We find optimal scheduling rules that minimize the expected total waiting cost (expected total weighted flowtime). We consider both nonpreemptive and preemptive scheduling. The optimal nonpreemptive schedule is derived by a variation of the usual interchange argument, while the optimal schedule in the preemptive case is given by a Gittins index policy. These index policies continue to be optimal for systems in which new writers enter the system in a Poisson fashion. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 483–495, 1998