MP in Action‎ > ‎Software‎ > ‎

New Directions in Integer Programming

This article is based on a talk given by Bob Hattersley of EDS to the Mathematical Programming Study Group.

SCICONIC is one of the world's leading LP codes with particular strength in integer programming. First released in 1970, it has been developed continuously since then and has recently undergone a substantial rewrite. One of the main aims has been to address the needs of two groups of advanced users:

  • those building integrated applications which make use of optimization;
  • researchers wishing to use clever techniques to tackle hard problems.

Both these groups need to use the functions of an LP code but not as a free-standing code. Instead they require the individual functions as subroutines to build into their own programs; hence the SCICONIC Subroutine Library (SSL).

Design of Subroutine Library

In designing the SSL the most important principle has been to minimize user coding errors. This led to the decision to deny users direct access to SCICONIC's data structures. Instead they use subroutine calls both to access the optimization functions and to manipulate the internal data structures. A consequence is that rows and columns can be accessed using their names from the LP matrix rather than the index numbers which are used internally.

Economic considerations imposed some constraints. A complete rewrite was not possible, so the code remains written in Fortran 77. Two implications follow:

  • the maximum size of matrix which can be solved is fixed when some master routines in the library are compiled; if larger problems are to be tackled, a utility (which is supplied) must be used to recompile them and relink the library;
  • it is easiest to call the subroutines from a Fortran master program, although other languages can be used if the correct calling conventions are followed and the linker permits it. Those working under Windows on a PC should note that the library is not a DLL, so linkers and DOS extenders remain an issue.

Flexible Definition of Matrix

When setting up the matrix, rows and columns can be created in any order and with gaps between them. In effect the matrix is a blank sheet of paper onto which you write fragments of the problem as you go. When you want to solve some part of the matrix, you specify a series of chunks of contiguous rows and columns which are to be optimized. These chunks may contain completely blank rows and columns, which are ignored. Row and column entries can be changed at any time and new ones added.

These facilities make it possible to tackle enormous problems using a variety of decomposition techniques and to add rows and columns dynamically to a problem and reoptimize. They therefore lay the groundwork for tackling hard integer programming problems using row and column generation techniques.

One difficulty which arises is that the usual representation of an LP basis becomes less meaningful. An LP basis usually consists of pairs of basic columns and non-basic rows. But with a flexible matrix the bounds on rows and columns can be changed at any time, as can the nature of the row (less than, equality, etc). To overcome this, the basis stores whether each row or column is basic and its value. There are procedures to patch up bases which have lost their meaning and to restart optimization from a solution which is no longer at a vertex.

Integer Structures

The integer structures which are supported are integer variables (including binary); Special Ordered Sets of types 1 and 2 and generalised semi-continuous variables. These last have been developed to tackle scheduling problems but have other applications as well. Semi-continuous variables can take the value 0 or anything between 1 and some upper limit U. This definition has been generalised to the union of a series of ranges {Ri} such that x must lie between Li and Ui for some i.

As with the definition of the matrix, the integer structures can be modified during the process of tackling a problem. Members can be added to or deleted from Special Ordered Sets; bounds can be changed on integer variables; and ranges can be added to or deleted from generalised semi-continuous variables.

Ultimate flexibility is provided in the form of User Defined Entities (UDEs). These are collections of variables which the user specifies and for which he provides subroutines to perform all the functions which the branch-and-bound algorithm requires. An example of their use is given in the "N Queens" problem below.

Enhancing Branch-and-Bound

SCICONIC uses the Branch-and-Bound algorithm for integer programming and provides a comprehensive set of controls for managing the search. In addition, the advanced user can write his own routines to choose the next sub-problem to be solved; solve it; and estimate the degradation of the objective function in moving to an integer feasible solution.

Perhaps more significantly, he can use these routines to modify the sub-problem in the course of solution. This enables constraints to be added to individual sub-problems based on the LP relaxation. When a constraint is added, it becomes part of the matrix and so is available to all the sub-problems. If it is only required in this sub-problem and its descendants, the user can set flags to achieve this. If this sub-problem and its descendants subsequently prove to be a dead-end, the constraint can be deleted, thus freeing the space in the matrix for reuse.

Using Cuts in the Branching Tree

The Travelling Salesman Problem (see March's article) can be tackled using this approach. The standard formulation is used. First the LP solution is found. This may contain sub-tours. If it does, sub-tour elimination constraints are added and the problem is re-solved. At some point there are no more sub-tours but the solution still contains fractional values.

The normal approach is then to add more sophisticated "comb constraints" which are a generalisation of the sub-tour elimination constraints and re-solve. Once no more comb constraints can be found, the augmented matrix is turned over to the Branch-and-Bound algorithm to solve.

With the SSL, an alternative is to start the Branch-and-Bound algorithm as soon as no more sub-tour elimination constraints can be found. But once the algorithm has branched a variable which was at a fractional value and solved it as an LP, the user-written routine then looks again for sub-tours, applies sub-tour elimination constraints and re-solves the sub-problem within the Branch-and-Bound tree. This proves to be extremely effective and enables a 100-city problem to be solved to proven optimality in 110 seconds on a 33MHz 486.

The N Queens Problem

This problem is to place N queens on an N x N chess-board so that they do not attack each other (see Figure 1). The problem is made more difficult where there is some cost on each square and the problem is to minimize the total cost. The natural formulation has N2 binary variables and 6N - 6 constraints, for the ranks, files and diagonals.

Figure 1: The N Queens Problem

The N queens problem is very hard because the feasibility of a potential solution depends on the interaction of the binary variables representing the positions of the queens. Yet if the diagonal constraints are ignored, the problem reduces to a simple transportation problem for which the LP solution is always integer feasible.

This prompts a novel approach to tackling the problem. Define a User Defined Entity for all the diagonals which is integer feasible when no queen is attacking any other queen on a diagonal. Then if the UDE is not satisfied, choose the cheapest queen on the busiest diagonal and branch it up. The effect is to impose the diagonal constraints logically and to branch the queens in an order which follows a simple but effective heuristic. Using this approach it took 35 seconds on a 33MHz 486 and 838 branches to find and prove the optimal solution to a 30 x 30 problem with 1017 potential solutions.

Commentary

[The views expressed here are those of the author of this article alone.] The facilities described should help to keep SCICONIC in the forefront of practical integer programming. But using them will never be as easy as solving an LP. These are tools for advanced users and researchers who wish to combine the benefits of LP with their own heuristics for tackling integer programming. Using them inevitably involves significant effort in problem structuring, algorithm design and programming. Having said that, the end result can be gratifying: other approaches to solving TSPs or the N Queens problem would require far greater programming effort to achieve comparable run-times and might be unable to prove optimality.

Postscript

Bob Hattersley subsequently reported that the time he had quoted for the 30 x 30 problem was in fact for a 15 x 15 problem, on which an efficient direct search beat integer programming by a factor of 4. On 20 x 20 problems he found integer programming to be more than 3 times faster than direct search. He failed to obtain a result by either method for 30 x 30 problems.

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

Comments