MAJOR－EFFICIENT SOLUTIONS AND WEAKLY MAJOR－EFFICIENT SOLUTIONS OF MULTIOBJECTIVE PROGRAMMING

ＭＡＪＯＲ－ＥＦＦＩＣＩＥＮＴＳＯＬＵＴＩＯＮＳＡＮＤＷＥＡＫＬＹＭＡＪＯＲ－ＥＦＦＩＣＩＥＮＴＳＯＬＵＴＩＯＮＳＯＦＭＵＬＴＩＯＢＪＥＣＴＩＶＥＰＲＯＧＲＡＭＭＩＮＧ￥ＨＵＹＵＤＡ（Ｄｅｐｔ．ｏｆＡｐｐｌ．Ｍａｔｈ．，ＳｈａｎｇｈａｉＪｉａｏＴｏｎ...     

An MPEC approach to second-best toll pricing

This paper addresses two second-best toll pricing problems, one with fixed and the other with elastic travel demands, as mathematical programs with equilibrium constraints. Several equivalent nonlinear programming formulations for the two problems are discussed. One formulation leads to properties that are of interest to transportation economists. Another produces an algorithm that is capable of solving large problems and easy to implement with existing software for linear and nonlinear programming problems. Numerical results using transportation networks from the literature are also presented.This research was partially supported by NSF grants DMI-9978642 and DMI-0300316.     

A simplicial decomposition algorithm for solving the variational inequality formulation of the general traffic assignment problem for large scale networks

Summary The class of simplicial decomposition methods has been shown to constitute efficient tools for the solution of the variational inequality formulation of the general traffic assignment problem. This paper presents a particular implementation of such an algorithm, with emphasis on its ability to solve large scale problems efficiently. The convergence of the algorithm is monitored by the primal gap function, which arises naturally in simplicial decomposition schemes. The gap function also serves as an instrument for maintaining a reasonable subproblem size, through its use in column dropping criteria. The small dimension and special structure of the subproblems also allows for the use of very efficient algorithms; several algorithms in the class of linearization methods are presented. When restricting the number of retained extremal flows in a simplicial decomposition scheme, the number of major iterations tends to increase. For large networks the shortest path calculations, leading to new extremal flow generation, require a large amount of the total computation time. A special study is therefore made in order to choose the most efficient extremal flow generation technique. Computational results on symmetric problems are presented for networks of some large cities, and on asymmetric problems for some of the networks used in the literature. Computational results for bimodal models of some large cities leading to asymmetric problems are also discussed.     

Iterative Characterizations of Computable Unary Functions: A General Method

Iterative characterizations of computable unary functions are useful patterns for the definition of programming languages based on iterative constructs. The features of such a characterization depend on the pairing producing it: this paper offers an infinite class of pairings involving very nice features.     

Bounding a class of nonconvex linearly-constrained resource allocation problems via the surrogate dual

We consider a class of problems of resource allocation under economies of scale, namely that of minimizing a lower semicontinuous, isotone, and explicitly quasiconcave cost function subject to linear constraints. An important class of algorithms for the linearly constrained minimization of nonconvex cost functions utilize the branch and bound approach, using convex underestimating cost functions to compute the lower bounds.We suggest instead the use of the surrogate dual problem to bound subproblems. We show that the success of the surrogate dual in fathoming subproblems in a branch and bound algorithm may be determined without directly solving the surrogate dual itself, but that a simple test of the feasibility of a certain linear system of inequalities will suffice. This test is interpreted geometrically and used to characterize the extreme points and extreme rays of the optimal value function's level sets.Research partially supported by NSF under grant # ENG77-06555.     

Optimality in transient markov chains and linear programming

It is shown how a discrete Markov programming problem can be transformed, using a linear program, into an equivalent problem from which the optimal decision rule can be trivially deduced. This transformation is applied to problems which have either transient probabilities or discounted costs.This research was supported by the National Research Council of Canada, Grant A7751.     

On degeneracy in enumeration

In the case of degeneracy in an LP-formulation, there is not a one-to-one correspondence between extreme points and feasible bases. If the task is to find thek best extreme points in the set of feasible solutions to an LP, this lack of correspondence has a certain importance, since methods based on the Simplex Algorithm are oriented towards feasible bases instead of the relevant extreme points. We therefore present an easily implementable method to avoid this problem.     

The Manne-Chao-Wilson algorithm for computing competitive equilibria: A modified version and its implementation

We present a modification of the Manne-Chao-Wilson algorithm for computing competitive equilibria and discuss some of its convergence properties. Numerical experiments involving models with up to 100 price responsive agents are provided.This research has been partially supported by the Belgian Department for Science Policy. We are indebted to Alan Manne for helpful comments; all errors and shortcomings are ours.     

Programming by action clusters

The paper describes a programming discipline, aiming at the systematic construction of programs from given global requirements. The crucial step in the approach is the conversion of the global requirements into sets of action clusters (sequences of program statements), which are then used as building blocks for the final program. The relation of the approach to proof techniques and to programming languages is discussed briefly.     

Integrating Geographical Information Systems and Multi-Criteria Methods: A Case Study

This paper presents an application of the integration between Geographical Information Systems (GIS) and Multi-Criteria Decision Analysis (MCDA) to aid spatial decisions. We present a hypothetical case study to illustrate the GIS–MCDA integration: the selection of the best municipal district of Rio de Janeiro State, Brazil, in relation to the quality of urban life. The best municipal district is the one that presents the closest characteristics to those considered ideal by the decision-maker. The approach adopted is the Multi-Objective Linear Programming (MOLP) and the chosen method is the Pareto Race.