Search

In an earlier paper [20] combinatorial programming procedures were presented for solving a class of integer programming problems in which all elements are zero or one. By representing the problem elements in a binary computer as bits in a word and employing logical "and" and "or" operations in the problem-solving process, a number of problems involving several hundred integer variables were solved in a matter of seconds. In the present paper a number of improvements in these earlier algorithms are presented, including a new search strategy, methods for reducing the original problem, and mechanisms for feasibility filtering in multi-word problems. With these improvements problem-solving efficiency has been increased in many instances by an order of magnitude. In addition, the present paper contains computational experience obtained in solving problems for the k-best solutions. [ABSTRACT FROM AUTHOR]

The optimum coupon schedule for serial bonds issued by municipalities has been solved as a knapsack problem, and is widely implemented in bank and nonbank underwriting firms. A large subset of issues carries the additional requirement that limits the number of distinct coupons which the underwriters may assign to the issue. The paper formulates this problem as a dynamic programming model and discusses the computational aspects relating to this formulation by comparing it with a direct 0/1 integer programming model. Some computational experience is also provided. [ABSTRACT FROM AUTHOR]

The paper presents a new approach to solving a class of combinatorial economic allocation problems. One member of this class is known as the quadratic assignment problem. Besides presenting an algorithm to solve this problem, we will discuss in general terms the techniques for treating combinatorial problems. A novel feature of the paper is the development of the statistical properties of the criterion function. These statistical properties are used in conjunction with a general enumerative procedure to form the main parts of the algorithm. Using the idea of confidence level enumeration, an extension of the algorithm is proposed which should allow for the effective treatment of large scale combinatorial problems. Finally we present some computational results in order to illustrate the effectiveness of the general approach. [ABSTRACT FROM AUTHOR]

This paper proposes a search decision rule (SDR) approach to the aggregate scheduling problem. The approach is tested by converting the objective function of the classic Holt, Modigliani, Muth and Simon paint factory scheduling problem into a 20 dimension response surface which is then explored by the SDR. Conjugate gradient, variable metric and pattern search methods are tested. All three methods demonstrate the ability to consistently descend to the neighborhood of the minimum. The pattern search technique is selected for incorporation into the SDR heuristic because of its excellent performance in terms of reducing the computation time required. Production and work force decisions made up by the SDR are comparable to those made by the linear decision rule and total costs are within 0.1%. By means of the search decision rule approach it should be possible to eliminate the restrictions imposed by linear and quadratic cost models and thereby pursue a more general and realistic approach to the aggregate scheduling problem. [ABSTRACT FROM AUTHOR]

This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric travelling-salesman problem. The procedure is based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems. The procedure produces optimum solutions for all problems tested, 'classical' problems appearing in the literature, as well as randomly generated test problems, up to 110 cities. Run times grow approximately as n² in absolute terms, a typical 100-city problem requires less than 25 seconds for one case (GE63S), end about three minutes to obtain the optimum with above 95 per cent confidence. [ABSTRACT FROM AUTHOR]

This paper discusses the problem of assigning locations to indivisible facilities and its relation to the quadratic assignment problem. It also develops two suboptimal algorithms, one dealing with the general quadratic assignment problem and the other with an interesting special case. Qualitative and quantitative comparisons with existing suboptimal algorithms are presented. [ABSTRACT FROM AUTHOR]

In certain problem areas it is not possible to establish one objective function. There may be several, sometimes conflicting, goals. This paper presents a method of reconciling such conflicting goals by establishing a global objective function. A combinatorial example is given and solved by "modified" dynamic programming. [ABSTRACT FROM AUTHOR]

This paper presents a formulation of the quadratic assignment problem, of which the Koopmans-Beckmann formulation is a special case. Various applications for the formulation are discussed. The equivalence of the problem to a linear assignment problem with certain additional constraints is demonstrated. A method for calculating a lower bound on the cost function is presented, and this forms the basis for an algorithm to determine optimal solutions. Further generalizations to cubic, quartic, N-adic problems are considered. [ABSTRACT FROM AUTHOR]

Problem-solving procedures based on the methods of combinatorial programming are presented for solving a class of integer programming problems in which all elements are zero or one. All of the procedures seek first a feasible solution and then successively better and better feasible solutions until ultimately one is discovered which is shown to be optimal. By representing the problem elements in a binary computer as bits in a word and employing logical "and" and "or" operations in the problemsolving process, a number of problems involving several hundred integer variables have been solved in a matter of seconds. [ABSTRACT FROM AUTHOR]

A point target is threatened with attack by a raid of enemy aircraft. The enemy has a spectrum of attack tactics at his disposal, each tactic being defined m terms of speed, altitude, bomber cross-section, and raid size. The defense consists of a deployment of missile batteries surrounding the target. There are several types of missile batteries, each having a characteristic cost and a characteristic capability against a given attack tactic. The problem is to determine the optimal mix of missile batteries, and the deployment of that mix, so as to obtain the best defense against the entire spectrum of attack tactics. Although a general approach is outlined, the model is developed and the solution obtained for the special case m which the measure of effectiveness is linear with respect to both raid size and the number of defense units [ABSTRACT FROM AUTHOR]

Since engineering designs generally involve a number of elements about which only partial information is available, design optimization should be conducted under conditions of risk. Utility is nonlinear with cost or revenue; consequently, the enterprise's view of risk is considered through utilities assigned to costs or revenues which deviate from the mean. This is termed "risk programming" to distinguish it from previous contributions in this area. General forms of the objective function, yielding expected utility, are derived for utility functions of two types. When the total cost distribution is normal, an exact solution requiring only a knowledge of expected total cost and the cost variance is obtained. For nonnormal cost distributions, an upper bound of the objective function, requiring knowledge only of the same two quantities, is obtained. A model for engineering design, which provides both the expected total cost and cost variance, is developed based upon division of the elements of variability into several categories. With this division, a reasonable computational procedure is possible. The procedure has been incorporated into a modified direct search optimization program capable of solving large-size design problems. [ABSTRACT FROM AUTHOR]

Ronald Howard's editorial comments in the June, 1967 volume of this journal stressed the power of the pricing mechanism in the control and optimization of social systems. This article illustrates how such a concept can be applied via a decomposition algorithm for quadratic programming. A set of artificial markets for scarce resources and transfer goods is introduced into a model of a divisionalized firm and a quadratic decomposition algorithm is used to find the optimal (profit maximizing) set of prices for these goods. The algorithm requires a minimal amount of information transmission from the divisions to corporate headquarters and can be applied to divisionalized firms operating in imperfect markets. It also has significant behavioral implications not found in other decomposition algorithms for the firm which employs a profit-center method of control. The value of the algorithm is evident in those situations where decentralization is either desirable or a necessity and where interdependencies exist. [ABSTRACT FROM AUTHOR]

The article discusses the "transportation problem," which is a class of linear programming problems involving the selection of the most economical shipping routes for a commodity from given sources to given destinations. The transportation problem has been typically approached either as a specialized type of linear programming problem or as a method of representation of some combinatorial problems. The author asserts that a third method is possible, which is applicable for the determination of optimum linked paths over a series of points, or "transhipment." The transhipment problem is more complex than shipping an item from one point to another, because points can now be both origins and destinations. The question resembles a combinatorial problem but may be solved by linear programming.

This article focuses on a mathematical decision model to solve decision problems arising from governmental actions aimed at economic growth and stabilization. A particular decision analysis based on linear dynamic relations and a quadratic criterion function is presented and is shown to incorporate both feedback and feed forward. It is applied to a simple economic example and simulation tests are used to make comparisons with a policy of inaction, and to study the effects of economic growth, forecast errors, errors in the welfare function, and errors in estimating the economic relationships. Probably the most important application of this decision analysis is to cases of multiple interacting control instruments where the decision problem is so complex that simpler analyses fail to produce the desired results. In such cases a linear decision rule is obtained for each instrument variable, and these rules are used in concert. For complex decision problems, the decision rules also become complex. Indeed, an optimal decision on a single instrument variable will literally depend upon all the initial conditions of the system and all of the forecasts.