Search

We present an algorithm for solving bilevel linear programs that uses simplex pivots on an expanded tableau. The algorithm uses the relationship between multiple objective linear programs and bilevel linear programs along with results for minimizing a linear objective over the efficient set for a multiple objective problem. Results in multiple objective programming needed are presented. We report computational experience demonstrating that this approach is more effective than a standard branch-and-bound algorithm when the number of leader variables is small.

This paper provides a comparison and analysis of the performance of a special purpose algorithm and several specific available nonlinear programming codes applied to a robot trajectory problem.

While significant progress has been made, analytic research on principal-agent problems that seek closed-form solutions faces limitations due to tractability issues that arise because of the mathematical complexity of the problem. The principal must maximize expected utility subject to the agent’s participation and incentive compatibility constraints. Linearity of performance measures is often assumed and the Linear, Exponential, Normal (LEN) model is often used to deal with this complexity. These assumptions may be too restrictive for researchers to explore the variety of relationships between compensation contracts offered by the principal and the effort of the agent. In this paper we show how to numerically solve principal-agent problems with nonlinear contracts. In our procedure, we deal directly with the agent’s incentive compatibility constraint. We illustrate our solution procedure with numerical examples and use optimization methods to make the problem tractable without using the simplifying assumptions of a LEN model. We also show that using linear contracts to approximate nonlinear contracts leads to solutions that are far from the optimal solutions obtained using nonlinear contracts. A principal-agent problem is a special instance of a bilevel nonlinear programming problem. We show how to solve principal-agent problems by solving bilevel programming problems using the ellipsoid algorithm. The approach we present can give researchers new insights into the relationships between nonlinear compensation schemes and employee effort.

We study the performance of four general-purpose nonlinear programming algorithms and one special-purpose geometric programming algorithm when used to solve geometric programming problems. Experiments are reported which show that the special-purpose algorithm GGP often finds approximate solutions more quickly than the general-purpose algorithm GRG2, but is usually not significantly more efficient than GRG2 when greater accuracy is required. However, for some of the most difficult test problems attempted, GGP was dramatically superior to all of the other algorithms. The other algorithms are usually not as efficient as GGP or GRG2. The ellipsoid algorithm is most robust.

A nonlinear model is developed for allocating treatment requirements along a stream so as to meet stream dissolved oxygen standards at each point in the stream while minimizing the total annual cost of all discharging activities. An application of the model to several reaches of the Upper Hudson River is considered, and some alternative pollution abatement policies are analyzed.

A method for generating the entire efficient set for a multiple objective linear program is developed. The method is based on two characterizations of maximal efficient faces. The first characterization is used to determine the set of maximal efficient faces incident to a given efficient vertex, and the second characterization ensures that previously generated maximal efficient faces are easily recognized (and not regenerated). The efficient set is described as the union of maximal efficient faces. An alternate implicit description of the efficient set as the set of all optimal vectors for a finite set of linear programs is also provided.

In this paper we consider algorithmic and computational aspects of selected methods for posynomial and signomial programming problems. In particular, we consider the modified concave simplex method for dual posynomial programs and discuss some recent developments suggesting a new dual algorithm. We also consider linear programming based algorithms for primal posynomial programs. Finally, we discuss a recently developed branch and bound method for signomial programming.

In this paper, a dual method is developed for minimizing a convex quadratic function of several variables subject to inequality constraints on the same type of function. The dual program is a concave maximization problem with constraints that are essentially linear. However, the dual objective function is not differentiable over the dual constraint region. In particular, if the primal constraints are not all active, the dual objective function is not differentiable at the optimal point. The numerical difficulties associated with this nondifferentiability are circumvented by considering a sequence of dual programs via a modified penalty function technique that does not eliminate the dual constraints but does insure that they will all be active at optimality. A numerical example is included.

An algorithm for solving posynomial geometric programs is presented. The algorithm uses a modification of the concave simplex method to solve the dual program which has a nondifferentiable objective function. The method permits simultaneous changes in certain blocks of dual variables. A convergence proof follows from the convergence proof of the concave simplex method. Some computational results on problems with up to forty degrees of difficulty are included.

In this paper, a posynomial programming model is developed for the optimal selection of steam turbine exhaust annulus and condenser sizes. After formulating the general model, a numerical example is presented and sensitivity analysis is considered. A simple formula expressing the optimal cost of the condensing system as a function of selected parameters is obtained.

We investigate an ellipsoid algorithm for nonlinear programming. After describing the basic steps of the algorithm, we discuss its computer implementation and present a method for measuring computational efficiency. The computational results obtained from experimenting with the algorithm are discussed and the algorithm's performance is compared with that of a widely used commercial code.

A dual algorithm is developed for solving a general class of nonlinear programs that properly contains all convex quadratic programs with quadratic constraints and l p -constrained l p -approximation problems. The general dual program to be solved has essentially linear constraints but the objective function is nondifferentiable when certain variables equal zero. Modifications to the reduced gradient method for linearly constrained problems are presented that overcome the numerical difficulties associated with the nondifferentiable objective function. These modifications permit ‘blocks’ of variables to move to and away from zero on certain iterations even though the objective function is nondifferentiable at points having a block of variables equal to zero.

In this paper we develop a method for finding all efficient extreme points for multiple objective linear programs. Simple characterizations of the efficiency of an edge incident to a nondegenerate or a degenerate efficient vertex are given. These characterizations form the basis of an algorithm for enumerating all efficient vertices. The algorithm appears to have definite computational advantages over other methods. Some illustrative examples are included.

A simple primal solution method for geometric programming is proposed. The method exploits the proximity of geometric and linear programming and is easy to implement by anyone having a linear programming code. Some examples and computational experience are given.

In this paper, we give an applications-oriented survey of geometric programming. This important class of nonlinear programming problems has been intensively studied over the past decade and has played a crucial role in an extremely broad range of applications. The focus of the paper will be on posynomial programs and the slightly more general class of signomial programs. The approach used in studying posynomial programs has been generalized to a much broader class of optimization problems, and an excellent survey of that generalized theory recently appeared in a paper by E. L. Peterson [SIAM Rev., 18 (1976), pp. 1–51]. We do not consider that generalized theory here. It is our intent to provide the reader with an understanding of the basic results in posynomial and signomial programming that have played a crucial role in applications. After reviewing these basic results, we consider computational methods and applications. Three specific applications are considered in detail, and a bibliography indicating ...

Optimization of a special class of geometric programs is achieved by a decomposition technique. Optimal vectors to certain subproblems are obtained by solving a single unconstrained minimization problem involving a strictly convex function. These optimal vector readily yield an optimal vector to the original program.

This note identifies instances where nonlinearities may occur in the application of goal programming. An illustration is presented and implications discussed.

In this note we provide a counter example to a proposed method of finding an initial efficient extreme point for multiple objective linear programs. We also show that the existing method of Ecker and Kouada for finding an initial efficient point can be used to find an efficient extreme point easily.

In this paper, the optimal design of dry-type natural-draft cooling towers is investigated. Using physical laws and engineering design relations that govern the system, a rather detailed optimization model is developed. This model is then reformulated as a geometric programming problem. A primary consideration in this reformulation is how certain polynomial equations may be effectively replaced by inequalities. A numerical example follows.

In this paper, we present a method for solving the dual of a posynomial geometric program based on modifications of the reduced gradient method. The modifications are necessary because of the numerical difficulties associated with the nondifferentiability of the dual objective function. Some preliminary numerical results are included that compare the proposed method with the modified concave simplex method of Beck and Ecker of Ref. 1.

In this paper, we develop a method for finding all nondominated compromise solutions to a multiple objective linear program. We also develop an iterative technique that yields an interesting subset of the nondominated set termed the tradeoff — compromise set. This subset depends on the ideal vector and gives insight into what tradeoffs are possible amongst the objectives.