[Next chapter]

Introduction


Overview

Part of the Xpress‑MP software suite, the Xpress‑Optimizer is an extremely versatile and powerful tool which is well-suited to a broad range of optimization problems. Accessible both directly via a Console or graphical interface, or by means of library functions, the Optimizer combines ease of use with speed and flexibility for the best results. A broad range of access routines and optimization algorithms, employing the best techniques available allows the user to tackle problems previously too large to solve within a reasonable time span. Either as a standalone program or handling tasks within users' own programs, the Xpress‑Optimizer opens a world of possibilities.

For users of Console Xpress, the 'Console Mode' encompasses a number of commands for using the Optimizer's core functionality. Models may be imported from either MPS or LP format files, optimized using any of the algorithms supported by the Optimizer and the solution viewed in a number of ways. Further control may be exerted over the optimization process by the setting of a number of controls which influence various aspects of the algorithms.

Users of the Xpress‑MP Optimizer library enjoy all the functionality of the Console Mode, with additional access to an 'Advanced Mode'. This extension of the interface provides users with access to the internal data structures of the Optimizer and greater matrix management. The inclusion of a Cut Manager allowing the addition of cutting planes provides users with the possibility of 'tailor-made' strategies for efficiently solving mixed integer problems in individual models.

The main benefit of the library, however, is the ability to embed all Optimizer calls within a user's own program, automating much of the above and providing the possibility of harnessing the power of the Xpress‑Optimizer within one's own applications. To this end the set of library functions are available for a number of common languages including C, Fortran, Java and Visual Basic. The convention employed throughout will be to give all descriptions in terms of the C structure, although differences and short examples for other languages may be found in the Xpress‑MP Getting Started manual.

The Xpress-Optimizer

The Xpress‑Optimizer is a Linear and Integer Programming optimizer which has been carefully programmed to take full advantage of matrix structure. The Integer Programming component has the ability to handle a variety of global entities, i.e. objects which must satisfy some nonlinear properties in an acceptable solution. We call such a solution an integer solution, although this nomenclature is not always strictly accurate.

The Optimizer can read in a problem in one of three ways:

It will then perform linear optimization by the primal or dual simplex method, or the Newton barrier method if licensed. The Optimizer may be instructed to go on to search for integer solutions. Ranging (sensitivity analysis) may also be performed. For interfacing with spreadsheets or database programs, ASCII representations of the solution may be produced.

The Optimizer may also save intermediate solutions in the form of basis files. If an optimal linear solution has been found to one problem and the status of the variables has been stored in a basis file, then the simplex LP solution path for a similar model may be shortened by starting the process from the same point, reading in the basis file just obtained.

Integer Programming Considerations

Though many systems can be modeled accurately as Linear Programs, there are situations where discreteness is central to the decision-making problem. It appears that there are three major areas where such nonlinear facilities are required:

Problems such as these can be modeled using any of Xpress‑Mosel, Xpress‑BCL or the Xpress‑Modeler. If enabled by your license, the Optimizer can then be used to find the global optimum. Usually the underlying structure is that of a Linear Program, but optimization may be used successfully when the nonlinearities are separable into functions of just a few variables.

The Xpress‑MP suite supports the following global entities:

Binary variables (BV) – decision variables that must take either the value 0 or the value 1, sometimes called 0/1 variables;

Integer variables (UI) – decision variables that must take on integer values. Some upper limit must be specified;

Partial integer variables (PI) – decision variables that must take integer values below a specified limit but can take any value above that limit;

Semi-continuous variables (SC) – decision variables that must take on either the value 0, or any value in a range whose lower an upper limits are specified. SCs help model situations where, if a variable is to be used at all, it has to be at some minimum level;

Semi-continuous integer variables (SI) – decision variables that must take either the value 0, or any integer value in a range whose lower and upper limits are specified;

Special ordered sets of type one (SOS1) – an ordered set of non-negative variables of which at most one can take a nonzero value;

Special ordered sets of type two (SOS2) – an ordered set of non-negative variables of which at most two can be nonzero, and if two are nonzero, they must be consecutive in their ordering.

The Optimizer employs a Branch and Bound search to locate and ensure optimality of a solution. It has a set of default strategies which have been found to work well on most problems. However, the user should note that sophistication in modeling is important in large scale MIP work. It has always been our experience that careful experimentation with realistic but small scale examples pays off when moving to large production versions of the models.

The special Integer Programming features of the Optimizer (except presolving) are used after solving the underlying Linear Programming problem to optimality. It is only following this that the nonlinearities and discreteness that have been specified in the input data are recognized. Examples of using the global search facilities of the Optimizer for the various interfaces may be found in Xpress‑MP Getting Started manual and it is assumed that you have read the relevant sections of that guide before using the reference manuals.

Running the Xpress-Optimizer

Initialization

To be able to run, the Optimizer requires a valid licence file, xpauth.ini. This may be configured for a specific machine, ethernet address or an authorized dongle. If the license file or dongle is missing, a message will be displayed describing the problem and the Optimizer will exit. Under Windows the Optimizer looks for the license file in the directory of the executables; under Unix the directory pointed to by the XPRESS environment variable is searched. Note that the license file should always be kept in the same directory as the Xpress‑MP DLL xprl.dll, which is installed by the default into the c:\XpressMP\bin folder.

Following this, the Optimizer will attempt to determine the problem name. If none is given, users of Console Xpress will be prompted for one and if this request is ignored a default problem name of $$$$$$$$ will be assumed. For problem names specified by the user, only the (optional) drive and path and the (required) filename are noted, any extension being ignored.

The problem name, problem_name, is used as a base for all files generated by the Optimizer, with separate files distinguished by different extensions. Matrix input files are problem_name.mat, problem_name.mps, problem_name.lp, problem_name.mat.gz, problem_name.mps.gz and problem_name.lp.gz where files with the .gz extension are compressed in gzip format.

Console Xpress Options

For Console Xpress users, the syntax for calling the Optimizer is as follows:

C:\> optimizer [problem_name] [@filename]

The problem name may optionally be specified on the command line when the Optimizer is invoked, but if omitted the problem name will be prompted for as described above. The optional second argument allows you to specify a text file from which the optimizer console input will be read ( as if they had been typed interactively ).

The Optimizer console is an interactive command line interface to the library. The features of the Optimizer console include improved online help, auto- completion of command names, and command prompt integration. Type "help commands" to get a list of available commands, and then try, e.g., "help minim" for help on a specific command. Some other useful commands are "help attributes", "help controls", or just "help".

To use the auto-completion feature, type the first part of an optimizer command name and press the tab key, for example "min<tab>" or "mat<tab>". Once you have finished typing the command name portion of your input line, the optimizer console will auto-complete file names. For example, if you have a matrix named hpw15, try "readprob h<tab>".

The console also provides convenient access to the operating system's shell commands. For example, try typing "dir" (or "ls" under Unix). You can also use the "cd" command to change the working directory, which will be indicated in the prompt:

[optimizer bin] cd \
[optimizer C:\]

When started, the Optimizer console will attempt to read in an initialization file called optimizer.ini located in the current working directory. This is an ASCII file which may contain any statements or commands which you wish to use by default in any run of the Optimizer. If the initialization file does not exist or cannot be found, the Optimizer will be initialized with its own built-in defaults.

The Optimizer console for 2006A onwards is implemented as a TCL shell. Users should be aware that it is possible therefore to type incorrect input which is interpreted as valid TCL syntax rather than as an error. Users of releases prior to 2006A should consult the release notes for a list of incompatibilities between old and new consoles.

Interrupting an Optimization Run in Console Xpress

Console Xpress users of the Optimizer may interrupt the processing of any command in a graceful way by typing CTRL-C, following which the Optimizer will return to its > prompt. If optimization has been interrupted in this way, any solution process will stop at the first 'safe' place before returning to the prompt. Iterations may be resumed at a later point by re-typing the interrupted command.

Note that if you have typed ahead, the CTRL-C mechanism may fail under some operating systems.

Termination

The Optimizer can terminate in one of three possible ways:

  1. normally, with no errors;
  2. with an error status indicating the solution status;
  3. immediately upon detection of a fatal error.

A normal termination means that the Optimizer has been terminated successfully, possibly with the QUIT or STOP command. The problem has not necessarily been solved to optimality since this will depend on the commands issued and whether any non-fatal errors occurred.

If Console Xpress users terminate the Optimizer with the STOP command, then a nonzero return code indicates the solution status of the problem. A complete list of these return codes is provided in Return Codes and Error Messages.

A fatal error stops the Optimizer immediately. Such errors usually arise from files being unavailable or disks being full, but may occur if available memory is exhausted.

Structure of this Manual

The main body of the manual is essentially organized into two parts. It begins in Problem-Solving with Xpress-MP with a brief overview of common Optimizer usage, introducing the various routines available and setting them in the context in which they are very often used. This is followed in Optimality, Infeasibility and Unboundedness with a brief overview of the sorts of problems which may arise during the optimization process and the kind of solution that might be expected from a problem. Performance Issues provides a description of some of the more-frequently used controls along with some ideas of how they may be used to enhance the solution process. Finally, Implementing Algorithms details some more advanced topics in Optimizer usage.

Following the first five chapters, the remainder forms the main reference section of the manual. Console and Library Functions details all functions in both the Console and Advanced Modes alphabetically. Control Parameters and Problem Attributes then provide a reference for the various controls and attributes, followed by a list of Optimizer error and return codes in Return Codes and Error Messages. A description of several of the file formats is provided in Log and File Formats.

Conventions Used

Throughout the manual standard typographic conventions have been used, representing computer code fragments with a fixed width font, whilst equations and equation variables appear in italic type. Where several possibilities exist for the library functions, those with C syntax have been used, and C style conventions have been used for structures such as arrays etc. Console Mode routines which have both a Console and library equivalent are usually described in both forms, with the Console command bracketed. In sections which are irrelevant for Console users, only the library form is given. For differences in syntax between the Console and Library versions of commands and controls, see the introduction to Console and Library Functions. Where appropriate, the following have also been employed:


[Next] [Index]
If you have any comments or suggestions about these pages, please send mail to docs@dashoptimization.com.