Problem-Solving with Xpress-MP
Overview
A wide range of routines are available for interacting with the Xpress‑Optimizer, providing a handle on its core functionality through Console Mode commands, or more extensive access to its internal data structures through the Advanced Mode routines. Whilst the users of the Xpress‑Optimizer are diverse and the range of problems studied by them is wide, most optimization tasks adhere to a fairly standard template, providing a "natural grouping" of the routines. A discussion of this forms the subject matter for this chapter.
The general layout of an optimization process is given in Figure 2.1. Generally, a user goes through five main processes in solving a problem. The Optimizer must first be initialized, preparing it to handle a problem. The problem matrix is then read into memory before one of the optimization routines is called to solve it. The solution to the problem may be viewed and finally the user may exit the Optimizer. This structure may be more complex if the Optimizer's capability for handling multiple problems is used, but it serves to structure its commands.
Figure 2.1: Optimizing a Problem
Initialization and Termination
The Optimizer
The first stage in running the Optimizer is the initialization process. In Console Xpress, this process is run automatically, but for library users, the system must be initialized manually by calling XPRSinit before any of the other library routines. This command checks for any necessary libraries, and runs security checks to determine licence information about your Xpress‑MP installation. Only once this has completed can any of the other routines be run.
When all calls to the Optimizer routines have completed at the end of your session, the termination stage is entered. At this point, any memory used by the Optimizer is released for other processes and any files still open for reading or writing are closed. Again, this process is handled automatically for Console Xpress users when the QUIT or STOP command is given. Library users must call the routine XPRSfree to perform the equivalent tasks.
The Problem Environment
For library users, enjoying the benefits of a multiple problem environment, once the Optimizer has been initialized and before a problem matrix can be read in, a problem environment must be created using the XPRScreateprob routine. The user may create any number of these (license permitting) and may optimize, store and work on several such at any given time, referring to them by passing the problem pointer as the first argument to each subsequent function call. When an environment is no longer needed, it can be removed using XPRSdestroyprob. It is good practice to remove all such environments before calling XPRSfree.
Optimizer Output
For Console Xpress users, output is sent both directly to the screen and to a log file. Library users have greater flexibility with this. Using the command XPRSsetlogfile, a log file can be specified to catch output associated to a particular problem. Alternatively, an output callback function may be employed, defined by the XPRSsetcbmessage command, to catch any output and process it directly within the application. See Using the Callbacks for details.
Reading in a Problem
Once initialized, the Optimizer will accept a problem for optimization. Problems may be read into the Optimizer data structures in essentially two ways. The simplest of these is to read a matrix from an MPS or LP file using XPRSreadprob (READPROB), although library users can also load problems from their data structures using XPRSloadlp, XPRSloadqp, XPRSloadglobal, or XPRSloadqglobal. MPS names may then be added to the model using XPRSaddnames. Once the problem has been loaded, any subsequent call to one of these input routines will overwrite it.
It is important to note that for MIP problems presolve will take a copy of the matrix and modify it. The original matrix may be retrieved by calling XPRSpostsolve (POSTSOLVE). If the matrix is in the original state then XPRSpostsolve (POSTSOLVE)will return without doing anything.
Solving the Problem
Having loaded the problem, the user may (attempt to) find a solution to it.
The XPRSmaxim (MAXIM) and XPRSminim (MINIM) commands allow for maximization and minimization of LP, QP and mixed integer (MIP) problems, whilst the command XPRSglobal (GLOBAL) may be used to find the solution of MIP problems once the initial LP relaxation has been solved. Additionally, ranging may be performed using XPRSrange (RANGE).
A number of other possibilities are also available to users. The simplex LP optimization process may be accelerated by starting with an optimal basis from a previous, similar problem. Such bases may be saved and restored using the XPRSwritebasis (WRITEBASIS) and XPRSreadbasis (READBASIS) functions, or input from the user's own data structures using XPRSloadbasis. The user may additionally specify directives to influence the global search, which may be loaded from file using XPRSreaddirs (READDIRS). The format for the directives file is described in Log and File Formats. Other more advanced possibilities include the use of callback functions and customization of the cut manager, both of which are discussed in Implementing Algorithms.
Viewing the Solution
Once the optimization algorithms have completed, either a solution will be available, or else the problem will have been identified as infeasible or unbounded. In the latter case, the user may want to know why a problem has occurred and take steps to correct it. This is the subject matter for Optimality, Infeasibility and Unboundedness, following. In the former case, the user will probably want to consult the identified solution.
Xpress‑MP provides a number of functions for accessing details of a solved problem. Using either of XPRSwritesol (WRITESOL) or XPRSwriteprtsol (WRITEPRTSOL) a full solution may be obtained as an ASCII file. The first of these is suitable for interpretation by another application, whilst the second is primarily intended to be sent to a printer. Equivalent commands for obtaining range information are XPRSwriterange (WRITERANGE) and XPRSwriteprtrange (WRITEPRTRANGE).
Library users may also access the solution directly through their programs using XPRSgetlpsol, which will return the values of the decision variables, the slack variables, dual values and reduced costs for the current LP solution. The decision variables and slack variables for a MIP solution may be obtained with the XPRSgetmipsol function. In addition, the optimization algorithms provide extra details of a problem as it is solved by means of problem attributes. These are a set of objects which may be interrogated for particular information and transferred to user variables by type using the library functions XPRSgetintattrib, XPRSgetdblattrib and XPRSgetstrattrib. Examples of attributes include LPOBJVAL and MIPOBJVAL, which return the optimal values of the objective function for LP and (M)IP problems respectively. A full list of attributes may be found in Problem Attributes.
Optimization by Example
The above sections provide a brief introduction to the most common features of the Xpress‑Optimizer and its most general usage. Over the course of the following chapters, topics such as common problems and Optimizer performance will be considered, as well as some of the more advanced features of the Optimizer. The second part of the manual forms a reference for the various functions and their usage.
Examples of using the Optimizer are available from a number of sources, most notably from Xpress‑MP Getting Started manual. This provides a straight forward, "hands on" approach to the Xpress‑MP software suite and it is highly recommended that users read the relevant chapters before considering the reference manuals. Additional, more advanced, examples may be found on the Xpress‑MP CD-ROM.
Quick Reference
Initialization and Termination
| XPRSinit | Initialize the Optimizer. |
| XPRScreateprob | Create a problem environment. |
| XPRSsetlogfile | Direct all Optimizer output to a log file. |
| XPRSsetcbmessage | Define an output callback function. |
| XPRSdestroyprob | Destroy a problem environment. |
| XPRSfree | Release memory used by the Optimizer and close any open files. |
Reading In a Problem
| XPRSreadprob | Read in an MPS, LP, QP or binary interface format file. |
| XPRSloadlp | Load an LP problem into the Optimizer. |
| XPRSloadqp | Load a QP problem into the Optimizer. |
| XPRSloadglobal | Load a MIP problem into the Optimizer. |
| XPRSloadqglobal | Load a quadratic MIP problem into the Optimizer. |
| XPRSaddnames | Provide names for a range of rows or columns. |
Solving the Problem
| XPRSreadbasis | Read a basis from file. |
| XPRSloadbasis | Load a basis from a user's data structures. |
| XPRSreaddirs | Read a directives file. |
| XPRSmaxim | Maximize the problem's objective function. |
| XPRSminim | Minimize the problem's objective function. |
| XPRSglobal | Search for an integer solution. |
| XPRSrange | Calculate ranging information and save it to file. |
| XPRSgetbasis | Get the current basis into user arrays. |
| XPRSwritebasis | Write a basis to file. |
Viewing the Solution
| XPRSwritesol | Write the current solution to ASCII files. |
| XPRSwriteprtsol | Write the current solution in printable format to file. |
| XPRSwriterange | Write range information to ASCII files. |
| XPRSwriteprtrange | Write range information in printable format to file. |
| XPRSgetlpsol | Retrieve current LP solution values into users arrays. |
| XPRSgetmipsol | Retrieve last MIP solution values into users arrays. |
| XPRSgetintattrib | Recover the value of an integer problem attribute. |
| XPRSgetdblattrib | Recover the value of a double problem attribute. |
| XPRSgetstrattrib | Recover the value of a string problem attribute. |
If you have any comments or suggestions about these pages, please send mail to docs@dashoptimization.com.