Search

This paper considers the mathematical properties of chance constrained programming problems where the restriction is on the joint probability of a multivariate random event. One model that is considered arises when the right-handside constants of the linear constraints are random. Another model treated here occurs when the coefficients of the linear programming variables are described by a multinormal distribution. It is shown that under certain restrictions both situations can be viewed as a deterministic nonlinear programming problem. Since most computational methods for solving nonlinear programming models require the constraints be concave, this paper explores whether the resultant problem meets the concavity assumption. For many probability laws of practical importance, the constraint in the first type of model is shown to violate concavity. However, a simple logarithmic transformation does produce a concave restriction for an important class of problems. The paper also surveys the “generalized linear programming” method for solving such problems when the logarithmic transformation is justified. For the second type model, the constraint is demonstrated to be nonconcave.

In a previous paper we obtained characterizations of constraint sets determined by a finite number of differentiate pseudoconcave constraint functions possessing an interior point, and showed that they are convex Lagrange regular. In this paper we introduce a weaker type of constraint qualification and obtain asymptotic Lagrange regularity conditions from the constructs of semi-infinite programming. We impose the constraint qualification that each constraint function possess an interior point, possibly different for different constraint functions. Computationally speaking, it is relatively easy to verify since each constraint function is examined individually for interior points in consistent problems. Artificial vectors are adjoined to the dual problem and within the constructs of this problem involving no new data, convergence is assured asymptotically to Lagrangian type conditions. In this case the dual objective value tends to the optimal primal value in the limit. In case the constraint functions are differentiable concave, then asymptotic Lagrange regularity is obtained without any constraint qualification whatever.

This paper establishes necessary and sufficient conditions for constraint set stability requiring neither convex constraint functions not convex constraint sets. These conditions then lead to a sufficiency result for the continuity of the optimal objective values as the right-hand side varies. Applications to quasiconvex functions are presented.

Mathematical models of complex physical or bionic systems involve many simultaneous nonlinear equations. These groups of relationships are difficult to manipulate and even simulalation on a computer is unwieldy because most computational paths are multidirectional and are either over-or under-constrained. The foundation and purposes for an algebra of contraints are outlined in this paper. A typical application of constraint algebra would be as a supervisory routine for a digital program that operates on the topological properties of the set of the equations and determines the allowable computational paths. At the conclusion of these logical operations, which are performed with the aid of a constraint matrix, normal programming can be employed for the quantitative operations on the allowable paths. Thus, one more rational function in the man/computer relationship-that of the generation of perfectly constrained relationships-can now be taken over by the computer. The inclusion of a theorem from thermodynamics allows quite a different application: new variables may be deduced from the constraints which, together with their corresponding equations, simplify the model. This ability to synthesize new concepts (variables) and relationships (equations) which tend to simplify models can be considered as an analog for the cognitive process of abstraction.

SUMMARY The calculation of economic lot sizes with more than one constraint on the system is a recognized problem in inventory control theory. This paper presents a simplex like solution procedure. The algorithm as presented can be readily adapted to other constraints which may arise in a specific application. The essential conditions for application are that the non-linear constraints and/or objective function be differentiable, convex functions.

This paper describes an effort to design a heuristic problem-solving program which accepts problems stated in a nondeterministic programming language and applies constraint satisfaction methods and heuristic search methods to find solutions. The use of nondeterministic programming languages for stating problems is discussed, and REF, the language accepted by the problem solver ARF, is described. Various extensions to ref are considered. The conceptual structure of the program is described in detail and various possibilities for extending it are discussed. The use of the input language and the behaviour of the program are described and analyzed in sixteen sample problems.

In this paper we examine the relationship between two constraint qualifications developed by Abadie and Arrow, Hurwicz, and Uzawa. A third constraint qualification is discussed and shown to be weaker than either of those mentioned above.

By starting with an all-integer zero-one linear programming problem, it is possible to develop a modified, possibly linear, programming problem that provides a characterization of the basis corresponding to a feasible zero-one solution to the integer problem. This characterization is based on the number of variables equal to one in the feasible solution. This paper develops an approach to zero-one programming based on this characterization. The method uses the criterion function of the original problem as a constraint, and then generates a sequence of feasible zero-one solutions, each with a greater value of the objective function. The solution technique is terminated when no more feasible solutions can be found, indicating that the last feasible solution determined is the optimum.

The aim of this paper is to construct sets of uniformly tighter linear constraints to replace a chance constraint, in order to be able to solve the chance-constrained programming problem by the simplex method. The chance constraints are first diagonalized by a linear orthonormal transformation. Uniformly tighter linear constraints can then be formed to replace the chance constraint. The developed multistage linear programming problem can also be solved using the Dantzig-Wolfe decomposition technique. Approximation errors of our method and one of Hillier's [8] are compared.

This paper describes a new algorithm solving the deterministic equivalents of chance-constrained problems where the random variables are normally distributed and independent of each other. In this method nonlinear chance-constraints are first replaced by uniformly tighter linear constraints. The resulting linear programming problem is solved by a standard simplex method. The linear programming problem is then revised using the solution data and solved again until the stopping rule of the algorithm terminates the process. It is proved that the algorithm converges and that the solution found is the e-optimal solution of the chance-constrained programming problem. The computational experience of the algorithm is reported. The algorithm is efficient if the random variables are distributed independently of each other and if they number less than two hundred. The computing system is called “CHAPS”, i.e. “Chance-ConstrainedProgrammingSystem”.

The result of this paper concerns the continuity of the solution vector for a parametric programming problem in which both the objective function and the constraint functions involve parameters.

In this correspondence two optimal control problems with state variable inequality constraints are solved using a quadratic programming technique. These problems were originally solved in the above paper with a proposed technique and a penalty function technique. The results given in this correspondence, along with Jacobson and Lele's results, constitute the beginning of a relative performance data base.

This paper presents a new function minimization algorithm for minimizing nonlinear functions of a finite number of variables subject to nonlinear equality constraints. The algorithm also provides for the explicit handling of upper and lower bounds on each of the independent variables. Although other more general inequality constraint can be transformed into an equality constraint at the expense of introducing an additional slack variable. The algorithm proposed combines the idea of a "balance function," developed independently in References 1 and 2 with a second order method for updating the balance function La grange multipliers originally developed in Reference 3. This updating technique makes use of the current estimate of the inverse Hessian of the balance function which is a byproduct of the unconstrained minimization of the balance function using the Fletcher-Powell algorithm.

This paper presents a new method for the optimization of system reliability with linear constraints, using the parametric approach [1]. The classical nonlinear programming technique is used for the solution. This method, which is analytically complete, sufficiently accurate and computationally simple, gives optimum or near optimum design. The procedure is illustrated with examples, and flow charts for the problems are given.

This paper describes the mathematical formulation of a class of three-dimensional surfaces parametrically represented for efficient computer display. The degrees of freedom in the representation are such as to provide a rich variety of surfaces with convenient parameters for manipulation and constraint satisfaction. Historically this work began as an investigation of the properties of rational parametric cubics, a class of curves well-suited to the Harvard three-dimensional display. The desire to represent curvilinear surfaces in terms of these curves and an introduction to the Coons' surface formulation were sufficient to suggest the approach discussed here.