On the core and nucleolus of minimum cost spanning tree games

We develop two efficient procedures for generating cost allocation vectors in the core of a minimum cost spanning tree (m.c.s.t.) game. The first procedure requires O(n ²) elementary operations to obtain each additional point in the core, wheren is the number of users. The efficiency of the second procedure, which is a natural strengthening of the first procedure, stems from the special structure of minimum excess coalitions in the core of an m.c.s.t. game. This special structure is later used (i) to ease the computational difficulty in computing the nucleolus of an m.c.s.t. game, and (ii) to provide a geometric characterization for the nucleolus of an m.c.s.t. game. This geometric characterization implies that in an m.c.s.t. game the nucleolus is the unique point in the intersection of the core and the kernel. We further develop an efficient procedure for generating fair cost allocations which, in some instances, coincide with the nucleolus. Finally, we show that by employing Sterns' transfer scheme we can generate a sequence of cost vectors which converges to the nucleolus. Part of this research was done while the author was visiting the Department of Operations Research at Stanford University. This research was partially supported by Natural Sciences and Engineering Research Council Canada Grant A-4181.     

On market prices in linear production games

Consider a game in which resources may be combined to produce products of known values. For linear production processes, the game may be characterized by a family of linear programs. It is shown that appropriately defined market prices for the resources coincide with the set of optimal dual solutions to one of these linear programs. This result generalizes and unifies the known cases in game theory, in which the core of a game coincides with the set of dual optimal solutions to a corresponding master linear programming problem.Based on working papers by Engelbrecht-Wiggans (1982) and Granot (1983). The work was motivated by an application, reported in Engelbrecht-Wiggans (1983), supported by the US EPA.Research was partially supported by the Natural Science and Engineering Research Council of Canada Grant A4181.     

Lower and upper bounds for linear production games

We study the problem of allocating the total profit of a production enterprise among the resource owners, using the game-theoretic framework introduced by Owen [Owen, G., 1975. On the core of linear production games. Mathematical Programming 9, 358–370]. We provide lower (upper) bounds on the values of the game by aggregating over columns (rows) of the LP-problem. By choosing aggregation weights corresponding to optimal solutions of the primal (dual) LP-problem, we can create new games whose core form a superset (subset) of the original core. An estimate of the resulting error, in terms of an ?$?$-core, is obtained by solving a mixed integer programming problem, and we also suggest an iterative procedure for improving the bounds. Using a set of numerical examples, we investigate how the performance of the aggregation approach depends on the structure of the problem data.     

A RECOGNITION PROBLEM IN CONVERTING LINEAR PROGRAMMING TO NETWORK FLOW MODELS

The main goal of this paper is to study the following combinatorial problem.given a finite set E={e1,e2,…em} and a subset familly σ={S1,S2,…,Sn}of E,does there exist a tree T with the edge set E such that each induced subgraph T[Si] of Si is precisely a path (1≤i≤k)?     

An algorithm for a piecewise linear model of trade and production with negative prices and bankruptcy

The general equilibrium model is approximated as a piecewise linear convex model and solved from the point of view of welfare economics using linear programming and fixed point methods.This research was supported in part by Army Research Office-Durham Contract DAAG-29-74-C-0032, NSF Grant MPS-72-04832-A03, and Energy Research and Development Administration Contract E(04-3)-326 PA#18.     

Solving staircase linear programs by the simplex method, 2: Pricing

This and a companion paper consider how current implementations of the simplex method may be adapted to better solve linear programs that have a staged, or ‘staircase’, structure. The preceding paper considered ‘inversion’ routines that factorize the basis and solve linear systems. The present paper examines ‘pricing’ routines that compute reduced costs for nonbasic variables and that select a variable to enter the basis at each iteration. Both papers describe extensive (although preliminary) computer experiments, and can point to some quite promising results. For pricing in particular, staircase computation strategies appear to offer modest but consistent savings; staircase selection strategies, properly chosen, may offer substantial savings in number of iterations, time per iteration, or both.     

Solving staircase linear programs by the simplex method, 1: Inversion

This and a companion paper consider how current implementations of the simplex method may be adapted to better solve linear programs that have a staged, or staircase, structure. The present paper looks at inversion routines within the simplex method, particularly those for sparse triangular factorization of a basis by Gaussian elimination and for solution of triangular linear systems. The succeeding paper examines pricing routines. Both papers describe extensive (though preliminary) computational experience, and can point to some quite promising results.     

A parallel algorithm for solving the linear complementarity problem

The concept of multitasking mathematical programs is discussed, and an application of multitasking to the multiple-cost-row linear programming problem is considered. Based on this, an algorithm for solving the Linear Complementarity Problem (LCP) in parallel is presented. A variety of computational results are presented using this multitasking approach on the CRAY X-MP/48. These results were obtained for randomly generated LCP's where thenxn dense matrixM has no special properties (hence, the problem is NP-hard). based on these results, an average time performance ofO(n ⁴) is observed.     

A nonlinear equation for linear programming

We present a characterization of the normal optimal solution of the linear program given in canonical form max{c ^tx: Ax = b, x 0}. (P) We show thatx ^* is the optimal solution of (P), of minimal norm, if and only if there exists anR > 0 such that, for eachr R, we havex ^* = (rc – A^t_r)₊. Thus, we can findx ^* by solving the following equation for _r A(rc – A^t_r)₊ = b. Moreover,(1/r) _r then converges to a solution of the dual program.On leave from The University of Alberta, Edmonton, Canada. Research partially supported by the National Science and Engineering Research Council of Canada.     

A simplex algorithm for piecewise-linear programming I: Derivation and proof

The simplex method for linear programming can be extended to permit the minimization of any convex separable piecewise-linear objective, subject to linear constraints. This three-part paper develops and analyzes a general, computationally practical simplex algorithm for piecewiselinear programming.Part I derives and justifies the essential steps of the algorithm, by extension from the simplex method for linear programming in bounded variables. The proof employs familiar finite-termination arguments and established piecewise-linear duality theory.Part II considers the relaxation of technical assumptions pertaining to finiteness, feasibility and nondegeneracy of piecewise-linear programs. Degeneracy is found to have broader consequences than in the linear case, and the standard techniques for prevention of cycling are extended accordingly.Part III analyzes the computational requirements of piecewise-linear programming. The direct approach embodied in the piecewise-linear simplex algorithm is shown to be inherently more efficient than indirect approaches that rely on transformation of piecewise-linear programs to equivalent linear programs. A concluding section surveys the many applications of piecewise-linear programming in linear programming,l ₁ estimation, goal programming, interval programming, and nonlinear optimization.This research has been supported in part by the National Science Foundation under grant MCS-8217261.     

A node rooted flow-based model for the local access network expansion problem

In this paper, we present a new formulation for the local access network expansion problem. Previously, we have shown that this problem can be seen as an extension of the well-known Capacitated Minimum Spanning Tree Problem and have presented and tested two flow-based models. By including additional information on the definition of the variables, we propose a new flow-based model that permits us to use effectively variable eliminations tests as well as coefficient reduction on some of the constraints. We present computational results for instances with up to 500 nodes in order to show the advantages of the new model in comparison with the others.     

On the Glivenko-Cantelli problem in stochastic programming: Mixed-integer linear recourse

Expected recourse functions in linear two-stage stochastic programs with mixed-integer second stage are approximated by estimating the underlying probability distribution via empirical measures. Under mild conditions, almost sure uniform convergence of the empirical means to the original expected recourse function is established.     

A natural selection from the core of a TU game: the core-center

We present a new allocation rule for the class of games with a nonempty core: the core-center. This allocation rule selects a centrally located point within the core of any such game. We provide a deep discussion of its main properties.     

A unifying theory of exactness of linear penalty functions II: parametric penalty functions

In this article, we develop a general theory of exact parametric penalty functions for constrained optimization problems. The main advantage of the method of parametric penalty functions is the fact that a parametric penalty function can be both smooth and exact unlike the standard (i.e. non-parametric) exact penalty functions that are always nonsmooth. We obtain several necessary and/or sufficient conditions for the exactness of parametric penalty functions, and for the zero duality gap property to hold true for these functions. We also prove some convergence results for the method of parametric penalty functions, and derive necessary and sufficient conditions for a parametric penalty function to not have any stationary points outside the set of feasible points of the constrained optimization problem under consideration. In the second part of the paper, we apply the general theory of exact parametric penalty functions to a class of parametric penalty functions introduced by Huyer and Neumaier, and to smoothing approximations of nonsmooth exact penalty functions. The general approach adopted in this article allowed us to unify and significantly sharpen many existing results on parametric penalty functions.     

A linear regression model with persistent level shifts: An alternative to infill asymptotics

A changepoint in a time series is a time of change in the marginal distribution, autocovariance, or any other distributional structure of the series. Examples include mean level shifts and volatility (variance) changes. Climate data, for example, is replete with mean shift changepoints, occurring whenever a recording instrument is changed or the observing station is moved. Here, we consider the problem of incorporating known changepoint times into a regression model framework. Specifically, we establish consistency and asymptotic normality of ordinary least squares regression estimators that account for an arbitrary number of mean shifts in the record. In a sense, this provides an alternative to the customary infill asymptotics for regression models that assume an asymptotic infinity of data observations between all changepoint times.     

MIN-MAD life: A multi-period optimization model for life insurance company investment decisions

This paper presents a model, called the MIN-MAD Life Model, for managing the investments of a life insurance company over a multiperiod planning horizon. The MIN-MAD Life Model is a linear programming under uncertainty model based on Markowitz portfolio theory. Given the insurance company's current position and its forecasts of possible future developments with their associated probabilities, the model helps determine the set of efficient investment decisions over the planning horizon subject to market constraints and to the insurance company's legal and policy constraints. The senior executives of the life insurance company need examine only the set of efficient investment decisions to determine their optimal investment decisions.     

Coherent mortality forecasting with generalized linear models: A modified time-transformation approach

In this paper, we propose an alternative approach for forecasting mortality for multiple populations jointly. Our contribution is developed upon the generalized linear models introduced by Renshaw et al., (1996) and Sithole et al., (2000), in which mortality forecasts are generated within the model structure, without the need of additional stochastic processes. To ensure that the resulting forecasts are coherent, a modified time-transformation is developed to stipulate the expected mortality differential between two populations to remain constant when the long-run equilibrium is attained. The model is then further extended to incorporate a structural change, an important property that is observed in the historical mortality data of many national populations. The proposed modeling methods are illustrated with data from two different pairs of populations: (1) Swedish and Danish males; (2) English and Welsh males and U.K. male insured lives.     

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.     

Shape Hessian for generalized Oseen flow by differentiability of a minimax: A Lagrangian approach

The goal of this paper is to compute the shape Hessian for a generalized Oseen problem with nonhomogeneous Dirichlet boundary condition by the velocity method. The incompressibility will be treated by penalty approach. The structure of the shape gradient and shape Hessian with respect to the shape of the variable domain for a given cost functional are established by an application of the Lagrangian method with function space embedding technique. This work was supported by the National Natural Science Fund of China (No. 10371096) for ZM Gao and YC Ma.