Search

Strong theorems concerning globally unique solutions to nonlinear inequalities have been obtained by Gale and Nikaido via P-matrix characterizations of the Jacobians of the mappings involved. The authors introduce two new concepts here: 'v-positivity' and the 'poverse.' These permit the authors to state and prove significant generalizations of the theorems just mentioned and, equally important, provide access to preliminary results concerning linear inequalities by the powerful direct techniques of linear programming theory., Prepared in cooperation with Naval Postgraduate School, Monterey, Calif.

Easily manipulated list structures for recording the basis tree for adjacent extreme point (simplex type) network algorithms are paramount to the development of computationally efficient network algorithms. The paper presents a new list structure which is shown to be computationally more efficient and to require one-third less computer memory to implement than all alternate list structures. (Author)

The augmented predecessor indexing method is a procedure for efficiently updating the basis representation, flows and node potentials in an adjacent extreme point (or 'simplex' type) method for network problems, using ideas due to Ellis Johnson in his proposed application of a triple-label representation to networks. The procedure is extended here to accommodate the more complex basis structures and updating processes of the generalized network problem, specifying rules for expediting the calculations., Prepared in cooperation with Colorado Univ., Boulder.

One purpose of the paper is to describe the development, implementation, and availability of a computer program for generating a variety of feasible network problems. In particular the code can generate capacitated and uncapacitated transportation and minimum cost flow network problems, and assignment problems. In particular the code can generate capacitated and uncapacitated transportation and minimum cost flow network problems, and assignment problems. In addition to generating structurally different classes of network problems the code permits the user to vary structural characteristics within a class. Since researchers can generate identical networks using this code, another pupose of the paper is to provide problems benchmarked on several codes currently available. In particular, the later part of the paper contains the solution time and objective function value on 40 assignment, transportation and network problems varying in size from 200 nodes to 8,000 nodes and from 1,300 arcs to 35,000 Arcs. (Author)

Many practical operations research problems have the form in which the objective is to select an optimal production schedule, rental policy, distribution pattern, etc., from among a variety of alternatives each of which has an associated set of constraints that must all be satisfied if that particular alternative is chosen. The disjunctive facet problem provides a 'direct' formulation for such problems, circumventing the need to resort to artifices involving the creation of discrete variables and supporting constrains to model these problems as mixed integer programs. The authors provide special cutting plances that are designed to take particular advantage of the disjunctive facet problem structure. Thus their results not only give a more compact representation of certain classes of discrete optimization problems, but provide more powerful methods for solving these problems as well. (Author)