Search

The problem of determining continuous flows of minimum cost in a network with convex cost functions is considered. The approach used is that of finding, for any given feasible flow, circuit flows of negative incremental costs. In the main theoretical result of this paper, it is proved that if at each stage, given a feasible nonoptimal flow X, the circuit flow with most negative incremental cost is added to X, linear convergence to the optimal solution will be obtained. In addition, this most negative incremental cost determines an upper bound on the difference in cost between the given feasible solution and the optimal. Based on these concepts, an algorithm, which preserves linear convergence, is presented to determine minimum cost flows in networks with convex costs in the arcs. Results of computer runs made for this algorithm are given. The special case of networks with linear costs is also considered. [ABSTRACT FROM AUTHOR]

Commentary is presented for an article published in the July 1960 issue of "Management Science," written by L. V. Kantorovich with an introductory note by T. C. Koopmans. According to the author, in his introduction Koopmans addresses in particular a linear programming problem and a matrix game presented by Kantorovich. Also presented is an interpretation of the article's treatment of decision variables and mathematical optimization. The author notes that the article presents algorithms that have been improved from their contemporary presentations.

This paper considers "critical path" networks which are used for the planning and scheduling of projects that consist of well defined sequences of individual activities. When the number of activities is large, it becomes difficult to prepare a network for the project as one unit, and it may also be difficult to store the network in the high speed memory of a digital computer. Also, in the cases where there are two or more independent projects, which are weakly inter-related by common activities, the problem of efficient scheduling of all the projects becomes quite difficult. This paper presents a method to "tear" or "decompose" a project network into several subnetworks, schedule the subnetworks and then to put the subnetworks back together. A computational algorithm is first given for time-only networks; then two computational formulations are given for cost-time network of project subnetworks. The latter essentially generalize the algorithm due to Fulkerson, in order to handle piecewise linear, convex, cost-time curves for some or all of the activities. [ABSTRACT FROM AUTHOR]

This paper gives a detailed description of an algorithm for the solution of a specialized Linear Programming model, to be called the Machine Loading model. It is a generalization of the Transportation Problem, in that weighting factors are applied to the individual elements which form the row and column sums. For the Machine Loading model, the simplex method reduces to a specialized algorithm which generalizes the stepping stone method of the Transportation Problem [2], [3]. With the resulting generalized stepping stone method, it becomes practicable to solve many large-scale problems for which the direct application of the simplex method would be impracticable. The present paper is restricted to a discussion of the following topics: (I) the general characteristics of the model and its topological features; (ii) a detailed solution algorithm, including a consideration of degenerate cases and the use of a computer; (iii) a more restrictive capacitated model and the corresponding modifications to the solution algorithm; and (iv) the complete illustrative solution of a numerical example. The purpose is to aid interested readers in gaining familiarity with the algorithm and facility in the solution of numerical problems. No derivations or proofs will be included. [ABSTRACT FROM AUTHOR]

The purpose of the present paper is to extend the loop-technique of the stepping-stone algorithm to the generalized transportation problem. The main result (Theorem and Corollary of §6) is, that passing from a basic feasible solution to another one may always be carried out by constructing a simple symmetrical or a double loop (as defined in §2) and computing new values for the variables only along this path. The amount of computations needed for this turns out to be substantially reduced as compared to the usual way of solving the system of equations relating the new basis to the old one. [ABSTRACT FROM AUTHOR]

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]

In order to discuss scheduling algorithms for time-sharing computer systems, this paper analyzes the M/G/1 queue under the well known round-robin (RR) discipline. Three models are considered: the constant-quantum RR model, the processor-shared (or zero-quantum RR) model, and the variable-quantum RR model. The paper proposes an effective calculating method for obtaining the expected response time under an arbitrary processing-time distribution with overhead. By the theoretical analysis, one can show how the response time is affected by the scheduling and processing-time distributions, as is demonstrated by some typical examples. [ABSTRACT FROM AUTHOR]

This paper considers fluid analogues for the standard linear programming problem and for a separable nonlinear programming problem. In the former case the usual duality results are demonstrated using the principle of minimum potential energy. In addition by examining the dynamics of the system a new method, referred to as the R-method, is derived for solving linear programmes, although it is not demonstrated that this has any computational advantages over the standard simplex method, except that degeneracy causes no problems. In the nonlinear case the weak Lagrangian principle is derived. The purpose of the paper is to demonstrate that analogue methods, while being impracticable as a physical method of solving optimisation problems, may give some insight into computational algorithms via dual energy concepts and/or dynamic behaviour. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to furnish a computational scheme for a class of programming problems with nonlinear constraints. The algorithm is sequential in nature, producing a sequence of feasible solutions whose limit points are optimal solutions of the original problem. Further, with a view to accelerating convergence we suggest two variants of the solution procedure. [ABSTRACT FROM AUTHOR]

A mean-variance portfolio selection model suitable for the small investor is formulated as a sequence of quadratic integer programming problems. The special structure of these quadratic problems is exploited in a partial enumeration algorithm which uses cutting planes to accelerate convergence. Computational experience is reported on problems ranging in size from fifteen to fifty variables. [ABSTRACT FROM AUTHOR]

This part of the paper introduces some possible implementations of Self-Scaling Variable Metric algorithms based on the theory presented in Part I. These implementations are analyzed theoretically and discussed qualitatively. A special class of SSVM algorithms is introduced, which has the additional property of being invariant under scaling of the objective function or of the variables. Experimental results are provided for a particular case of this class. This case has been tested in comparison to the DFP algorithm on a variety of functions with up to 50 variables. The results indicate that the new method has substantial advantage for functions with a large number of variables. [ABSTRACT FROM AUTHOR]

A framework of concepts is developed which helps to unify a substantial portion of the literature on large-scale mathematical programming. These concepts fall into two categories. The first category consists of problem manipulations that can be used to derive what are often referred to as "master" problems; the principal manipulations discussed are Projection, Inner Linearization, and Outer Linearization. The second category consists of solution strategies that can be used to solve the master problems, often with the result that "subproblems" arise which can then be solved by specialized algorithms. The Piecewise, Restriction, and Relaxation strategies are the principal ones discussed. Numerous algorithms found in the literature are classified according to the manipulation/strategy pattern they can be viewed as using, and the usefulness of the framework is demonstrated by using it (see Part II of this paper) to rederive a representative selection of algorithms. The material presented is listed in the following order: The first section is introductory in nature, and discusses types of large-scale problems, the scope of discussion and the literature, and the notation used. The second section, entitled "Problem Manipulation: Source of 'Master' Problems" covers the subjects of projection, inner linearization and outer linearization. The third section, "Solution Strategies: Source of 'Subproblems'," discusses piecewise strategy, restriction and relaxation. The fourth section is entitled "Synthesizing Known Algorithms from Manipulations and Strategies," and is followed by a concluding section and an extensive bibliography. [ABSTRACT FROM AUTHOR]

In this paper the Fiacco-McCormick SUMT technique is embedded in a class of inside-out algorithms. Convergence is demonstrated for the nonlinear programming problem under fairly general conditions and the algorithms are interpreted in a geometric structure. [ABSTRACT FROM AUTHOR]

The article presents an algorithm for solving a linear integer programming problem and describes the theoretical foundations for a new approach to integer programming. According to the authors, the approach may be described as an extension of the methods using enumeration, but by using a new, more powerful approach based on population statistics. The optimal solution to the integer programming problem in this paper is viewed as one of selecting the optimal function among a certain class of functions which map elements of one set into another. With this method in mind, the authors intend to view the different problems by characterizing the statistical structure of the associated finite class of maps.

The usefulness of integer programming as a tool of capital budgeting hinges on the development of an efficient solution technique. An algorithm based on partial enumeration has been developed by E. L. Lawler and M. D. Bell for solving integer linear programs with 0-1 decision variables; however their algorithm is not general enough to deal with all problems in which the objective function is quadratic. This paper extends Lawler and Bell's method so that it can be generally applied to integer quadratic programs. The new algorithm is illustrated by examples from capital budgeting. [ABSTRACT FROM AUTHOR]

This paper presents results which apply to convex programming problem in parametric form. The results secured are also related to the problem of fractional programming in a way which indicates computational possibilities for the latter class of problems. The results are extended to general non-linear programming problems with special reference to continuous criterion functions. As a particular case, the linear fractional programming problem is considered and, in conclusion, the results secured here are pointed up by reference to existing algorithms for the latter class of problems. [ABSTRACT FROM AUTHOR]

The topology of the Generalized Transportation Problem, at the end of each iteration of the stepping-stone method, is characterized by a variable number of loops to which are attached multiple branched side chains or trees. An efficient computer representation of this structure and methods for updating it are described in this paper. [ABSTRACT FROM AUTHOR]

The well known chemical equilibrium problem is expressed in the form of minimizing the free energy of a mixture in order to compute the chemical composition at equilibrium. By piece-wise linear approximations to the free energy function, the problem becomes a linear program which can be solved by a standard code on a computing machine. Successive approximations give any degree of accuracy. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to illustrate some applications of the functional equation technique of the theory of dynamic programming to a general class of problems arising in the study of networks, particularly those arising in transportation theory. [ABSTRACT FROM AUTHOR]

A mathematical programming problem P: minimize z=d[supT]x+e[supT]u+f[supT]v subject to Ax+Bu+Cv≥g, x, u, v≥0, u[supT]v=0, is called a complementary programming (CP) problem. The condition u[supT]v=0 distinguishes CP problems from ordinary LP problems. A variety of nonlinear programming problems can be formulated in this form, including absolute-value programming problems, 0-1 mixed-integer-programming problems, quadratic-programming problems, and so forth. This paper proposes a branch-and-bound algorithm for CP problems and reports some computational results. [ABSTRACT FROM AUTHOR]

This paper studies the optimal operation of an M/G/1 queuing system with removable server and the following cost structure: a holding cost per customer in the system per unit time, a cost per unit time of keeping the server running, and fixed charges for turning the server on or off. The server can be turned on at arrival epochs or off at service-completion epochs. The paper characterizes an optimal policy for the infinite-horizon discounted problem, offers an optimality proof, and presents a computational algorithm. [ABSTRACT FROM AUTHOR]

The algorithms of this paper belong to the direct-search or implicit-enumeration type. They compare to the recently proposed algorithm of EFROYM- SON AND RAY, as does the mixed integer algorithm proposed by C. E. LEMKE and the author to that of LAND AND DOIG The general plan of procedure is expected to be equally valid for the capacitated plant-location problem and for transshipment problems with fixed charges; with some of the proposed devices more important for these difficult problems than for the simple plant location problem. Considerable computational experience has been accumulated and is discussed at some length. It suggests that additional work on the construction of adaptive' programs, matching algorithm to data structure, is desirable. [ABSTRACT FROM AUTHOR]

This paper presents a dynamic programming algorithm for determining optimal production in a series type multi-echelon inventory system with stochastic final product demand. Setup costs at individual facilities are permitted. For the case where it is physically possible (but not required) for a product unit to pass through all the facilities within a single time period, a second dynamic programming algorithm is presented which can be used in conjunction with the first to substantially decrease computation time. The model can also be readily specialized to the case of deterministic demand and permits a larger class of cost functions than existing deterministic multi-echelon models. [ABSTRACT FROM AUTHOR]

In Part I of this paper, we developed an algorithm for finding planning horizons for the deterministic production smoothing problem when all demand was required to be met from regular production, under rather general assumptions for the production smoothing, and holding cost functions. Here, in Part II, we develop analogous planning horizons when the model is extended to include such factors as overtime, lost sales, simple subcontracting, undertime, and backlogging. Part II depends heavily on Part I. To avoid unnecessary tedium, all cost functions will be assumed to be stationary in Part II. Overtime, undertime, holding, and backlogging will be assumed to be convex increasing, all other costs linear and proportional. However, it is not difficult to see that the techniques of Part I can be utilized directly to cover more general cost functions. Part II concludes with a discussion of the application of our general approach to actual data. [ABSTRACT FROM AUTHOR]

This paper presents an in-depth computational comparison of the basic solution algorithms for solving transportation problems. The comparison is performed using "state of the art" computer codes for the dual simplex transportation method, the out-of-kilter method, and the primal simplex transportation method (often referred to as the Row-Column Sum Method or M O D I method). In addition, these codes are compared against a state of the art large scale LP code, O P H E L I E/LP. The study discloses that the most efficient solution procedure arises by coupling a primal transportation algorithm (embodying recently developed methods for accelerating the determination of basis trees and dual evaluators) with a version of the Row Minimum start rule and a "modified row first negative evaluator" rule. The resulting method has been found to be at least 100 times faster than OPHELIE, and 9 times faster than a streamlined version of the SHARE out-of-kilter code. The method's median solution time for solving 1000 X 1000 transportation problems on a CDC 6600 computer is 17 seconds with a range of 14 to 22 seconds. Some of the unique characteristics of this study are (1) all of the fundamental solution techniques are tested on the same machine and the same problems, (2) a broad spectrum of problem sizes are examined, varying from 10 X 10 to 1000 X 1000; (3) a broad profile of nondense problems are examined ranging from 100 percent to 1 percent dense; and (4) additional tests using the best of the codes have been made on three other machines (IBM 360/65, UNIVAC 1108, and CDC 6400), providing surprising insights into conclusions based on comparing times on different machines and compilers. [ABSTRACT FROM AUTHOR]

A multi-stage linear program is defined with linking variables that connect consecutive stages. Optimality conditions for the composite problem are partitioned into local and linking conditions. When the Dantzig-Wolfe decomposition scheme is applied with the first stage as the master, the subproblem is also a MLP with one less stage. The same decomposition is then applied to the subproblem, giving rise to a nested decomposition scheme, in which each stage acts as a master for the following stage and a subproblem for the preceding. Optimizing a single stage problem results in satisfying the "local" optimality conditions. A very general rule is given for selecting the next subproblem to optimize, and finite convergence to a solution satisfying all linking conditions is demonstrated. Procedures for extracting the optimal primal solution at the end of the main algorithm and for initialization are given. Particular rules for selecting the next subproblem and for generating additional proposal vectors are discussed. Finally, it is shown how a variety of problems may be restructured as multi-stage linear programs to which this algorithm may be applied, and some computational experience is reported. [ABSTRACT FROM AUTHOR]

This paper presents an implicit enumeration algorithm for redrawing school attendance boundaries in order to meet integration requirements. The basis of the approach is the division of the city into smaller areas or zones corresponding to neighborhoods. These zones are assigned to schools with the objective of minimizing the required bussing while meeting the school capacity and racial mix constraints. An entire zone is assigned to one school, thus preserving the neighborhood school concept. Viewing the possible zone-school assignments as a combinatorial problem, a general enumerative procedure is combined with probability theory to form the implicit enumeration algorithm. An explanation of the algorithm along with computational results of an application of the method to an existing school system is presented. [ABSTRACT FROM AUTHOR]

This paper reports on an application of computer technology to a significant and costly school administration problem: the transportation of students between home and school. The problem, as it is generally thought of, has been complicated by the consideration of attempting racial balance via busing. We present an algorithm to find a feasible solution which tends to minimize the number of required routes and mileage. After setting down the basic approach used and the results of an application, we will present possible extensions of the approach to school location planning, bus fleets composition and timing conditions on particular bus stops. [ABSTRACT FROM AUTHOR]

The objective of this paper is the construction of a branch-and-bound algorithm for computing minimum cost flows in capacitated networks when the cost of passing a flow over an arc is concave. The method is based on the equivalence of the general network flow problem to a network flow problem in a bipartite network of a special form. An optimal flow is found by implicit enumeration of the set of extremal flows in that network. [ABSTRACT FROM AUTHOR]

This paper considers an n-server queueing system with m customer classes distinguished by the reward associated with serving customers of that class. Our objective is to accept or reject customers so as to maximize the expected value of the rewards received over an infinite planning horizon. By making the assumptions of Poisson arrivals and a common exponential service time this problem can be formulated as an infinite horizon continuous time Markov decision problem. In §3 we customize the general algorithm for solving continuous time Markov decision problems to our queueing model. In §4 we obtain qualitative results about the form of the optimal policy. §6 reports the results of simulation tests which compare heuristic policies for our model when the service times associated with each customer class have arbitrary distributions. The ‘winning’ policy is based on a rather intricate theorem whose proof comprises §6. [ABSTRACT FROM AUTHOR]

In this paper we present an algorithm for solving mathematical programming problems of the form: Find x = (x[sub 1], ..., x[sub n]) to minimize Σφ[sub i] (x[sub i]) subject to x ε G and I ≤ x ≤ L. Each φ[sub i] is assumed to be lower semicontinuous, possibly nonconvex, and G is assumed to be closed. The algorithm is of the branch and bound type and solves a sequence of problems in each of which the objective function is convex. These problems correspond to successive partitions of the feasible set. Two different rules for refining the partitions are considered; these load to convergence of the algorithm under different requirements on the problem functions. Examples are given, and computational considerations are discussed. [ABSTRACT FROM AUTHOR]

The general linear programming problem is considered in which the coefficients of the objective function to be maximized are assumed to be random variables with a known multinormal distribution. Three deterministic reformulations involve, respectively, maximizing the expected value, the α,-fractile (α fixed, 0 < α < ½), and the probability of exceeding a predetermined level κ of payoff. In this paper the author's previous work on "hi-criterion programs" is specialized to give an algorithm for routinely and efficiently solving the second and third reformulations. A by-product of the calculations in each ease is the tradeoff-curve between the criterion being maximized and expected value. The intimate relationships between all three reformulations are illuminated, with the cumulative effect of considerably lessening the burden on the decision-maker to preselect with finality a particular value of α or κ. [ABSTRACT FROM AUTHOR]

The technique described in this paper was devised for sequencing jobs on individual machines having characteristics of: (1) high job changeover costs; (2) small backlogs (10-20 jobs); (3) occasional "rush" orders. The algorithm starts with four-job sequences and from these constructs five-job sequences; from the five-job sequences, six-job sequences are constructed, and so on. At each stage, a large fraction of sequences are eliminated from further consideration. This elimination process makes the computation feasible because the number of all possible sequences becomes unmanageably large, even for small problems. The technique always provides a minimum cost sequence. It also permits determination of optimum sequences of backlog sub-sets; thus, rush orders can be accommodated and anticipated changes in the job backlog can be recognized. [ABSTRACT FROM AUTHOR]

In formulating linear programming problems, analysts tend to include constraints that are not binding at the optimal solution for fear of excluding necessary constraints. The inclusion of such constraints does not alter the optimum solutions, but may require many additional iterations to be taken, as well as increase the computational difficulties encountered. Most of the methods proposed to date for identification of redundant and non-binding constraints are not warranted in practice because of the excessive computations required to implement them. These methods are reviewed in the present paper, and some of them are extended. A number of additional methods are also considered. Two of these new methods are not only practical, but have proven to be powerful in solving a number of problems. These methods may be incorporated in a variant of the simplex method. After each simplex iteration is made, constraints and variables are tested and, when identified as non-binding, are eliminated. The procedure is continued, with the problem size dwindling as the algorithm progresses, until the optimum is reached. Then the values of the eliminated variables are computed by substitution into the eliminated constraints. Early evidence shows that a size reduction for small problems (having 25-30 constraints) of 50 percent is not unusual. It is hoped that the results on larger problems will be even more significant.(n4) [ABSTRACT FROM AUTHOR]

This paper describes a variant of the Simplex algorithm, applicable to matrices containing blocks of elements along and just below the diagonal. It uses the emptiness of the other blocks to save space and computation. [ABSTRACT FROM AUTHOR]

In a previous article [7] the authors gave the theoretical validation of the sequential unconstrained minimization technique for solving the convex programming problem. The technique is based on an idea proposed by C. W. Carroll [2], [3]. The method has been implemented via an algorithm based on a second-order gradient technique that has proved extremely efficient on a considerable number of test problems of varying complexity. This paper explores the computational aspects of the method. Included are discussions of parameter selection, convergence criteria, and methods of minimizing an unconstrained function. It is shown that the problem variables, on the trajectory of minima of the sequence of unconstrained functions, can be developed as functions of a single parameter. This provides the theoretical basis for an extrapolation technique that significantly accelerates convergence in actual computations. The detailed computer solution of a small example is given to illustrate the typical convergence characteristics of the method. The speed and accuracy of the computational procedure are believed to be competitive with other known techniques for solving the convex programming problem. [ABSTRACT FROM AUTHOR]

The problem considered in this paper is that of allocating a budget of resources among the links of a network for the purpose of increasing its flow capacity relative to given sources and sinks. On the assumption that the cost of increasing each link capacity is linear, a labeling algorithm is described that permits rapid calculation of optimal allocations for all budgets. [ABSTRACT FROM AUTHOR]

In deriving the well known cuts for cutting-plane methods in 0, 1 integer programming, the integer points outside the 0, 1 space can limit the parallel movement of the hyperplane of the cut toward the solution set. Furthermore it is unnecessarily restrictive to limit the movement of this hyperplane to parallel translations. This paper removes these two limitations in order to derive stronger cuts and reduce the total number of cuts required. Thus, it describes a method based on a special case of the knapsack function that replaces each cut or original constraint by a new inequality whose hyperplane passes through as many integer points in 0, 1 space as possible. [ABSTRACT FROM AUTHOR]

The main result of this paper is a group theoretic algorithm (GTIP2) for the integer programming problem. This algorithm is an extension of an algorithm from an earlier paper (part I). The algorithm in part I solves a group optimization problem derived from a given integer programming problem. The optimal solution to the group problem thereby obtained is an optimal solution to the integer programming problem if it is feasible. Unfortunately, an optimal solution to the group problem may yield an infeasible integer solution. The algorithm GTIP2 of this paper is an extension of the method of part I when it fails. In particular, GTIP2 employs a search procedure to find an optimal solution to the integer programming problem. The extent of the search is bounded by procedures derived from a variety of relevant group problems that are solved by the algorithm of part I. There is a discussion of the class of problems for which GTIP2 is primarily intended and the relation of GTIP2 to other algorithms is indicated. A numerical example and some partial computational results are included. [ABSTRACT FROM AUTHOR]

We consider a fractional flow model of a graded manpower system and develop algorithms for calculating optimal control policies in four situations: (I) finite time horizons with no constraints on staff distributions, (ii) finite time horizon with constraints on final staff distribution, (iii) infinite horizon with constraints on staff distribution and (iv) problems with a nonstationary transient stage and an infinite stationary stage. In each case results developed in solving the simpler problems are useful in analyzing more complicated situations. In addition to providing computational procedures we apply the algorithms to a three rank model and discuss the possible uses and limitations of our procedure. [ABSTRACT FROM AUTHOR]

GOMORY has transformed the integer programming problem into a related group optimization problem which can be more easily solved. An optimal solution to the group problem is optimal for the integer programming problem from which it is derived if the solution is feasible. An algorithm (IP Algorithm I) for solving the group optimization problem is developed, and sufficient conditions on its use are given. The usefulness of IP Algorithm I is extended by amending it to find alternative optima. In a subsequent paper, this algorithm is extended to an algorithm that can solve any integer programming problem. [ABSTRACT FROM AUTHOR]

The paper presents a response to a comment on the article "Economically Optimum Design of CUSUM charts." The author feels that they are making two specific points; they question his use of the word "optimum" and attempt to point out that other search methods may be more appropriate in certain situations. He feels that while they are correct that some search methods work better in certain circumstances, he thinks his use of the word "optimum" is correct and explained thoroughly. Optimum, in this case, refers to the values of the parameter that yield the minimum cost, which he believes he explains in the abstract.

A simple algorithm is developed for the problem of assigning days off to full-time staff given a cyclic seven-day demand pattern. The formulation assumes that employees are entitled to two consecutive days off each week and that the objective is to find a minimum staff size capable of meeting the requirements. The algorithm involves only hand calculations, and its computing effort is predictable. [ABSTRACT FROM AUTHOR]

The theory of equivalent integer programs is generalized so that a set of minimal canonical problems always exists within each equivalence class. An example is used to demonstrate how highly computation time depends on the particular canonical problem chosen to be solved by implicit enumeration algorithms. [ABSTRACT FROM AUTHOR]

The closed convex polyhedron consisting of all 0-1 normal n-person games with nonempty core is characterized by naming its extreme points. This characterization establishes a geometric setting, in the game space itself, for such solution concepts as the core and the nucleolus. This geometric setting also suggests new solution concepts. A similar geometric setting is also established for the Shapley value, and core and nucleolus solution concepts can be defined in this geometric setting. [ABSTRACT FROM AUTHOR]

A solution method is given for a class of practical optimization problems requiring the determination of a consistent partial ordering for sets of objects, events, preferences, and the like. These problems are characterized by the existence of "noisy" (or contradictory) links of varying strengths. The origin of this class of problems is an anthropological study in which it is desired to specify a global chronological ordering of ancient cemetery data. A mathematical formulation is given which results in a minimum weight feedback model. A heuristic is developed similar to the Greedy algorithm for minimum weight spanning trees which requires only one pass through the network. [ABSTRACT FROM AUTHOR]

A new criterion is introduced for comparing the convergence properties of variable metric algorithms, focusing on stepwise descent properties. This criterion is a bound on the rate of decrease in the function value at each iterative step (single-step convergence rate). Using this criterion as a basis for algorithm development leads to the introduction of variable coefficients to rescale the objective function at each iteration, and, correspondingly, to a new class of variable metric algorithms. Effective sealing can be implemented by restricting the parameters in a two-parameter family of variable metric algorithms. Conditions are derived for these parameters that guarantee monotonic improvement in the single-step convergence rare. These conditions are obtained by analyzing the eigenvalue structure of the associated inverse Hessian approximations. [ABSTRACT FROM AUTHOR]

When developing offshore oil fields most wells are dual completions; i.e., two oil traps (targets) are produced together through a single hole. This problem is discussed and a model is developed for finding the pairing of targets in order to minimize the total drilling cost. The mathematical formulation of this problem turns out to be the well known "symmetric assignment problem" (or "matching problem"). Algorithms for the solution of these problems are discussed and computational results are presented. [ABSTRACT FROM AUTHOR]