Computing equilibria via nonconvex programming

The problem of determining a vector that places a system in a state of equilibrium is studied with the aid of mathematical programming. The approach derives from the logical equivalence between the general equilibrium problem and the complementarity problem, the latter being explicitly concerned with finding a point in the set S = {x: < x, g(x)> = 0, g(x) ≦ 0, x ≧ 0}. An associated nonconvex program, min{? < x, g(x) > : g(x) ≦ 0, x ≧ 0}, is proposed whose solution set coincides with S. When the excess demand function g(x) meets certain separability conditions, equilibrium solutions are obtained by using an established branch and bound algorithm. Because the best upper bound is known at the outset, an independent check for convergence can be made at each iteration of the algorithm, thereby greatly increasing its efficiency. A number of examples drawn from economic and network theory are presented in order to demonstrate the computational aspects of the approach. The results appear promising for a wide range of problem sizes and types, with solutions occurring in a relatively small number of iterations.     

Spike swapping in basis reinversion

During basis reinversion of either a product form or elimination form linear programming system, it may become necessary to swap spike columns to effect the reinversion and maintain the desired sparsity characteristics. This note shows that the only spikes which need be examined when an interchange is required are those not yet processed in the current external bump.     

An optimum group maintenance policy

In this article we present an optimum maintenance policy for a group of machines subject to stochastic failures where the repair cost and production loss due to the breakdown of machines are minimized. A nomograph was developed for machines with exponential failure time distributions. The optimal schedule time for repair as well as the total repair cost per cycle can be obtained easily from the nomograph. Conditions for the existence of a unique solution for the optimum schedule and the bounds for the schedule are discussed.     

Nonadjacent extreme point methods for solving linear programs

In this article we present some advanced basis or block-pivoting, relaxation, and feasible direction methods for solving linear programming problems. Preliminary computational results appear to indicate that the former two types of simplex-based procedures may hold promise for solving linear programming problems, unlike the third type of scheme which is shown to be computationally unattractive.     

An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns

We consider the stochastic linear knapsack problem in which costs are known with certainty but returns are independent, normally distributed random variables. The objective is to maximize the probability that the overall return equals or exceeds a specified target value. A previously proposed preference order dynamic programming-based algorithm has been shown to be potentially suboptimal. We offer an alternative hybrid DP/branch-and-bound algorithm that both guarantees optimality and significantly outperforms generating the set of Pareto optimal returns.© 1993 John Wiley & Sons, Inc.     

Sandwich approximation of univariate convex functions with an application to separable convex programming

In this article an algorithm for computing upper and lower ? approximations of a (implicitly or explicitly) given convex function h defined on an interval of length T is developed. The approximations can be obtained under weak assumptions on h (in particular, no differentiability), and the error decreases quadratically with the number of iterations. To reach an absolute accuracy of ? the number of iterations is bounded by