Software Review
Xpress-MP 2005A
Mathematical modeling and optimization suite
serves many needs.
By Hernan Wurgaft
The new release 2005A of Xpress-MP adds a number of enhancements to an already impressive suite of optimization and modeling software. Since its inception, Xpress-MP has distinguished itself for fulfilling the efficient implementation of algorithms to solve linear and mixed integer programming (MIP) problems. Every new release has continued to expand the state-of-the-art for mathematical programming commercial solvers. The solvers implemented in the Xpress-Optimizer — a central component of the Xpress-MP suite — benefit from many search-accelerating techniques like presolve algorithms, use of global variables, advanced cutting planes strategies, heuristics, and customizable node and variable selection strategies. The latest release has speed improvements to the algorithms, and it also has added parallel MIP for multi-processing machines. Experience with time-critical applications, with large-scale linear programs and with tough integer problems has earned Xpress-Optimizer a reputation among practitioners and academicians for being second to none in terms of speed and reliability.
In addition to the Xpress-Optimizer, the Xpress-MP suite contains an innovative modeling tool in the form of the Xpress-Mosel component. Mosel is conceived as a programming environment for both modeling and solving optimization problems. As such, the Mosel language is at the same time an algebraic modeling language and also a true high-level programming language. This is in contrast with other algebraic modeling languages like AMPL [Fourer et. al. (1993)] and OPL [Van Hentenryck (1998)], which rely on scripting to perform operations around the model specification.
In Mosel, it is normal to alternate modeling and solving statements to program specialized solution algorithms or any application that is centered in an optimization model. And because the architecture of Xpress-Mosel was designed to be open and modular, the syntax of the Mosel language can be naturally extended. Mosel has a native interface that is defined as public, allowing anyone to enrich the functionality of the language by creating new modules. For example, calls to external functions and procedures of existing specialized solvers and other programs can be turned into simple Mosel statements. This characteristic makes Xpress-Mosel an exciting and virtually limitless environment for optimization-centered applications.
Mosel models are typically developed within the graphical user interface Xpress-IVE. This visual environment has many facilities for model debugging, solution analysis and solution display that bolster the productivity of the development effort. Once a Mosel model has been built and tested in Xpress-IVE, it may be accessed and executed from other applications through Mosel libraries. The latest release of Xpress-MP adds a .NET library to the existing C/C++, Java, and VB libraries. The Mosel libraries provide a simple and efficient device for an organization to integrate sophisticated optimization models with the rest of its information systems.
The Mosel Language
Coding in Mosel is straightforward enough if you have some experience with other high-level programming languages. The statements that specify a model's variables and constraints closely resemble the usual notation to describe optimization models.The accompanying lines (see box) provide an example of Mosel code.
|
The Mosel code defines and solves a capacitated facility location model where the demand in a set of DemandCities must be satisfied from facilities to be located in a set of candidate SupplyCities, while minimizing the sum of transportation costs and the fixed costs associated with open facilities. The statement uses "mmxprs" specifies that the functionality from the module Xpress-Optimizer is used in this code. The declarations block defines the objects in the model. The sets with the cities are declared as constant sets of string as they are populated with string data. The cost, capacity and demand data structures are declared as integer arrays indexed with the sets of cities. The shipped quantities (x) and the decision whether to open a facility at a candidate location (y) are arrays of type mpvar, a specialized type to define mathematical programming variables. The initializations block indicates that the problem data is read from an external file. Following the initialization block, there are a number of statements that define the problem constraints. There are comments (lines that begin with exclamation point !) describing each type of constraint. The minimize statement calls on the optimizer to solve the problem. Finally, some aspects of the solution are written to the standard output.
Of course, Mosel's data structures and data handling capabilities are a lot more powerful than what is presented in the example. Usually, problem domain sets are declared as dynamic sets that are re-sized automatically as they are populated with elements from external data sources. Mosel offers great versatility to perform input/output operations with external data sources such as databases and spreadsheets. A number of drivers that allow using standard input/output statements with various sources are part of the Mosel distribution. Also, user-defined drivers can be generated as customized Mosel modules.
Mosel's language structures for program flow control include "if "selections, loops, procedures and functions. For example, the following block of code has a loop over the set of SupplyCities, and it calls the procedure SolveAndReport:
| forall (j in SupplyCities) do | ||
| FORCED := y(j)=1 writeln(j, " is forced in") SolveAndReport |
||
| end-do |
The block of code illustrates how modeling and processing statements are interlaced in Mosel. A constraint named FORCED is repeatedly redefined to study the effect of individually forcing each candidate facility to be open. The procedure SolveAndReport groups the minimize and reporting statements from the original example.
The Graphical User Interface
Figure 1 shows a view of the Capacitated Location Problem example in the Xpress-IVE. The center panel is the editor window for the Mosel code, and it features color highlighting of the language syntax, mouse-over-information on identifiers and auto-complete when typing. The left panel is the Project Bar that shows the entity tree that gets populated with the model identifiers after a successful compilation. The value of the identifiers can be displayed on tooltips or view dialogs after the problem is solved. The right panel is the Run Bar, and it contains a number of tabs that display output from Mosel and the Optimizer. The view in Figure 1 shows the text output from Mosel generated by the procedure SolveAndReport in the example. Some of the other Run Bar tabs display the optimization statistics, different views of the matrix to be optimized (see Figure 2), the progress of the optimization and the MIP search, a tree representation of the branch-and-bound search (see Figure 3), and user-defined graphs built with the functionality of the mmive module.
Figure 1: Xpress-IVE.
Figure 2: Matrix representation.
Figure 3: Branch and Bound Tree representation.
The Xpress-IVE has a number of wizards to assist in the process of developing a model. Each wizard addresses a specific task typically required by a model, like the definition of Data Input, Variables, Objectives and Constraints, and special tasks like Text Output and Graphing. Wizards are based on mouse selection options that interactively generate Mosel source code. Figure 4 shows the wizard dialog and the selections for the programming and the Xpress-Optimizer callback wizards. The programming wizard produces the syntax of the different Mosel programming structures on the preview editor. The Xpress-Optimizer callback wizard produces the syntax to write Mosel procedures that are executed every time the optimizer encounters certain events. For example, a Mosel procedure could be called every time an integer solution is found during a branch-and-bound search.
Figure 4: Wizard Dialog with Programming and Optimizer Callback wizard.
Bundled with the wizards, there is a collection of complete sample models that are organized according to the level of difficulty in terms of the use of Mosel and Xpress-Optimizer features. The sample models are generally well-documented, and further information about most of them is available in the book "Applications of Optimization with Xpress-MP" (see Heipcke 2002). The book, which can be downloaded for free from www.dashoptimization.com, contains many more sample models and an impressive range of applications implemented in Mosel. The wizards and sample models are an excellent tool to get exposed and to learn both the basics and the more advanced features of Xpress-MP.
I find the experience to develop a Mosel model using Xpress-IVE to be productive and rewarding. The user interface is well designed to perform the basic operations of editing the code, compiling and running the model, and analyzing the results. The dialogs are intuitive and self-explained, and they encourage the user to directly experiment with options and features without having to resort to help documents. Compilation and logical errors get quickly resolved. The many ways to retrieve information about model entities and data, a state-of-the-art Mosel debugger in the latest Xpress-MP release, and the different available views of the problem matrix are particularly useful tools to produce correct results. A tool to monitor and improve the efficiency of the code, in the form of a profiler that calculates how long it takes to execute each line of code, is also available with the latest release.
The Basics and Beyond
At a basic level Mosel provides an environment where it is simple to define and solve mathematical programming models. In my classroom experience with an introductory O.R. course, students felt comfortable when I presented Mosel models and the Xpress-IVE. There is value in working with a tool that offers more modeling flexibility than the spreadsheets typically used in O.R. courses. There is also great value in the facilities to visualize the solutions and the behavior of the algorithms.
Mosel also provides an environment where it is natural to accomplish advanced tasks. Although the Xpress-IVE and much of the documentation is targeted for using Xpress-Optimizer as the solver, the Mosel language itself does not have a default solver, and the procedures from different solvers can be invoked when they are made available as Mosel modules. The Xpress-Optimizer includes the simplex, barrier and MIP algorithms, as well as algorithms for quadratic and mixed integer quadratic problems often arising in financial applications. Another module from the Xpress-MP developers, Xpress-SLP, is a solver for non-linear and mixed integer non-linear problems based on the technique of successive linear approximations usually applied to problems in the process industries. Finally, Xpress-CP is a module containing constraint programming (CP) functionality, which is a solution approach for problems with general constraint relations over discrete variables. Constraint programming has a broad range of applications in scheduling and planning. The Xpress-CP module uses the CHIP engine developed by COSYTEC SA (see www.cosytec.com). The Mosel language has been extended to use high-level objects to define CP problems. Also, by formulating and solving CP problems in the Mosel, it is possible to customize search strategies, and to combine the problem-solving strengths of CP and LP/MIP.
The Mosel language has also been extended to formulate and solve stochastic programming problems. Many decision problems involving uncertainty achieve better solutions when modeled as a stochastic program. Xpress-SP provides stochastic data types, such as random decision variables that take different values in different scenarios, and tools to build scenario trees. These language extensions significantly simplify the traditionally cumbersome process of defining a stochastic programming problem. Xpress-SP is also integrated with the Xpress-IVE providing visualization tools to analyze and debug the stochastic model and to interpret the results. There are many applications of stochastic programming, especially in energy, finance and transportation.
A new Mosel language extension available with the Xpress-MP 2005A is the Xpress-Application Developer (XAD). This module contains functions and procedures to build graphical user interfaces in Mosel. Figure 5 shows an example of a facility location GUI developed with the Xpress-Application Developer. The exciting possibility to develop applications that combine modeling, optimization, and user-interface functions within a single environment is now a reality with Xpress-MP.
Figure5: Facility location GUI built with XAD Mosel Module.
Availability, Cost and Installation
Xpress-MP 2005A is available from Dash Optimization (www.dashoptimization.com). Xpress-MP components are available off-the-shelf on multiple Windows and Unix platforms, except for Xpress-IVE that is only available on Windows 32 platforms. Licenses may be either computer specific or dongle specific.
The process of installing the software and configuring a computer-specific license on my Windows XP machine went smoothly, and it only took a few minutes.
The price of a basic Xpress-Mosel/Xpress-Optimizer commercial license starts at about $5,000, and it goes up from there depending on the features used and problem size. Free evaluation licenses with full functionality are available for a limited evaluation time period. Free licenses with full functionality but limited by the size of the problem that can be solved are available for students. Students may solve bigger size problems by submitting them to the NEOS server for optimization (see www-neos.mcs.anl.gov/neos/), subject to prior authorization and availability. The Xpress-IVE has a dialog to facilitate the process of submitting problems to the NEOS server. For academicians, there is an attractive academic partnership program that provides a full version of Xpress-MP at no cost subject to satisfying certain conditions consisting of using the software for teaching and doing research.
Conclusion
Xpress-MP is a world-class software suite for mathematical programming modeling and optimization. Mosel is an innovative modeling environment that has the potential of becoming the standard tool to develop optimization-centric applications. Mosel's simplicity and elegance is appropriate for students and users who are just being introduced to mathematical programming. At the same time, Xpress-MP's efficiency and robustness is appropriate for the development and deployment of industrial-strength applications. Finally, Mosel's open architecture is appropriate for researchers and academicians who wish to advance the field of optimization. I strongly recommend Xpress-MP for anyone seriously interested in optimization.
|
|
Hernan Wurgaft, Ph.D., (hwurgaft@sunymaritime.edu) is an assistant professor at the State University of New York Maritime College.
References
- Fourer R. , D. Gay, and B. W. Kernighan, 1993, "AMPL: A Modeling Language for Mathematical Programming," The Scientific Press, San Francisco, Calif.
- Heipcke S., 2002, "Applications of Optimization with Xpress-MP," Dash Optimization, Blisworth, U.K..
- Van Hentenryck, P., 1998, "The OPL Optimization Programming Language," MIT Press, Cambridge, Mass.
OR/MS Today copyright © 2005 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Lionheart Publishing, Inc.
506 Roswell Rd., Suite 220, Marietta, GA 30060 USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com
Web Site © Copyright 2005 by Lionheart Publishing, Inc. All rights reserved.