Search

We present a computationally efficient implementation of an interior point algorithm for solving large-scale problems arising in stochastic linear programming and robust optimization. A matrix factorization procedure is employed that exploits the structure of the constraint matrix, and it is implemented on parallel computers. The implementation is perfectly scalable. Extensive computational results are reported for a library of standard test problems from stochastic linear programming, and also for robust optimization formulations. The results show that the codes are efficient and stable for problems with thousands of scenarios. Test problems with 130 thousand scenarios, and a deterministic equivalent linear programming formulation with 2.6 million constraints and 18.2 million variables, are solved successfully. [ABSTRACT FROM AUTHOR]

Sequential quadratic (SQP) programming methods are the method of choice when solving small or medium-sized problems. Since they are complex methods they are difficult (but not impossible) to adapt to solve large-scale problems. We start by discussing the difficulties that need to be addressed and then describe some general ideas that may be used to resolve these difficulties. A number of SQP codes have been written to solve specific applications and there is a general purposed SQP code called SNOPT, which is intended for general applications of a particular type. These are described briefly together with the ideas on which they are based. Finally we discuss new work on developing SQP methods using explicit second derivatives. [ABSTRACT FROM AUTHOR]

The facility layout problem (FLP) has many practical applications and is known to be NP-hard. During recent decades exact and heuristic approaches have been proposed in the literature to solve FLPs. In this paper we review the most recent developments regarding simulated annealing and genetic algorithms for solving facility layout problems approximately. [ABSTRACT FROM AUTHOR]

Numerical and computational aspects of direct methods for large and sparse least squares problems are considered. After a brief survey of the most often used methods, we summarize the important conclusions made from a numerical comparison in matlab. Significantly improved algorithms have during the last 10-15 years made sparse QR factorization attractive, and competitive to previously recommended alternatives. Of particular importance is the multifrontal approach, characterized by low fill-in, dense subproblems and naturally implemented parallelism. We describe a Householder multifrontal scheme and its implementation on sequential and parallel computers. Available software has in practice a great influence on the choice of numerical algorithms. Less appropriate algorithms are thus often used solely because of existing software packages. We briefly survey software packages for the solution of sparse linear least squares problems. Finally, we focus on various applications from optimization, leading to the solution of large and sparse linear least squares problems. In particular, we concentrate on the important case where the coefficient matrix is a fixed general sparse matrix with a variable diagonal matrix below. Inner point methods for constrained linear least squares problems give, for example, rise to such subproblems. Important gains can be made by taking advantage of structure. Closely related is also the choice of numerical method for these subproblems. We discuss why the less accurate normal equations tend to be sufficient in many applications. [ABSTRACT FROM AUTHOR]

Recently, in [12] a very general class of truncated Newton methods has been proposed for solving large scale unconstrained optimization problems. In this work we present the results of an extensive numerical experience obtained by different algorithms which belong to the preceding class. This numerical study, besides investigating which are the best algorithmic choices of the proposed approach, clarifies some significant points which underlies every truncated Newton based algorithm. [ABSTRACT FROM AUTHOR]

This paper considers the number of inner iterations required per outer iteration for the algorithm proposed by Conn et al. [9]. We show that asymptotically, under suitable reasonable assumptions, a single inner iteration suffices. [ABSTRACT FROM AUTHOR]

ELSO is an environment for the solution of large-scale optimization problems With ELSO the user is required to provide only code for the evaluation of a partially separable function. ELSO exploits the partial separability structure of the function to compute the gradient efficiently using automatic differentiation. We demonstrate ELSO's efficiency by comparing the various options available in ELSO. Our conclusion is that the hybrid option in ELSO provides performance comparable to the hand-coded option, while having the significant advantage of not requiring a hand-coded gradient or the sparsity pattern of the partially separable function. In our test problems, which have carefully coded gradients, the computing time for the hybrid AD option is within a factor of two of the hand-coded option. [ABSTRACT FROM AUTHOR]

This paper provides a means for comparing various computer codes for solving large scale mixed complementarity problems. We discuss inadequacies in how solvers are currently compared, and present a testing environment that addresses these inadequacies. This testing environment consists of a library of test problems, along with GAMS and MATLAB interfaces that allow these problems to be easily accessed. The environment is intended for use as a tool by other researchers to better understand both their algorithms and their implementations, and to direct research toward problem classes that are currently the most challenging. As an initial benchmark, eight different algorithm implementations for large scale mixed complementarity problems are briefly described and tested with default parameter settings using the new testing environment. [ABSTRACT FROM AUTHOR]