Introduction
Mathematical Programming
Mathematical Programming is a technique of mathematical optimization. Many real-world problems in such different areas as industrial production, transport, telecommunications, finance, or personnel planning may be cast into the form of a Mathematical Programming problem: a set of decision variables, constraints over these variables and an objective function to be maximized or minimized.
Mathematical Programming problems are usually classified according to the types of the decision variables, constraints, and the objective function.
A well-understood case for which efficient algorithms (Simplex, interior point) are known comprises Linear Programming (LP) problems. In this type of problem all constraints and the objective function are linear expressions of the decision variables, and the variables have continuous domains—i.e., they can take on any, usually non-negative, real values. Luckily, many application problems fit into this category. Problems with hundreds of thousands, or even millions of variables and constraints are routinely solved with commercial Mathematical Programming software like Xpress-Optimizer.
Researchers and practitioners working on LP quickly found that continuous variables are insufficient to represent decisions of a discrete nature (`yes'/`no' or 1,2,3,...). This observation lead to the development of Mixed Integer Programming (MIP) where constraints and objective function are linear just as in LP and variables may have either discrete or continuous domains. To solve this type of problems, LP techniques are coupled with an enumeration (known as Branch-and-Bound) of the feasible values of the discrete variables. Such enumerative methods may lead to a computational explosion, even for relatively small problem instances, so that it is not always realistic to solve MIP problems to optimality. However, in recent years, continuously increasing computer speed and even more importantly, significant algorithmic improvements (e.g. cutting plane techniques and specialized branching schemes) have made it possible to tackle ever larger problems, modeling ever more exactly the underlying real-world situations.
Another class of problems that is relatively well-handled are Quadratic Programming (QP) problems: these differ from LPs in that they have quadratic terms in the objective function (the constraints remain linear). The decision variables may be continuous or discrete, in the latter case we speak of Mixed Integer Quadratic Programming (MIQP) problems. In Chapters 7 and 12 of this book we show examples of both cases.
More difficult is the case of non-linear constraints or objective functions, Non-linear Programming (NLP) problems. Frequently heuristic or approximation methods are employed to find good (locally optimal) solutions. One method for solving problems of this type is Successive Linear Programming (SLP); such a solver forms part of the Xpress-MP suite. However, in this book we shall not enlarge on this topic.
Building a model, solving it and then implementing the `answers' is not generally a linear process. We often make mistakes in our modeling which are usually only detected by the optimization process, where we could get answers that were patently wrong (e.g. unbounded or infeasible) or that do not accord with our intuition. If this happens we are forced to reflect further about the model and go into an iterative process of model refinement, re-solution and further analyses of the optimum solution. During this process it is quite likely that we will add extra constraints, perhaps remove constraints that we were mislead into adding, correct erroneous data or even be forced to collect new data that we had previously not considered necessary.
Figure 2.1: Scheme of an optimization project
This books takes the reader through all these steps: from the textual description we develop a mathematical model which is then implemented and solved. Various improvements, additions and reformulations are suggested in the following chapters, including an introduction of the available means to support the analysis of the results. The deployment of a Mathematical Programming application typically includes its embedding into other applications to turn it into a part of a company's information system.
Xpress-MP product suite
Arising from different users' needs and preferences, there are several ways of working with the modeling and optimization tools that form the Xpress-MP product suite:
- High-level language: the Xpress-Mosel language
allows the user to define his models in a form that is close to algebraic notation and to solve them in the same environment.
Mosel's programming facilities also make it possible to implement solution algorithms directly in this high-level language.
Mosel may be used as a standalone program or through the Xpress-IVE development environment that provides, amongst many other tools, graphical displays of solution information.
Via the concept of modules the Mosel environment is entirely open to additions; modules provided by Dash include access to access to solvers (Xpress-Optimizer for LP, MIP, and QP, Xpress-SLP, Xpress-SP), data handling facilities (e.g. via ODBC) and access to system functions. In addition, via the Mosel Native Interface users may define their own modules to add new features to the Mosel language according to their needs (e.g. to implement problem-specific data handling, or connections to external solvers or solution algorithms). - Libraries for embedding: two different options are available for embedding mathematical models into large applications. A model developed using the Mosel
language may be executed and accessed from a programming language environment (e.g. C, C++, Java, etc.) through the Mosel libraries; certain modules also provide direct access to their functions from a programming language environment.
The second possibility consists of developing a model directly in a programming language with the help of the model builder library Xpress-BCL. BCL allows the user to formulate his models with objects (decision variables, constraints, index sets) similar to those of a dedicated modeling language.
All libraries are available for C, C++, Java, and Visual Basic (VB). - Direct access to solvers: on the lowest, most immediate level, it is possible to work directly with the Xpress-Optimizer or Xpress-SLP in the form of a library or a standalone program. This facility may be useful for embedding the Optimizer into
applications that possess their own, dedicated matrix generation routines.
Advanced Xpress users may wish to employ special features of the Optimizer that are not available through the different interfaces, possibly using a matrix that has previously been generated by Mosel or BCL.
Figure 2.2: Xpress-MP product suite
Of the three above mentioned approaches, a high-level language certainly provides the easiest-to-understand access to Mathematical Programming. So in the first and largest part of this book we show how to define and solve problems with the Xpress-Mosel language, and also how the resulting models may be embedded into applications using the Mosel libraries. We work with Mosel models in the graphical user interface Xpress-IVE, exploiting its facilities for debugging and solution analysis and display.
In the reminder of this book we show how to formulate and solve Mathematical Programming problems directly in a programming language environment. This may be done with modeling support from BCL or directly using the Xpress-Optimizer library. With BCL, models can be implemented in a form that is relatively close to their algebraic formulation and so are quite easy to understand and to maintain. We discuss BCL implementations of the same example problems as used with Mosel.
The last part of this book explains how problems may be input directly into the Optimizer, either in the form of matrices (possibly generated by another tool such as Mosel or BCL) that are read from file, or by specifying the problem matrix coefficient-wise directly in the application program. The facility of working directly with the Optimizer library is destinated at embedders and advanced Xpress-MP users. It is not recommendable as a starting point for the novice in Mathematical Programming.
Note on product versions
All examples in this book have been developed using the Xpress-MP Release 2007A (Mosel 2.0.0, IVE 1.17.2, BCL 3.0.1, Optimizer 17.0.2). If they are run with other product versions the output obtained may look different. In particular, improvements to the algorithms or modifications to the default settings in Xpress-Optimizer may influence the behavior of the LP search or the shape of the MIP branching trees. The IVE interface may also undergo slight changes in future releases as new features are added, but this will not affect the actions described in this book.
If you have any comments or suggestions about these pages, please send mail to docs@dashoptimization.com.