Presentations


Robert Fourer
Dept. of Industrial Engineering & Management Sciences
Northwestern University
2145 Sheridan Road
Evanston, IL 60208-3119, U.S.A.

847/491-3151 (voice)
847/467-1828, 847/491-8005 (fax)

4er@iems.northwestern.edu


R. Fourer, J. Moré, T. Munson, and J. Sarich, New Developments in the Design and Operation of the NEOS Server. Session TB31, APMOD 2004, Brunel University, London, June 22, 2004.

Enhancements to the NEOS Server are making optimization methods available over the Internet to an increasingly large audience. New utilities assist users in problem analysis and solver selection, and perform benchmark tests automatically. Submissions can be made from a growing variety of modeling environments to an increasingly varied lineup of general and specialized solvers. We survey these developments as well as others currently underway.

    2-page vertical, in: PDF (1011K)
    4-page horizontal, in: PDF (627K)

R. Fourer, Assigning People in Practice. Session WC02, CORS/INFORMS Joint International Meeting, Banff, May 16-19, 2004.

Chances are you've been stuck at least once with a problem of assigning people to something -- offices, projects, tables, whatever. The venerable idea of an "assignment problem" can be useful in these circumstances, if applied with care. This presentation describes several applications of assignment problems to real people, along with some rules for success suggested by these experiences.

    1-page horizontal, in: PDF (197K)

D. Orban and R. Fourer, DrAMPL: A Meta-Solver for Optimization. Session TD02, CORS/INFORMS Joint International Meeting, May 16-19, 2004.

Building upon the AMPL interface library, DrAmpl is a meta-solver for obtaining statistics on an optimization problem, for symbolically proving or numerically disproving convexity of the functions involved, and for suggesting appropriate solvers. Problem characteristics are matched with solvers available on the NEOS Server, by use of a relational database. In this presentation, we describe the design of DrAmpl along with the needs that it meets and the perspectives that it offers.

    1-page horizontal, in: PDF (1772K)

R. Fourer, Languages and Servers for Optimization Support. Track 14, INFORMS Conference on OR/MS Practice, Cambridge, MA, April 26-27, 2004.

The race to build faster “solvers” may generate the most excitement in large-scale optimization, but the full potential of algorithmic software has required corresponding breakthroughs in software for the support of optimization modeling. Optimization support systems encompass:

  • Modeling languages and systems that substitute natural, high-level interfaces for the low-level data input required by solvers; and
  • Optimization servers that provide network access to a much broader variety of solvers than are likely to be installed locally.
This survey will elucidate essential features, recent advances and likely future improvements to such systems, along with guidelines for successfully choosing among them.

R. Fourer, Cyberinfrastructure — The NEOS Server. Sector Context for CI Investment Strategies for Research and Education, Workshop convened by the Directorate for Engineering, National Science Foundation, Washington, January 14, 2004.


R. Fourer and D.M. Gay, Numerical Issues and Influences in the Design of Algebraic Modeling Languages for Optimization. 20th Biennial Conference on Numerical Analysis, Dundee, Scotland, June 24-27, 2003.

The idea of a modeling language is to describe mathematical problems in a symbolic form that is familiar to people, but that can be processed by computer systems. In particular the concept of an algebraic modeling language, based on objective and constraint expressions in terms of decision variables, has proved to be valuable for a broad range of optimization and related problems.

One modeling language can work with numerous solvers, each of which implements one or more optimization algorithms. The separation of model specification from solver execution is thus a key tenet of modeling language design. Nevertheless, several issues in numerical analysis that are critical to solvers are also important in implementations of modeling languages. So-called presolve procedures, which tighten bounds with the aim of eliminating some variables and constraints, are numerical algorithms that require carefully chosen tolerances and can benefit from directed roundings. Correctly rounded binary-decimal conversion is valuable in portably conveying problem instances and in debugging. Further rounding options offer tradeoffs between accuracy, convenience, and readability in displaying numerical data.

Modeling languages can also strongly influence the development of solvers. Most notably, for smooth nonlinear optimization, the ability to provide numerically computed, exact first and second derivatives has made modeling languages a valuable tool in solver development. The generality of modeling languages has also encouraged the development of more general solvers, such as for optimization problems with equilibrium constraints.

This presentation draws from our experience in developing the AMPL modeling language to provide examples in all of the above areas. We conclude by describing possibilities for future work that would have a significant numerical aspect.

    1-page horizontal, in: PDF (685K)
    2-page vertical, in: PDF (368K)

R. Fourer, AMPL "Hands-On" Session, Institute for Mathematics and Its Applications, Optimization Year, Supply Chain and Logistics Optimization Tutorial, September 9-13, 2002.

Modeling languages describe optimization problems to computer systems in the symbolic terms familiar to people, rather than in the obscure input forms convenient to optimizing algorithms. In typical use, a symbolic model and specific data are automatically translated to a problem instance and submitted a solver; subsequent results are automatically retrieved and translated back to forms convenient for inspection and analysis. A single modeling language can be interfaced to many solvers, providing access to techniques for a range of linear, nonlinear, and discrete problems, and encouraging comparisons between alternative algorithms for individual problem types.

This session will provide an introduction to AMPL, one of the more widely used optimization modeling languages, through a series of simple linear and integer programming models. Participants will have a chance to experiment with AMPL models and to ask how a modeling language might be applied to problems of special interest to them.

    1-page horizontal, in: PDF (430K)
    2-page vertical, in: PDF (322K)

R. Fourer, E.D. Dolan, J.J. Moré and T.S. Munson, Interactions between Modeling Languages and Internet Optimization Services: An Introduction to Kestrel.  APMOD 2000, Varenna, Italy, June 19, 2002.

Modeling languages are a key factor in the popularity of online optimization servers, particularly for experimentation, benchmarking, and prototyping.  Conversely, the availability of solver services via the Internet may be starting to have an effect on how modeling languages and their supporting environments are designed and implemented.  Using our experience with the NEOS Server as an example, we describe a number of current interactions between modeling languages and Internet optimization services, and make some predictions concerning future developments.

    1-page horizontal, in: PDF (1394K)
    2-page vertical, in: PDF (557K)

R. Fourer, Constraint Programming for Math Programmers, Session TC11, INFORMS International Meeting, Maui, June 19, 2001.

The commercial development of constraint logic programming (CLP) methods is changing the way that people approach optimization modeling, especially for highly combinatorial problems. This survey addresses the implications of CLP from the standpoint of potential users whose backgrounds are in OR and whose experience is with conventional mathematical programming systems.

    1-page horizontal, in: PDF (617K)
    2-page vertical, in: PDF (598K)

R. Fourer and D.M. Gay, Hooking Nontraditional Solvers to an Algebraic Modeling Language, Session SA30.3, INFORMS Annual Meeting, San Antonio, November 5, 2000.

New optimization techniques are forcing algebraic modeling languages to adopt new approaches in communicating problems to solvers. Global optimization and constraint programming solvers may need to see explicit expression trees, while accepting diverse nonsmooth and combinatorial expression forms. We take examples from several solver interfaces to the AMPL modeling language.

    1-page horizontal, in: PDF (168K)
    2-page vertical, in: PDF (151K)

R. Fourer, Optimization as an Internet Resource, Isolated Practitioners Workshop, INFORMS National Meeting, Salt Lake City, May 8, 2000; Plenary Presentation, APMOD 2000, Brunel University, London, April 17, 2000.

Few users of optimization techniques have more than a handful of solver packages installed on computers they use regularly. Recent advances in network interfaces are beginning to encourage experimentation with a greater variety of solvers. This presentation surveys current Internet optimization interfaces and suggests priorities for making them more effective. Examples will include the new @NEOS optimization server under development in collaboration with Argonne National Laboratory.


R. Fourer, Relational Database Access for an Algebraic Modeling Language, Invited Presentation, APMOD 2000, Brunel University, London, April 18, 2000.

The description of data in algebraic modeling languages is well known to have useful parallels to the organization of data in relational databases. We describe new features of the AMPL modeling language that take advantage of these parallels to facilitate exchanges of information between optimization models and database files. Our emphasis is on features that differ from those of existing modeling language database links. A system of modular "handlers" enables vendors or developers to add database connections without modifying the core AMPL code. Various input and output modes provide flexibility in how data representations are converted between AMPL and relational tables.


R. Fourer, Optimization as an Internet Resource, Session TD20.4, INFORMS National Meeting, Philadelphia, November 9, 1999.

Few users of optimization techniques have more than a handful of solver packages installed on computers they use regularly. Recent advances in network interfaces are beginning to encourage experimentation with a greater variety of solvers. This presentation surveys current Internet optimization interfaces and suggests priorities for making them more effective.


R. Fourer and D.M. Gay, Designing an Open Interface for Hooking Constraint Logic Programming Solvers to an Algebraic Modeling Language, Session TE30.2, INFORMS National Meeting, Philadelphia, November 9, 1999. Earlier version in Session CLP5, OR41: Conference of the Operational Research Society, Edinburgh, Scotland, September 16, 1999.

Combinatorial modeling language extensions motivated by constraint logic programming methods are valuable to modelers, but introduce new difficulties in maintaining an open interface that can accommodate a variety of current and future solvers. We describe several representation and recognition issues that arise in extending the interface of the AMPL language.


R. Fourer and D.M. Gay, New Developments in the AMPL Modeling System for Mathematical Programming, Session MOB24.2, IFORS Triennial Meeting, Beijing, August 16, 1999.

Modeling systems for optimization can be enhanced by extending the design of their input (a modeling language) or of their output (a problem representation for solvers). Often, extensions to both are required. We discuss a variety of extensions and their interactions, with examples from recent and forthcoming features in AMPL.


R. Fourer, New Complementarity Features from Advanced AMPL Tutorial, INFORMS National Meeting, Cincinnati, May 2, 1999.

R. Fourer, New Standard Database Features from Advanced AMPL Tutorial, INFORMS National Meeting, Cincinnati, May 2, 1999.

R. Fourer and D.M. Gay, New Directions in Algebraic Modeling Languages, Session MC04.3,
INFORMS National Meeting, Seattle, October 26, 1998.

Modeling systems for optimization can be enhanced by extending the design of their input (a modeling language) or of their output (a problem representation for solvers).  Often, extensions to both are required. We discuss a variety of extensions and their interactions, with examples from recent and forthcoming features in AMPL.


R. Fourer, Recent Developments in Mathematical Programming Modeling Systems, OR40: Conference of
the Operational Research Society, Lancaster, England, September 8, 1998.

Although modeling systems for optimization are by now well established, they continue to admit significant improvements.  In general terms, enhancements to these systems may be accomplished by extending the design of their input (a modeling language) or of their output (a problem representation for solvers); often, extensions to both are necessary to achieve a desired result.  This presentation will survey a variety of extensions, for such purposes as expressing complementarity conditions, linking to databases, manipulating solver statuses and analyses, and providing remote access to model translators and solvers.  Prospective extensions for better supporting stochastic programming and combinatorial optimization will also be touched upon.


R. Fourer, Optimization Approaches to Production Planning in the Steel Industry,  Association of Iron
and Steel Engineers Specialty Conference, Advanced Technologies in Modeling, Scheduling and
Control, M.I.T., Cambridge, Massachusetts, July 22, 1998.

Planning is the longer-term counterpart of scheduling in managing a steelmaking operation. After brief remarks on the desirability of optimization in planning generally, this presentation surveys current technologies for building and maintaining planning optimization models. The fundamental characteristics of steelmaking are shown to be well suited to the creation of a generic model, which is in turn readily specialized to particular situations. The practical limits of size and complexity in such a model have increased substantially in recent years, due to the interaction of faster computers with improved algorithmic technology and more advanced optimization languages and environments. As a result, it has become sensible to consider the use of general- purpose prototyping tools in steel planning applications, as a complement to custom-developed optimization software. Examples of both approaches will be described and contrasted.


R. Fourer, On-Line Optimization Services, from Panel on The OR/MS-WWW Interface, Session TC03, INFORMS Israel International Meeting, Tel Aviv, June 30, 1998.


R. Fourer, C.R. Coullard and J.H. Owen, General-Purpose Algorithms & Systems for Combinatorial Optimization,  Session MA14, INFORMS International Meeting, Tel Aviv, June 29, 1998.

General-purpose modeling systems have had little impact on combinatorial optimization outside of integer programming, but recent developments in logic programming algorithms and object-oriented system design are changing this situation. We describe two approaches from our current research, one employing an algebraic modeling language and the other a 'toolkit' for network optimization.


R. Fourer, Tutorial: Software for Linear and Integer Programming, Session TC19, CORS/INFORMS Meeting, Montreal, April 28, 1998.

Having grown in variety and sophistication over the past decade, LP software is now available in a profusion of formats and packages. This presentation surveys current software for formulating, solving, analyzing and managing LPs, with or without integer variables. Recent trends in language, interface and algorithm design are emphasized.


R. Fourer and D.M. Gay, Updating the AMPL/Solver Interface, Session TD1.2, APMOD '98, Limassol, Cyprus, March 12, 1998.

AMPL is both a declarative modeling language and an imperative modeling environment for stating and manipulating mathematical programming problems.  Instead of trying to solve these problems itself, AMPL invokes separate solvers.  We have lately been working to enhance the AMPL/solver interface, with the goals of making it easier to use and making more information available, such as Hessian (2nd derivative) information for nonlinear problems.  This talk gives an overview of the evolving AMPL/solver interface and the thinking behind it, illustrated in part by recent extensions to more conveniently handle complementarity problems.  Extensions for exchanging various other kinds of solver directive and solution analysis information will also be discussed.


R. Fourer, General-Purpose Modeling Languages for Combinatorial Optimization, Session WC1.1, APMOD '98, Limassol, Cyprus, March 11, 1998.

General-purpose modeling languages are widely used to formulate and solve broad classes of optimization problems, particularly linear programs and smooth nonlinear programs.  These languages could be made much more useful for combinatorial optimization, however, through a variety of extensions such as conditional and counting operators, variables in subscripts, and object-valued or set-valued variables.

One major obstacle to such extensions has been a lack of general-purpose solvers to deal with them.  In some cases, established branch-and-bound codes can find solutions efficiently by relying on conversion to an integer program.  But often the most appropriate solvers are ones that operate more directly on the combinatorial formulation, employing methods that have their roots in logic programming.

These observations are illustrated using the AMPL modeling language and ILOG's C++ solver class library, with emphasis on recent progress in implementation.


R. Fourer, Implications of Constraint Logic Programming for the Design of Mathematical Programming Systems, Tutorial TC3, INFORMS CSTS Conference, Monterey, CA, January 8, 1998.

The commercial development of constraint logic programming methods is changing the way that people approach optimization modeling.  This survey addresses the implications of CLP from the standpoint of potential users whose backgrounds are in operations research and whose experience is with conventional mathematical programming systems.

CLP methods are likely to have their greatest effect on the facilities that general-purpose mathematical programming systems provide for discrete or combinatorial optimization.  These systems' support for combinatorial problems have traditionally begun and ended with integer programming formulations and branch-and-bound methods. CLP embodies alternative forms of tree search that can be applied directly to a much broader variety of constraint forms, freeing the modeler from conversions to integer programming and speeding the search in a significant number of cases.

To take advantage of CLP methods, existing modeling languages and other front ends to optimization will have to be extended to deal with a richer and more natural variety of formulations.  Prospective extensions, to be illustrated by examples, include a variety of logical and counting operators, an "all different" operator, "subscripting" by variables, and variables that take nonnumerical or subset values.

Other topics touched upon include hybrids of branch-and-bound with CLP-style tree search, and applications to global optimization for nonlinear functions.


R. Fourer, and D.M. Gay, Analysis Support in a Modeling Language for Mathematical Programming,
Session WB1, INFORMS CSTS Conference, Monterey, CA, January 7, 1998.

Modeling languages let people describe optimization problems in a natural form that is nonetheless readable by a computer system.  Most such languages provide expressions for a variety of values generated by the optimization process, such as variables' reduced costs and bounds, and constraints' shadow prices and slacks.  These expressions are built into the languages, however, and as a result they often prove to be insufficient -- both in number and in flexibility -- to report all of the useful information that solvers generate as a result of optimization.

We describe an approach to this situation that allows the user or solver to define any number of new entities associated with each variable, constraint or other model component.  We refer to these new
entities as "suffixes" since they are typically represented by appending a short tag to a component's name.  Each suffix permits reference to a different piece of information about the solution, such
as might be produced by sensitivity or infeasibility analysis; different solvers are free to employ different collections of suffixes as appropriate to the analyses they perform.  The suffix mechanism also
proves useful for conveying information such as integer variable priorities to solvers, and for exchanging information such as basis statuses.

We illustrate these ideas with examples from their implementation in the AMPL modeling language.


R. Fourer and D.M. Gay, Proposals for Stochastic Programming in the AMPL Modeling Language, Session WE4-G-IN11, International Symposium on Mathematical Programming, Lausanne, August 27, 1997.

The AMPL modeling language was originally designed for expressing deterministic mathematical programming problems.  It could, of course, express explicit deterministic equivalents of some stochastic programming problems, but this is only practical for problems involving a relatively small number of scenarios, and even then the expression could be somewhat clumsy.  We are working on several ways to make expressing at least some stochastic programming problems more convenient.  One is the introduction of named scenarios, a facility that should also be convenient in other contexts.  Another is a "stochastic" declaration for expressing the time/stage structure of recourse problems.  A third way extends the existing mechanism for handling nonlinearities to permit expressing both dependent and independent random variables.


R. Fourer, Uses of the AMPL Modeling Language in Solving "Balanced" Assignment Problems, Session TC24.3, EURO/INFORMS International Meeting, Barcelona, July 15, 1997.

A common but little-known application of mathematical programming involves dividing people into groups that are "as similar as possible" in composition, subject to restrictions that prevent any individual from being too "isolated" in specific ways. This kind of "balanced" assignment problem can be difficult to formulate and to solve, and its difficulty is often compounded by tight deadlines. Under such circumstances, an algebraic modeling language is especially valuable for permitting varied formulations and solution strategies to be tried out quickly.  These observations are illustrated by examples of the AMPL language's use in forming balanced groups of meeting participants.


Updated June 29, 2001