This article is based on a talk given by Professor Gautam Mitra of Brunel University to the Mathematical Programming Study Group. General Principles Integer programming remains the subject of much research. This has led to important improvements, although not to a breakthrough. The general principle in making integer programming run faster has been to reduce the "duality gap". This is the difference between the value of the LP optimum (i.e. the value of the optimum solution in which the integer requirements do not have to be satisfied) and that of the IP optimum (in which they do). This "sharpening" can be done in a number of ways:
In addition the optimization can be speeded up by:
The aim among researchers is to make integer programming as speedy and robust as LP. In practice this is still far off. Nonetheless, automatic cut-generation and integer pre-processing are techniques which can be applied to large numbers of problems. They are appearing in state-of-the-art IP packages and offer substantial benefits without requiring significant effort from the user. Structuring the Problem Restructuring the formulation of the problem often achieves substantial, and sometimes spectacular, improvement. The general aim is to identify how the LP solution can "cheat" the integer requirements and then to modify the formulation to reduce the scope for "cheating". One particular area to watch out for is where integer decisions intersect. If you have two decisions to make, each of which is to choose one option from five, it is likely to be better to define a single set of 25 decision variables than two sets of 5. The LP model will have more decision variables and take longer to solve, but the integer programming will run much faster. The IP code can help by providing high-level structures which enable you to model aspects of your problem directly. The most important of these are Special Ordered Sets, whose use was described in But my Problem Isn't Linear! and Non-Linear Optimization Using Extensions to LP. These enable you to model the selection of one option from many and to represent piecewise linear functions of a single variable. Various more complicated structures have been proposed to model functions of two or more variables but none has become established. Another useful construct is the semi-continuous variable. This can take the value 0 or any continuous value between 1 and some upper bound U. Generalisations include variables whose values:
Guiding the Search Linear programming algorithms are so efficient and effective that you can treat an LP code as a "black box". You do not need to tell it how to tackle the problem or set control parameters. This is not true for integer programming. You often need to work with the IP code, helping it to find the optimum solution by pointing it in the right direction. Some of this is achieved by using high-level integer structures such as Special Ordered Sets and by defining meaningful reference rows. More can be achieved if the IP code allows you to:
Further advice about using integer programming codes effectively was provided in How to Succeed with Integer Programming. Adding Cuts The optimum solution to an LP problem lies at one of the vertices of the polyhedron defined by its constraints. The Simplex Method works by pursuing a hill-climbing path around its vertices. Integer programming is much more difficult because the potential solutions don't just lie at vertices but are usually strictly within the interior (see Figure 1). But if we add extra constraints, cuts, which chop off areas which contain no integer feasible solutions (the dotted lines in Figure 1), we may find that the optimum LP solution is integer feasible. If this happens we have found not just a good integer solution but the best possible. Figure 1: Adding Cuts to Find the Integer Optimum This principle is exploited in some integer programming codes and is available as a bolt-on extra (often from academics) in others. Cuts may be generated directly from the matrix and its LP solution or by first analysing the matrix's structure and identifying the types of constraint used. There is a relatively small number of classes of constraint in IP models and standard ways have been developed to exploit and tighten their structure. Although cut-generation is powerful, it does have its disadvantages. With Branch-and-Bound what is added at each stage is a simple bound, which doesn't increase the size of the LP matrix. But cuts are full rows and therefore add to the size of the LP matrix. If the cuts eliminate large swathes of non-integer-feasible solutions, they justify their existence. But as time goes on they become progressively less useful and are not worth having. What this means is that you should not expect too much of automatic cut-generation software. With a weakly-formulated problem it may well help a lot. But it tends to be less effective if you have structured your problem well. Software which adds cuts progressively within the search tree is considerably more powerful than that which adds cuts only after the LP solution. In many ways the most powerful feature associated with cuts is the ability for the IP code to interact with the problem definition and identify and add violated constraints within the search tree. In tackling a hard IP problem you will often have an enormous number of potential constraints, too many to include in the LP matrix. You then define the problem with a subset of these, solve it as an LP, check which of the larger set are violated by the LP solution, and add those violated constraints. You may wish to do this many times and also within the Branch-and-Bound tree. This requires sophisticated IP software with flexible data structures and is generally found in the "toolkit" or "software library" version of an IP code. Integer Pre-Processing Most industrial-strength LP codes pre-process the LP matrix before solving it. They try to tighten the bounds on rows and columns (and on their dual values) with the aim of removing from the matrix columns whose values are fixed and rows which are never binding. In this way the size of the matrix is reduced, thereby speeding up the solution process. Such analysis can be extended if one knows that a variable must be integer. For instance, if an integer variable takes a value less than 1.43, its value must be either 0 or 1; if its value is less than 0.95 it must be 0. This integer presolve can be carried out on each sub-problem in the Branch-and-Bound tree. Although simple, it proves remarkably effective in speeding up integer programming. Dual Algorithms IP codes rely on dual algorithms to re-optimize the sub-problems within the Branch-and-Bound tree. Each sub-problem is formed by adding a bound to the previous sub-problem so the optimal solution to the parent sub-problem is dual feasible to child. A dual algorithm typically takes a tenth of the time to solve a sub-problem that a primal algorithm would. What relevance does this have to the speed of integer programming? Surely all IP codes use dual algorithms? Yes they do, but some of those dual algorithms aren't really up to the job. IP sub-problems are often highly degenerate with large numbers of parallel constraints. If the dual algorithm fails, the best that will happen is that it realises that it has failed and invokes primal, which is usually more robust. But the price to be paid is much longer run-times. Thus improving the robustness of dual algorithms speeds up integer programming. Faster Hardware Faster hardware always helps, but it is rarely the solution. A faster processor is usually only a couple of time faster, and the total system performance is generally less than this. Parallel hardware offers obvious benefits with the opportunity to solve several sub-problems simultaneously. But even here, although each processor may be used efficiently, the reduction in run-times is less spectacular. Many of the sub-problems which are explored in parallel turn out to be dead-ends and would be dismissed quickly at a later stage on a conventional machine. Conclusion Integer programming software is improving slowly but surely. For problems with a mixture of linear and integer components, integer programming is increasingly attractive. But it is still a long way from the ease of use of linear programming, where you simply have to define a problem and the LP code will find the best solution. Related articles include How to Suceed with Integer Programming and Using Idle PCs to Solve Scheduling Problems. To find other articles, refer to the MP in Action page. |
MP in Action > How to Use MP >