This article is based on a talk given by Robert Ashford, Technical Director of Dash Associates Ltd to the Mathematical Programming Study Group Integer Programming Integer Programming (IP) can be used to tackle many hard problems, particularly in scheduling. But it takes considerable skill and effort to use IP effectively. Run-times can often be very long, measured in hours or days rather than the seconds or minutes of Linear Programming. The IP algorithm, Branch-and-Bound, lends itself naturally to multiple processors, whether in parallel machines or in office computer networks. Integer Programming could gain a new lease of life if problems could be solved using the enormous processing power which goes to waste while people sit at their PCs thinking or typing. Branch-and-Bound Algorithm The most widely-used and effective algorithm for solving integer programming problems is Branch-and-Bound (see Figure 1). Figure 1: Branch-and-Bound Tree First the problem is solved as an LP, i.e. ignoring the requirement that the integer decision variables must take integer values. The solution is examined. If all the integer decision variables happen to have taken integer values, we are finished. If some of the integer decision variables are at non-integer values, we select one of these variables. Suppose n_{3} = 4.63. We define two sub-problems. In the first sub-problem we add the constraint n_{3} ≥ 5.0. In the other we add the constraint n_{3} ≤ 4.0. As the variable n_{3} must take an integer value, these two sub-problems between them contain all possible integer feasible solutions which the original problem contained. We select one of the sub-problems to solve as an LP. As we have already solved the parent problem, we can solve the sub-problem very efficiently by starting from the solution to the parent problem and using the dual simplex algorithm. There are two possible outcomes. Either the sub-problem has a feasible solution, in which case the variable n3 will be at its bound (which is integer); or the sub-problem will be infeasible. In the former case, we have made some progress towards our aim of finding an integer feasible solution; in the latter, we can exclude the sub-problem from further consideration. We then examine the solutions to the sub-problems for integer decision variables which are at non-integer values and repeat our procedure, developing a tree of sub-problems. The trouble with this approach is that at each stage there is an increase in the number of sub-problems which we have to consider. Further, integer decision variables which happen to be at integer values in one sub-problem may move away from those values as we add further constraints, or the sub-problem may become infeasible. Even if we find a solution in which all the integer decision variables take integer values we are not finished. All that we know is that the problem has an integer feasible solution. As we added constraints to the sub-problems in developing our tree, so the objective function worsened. We know the objective value of the original LP solution and the objective value of the integer feasible solution which we have found. But we do not know whether there are other integer feasible solutions which are better than the one we have found. We must explore the rest of the tree to find out.
This is where we use the "and-Bound" part of the algorithm. Once we have an integer feasible solution we know a worst-case value for the objective of integer feasible solutions. This becomes the cut-off. When we solve sub-problems we can discard them if their objective becomes worse than the cut-off. We thus have two weapons for pruning the proliferation of branches of the tree: infeasibility and the cut-off. If we find a better integer feasible solution, its objective value becomes the new cut-off. The Branch-and-Bound algorithm continues until either the entire tree has been traversed or we run out of time. Using Multiple Processors The Branch-and-Bound algorithm lends itself naturally to multiple processors. Sub-problems can be solved independently on separate processors which report their results back to the master. In practice things aren't quite so simple. A substantial quantity of data must pass from the master to the processor which is to solve a sub-problem, and some data must pass back. This communications overhead must be less, preferably much less, than the effort required to solve the sub-problem. In order for the communications overhead to be acceptable, the sub-problems must be relatively hard to solve. This implies that the matrices must be large (many thousands of rows and columns) and that the integer decision variables must be "important", so that branching on them causes significant change in the solution. These considerations apply less if the problem is being solved on a purpose-built parallel computer or if the task given to a processor is to develop an entire sub-tree from its sub-problem. Early Work on Transputers Dash's first work on using multiple processors for integer programming was in 1988, using 4 Inmos T800 transputers. One transputer acted as the master, controlling the Branch-and-Bound algorithm and farming out sub-problems to the three slaves to solve. The results were encouraging, offering roughly linear speed-up in performance with the number of processors. This work was extended in the early 1990s by Peter Connard for his PhD thesis. He obtained super-linear speed-up with up to 8 slaves on large MIP problems. On medium-sized combinatorial problems the speed-up stopped with between 4 and 6 slaves and on small combinatorial problems the parallel approach did not yield any benefits. With the benefit of hindsight, it now appears that these promising results were largely because an old version of XPRESS-MP was used. In this the sub-problems were optimised using the primal simplex algorithm rather than the dual simplex. The primal simplex algorithm is much less efficient at this and as a result each sub-problem took a long time to solve. This gave precisely the conditions on which parallel IP works best. ESPRIT Project More recently Dash has been working as part of a pan-European consortium on an ESPRIT project to improve integer programming techniques for tackling large practical scheduling problems. The latest version of XPRESS-MP has been used and the code has been designed to work on arrays of workstations (e.g. IBM RS/6000) as well as on dedicated parallel computers. The results have been more mixed than with the earlier work on transputers, ironically because the performance of XPRESS has been improved. Because the time taken to optimise sub-problems is now relatively small, the overheads of message passing are comparatively greater, thus reducing the benefits of using multiple processors. Greater speed-up has been obtained by giving the slave processors autonomy to develop sub-trees rather than just solving individual sub-problems. Using Office Networks Dash's most recent work has been to extend the approach to networks of heterogeneous workstations, as may be found in an office on a Local Area Network (LAN). Here the overheads of message passing become even greater, because the communications channels are slower. There are also problems of robustness, both of the network infrastructure and of individual machines. The message passing software (Parallel Virtual Machines and its Windows equivalent) is undergoing rapid development and is correspondingly fragile. Workstations running UNIX tend to be reliable but those running Windows are less so and may at any time be interrupted by the user rebooting or turning them off. Despite this, some promising results have been obtained with a heterogeneous network of Pentiums, IBM RS/6000s and a DEC Alpha. A typical performance is shown in the table.
Number of slaves Time (seconds)0 515 The result with 0 slaves is that of the standard (serial) XPRESS-MP while 1 slave represents the parallel code running on a master processor with all the sub-problems farmed out to a single slave. The speed-up is sub-linear in the number of slaves but demonstrates worthwhile gains. CPU utilization was 85 - 90%, even with large numbers of slaves. Conclusions [ The views expressed here are those of the author of this article alone. ] Parallel IP shows considerable promise but, at least on office networks, the supporting infrastructure is immature. In the next few years it seems likely to be of value primarily to sophisticated users of IP who need shorter run-times and have exhausted alternatives such as buying a faster processor or tightening their formulations. In the medium term the problems with the fragility of office networks and message passing software can be expected to be resolved. Once they have been, parallel IP can be expected to come into its own. Related articles include What Can Integer Programming Do? and How to Succeed with Integer Programming. To find other articles, refer to the MP in Action page. |
MP in Action > Software >