Search

This paper is concerned with the problem of determining diode optimal representations for two levels of logic with multiple inputs and multiple outputs. Previous papers by the authors and others have formulated algorithms for obtaining optimal representations. However, the linear integer programming problem obtained is often prohibitively large. In the present paper, methods for reducing the size of the problem before and after expanding into the linear integer format are presented. These methods insure that at least one optimal representation for the system is retained after each reduction. Examples are given.

Although computer-aided circuit analysis has advanced quite rapidly in the last few years, there is considerable room for applications of network theory to the computer-aided design of electronic networks. In this paper the scope of network theory is generalized to include multiterminal networks in which the voltages and currents are related by inequality as well as equality relations. Two classes of new singular elements useful in electronic network design are introduced. The first class generalizes the allowed v-i pairs of a nullator and its multiterminal counterparts. The second constrains the allowed pairs of the norator and its multiterminal counterparts. The new singular elements are used to constrain network variables and to represent bounded adjustable elements. In this way the role of the objectives and element constraints are handled in a unified scheme. By imbedding these elements in a network, the synthesis problem is transformed into a problem of analysis of a circuit containing singular elements. Although the method is applicable to a wide variety of circuits, only the dc linear case is treated here. By keeping a linear formulation throughout, the analysis can be done with linear programming techniques with the corresponding theoretical and computational advantages. On-line programs for interactive time-share use have been written, and their flow charts are given in the paper. They provide a very efficient on-line design system that avoids the iterative analysis optimization approach. The gains achieved in computation time are of several orders of magnitude, and the solutions are guaranteed to be found.

The purpose of this paper is to present a method of implicit enumeration that can be used in reliability problems to maximize system reliability subject to cost constraints. The method is based on a stochastic approach in which probability distributions are attached to families of allocations. Probability distributions permit the experienced scheduler to apply his experience as well as factors which are not taken directly into account by the mathematical form of the problem. This feature together with getting near-optimal solutions are its principal features. When compared to other methods, speed is gained because the cost projection part of the method deals with functions of random variables rather than methods such as linear programming. The method is presented for systems in which all components are in series.

This paper defines a mathematical model which simulates the growth of a power system and determines the least cost expansion plan for a system of distribution substations. A new approach employing linear and integer programming is used to optimize the system's substation capacities subject to the constraints of cost, load, voltage, and reserve requirements. The model has been successfully applied to a 1600 square mile urban area served by 70 distribution substations.

This paper discusses the use of linear programming techniques for the design of infinite impulse response (IIR) digital filters. In particular, it is shown that, in theory, a weighted equiripple approximation to an arbitrary magnitude function can be obtained in a predictable number of applications of the simplex algorithm of linear programming. When one implements the design algorithm, certain practical difficulties (e.g., coefficient sensitivity) limit the range of filters which can be designed using this technique. However, a fairly large number of IIR filters have been successfully designed and several examples will be presented to illustrate the range of problems for which we found this technique to be useful.

A new method is proposed in this paper to solve a single-stage expansion problem for a transmission network, given future generation and load patterns, and alternative types of lines available, subject to overload, reliability and right-of-way constraints. The problem is formulated as a series of zero-one integer programs which are solved by an efficient branch-and-bound algorithm. Complexity is reduced by the concepts of optimal cost-capacity curves and screening algorithms. A sample study is shown and the method is implemented in a computer program.

This paper applies the Dantzig-Wolfe decomposition technique to control systems governed by Markov chains, and the three usual types of costs: 1) the average cost attained until a target state is reached, 2) discounted cost, 3) average cost per unit time. Additional systems constraints are allowed. A technique for subdividing or "essentially" decomposing the problem is developed, and a Markov interpretation is given to each subsystem. The special significance, for this problem, of the extreme points and rays of the subproblem, is discussed.

At the present time, very few organizations appear to be using the more complex, portfolio based, resource allocation models proposed in the literature. It is the objective of this paper to discuss some extensions and improvements to a basic linear programming approach to decision making in R&D, pointing out their weaknesses whether of a theoretical or practical nature.

This paper considers the feasibility of simultaneous multicommodity flows with specified values in a capacity-limited communication network. A class of "bi-path networks" is defined and some basic topological properties of such networks are derived. It is shown that a bi-path network B satisfies a requirement matrix \bar{R} if, and only if, the value of each simple cutset in B is no smaller than the corresponding cutset value in the "requirement network" R . This result can be readily extended to the case with time-varying requirements. The optimal synthesis can be solved using linear programming techniques if linear cost can be assumed.

In this paper, a multistage linear programming method of pattern recognition is proposed. The usual n-dimensional linear program has been split up into n stages of a one-dimensional linear program in such a way that more and more patterns belonging to two classes A and B are correctly classified as we proceed to higher and higher stages. It has been shown that if the threshold is kept fixed for ali the stages, the formulation of the problem entails a preprocessing of the feature coordinates; on the other hand, if the threshold is allowed to be different values in different stages, no such preprocessing is required. The application of the proposed method for the recognition of two handwritten Bengali characters has been discussed and compared with the results of other methods.

When a decision maker is assessing a preference (utility) function for assets (wealth), it is natural for him to start by making some quantitative assessments of the certainty equivalents of a few simple gambles and some qualitative statements specifying any regions in which he feels risk-averse or risk-seeking and any regions in which he feels decreasingly or increasingly risk-averse or risk-seeking. Several questions then arise. Does any preference function exist which satisfies all the quantitative and qualitative restrictions simultaneously, that is, are the restrictions consistent? If so, how far do they determine the preference function? How might one fair a "smooth" function satisfying the restrictions? This paper is addressed to these questions. First the problem is introduced in some detail, and the concepts involved reviewed. Then the case is considered where the qualitative restrictions only specify regions of risk-aversion or risk-seeking. It turns out in this case that all the restrictions are linear in certain quantities, so that the existence problem is essentially one of satisfying linear constraints. Furthermore, finding the maximum or minimum solution at a specified point is exactly a linear programming problem. Also discussed briefly are the possibility that some smoothing problems might simply introduce a nonlinear objective function (though the general smoothing problem is more complicated) and the problem of making the derivative of the preference function continuous (which is not always possible). If regions of increasing or decreasing risk-aversion are also given, the problem becomes much more difficult.

The purpose of this paper is to obtain an optimum redundancy of the parallel system by a variational technique. The objective function is to maximize the system profit. A simple computational procedure is obtained for the optimum design of the multistage parallel systems by this method. Two numerical examples are given in detail.

The paper develops a-method of determining the minimum amount of reactive power capacity installation required to satisfy constrained system voltage conditions. The solution gives both location and amount of reactive sources. Sensitivity parameters are the basis of the model, and linear programming is used to obtain the solution. The method is practical and static operating constraints are naturally included. Numerical examples illustrate the application of the method.

Generally, the synthesis of coherent spatial filters is restricted to the linear region of the transfer characteristic of a photographic film. However, a technique of synthesizing a nonlinear spatial filter such that the signal detection may be optimum will be described. In this paper, a generalized linear optimization technique is formulated. The application of this optimization technique toward a simple nonlinear spatial filter is demonstrated, and the extension of this optimization technique for a more complicated nonlinear spatial filter is also given. The signal detection by nonlinear optimum spatial filtering is analyzed. Finally, it is concluded that, instead of restricting the spatial-filter recording to the linear region of the transfer characteristic of the photographic film, an optimum nonlinear spatial filter may be achieved.

In this paper, an algorithm is presented to find a minimal closed partition of the set of internal states of an incompletely specified flow table. The minimal partition is obtained by solving an integer linear program.

The realization of nonoriented communication nets satisfying requirements of two commodities is investigated in this paper. A necessary condition for a requirement matrix to be a terminal capacity matrix of a communication net is found. A method of synthesizing a 2n -terminal net with the use of a special configuration is presented. The results based on graph theory are more convenient than those of linear programming. Whenever a realization is obtained, it is an optimum realization. The procedures which convert a 2n -terminal net into a 2(n+ 1) -terminal net are also discussed.

Many indices of profitability for research and development (R and D) ventures have appeared in the literature. Most of these are calculations of the estimated economic value of a project, if successful. Their greatest utility has been in the development-type project where the probability of success has been relatively large (pr ? 0.25). This paper considers the optimum utilization of a scarce resource, professional man power, among many alternative research projects. Other parameters and restrictions of the model are: the economic value of a successful project, the probability of success, the man-hours required per test or screen per project, the total available man-hours, the cost per man-hour, and the available raw materials (compounds, components, etc.). These factors are used to construct a linear programming model. The solution indicates the optimum allocation of professional man power over the most attractive projects to maximize the return to the corporation. Further aspects of the model are discussed.

This paper describes the development of a criterion for the quantization of line-drawing data. The criterion provides a guide for selecting the quantization fineness required to assure that the significant features of given line-drawing data will be preserved in the quantization process. The criterion is based on viewing a line drawing as an elastic beam under flexure and selecting a quantization grid size that is fine enough to permit the line drawing to be represented by a beam of minimum strain energy. In this model, regions of sharp curvature of the line drawing correspond to regions of high strain-energy density of the elastic beam. The smoothest possible curve that can be reconstructed from a quantized representation is the minimum-energy curve that satisfies the constraints of the quantized data.

This paper presents a generalization of the results of Elias, Feinstein, and Shannon, and Ford and Fulkerson on the maximum rate of information flow through a communciation network. The problem which is considered is the following: suppose a fixed rate of flow of information is being maintained between a pair of stations A and B of a communication network, then 1) what is the maximum rate of flow of information between another pair of stations C and D of the same communication network, and 2) how can one allocate, among the channels, the original load on the communciation network to obtain the maximal flow between stations C and D . It is shown that within certain determinable limits the sum of these two rates of flow remains a constant. A technique for attaining the maximal flow between stations C and D based upon the linear programming is described. A solution of the generalization of this problem to the case of k simultaneous flows is also presented.

This paper proposes a solution to the problem of designing a filter of given structure, incorporating nonideal elements, to meet or exceed given insertion loss specifications subject to element value bounds. This problem is reformulated as a nonlinear programming problem, i.e., minimize an objective function subject to inequality constraints, whose solution yields a filter optimal in a min-max sense. To solve this problem, a recent penalty function approach is used, which converts the constrained problem into a sequence of unconstrained minimizations. These minimizations are carried out using a recent, very efficient, descent technique. The overall method is especially amenable to computer implementation. These techniques have been applied to the computer design of cascade crystal-realizable lattice filters. The results for several designs are presented, and are uniformly good.

One of the most important problems of computeraided network design is the optimization of network characteristics by iterative calculation. In this paper, the problem of realizing a network whose transmission characteristics approximate a given function in Chebyshev sense is treated as a nonlinear programming problem, and a method of solving this problem by successively solving linear programming problems, which are derived by locally linearizing the original nonlinear programming problem, is proposed. An improvement of the method for reducing the computation time is also considered and is proved to be practical and very effective by many design examples.

The investigation presented in this paper describes the problem of determining the proper quantities of fuel to be supplied from several production sources to meet plant requirements in such a manner that the minimum total cost is obtained. The solution is arrived at with cognizance of several parameters which introduce discontinuities in the availability of fuel from the several sources. The investigation also provides a convenient technique for determining an optimum solution by means of a proven mathematical approach to the problem which formerly had been analyzed by an involved cut-and-try procedure that did not provide a dependable optimum solution.

This paper shows that a pursuit-evasion problem can be made amenable to solution with nonlinear programming algorithms by operating the pursuer and evader systems in a "discrete" mode of control and by choosing the cost function judiciously.

The phasing out of products is not an uncommon occurrence in times of rapid technological change. The problem of terminating the production of complex apparatus is compounded when it involves entire families of related products. This paper describes a linear programming procedure that establishes an optimal policy of phase-out so that the final production runs will reduce the terminal inventory consistent with maximum income at an acceptable return on investment.

This paper obtains a new accurate model for sensitivity in power systems and uses it in conjunction with linear programming for the solution of load-shedding problems with a minimum loss of loads. For cases where the error in the sensitivity model increases, other linear programming and quadratic programming models have been developed, assuming currents at load buses as variables and not load powers. A weighted error criterion has been used to take priority schedule into account; it can be either a linear or a quadratic function of the errors, and depending upon the function appropriate programming techniques are to be employed.

This paper gives solutions to the problem of realizing a communication network at minimum cost. The network is composed of a set of nodes connected by a set of branches. Every branch has associated with it a capacity. The required amount of flow between every pair of nodes is specified. The unit costs of the branch capacities are given. The problem is to find the network and the branch capacities such that the total cost is minimum. The set of branch capacities and the set of terminal demands are shown to satisfy a set of linear inequalities. Linear programming is used to obtain the optimal solution. In the case of identical unit costs, several realizations are given which require fewer branches than previously reported.

This paper describes a self-scheduling routine which can be incorporated into the supervisory system of a computer. The problem of scheduling a number of tasks on an overloaded computer can be formulated as a linear programming problem and then solved by means of the transportation method. Priorities for both jobs and customers, as well as a nonlinear loss function for late completion, form the basis of the model.

A tabulation of the 2470 representative threshold functions of seven arguments has been prepared by the author. This paper discusses the methods used in, and the threshold logic implications of, the enumeration. The self-dual classification method of Goto-Takahasi was employed. A lattice was defined on the 8-cube in terms of which all 2-monotonic, canonical, self-dual functions of eight arguments were directly generated. Each such representative function was then treated by a modified form of the Muroga-Toda-Takasu linear programming test-synthesis procedure to obtain minimal 1-realizations. The Chow parameters for each function were calculated, and the final enumeration was ordered lexicographically by these parameters to afford a trivial test-synthesis procedure for n?7. The enumeration demonstrated that minimal 1-realizations are still integral for n?7; it corroborated Cobham's result that complete monotonicity is equivalent to 1-realizability, and established hyper-2-monotonicity as a useful characterization, for n?7. It significantly extended our knowledge of the number of threshold functions and the various symmetry types, the size of weights and threshold required, the number of iterations required by the linear program, and similar statistics.

—A common nonparametric method for designing linear discriminant functions for pattern classification is the iterative, or "adaptive," weight adjustment procedure, which designs the discriminant function to do well on a set of typical patterns. This paper presents a linear programming formulation of discriminant function design which minimizes the same objective function as the "fixed-increment" adaptive method. With this formulation, as with the adaptive methods, weights which tend to minimize the number of classification errors are computed for both separable and nonseparable pattern sets, and not just for separable pattern sets as has been the emphasis in previous linear programming formulations.

Let two sets of patterns be represented by two finite point sets in an n -dimensional Euclidean space E^{n} . If the convex hulls of the two sets do not intersect, the sets can be strictly separated by a plane. Such a plane can be constructed by the Motzkin-Schoenberg error-correction procedure or by linear programming. More often than not, however, the convex hulls of the two point sets do intersect, in which case strict separation by a plane is not possible any more. One may then resort to separation by more than one plane. In this paper, we show how two sets can be strictly separated by one or more planes or surfaces (nonlinear manifolds) via linear programming. A computer program that implements the present method has been written and successfully tested on a number of real problems.

This paper presents an approach to and the results of applying Linear Programming to the forecasting of minimum production costs of electric utility systems. It describes the linear problem format used in the optimization of the start-up and load allocation of generating units. Included are results from investigations of the influence of linear versus nonlinear unit cost/output curves and the number of time segments used to approximate a load duration curve. A comparison is made with production costs obtained from an established program. The results show that production costing can be reduced to a linear problem with little loss of accuracy. The speed, accuracy, and flexibility achieved by using Linear Programming techniques make it a desirable method of production costing for many study purposes.

Although it is possible to optimize selected characteristics of semiconductor devices by controlling the net impurity distribution, present methods used for fabricating planar devices by diffusion techniques invariably produce profiles which are approximately either Gaussian or complementary error functions. The purpose of this paper is to examine the feasibility of obtaining a general impurity profile within intrinsic material using diffusion techniques. It is shown that by treating the problem as an optimum control problem, one can, in principle, obtain a best-fit approximation to a given profile by controlling the gas stream impurity concentration. A first-order model is developed to characterize the surface interactions between the gas ambient and the solid; the boundary value problem for diffusion is then solved. A computational routine using linear programming techniques is developed which, for a given diffusion time, determines the necessary control function producing a best-fit approximation to the desired profile over the spatial range of interest. The optimum control functions governing the diffusion of boron in silicon for three given impurity profiles are synthesized: a constant profile, an exponential profile, and the minimum transit time profile. The computational results clearly establish the feasibility of obtaining an approximation to a given impurity profile.

The development of a nonlinear flowgraph notation for the representation of a large class of nonlinear systems is the central topic of this paper. By the definition of power operator branches, exponential operator branches, switching operator branches, and limiting operator branches, it becomes possible to represent a variety of nonlinear systems. In particular, it becomes possible to represent in a very simple manner a number of different types of hysteretic systems. A study of the rules for manipulation of nonlinear flow-graphs is made, so as to bring out the procedures that might be used in reducing the complexity of such a system as that represented by the flowgraphs. Generalized flowgraph inversion procedures are developed as a consequence of the defined nonlinear branch transmittances. A variety of nonlinear systems are illustrated to indicate the broad applicability of the notation in representing such systems.

This paper presents two methods for increasing the traffic handling capability of a communication network with a minimum cost. Although we concentrate on traffic between one pair of stations (one commodity), the first formulation can be extended to the case of k flows (or k commodities). Both methods lead to a linear programming procedure, because linear cost increase is assumed.