Dept. of Industrial Engineering & Management Sciences
2145 Sheridan Road
Evanston, IL 60208-3119, U.S.A.
847/467-1828, 847/491-8005 (fax)
To view saved PDF files, download and install Adobe Acrobat Reader.
To view the PDF files immediately, install in your browser the Acrobat Reader Plug-In
that comes with the Acrobat Reader download package.
R. Fourer, J. Ma and K. Martin, OSiL: An Instance Language for Optimization. Technical report, Department of Industrial Engineering and Management Sciences, Northwestern University (2006).
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 using different operating systems. Such a distributed environment makes it critical to have an open standard for exchanging model instances.
In this paper we present OSiL (Optimization Services instance Language), an XML-based computer language for representing instances of large-scale optimization problems including linear programs, mixed-integer programs, quadratic programs, and very general nonlinear programs. OSiL has two key features that make it much superior to current standard forms for optimization problem instances. First, it uses the object-oriented features of XML schemas to efficiently represent nonlinear expressions. Second, its XML schema maps directly into a corresponding in-memory representation of a problem instance. The in-memory representation provides a robust application program interface for general nonlinear programming, facilitates reading and writing postfix, prefix, and infix formats to and from the nonlinear expression tree, and makes the expression tree readily available for function and derivative evaluations.
G. Dutta and R. Fourer, Database Structure for a Class of Multi-Period Mathematical Programming Models. Technical report, Indian Institute of Management, Ahmedabad (2005).
We describe how a generic multi-period optimization-based decision support system can be used for strategic and operational planning in a company whose processes can be described in terms of five fundamental elements: Materials, Facilities, Activities, Times and Storage-Areas. We discuss the issues of interface design, data reporting and updating, and production and profit planning. We also compare the performance of two different types of database structure with respect to optimization.
An Operations Cyberinfrastructure: Using Cyberinfrastructure and Operations Research to Improve Productivity in the Enterprise. Report on a Workshop held in Washington, D.C. August 30-31, 2004; organized by Robert Fourer, Jorge Moré, Karthik Ramani and Stephen Wright; sponsored by the National Science Foundation.
Science and engineering are being revolutionized by a cyberinfrastructure (CI) that promises to provide hardware and software support for a wealth of new discoveries and innovations. The report of the National Science Foundation s Blue-Ribbon Advisory Panel on Cyberinfrastructure has identified diverse areas of science and engineering that are poised to benefit from this revolution.
Our workshop formulated the concept of an Operations Cyberinfrastructure (OCI), which will achieve far-reaching benefits for enterprise-wide applications by harnessing advanced sensing, data analysis, modeling, simulation, and optimization technologies. These benefits will be realized by integrating the financial, economic, and strategic objectives of an enterprise with the design of supply networks, product life cycles, and market environments. The field of Operations Research (OR) provides the integrating methodology for these diverse considerations and the scientific underpinning for the decision-making process. The OCI will combine OR methodology with the computational and knowledge-exchange capabilities of CI, producing tools for better planning and operational decision-making in a broad variety of enterprises.
We conclude that timely action is critical to the establishment of a successful Operations Cyberinfrastructure, and that NSF initiatives will be necessary to stimulate basic research on OCI standards, protocols, and applications before development can be taken over by more commercial entities. NSF initiatives in this area should include significant funding for basic OR research that is tied to development of an OCI, for research in the development of CI tools that are particularly relevant to an OCI, and especially for research projects at the interface of OR and CI. We further recommend that funding for OCI-related projects be leveraged by funds for other NSF programs in CI, information science, engineering, and social, behavioral, and economic sciences.
R. Fourer, L.B. Lopes and K. Martin, LPFML: A W3C XML Schema for Linear Programming. Technical report, Department of Industrial Engineering and Management Sciences, Northwestern University (2003).
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 instance, so that all modeling languages and all solvers deal with problem instances in the same form. Such a standard should be able to express instance-specific and vendor-specific information, should be simple to manipulate and validate, and should promote the integration of optimization software with other software.
Given the increasing importance of XML for data representation and exchange, and XMLís ability to support the characteristics above, it is natural to base a proposal for a standard for representing problem instances on XML. In this paper, we present the LPFML Schema, a W3C Schema for representing linear programming problem instances in XML. We also describe a library of open-source C++ classes that we have written to facilitate the exchange of information between modeling languages and solvers. We show how these classes have been used to provide previously unavailable language-solver connections.
R. Fourer, D.M. Gay and B.W. Kernighan, Design Principles and New Developments in the AMPL Modeling Language. In Modeling Languages in Mathematical Optimization, J. Kallrath, ed., Kluwer Academic Publishers (January 2004) 105-135.
R. Fourer and L.B. Lopes, StAMPL: A Filtration-Oriented Modeling Tool for Stochastic Programming. Technical report, Department of Industrial Engineering and Management Sciences, Northwestern University (2003).
This research investigates how to create a modeling tool specifically for stochastic programming problems with recourse. By taking advantage of the special structure these problems have, we produce a modeling language whose syntax is less redundant, more modular, and more expressive than the notation commonly associated with stochastic programming. We then implement a system that can convert models written using this syntax to instances that can be solved using standard mechanisms. With this approach, we are able to represent models in a very clean, simple, and scalable format.
E.D. Dolan, R. Fourer, J.-P. Goux and T.S. Munson, Kestrel: An Interface from Modeling Systems to the NEOS Server. Technical report, Department of Industrial Engineering and Management Sciences, Northwestern University (2002).
The NEOS Server provides access via the Internet to a broad variety of optimization software packages. Kestrel, a new interface to the NEOS Server, extends the Serverís usefulness by permitting local programs rather than human modelers to request optimization services and retrieve results. As a result, a locally running modeling system can have much the same access to remote NEOS solvers as to solvers installed locally; modelers can consider a wider variety of solvers, problems may be solved more effectively, and new solver technologies may be disseminated more rapidly.
Kestrel client programs have been implemented to support NEOS requests from locally executing instances of the AMPL and GAMS modeling environments. Extensions to the client designs enable them to queue subproblems for execution and later retrieval of results, making possible a limited form of parallel processing in some circumstances. The creation of the Kestrel interface has also led the NEOS Server to be enhanced with more flexible features for submitting binary files and for tracking progress via the Web.
R. Fourer and D.M. Gay, Numerical Issues and Influences in the Design of Algebraic Modeling Languages for Optimization. Proceedings of the 20th Biennial Conference on Numerical Analysis, Dundee, Scotland, D.F. Griffiths and G.A. Watson, eds., University of Dundee Numerical Analysis Report NA/217 (2003) 39-51.
R. Fourer and D.M. Gay, Extending an Algebraic Modeling Language to Support Constraint Programming. To appear in INFORMS Journal on Computing 14:4 (Fall 2002).
Although algebraic modeling languages are widely used in linear and nonlinear programming applications, their use for combinatorial or discrete optimization has largely been limited to developing integer linear programming models for solution by general-purpose branch-and-bound procedures. Yet much of a modeling language's underlying structure for expressing integer programs is equally useful for describing more general combinatorial optimization constructs.
Constraint programming solvers offer an alternative approach to solving combinatorial optimization problems, in which natural combinatorial constructs are addressed directly within the solution procedure. Hence the growing popularity of constraint programming motivates a variety of extensions to algebraic modeling languages for the purpose of describing combinatorial problems and conveying them to solvers.
We examine some of these language extensions along with the significant changes in solver interface design that they require. In particular, we describe how several useful combinatorial features have been added to the AMPL modeling language and how AMPL's general-purpose solver interface has been adapted accordingly. As an illustration of a solver connection, we provide examples from an AMPL driver for ILOG Solver.
R. Fourer and J.-P. Goux, Optimization as an Internet Resource. Interfaces 31:2 (March-April 2001) 130-150.
The rise of e-commerce promises particularly great benefits for the practice of large-scale optimization. The World Wide Web already offers information,advice,and remote access to software for solving optimization problems. A variety of client programs are helping to increase the scope and convenience of these tools. More sophisticated application service providers will further disseminate optimization-modeling environments and solvers, making their power and variety readily available to a broader range of customers and applications.
R. Fourer, OR Counterparts to AI Planning. In Constraints and AI Planning: Papers from the AAAI Workshop, Alexander Nareyek, ed., Technical Report WS-00-02 (AAAI Press, 2000) 1-6.
The term Planning is not used in Operations Research in the sense that is most common in Artifcial Intelligence. AI Planning does have many features in common with OR scheduling, sequencing, routing, and assignment problems, however. Current approaches to solving such problems can be broadly classified into four areas: Combinatorial Optimization, Integer Programming, Constraint Programming, and Local Search. These areas have developed somewhat independently; they have characteristic strengths and weaknesses, and have been commercially developed to varying degrees.
R. Fourer and D.M. Gay, Conveying Problem Structure from an Algebraic Modeling Language to Optimization Algorithms. In Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research, M. Laguna and J.L. González Velarde, eds. (Kluwer Academic Publishers, 2000) 75-89.
Optimization algorithms can exploit problem structures of various kinds, such as sparsity of derivatives, complementarity conditions, block structure, stochasticity, priorities for discrete variables, and information about piecewise- linear terms. Moreover, some algorithms deduce additional structural information that may help the modeler. We review and discuss some ways of conveying structure, with examples from our designs for the AMPL modeling language. We show in particular how "declared suffixes" provide a new and useful way to express structure and acquire solution information.
R. Fourer, Predictions for Web Technologies in Optimization.
Journal on Computing 10 (1998)
M.C. Ferris, R. Fourer and D.M. Gay, Expressing Complementarity Problems
in an Algebraic
Modeling Language and Communicating Them to Solvers. SIAM Journal on Optimization 9 (1999) 991-1009.
Diverse problems in optimization, engineering, and economics have natural formulations in terms of complementarity conditions, which state (in their simplest form) that either a certain nonnegative variable must be zero or a corresponding inequality must hold with equality, or both. A variety of algorithms have been devised for solving problems expressed in terms of complementarity conditions. It is thus attractive to consider extending algebraic modeling languages, which are widely used for sending ordinary equations and inequality constraints to solvers, so that they can express complementarity problems directly. We describe an extension to the AMPL modeling language that can express the most common complementarity conditions in a concise and flexible way, through the introduction of a single new "complements" operator. We present details of an efficient implementation that incorporates an augmented presolve phase to simplify complementarity problems, and that converts complementarity conditions to a canonical form convenient for solvers.
Robert Fourer, Extending a General-Purpose Algebraic Modeling Language
Optimization: A Logic Programming Approach. In D.L. Woodruff, ed., Advances in Computational and
Stochastic Optimization, Logic Programming, and Heuristic Search: Interfaces in Computer Science and Operations Research, Kluwer Academic Publishers, Dordrecht, The Netherlands (1998) 31-74.
Robert Fourer, Database Structures for Mathematical Programming Models. Decision Support Systems 20 (1997) 317-344.
In both the design and use of large-scale mathematical programming systems, a substantial portion of the effort has no direct relation to the variables and constraints, but is instead concerned with the description, manipulation and display of data. Established principles of database design do not apply directly to mathematical programming, however, because there are significant differences of organization and content between the data for an optimization model and the data for a conventional database application such as payroll or order entry.
This paper derives fundamental principles of database construction for large-scale mathematical programming, by use of a steel mill planning model as an example. Alternative formulations for the model -- which incorporate aspects of production and network linear programming -- are presented at the outset, and are shown to correspond to relational and hierarchical database schemes that have contrasting strengths and weaknesses. A particular implementation of the steel optimization package is then presented as an illustration. A concluding section puts this work into perspective, by surveying and categorizing a variety of approaches for providing data management features in mathematical programming applications. The views of data offered by this paper's approach are seen to differ substantially from the views offered by traditional mathematical programming systems, and certain ``intermediate'' strategies for integration of database and mathematical programming software are identified as having particular promise for future work.
J.J. Bisschop and Robert Fourer, New Constructs for the Description of Combinatorial Optimization Problems in Algebraic Modeling Languages. Computational Optimization and Applications 6 (1996) 83-116.
Algebraic languages are at the heart of many successful optimization modeling systems, yet they have been used with only limited success for combinatorial (or discrete) optimization. We show in this paper, through a series of examples, how an algebraic modeling language might be extended to help with a greater variety of combinatorial optimization problems. We consider specifically those problems that are readily expressed as the choice of a subset from a certain set of objects, rather than as the assignment of numerical values to variables. Since there is no practicable universal algorithm for problems of this kind, we explore a hybrid approach that employs a general-purpose subset enumeration scheme together with problem-specific directives to guide an efficient search.
Robert Fourer and David M. Gay, Expressing Special Structures in an Algebraic Modeling Language for Mathematical Programming. ORSA Journal on Computing 7 (1995) 166-190.
A knowledge of the presence of certain special structures can be advantageous in both the formulation and solution of linear programming problems. Thus it is desirable that linear programming software offer the option of specifying such structures explicitly. As a step in this direction, we describe extensions to an algebraic modeling language that encompass piecewise-linear, network and related structures. Our emphasis is on the modeling considerations that motivate these extensions, and on the design issues that arise in integrating these extensions with the general-purpose features of the language. We observe that our extensions sometimes make models faster to translate as well as to solve, and that they permit a "column-wise" formulation of the constraints as an alternative to the "row-wise" formulation most often associated with algebraic languages.
Robert Fourer, Notes on the Dual Simplex Method. Draft report (1994).
0. The standard dual simplex method.
1. A more general and practical dual simplex method.
2. Phase I for the dual simplex method.
3. Degeneracy in the dual simplex method.
4. A generalized ratio test for the dual simplex method.
Robert Fourer and David M. Gay and Brian W. Kernighan, A Modeling Language for Mathematical Programming. Management Science 36 (1990) 519-554.
Practical large-scale mathematical programming involves more than just the application of an algorithm to minimize or maximize an objective function. Before any optimizing routine can be invoked, considerable effort must be expended to formulate the underlying model and to generate the requisite computational data structures. AMPL is a new language designed to make these steps easier and less error-prone. AMPL closely resembles the symbolic algebraic notation that many modelers use to describe mathematical programs, yet it is regular and formal enough to be processed by a computer system; it is particularly notable for the generality of its syntax and for the variety of its indexing operations. We have implemented a translator that takes as input a linear AMPL model and associated data, and produces output suitable for standard linear programming optimizers. Both the language and the translator admit straightforward extensions to more general mathematical programs that incorporate nonlinear expressions or discrete variables.