Search

The U.S. Army Corps of Engineers is annually faced with the problem of determining which of several proposed civil works projects to fund. Each project has a specified cost. Furthermore, each project can contribute benefits in a number of different categories; for example, a water reservoir project may contribute benefits in the categories of flood control, power generation, river navigation, general recreation, conservation of fish and wildlife, water quality control, municipal and industrial water supply, irrigation, and other categories. Previous work by the Corps of Engineers has resulted in the development of methods for quantifying the benefit produced in a specific category by a particular project. However, because each project produces a multiplicity of benefits of a variety of types, a straightforward project selection procedure based on benefit cost ratios has obvious shortcomings. Many benefits have natural physical units of measure, but are difficult to measure in dollars. Even if all benefits could be assessed in dollars, they often accrue to different population segments and are hence qualitatively different. An uncritical summation even in this case may result in a loss of information relevant to the decision maker(s). Finally, a yes or no decision on a particular project should be made in the context of other projects with similar benefits which are competing for a part of the same limited supply of capital resources. Thus the desirability of a given project is dependent upon decisions made with respect to other related projects. Explicit consideration should therefore be given to sets of projects acting in concert. The purpose of this paper is to describe a computer program developed by the authors for use by Corps of Engineers planners as an aid in the project selection process. This program is based on a formulation of the multibenefit project selection problem as an integer programming problem. A specialized integer programming code developed by the first author is used to obtain specific solutions. The program can consider as many as 125 projects, each of which can produce benefits in any of 50 benefit categories. Computation times for typical problems are on the order of one minute for a UNIVAC 1108. The paper first summarizes the basic problem formulation. The integer programming algorithm for solving the program is then described. Finally, a summary of computational experience is prescribed.

This paper solves a particular min-max problem where the minimizing variables not only influence the performance index but also constrain the domain of action of the maximizing variables. The problem is approached as minimization of a supremal value function. It is shown here that if a weaker form of the classical sensitivity theorem of non-linear programming holds, then directional derivatives, and in some cases even ordinary derivatives, of the supremal value function exist. The existence of ordinary derivatives is especially useful for computation purposes, in that case the min-max becomes a stationary point under equality constraints with respect to both players separately. The problem originates from a new approach for control design of a dynamic uncertain system when a bound in norm of the approximation error is guaranteed.

Surveillance systems are often required to simultaneously estimate the trajectory parameters of several targets. This problem is complicated significantly in high target density situations since the individual data sequences required by standard estimation algorithms are difficult to form. This paper discusses certain computational aspects of assigning closely spaced sensor returns to individual tracks. We refer to this as a "multiple choice" estimation problem since the real tracks are generally hidden in a large set F of feasible tracks. Forming the feasible track set F on the basis of a priori knowledge of the problem is the first step on the assignment process. A subset of the potential tracks contained in F is then selected on the basis accomplished by 0-1 integer programming, as we now illustrate for a simple discrete linear problem.

In this paper a technique is proposed for solving the discrete terminal control problem. The plant is assumed to be linear with bounded input. The cost function is a quadratic function of the terminal states. The approach that is used is to change the original minimization problem with differential constraints into a mathematical programming formulation. Due to the linearity of the problem this is a simple operation. Since the cost function is quadratic, the resulting mathematical programming problem becomes a quadratic programming problem. A computationally efficient solution to this quadratic programming problem is presented which uses the properties of the solution of the discrete optimal terminal control problem. For instance it is shown that if the desired terminal point lies outside the reachable set, the optimum control will have at most n-1 control intervals, where n is the order of the system, when the control is not at its maximum magnitude. For the case where the desired point lies within the reachable set, there exists at least one control sequence with at most n intervals when the control is not at its maximum magnitude. The algorithm which is developed uses these properties to avoid the manipulation of any matrices of order greater than n.

The last few years have seen great improvements in computational methods for solving large scale systems. In this paper we outline some of these new methods, particularly those involving improvements in the simplex method, generalized upper bounds, branch and bound methods, special ordered sets and the method of approximation programming.