MP in Action‎ > ‎Software‎ > ‎

XPRESS Accelerates Towards Hard Scheduling Problems

This article is based on a talk given by James Tebboth of Dash Associates Ltd to the Mathematical Programming Study Group. Dash Associates are the authors of XPRESS-MP, one of the world's leading linear and integer programming codes.

Overview of XPRESS-MP

XPRESS-MP is a complete MP package which incorporates both a high-performance optimizer and a model-building package. The optimizer has primal and dual simplex algorithms for linear programming, a Newton barrier algorithm for very large LP problems and branch-and-bound and branch-and-cut algorithms for integer programming.

There are three different types of user interface:

  • Visual XPRESS, which provides an integrated windows development environment;
  • the traditional free-standing programs, mp-opt and mp-model;
  • callable subroutine libraries, which are used both by researchers seeking to build custom algorithms and by applications developers who embed LP models within a larger system.

Continuous development of the algorithms means that increasingly large problems can be solved. Run times for LPs have been reduced by a factor of 6 over the past 6 years, as is shown for an assortment of problems in Figure 1. Version 7 was released in 1993 while version 11 is the current version.

Figure 1: CPU Time (seconds) on a Variety of Problems

Recent Developments

Recent developments in integer programming include:

  • implementation of a branch-and-cut algorithm (discussed below) as well as branch-and-bound;
  • better search strategies;
  • strengthening of the dynamic presolve so that it identifies variable upper bound constraints at each node and disaggregates them.

All of these contribute to better performance for users who leave the code to solve MIPs by itself. Additional facilities have been provided through the callable subroutine libraries for advanced users to:

  • define their own branching objects;
  • define cuts which are applied at particular places in the tree;
  • influence the selection of the nodes to develop, the branching entity and the branching strategy.

In addition a new product, the EMOSL subroutine library, makes it possible to manipulate rows and columns by their algebraic model names rather than their internal sequence numbers, thereby facilitating the writing of advanced algorithms.

Finally, Dash have been working with COSYTEC, developers of the CHIP constraint logic programming system, to bring together MIP and constraint programming.

Cutting Planes

Cutting planes are constraints which must be satisfied by an integer feasible solution to a MIP problem but which may not be satisfied by a particular continuous solution. In principle one can solve a MIP by finding the continuous solution and then adding a series of cutting planes, re-solving the problem as an LP each time until the continuous solution happens to be integer feasible, at which point one has the optimum solution.

There are (at least) two problems with this approach: the number of cutting planes is vast, so identifying ones which are not satisfied by the current continuous solution is difficult; and adding a cutting plane may make only a minuscule improvement to the integer feasibility of the solution. This is why the less elegant branch-and-bound algorithm remains dominant as a practical solution technique for MIPs.

What Dash have done has been to implement code which searches the matrix structure for certain types of constraint from which relatively powerful cutting planes can be derived. Examples of these include:

  • knapsack sets - integer numbers of items of assorted sizes must be fitted together into some limited space;
  • cover inequalities - the sum of a number of integer variables must be greater than some lower bound, most often 1;
  • Generalised Upper Bounds - the sum of a number of integer variables must be less than some upper bound.

These cuts can be added before entering the branch-and-bound tree or within the tree. Heuristics are used to decide how many and which types of cut to apply at any point. The advantages are that integer feasible solutions can be found faster; they are often better; and it is easier to prove optimality. Even where it is not possible to prove optimality, a stronger lower bound is obtained on the value of the optimum solution. Unfortunately, such benefits do not always accrue: as cuts are added the matrix becomes larger and so takes longer to solve. If the benefit from the cuts is small, the overhead of the larger matrix may dominate, causing increased run-times. This is particularly likely to happen where the MIP formulation has been written by an expert.

An example of what can be achieved is given in Figure 2. This shows the solution value and run-times for solving a problem with 255 rows and 345 columns including 151 binary variables.

Figure 2: Effect of Using Cuts in Solving a MIP Problems


EMOSL

There has been a subroutine library version of XPRESS-MP for some years, but only with the new Entity Modelling and Optimization Subroutine Library (EMOSL) has it become possible to refer to variables and constraints in an algebraic way. This is important because there are many advanced ways of solving hard scheduling problems which are well-understood but which have just been too time-consuming and difficult to implement. EMOSL makes it easier to implement such algorithms and provides an efficient way to do so because rows and columns can be added to the matrix without its needing to be regenerated completely.

EMOSL has been used in two applications in scheduling electricity generating sets and forms the core of bc-prod, a prototype system for solving job-shop scheduling problems. Such problems are hard to solve using MIP but bc-prod makes it relatively straightforward by bringing to bear the full power of cuts derived from well-understood structures in these problems.

Constraint Programming

Constraint programming (CP) is derived from logic programming and Artificial Intelligence and uses a declarative approach to defining problems. Variables typically have a small number of possible values and the system works by assigning a value to one variable and propagating the consequences through the rest of the problem. Another variable is then selected and assigned a value. The process is repeated, creating a tree of possible values of the variables.

Constraint programming can thus be viewed as as a strengthened form of presolve at each node in a depth-first branch-and-bound search. It lacks the LP relaxation to provide a lower bound on the value of each node but makes up for this with the speed of evaluation of the nodes. It can be very effective, particularly on scheduling problems involving the sequencing of a number of tasks. However, it is not really geared towards optimization and significant programming effort is required.

Dash have been working on ways of combining MIP with CP, initially with a research code from the University of Marseilles and more recently with COSYTEC's CHIP. The two obvious ways of combining the approaches are to use:

  • CP as the master with MIP as a subroutine;
  • MIP as the master with CP as a presolve at each node.

It appears that the benefits from each of these approaches is not particularly great, except on some specialised problems. The most promising approach is:

  • double modelling, in which the problem is formulated both as a CP and as a MIP, with links between the variables and with a combined search tree.

At the moment such an approach involves more than twice the work involved in setting up the problem using a single technology. Even if problems can be solved more effectively using such a combined approach, its success will depend on the development of simpler ways of defining problems.

Related articles include Using Idle PCs to Solve Scheduling Problems and New Directions in Integer Programming. To find other articles, refer to the MP in Action page.

Comments