Optimization Software Design Principles

Computational Experience with a Software Framework for Parallel Integer Programming

Categories (Mixed) Integer Linear Programming, Optimization Software Design Principles, Parallel Algorithms

In this paper, we discuss the challenges that arise in parallelizing algorithms for solving mixed integer linear programs and introduce a software framework that aims to address these challenges. The framework was designed specifically with support for implementation of relaxation-based branch-and-bound algorithms in mind. Achieving efficiency for such algorithms is particularly challenging and involves a … Read more

New stopping criteria for detecting infeasibility in conic optimization

Categories Linear, Cone and Semidefinite Programming, Optimization Software Design Principles Tags , , ,

Detecting infeasibility in conic optimization and providing certificates for infeasibility pose a bigger challenge than in the linear case due to the lack of strong duality. In this paper we generalize the approximate Farkas lemma of Todd and Ye from the linear to the general conic setting, and use it to propose stopping criteria for … Read more

Extending Algebraic Modelling Languages for Stochastic Programming

Categories Modeling Languages and Systems, Optimization Software Design Principles, Stochastic Programming Tags

Algebraic modelling languages have gained wide acceptance and use in Mathematical Programming by researchers and practitioners. At a basic level, stochastic programming models can be defined using these languages by constructing their deterministic equivalent. Unfortunately, this leads to very large model data instances. We propose a direct approach in which the random values of the … Read more

StAMPL: A Filtration-Oriented Modeling Tool for Stochastic Programming

Categories Modeling Languages and Systems, Optimization Software Design Principles, Stochastic Programming Tags , ,

Every multistage stochastic programming problem with recourse (MSPR) contains a filtration process. In this research, we created a notation that makes the filtration process the central syntactic construction of the MSPR. As a result, we achieve lower redundancy and higher modularity than is possible with the mathematical notation commonly associated with stochastic programming. To experiment … Read more

Kestrel: An Interface from Optimization Modeling Systems to the NEOS Server

Categories Modeling Languages and Systems, Optimization Software and Modeling Systems, Optimization Software Design Principles Tags , , ,

The NEOS Server provides access to a variety of optimization resources via the Internet. The new Kestrel interface to the Server enables local modeling environments to request NEOS optimization services and retrieve the results for local visualization and analysis, so that users have the same convenient access to remote NEOS solvers as to those installed … Read more

OSiL: An Instance Language for Optimization

Categories Modeling Languages and Systems, Optimization Software and Modeling Systems, Optimization Software Design Principles

Distributed computing technologies such as Web Services are growing rapidly in importance in today’s computing environment. In the area of mathematical optimization, it is becoming increasingly common to separate modeling languages from optimization solvers. In fact, the modeling language software, solver software, and data used to generate a model instance might reside on different machines … Read more

Exploiting Structure in Parallel Implementation of Interior Point Methods for Optimization

Categories Optimization Software Design Principles, Parallel Algorithms Tags , ,

OOPS is an object oriented parallel solver using the primal dual interior point methods. Its main component is an object-oriented linear algebra library designed to exploit nested block structure that is often present is truly large-scale optimization problems. This is achieved by treating the building blocks of the structured matrices as objects, that can use … Read more

LPFML: A W3C XML Schema for Linear and Integer Programming

Categories Modeling Languages and Systems, Optimization Software and Modeling Systems, Optimization Software Design Principles Tags , , ,

There are numerous algebraic modeling languages for generating linear programs and numerous solvers for computing solutions to linear programs. This proliferation of modeling languages and solvers is frustrating to modelers who find that only certain languages connect to certain solvers. One way to encourage modeler-solver compatibility is to use a standard representation of a problem … Read more

On an Approximation of the Hessian of the Lagrangian

Categories Constrained Nonlinear Optimization, Optimization Software Design Principles Tags , ,

In the context of SQP methods or, more recently, of sequential semidefinite programming methods, it is common practice to construct a positive semidefinite approximation of the Hessian of the Lagrangian. The Hessian of the augmented Lagrangian is a suitable approximation as it maintains local superlinear convergence under appropriate assumptions. In this note we give a … Read more

Numerical Issues and Influences in the Design of Algebraic Modeling Languages for Optimization

Categories Complementarity and Variational Inequalities, Modeling Languages and Systems, Optimization Software Design Principles Tags , , , , ,

This paper draws from our experience in developing the AMPL modeling language, to show where numerical issues have been crucial to modeling language design and where modeling language advances have strongly influenced the design of solvers. CitationProceedings of the 20th Biennial Conference on Numerical Analysis, Dundee, Scotland, D.F. Griffiths and G.A. Watson, eds., University of … Read more