Chapter 8
Integer programming
8.1 Introduction
A surprisingly wide class of practical problems can be modelled using integer variables and linear constraints. Sometimes such a model consists solely of integer variables. That is a pure integer programming (PIP) model. More commonly, there are both conventional continuous variables together with integer variables present. Such a model is said to be a mixed integer programming (MIP) model.
The wide applicability of integer programming (IP) (sometimes known as discrete programming) as a method of modelling is not obvious. Clearly, we can think of situations where it is only meaningful to make integral quantities of certain goods, for example, cars, aeroplanes or houses, or use integral quantities of some resource, for example, employees. In these cases we might use an IP model instead of an LP model. Although such obvious applications of IP do occur they are not common. In fact, in such situations, it is often more desirable to use conventional LP and round off the optimal solution values to the nearest integers.
The obvious type of application described above obscures the real power of IP as a method of modelling. Most practical IP models restrict the integer variables to two values, 0 or 1. Such 0–1 variables are used to represent ‘yes or no’ decisions. Logical connections between such decisions can often be imposed using linear constraints. Such methods of modelling are described in the next chapters.
Before discussing the building of IP models something must be said about the way in which they are solved. Mathematically, IP models involve many times as much calculation in solution as similar-sized LP models. The difficulty of integer problems compared with (continuous) problems involving real or rational numbers is well known in other branches of mathematics. While an LP model involving thousands of constraints and variables can almost certainly be solved in a reasonable amount of time using a modern computer and package program, a similar situation does not hold for IP models. There is a considerable danger in building an IP model only to find no way of solving it in a reasonable time. Ways of avoiding this unfortunate and embarrassing experience are described in the next two chapters. In view of this danger as well as the computational difficulty of IP, Section 8.3 is devoted to methods of solving IP models. This section purposely outlines in any detail only the most successful method of solving IP models, the branch and bound method. It is felt necessary that a model builder should have, at least, this minimum level of understanding as he or she can often influence the exact way in which the calculation proceeds to great advantage. Moreover, this most successful method to date of solving IP models receives surprisingly little attention in theoretical mathematical programming books, possibly because of its lack of mathematical sophistication.
8.2 The applicability of integer programming
The purpose of this section is to classify loosely the different types of problem for which IP models may be built. Inevitably, there is a certain amount of overlap in this classification where particular applications do not fit neatly into any category. Many practical problems will combine aspects from a number of categories. By this loose classification, it is hoped to convey a feeling for the type of problem to which IP is applicable. In some ways the name ‘discrete programming’ conveys what this sort of problem is rather better. One of the reasons why IP has not been applied anywhere near as widely as it might to practical situations is the failure to recognize when a problem can be cast in this mould. This section is purposely rather superficial. Little indication is given of the way in which particular problems may be formulated as IP models. This is left to the next chapter or in particular cases to the detailed formulations of Part III of this book.
A precise definition of those situations, which can be formulated by IP models, is given by Meyer (1975) and Jeroslow (1987).
8.2.1 Problems with discrete inputs and outputs
This class of problems includes the most obvious IP applications mentioned earlier where it is only possible to make whole numbers of products or use integral units of a resource. Economists sometimes refer to such problems as having ‘lumpy’ inputs or outputs. To see why IP is sometimes necessary here, consider the following very small (and contrived) model:
If the variables represent quantities of two different goods to be made, it is important to be clear if these outputs should be integral, for example, represent indivisible goods such as aeroplanes. Should this not be the case and they represent divisible goods such as gallons of beer, we would be content with treating the problem as an LP model and taking the (continuous) optimum, which is
On the other hand, restricting the variables to be integer forces us to accept the integer optimum, which is
It is very difficult to see how one could arrive at the solution (8.2) from the continuous optimum (8.1). Rounding the values in (8.1) to the nearest integers gives an infeasible solution. In some circumstances such as this, it is therefore necessary to solve such a problem as an IP model. This is obviously likely to happen when the values of the variables will be small (say less than 5). For most problems of this type, however, the values of the variables are likely to be much larger than this and the errors involved in rounding the LP fractional solution will not be serious. Indeed, solving such a problem as an IP model could well take a great deal of time in view of the many combinations of integer solutions that could be considered. An extreme case of this was once seen where a national agricultural IP model was built. On examination this model was found to be an IP model only because there were an integral number of cows, hens, pigs, etc., in the country considered!
Similar considerations to those above apply to problems where the inputs rather than (or as well as) the outputs are discrete. Frequently, such an input will be manpower capacity which, if sufficiently large, may be treated as continuous (infinitely divisible).
An application that is quite common occurs when an input (usually a processing capacity or a resource) only occurs at certain discrete values. Apart from this the model may be a conventional LP model. For example, processing capacity might be measured in machine hours per week. By buying extra machines it might be possible to expand processing capacity. It will, however, only be correct to allow this capacity to expand in steps equal to the machine hours per week resulting from extra whole machines. IP can be used to model this type of situation. A related situation to this is presented in the FACTORY PLANNING 2 problem in Part II.
Another particular type of problem in this category where IP must be used is the knapsack problem. This is an IP problem with a single constraint. A particular instance where it might arise is in stocking a warehouse. The problem is as follows: given a limited warehouse capacity, stock the warehouse with goods (of different volumes) to maximize some objective (such as the total value of goods in the warehouse). It will generally not be possible to use the LP solution to this problem, which is trivial and simply involves stacking the warehouse to capacity with the most valuable good per unit volume, thereby ignoring the discrete nature of the goods. Extensions of the knapsack problem arise where extra simple upper bounding constraints also apply to the variables of the problem. It is again usually necessary to use IP rather than LP to obtain a meaningful solution. Knapsack problems do arise in practice but they occur most commonly as subproblems that have to be solved as part of a much larger LP or IP problem. An example of this arises in the cutting stock problem, discussed in Section 9.6.
8.2.2 Problems with logical conditions
It frequently happens that it is desired to impose extra conditions on an LP model. These conditions are sometimes of a logical nature that cannot be modelled by conventional LP. For example, an LP model might be used to decide how much to make of each of the possible products in a factory subject to capacity limitations (the product mix application). It might be desirable to add an extra condition such as ‘If product A is made then product B or C must be made as well’. By introducing some extra integer variables into the model together with extra constraints, conditions such as this easily can be imposed. The resultant model is a mixed integer problem. Any such logical condition as that above can be imposed on an LP model using IP. This is illustrated in the FOOD MANUFACTURE 2 problem. In addition, that problem also illustrates another common use of IP to extend an LP model, limiting the number of ingredients in a blend.
The correct formulation of logical conditions sometimes involves considerable ingenuity and can be done in a number of different ways. Methods of approaching such a formulation systematically are described in Chapter 9. Williams (2009) and Hooker (2000) cover the relationship between logic and IP at length.
8.2.3 Combinatorial problems
Many operational research problems have the characteristic of a very large number of feasible solutions (often an astronomical number) arising from different orders of carrying out operations or of allocating items or people to different positions. Such problems are loosely referred to as combinatorial. It is useful to further subdivide this category into sequencing problems and allocation problems. A particularly difficult type of sequencing problem arises in job-shop scheduling where an optimal ordering of operations on different machines in a job-shop is desired. IP gives a method of modelling this type of situation. There are a number of possible formulations. Unfortunately, IP has not proved a very successful way of tackling this problem to date.
Another very well-known sequencing problem is the travelling salesman problem. This is the problem of finding the optimal order in which to visit a set of cities and return home covering a minimum distance. There are other problems which take the same form. For example, the problem of sequencing operations on a machine so as to minimize total set-up cost takes this form. Obviously, the set-up cost for an operation will depend on the preceding operation and can be regarded as the ‘distance’ between operations. The travelling salesman problem is again a very difficult type of problem for which different IP formulations have been attempted.
A very straightforward allocation problem is given in Part II. This is the MARKET SHARE problem. The problem involves allocating customers to divisions in a company for their services. Although the formulation is comparatively straightforward, problems of this type are not always easy to solve. Problems of a very similar form arise in project selection and capital budget allocation.
The class of allocation problems includes two problems already mentioned for which IP is not needed. It has been pointed out in Section 5.3 that in the transportation problem it is not necessary to impose an integrality requirement. The LP optimal solution will automatically be integer because of the structure of the problem. As the assignment problem can be regarded as a special case of the transportation problem, this property holds for it also. Fortunately, these two problems, although apparently IP problems, can therefore be treated as LP problems and solved fairly easily. Other apparently IP problems also have this property or can be formulated to have this property with great computational advantage. This topic is treated further in Sections 10.1 and 10.2. A complicated extension of the assignment problem is the quadratic assignment problem. This problem occurs where the ‘cost of an assignment’ is not independent of other assignments. The resulting problem can be regarded as an assignment problem with a quadratic objective function. The quadratic terms can be converted into linear expressions reducing the problem to an IP problem. The quadratic assignment problem is one of the most difficult combinatorial problems known in mathematical programming. Fairly small problems can be tackled by reducing the problem to a linear IP model. The DECENTRALIZATION example of Part II is a special sort of quadratic assignment problem. The quadratic assignment problem is discussed further in Section 9.5.
A practical problem that arises and can be regarded as falling into the allocation category is the assembly line balancing problem. This is the problem of assigning workers to tasks on a production line to achieve a given production rate. It is possible to formulate this problem as an IP problem and solve it fairly easily. The usual formulation results in a special sort of IP model known as a set partitioning problem. This type of problem is discussed further in Section 9.5.
Another set partitioning problem is the aircrew scheduling problem. This is the problem of assigning aircrews to sets of flights (rotations or rosters). In practice, this type of problem frequently involves an enormous number of potential rosters and is difficult to solve as an IP problem in consequence. This is discussed further in Section 9.5.
Problems of logical design involving switching circuits or logical gates can be tackled through IP. Unfortunately, such problems often turn out to be very large when formulated in this way and so difficult to solve. A small problem of this kind, LOGICAL DESIGN, is given in Part II.
The political districting problem is also a set partitioning problem when regarded as an IP problem. This is the problem of designing constituencies or electoral districts in order to equalize, as near as possible, political representation. IP has been used in the United States to solve practical problems of this nature.
A fairly common application of IP is to the depot location problem. This is the problem of deciding where to locate depots (or warehouses or even factories) in order to supply customers. Two types of costs may enter the problem, the capital costs of building the depots and the distribution costs resulting from particular sites of the depots. This type of problem can be modelled using IP. Frequently, the resultant model is a mixed integer problem. The DEPOT LOCATION problem of Part II is an example.
8.2.4 Non-linear problems
As was mentioned in Chapter 7, non-linear problems can sometimes be treated as IP problems with advantage. If the problem can be expressed in a separable programming form, it can be solved using either separable programming as described in Section 7.3 or by IP. Should the problem be convex (this term is explained in Section 7.2) it may be treated by LP and no difficulty arises. On the other hand, special methods have to be used for non-convex problems where separable programming has the disadvantage of producing possibly local optima (this is again explained in Section 7.2). IP overcomes this difficulty and produces a true (global) optimal solution, although possibly with considerably more expenditure in computer time. Problems to which this method is relevant have already been mentioned in Chapter 7. They include problems involving economies of scale, quadratic programming problems and geometric programming problems as well as much more general non-linear programming problems.
The way in which such problems can be converted into a separable form is described in Chapter 7. How to convert the resultant separable problems into an IP form is described in Chapter 9. There is, however, an alternative way of approaching such problems by IP. This is through the use of special ordered sets of variables. A number of package programs have facilities for dealing with IP problems in this way to considerable computational advantage. The concept of special ordered sets and how they may be applied to non-linear problems (as well as other types of problem) is described by Beale and Tomlin (1969).
A very common application of IP is the fixed charge problem. This occurs when the cost of an activity involves a threshold set-up cost as well as the usual costs that rise in proportion to the level of the activity. In this way the problem can be regarded as non-linear. For example, if it is decided to produce any amount of a product at all it may be necessary to set up a piece of machinery. This set-up cost is independent of the quantity produced. It is not possible to model this situation using conventional LP but it can be modelled very easily using IP. This is described in Example 9.4.
8.2.5 Network problems
Many problems in operational research involve networks. A lot of these problems can be modelled using LP or IP. Those problems, which give rise to LP models, have already been considered in Section 5.3.
It has already been pointed out in Section 5.3 that the problem of finding the critical path in a PERT network can be viewed as an LP problem. A secondary problem often arises in practice. This is the problem of resource allocation on a PERT network. It may be necessary to alter the order in which certain activities (arcs) are carried out in view of the limited resources available, for example, we cannot simultaneously build the walls and lay the floors in a house if there are not enough workers available. The problem of optimally allocating these limited resources to the arcs of the PERT network so as to (for example) minimize the total completion time for a project can be formulated as an IP problem. Although an IP model is a method of tackling this problem, it is not to be recommended except in very simple cases. The computational difficulties of solving a complex problem of this kind by IP can be very great. In practice, non-rigorous heuristic means are used to obtain useful but non-optimal solutions.
Many IP problems arise in graph theory. A well-known problem to which IP is relevant is the four-colour problem. It has recently been proved that at most four colours are needed to colour every country on a map differently from its neighbouring countries. For any map, IP could be used to find the minimum number of colours necessary. The above problem can be represented as the problem of colouring the vertices of a graph so that vertices jointed by an edge are coloured differently. Other colouring problems arise in graph theory. For example, it is possible to devise problems involving colouring the edges of a graph. Although many such problems exist and can be solved using IP, such considerations are largely beyond the scope of this book. The concern here is mainly with practical problems. Graph theory and IP has been extensively treated elsewhere, for example, by Christofides (1975).
The above five categories encompass most of the different types of problem, which arise to which IP is applicable. In practice, most problems that one meets fall into the second category. They are LP problems on which it is desired to impose extra conditions. These extra conditions are frequently of a logical type. One therefore extends the LP model by adding integer variables and extra constraints. The extra constraints applied to the integer variables sometimes have a combinatorial flavour. Sometimes, these extra constraints serve the purpose of modelling non-linearities in an otherwise LP model.
PIP models arise less frequently in practice. They are usually combinatorial problems. The comparatively large number of combinatorial problems listed above should not disguise the fact that the majority of practical IP models are in the second category and may arise as extensions to almost any application of LP. Combinatorial problems do arise in practice, however, and are sometimes satisfactorily solved through IP. Great care must be exercised, however, when applying IP to such problems. While IP offers an apparently attractive way of modelling a combinatorial problem, experience has shown that such models can be very difficult to solve. It is often desirable to experiment with small-scale versions of the problem before embarking on a large model. There are also good and bad ways of formulating such problems from the point of view of ease of solution; this is discussed in Section 10.1. Also it is hoped that the comparative solution times given with the solutions to the models in Part IV will be indicators of the difficulty of certain types of model.
8.3 Solving integer programming models
This section is in no way intended to be a full description of IP algorithms. A much fuller description is given in Williams (1993). Instead, it is an attempt to indicate different ways in which IP models may be solved and to suggest how a model builder may use existing packages in an efficient manner. Some references to fuller expositions of the algorithmic side of IP are given.
The main approaches to solving IP problems are categorized below. Unlike LP with the simplex algorithm, no one good IP algorithm has emerged. Different algorithms prove better with different types of problem, often by exploiting the structure of special classes of problem. It seems unlikely that a universal IP algorithm will ever emerge. If it did, it would open up the possibility of solving a very wide class of problems. Some of these problems (such as the travelling salesman problem and the quadratic assignment problem) have defied many attempts to find powerful algorithms for their solution. There is now even some theoretical evidence resulting from the theory of computational complexity to suggest that a ‘universal’ IP algorithm is unlikely. The most successful algorithm so far found to solve practical general IP problems is the branch and bound method described below. Considering its apparent crudeness the success of this method is surprising. Almost all commercial packages offering an MIP facility use the algorithm. In fact, the algorithm is little more than an approach to solving IP problems. There is great flexibility in the way it can be used. This is one of the reasons why it is briefly described in a book on model building. Using the branch and bound method in a way suited to the problem can show dramatic improvements over less intelligent strategies.
Most methods of solving IP problems fall into one of four broad categories. There is some overlap between the categories and some particularly successful approaches to large problems have exploited features of a number of methods.
8.3.1 Cutting planes methods
These methods can be applied to general MIP problems. They usually start by solving an IP problem as if it were an LP problem by dropping the integrality requirements (known as the LP relaxation). If the resultant LP solution (the continuous optimum) is integer, this solution will also be an integer optimum; otherwise, extra constraints (cutting planes) are systematically added to the problem, further constraining it. The new solution to the further constrained problem may or may not be an integer. By continuing the process until an integer solution is found or the problem is shown to be infeasible, the IP problem can be solved.
Although cutting plane methods may appear mathematically fairly elegant, they have not proved very successful on large problems, although combined with Branch and Bound methods they can prove very powerful.
The original method of this type is described by Gomory (1958). Further references are given with the exposition in Chapter 5 of Garfinkel and Nemhauser (1972).
8.3.2 Enumerative methods
These are generally applied to the special class of 0–1 PIP problems. In theory there are only a finite (though extremely large) number of possible solutions to a problem in this class. Although it would be prohibitive to examine all these possibilities, by use of a tree search it is possible to examine only some solutions and systematically rule out many others as being infeasible or non-optimal. Such methods together with their variants and extensions have proved very successful with certain types of problem and not very successful on others. Commercial package programs do exist for such methods but are not widely used.
The best known of these methods is Balas's additive algorithm described by Balas (1965). Other methods are given by Geoffrion (1969). A good overall exposition is given in Chapter 4 of Garfinkel and Nemhauser (1972).
8.3.3 Pseudo-Boolean methods
Attempts have been made to exploit the obvious analogy between Boolean algebra and 0–1 PIP problems. A number of algorithms have been developed. As with other algorithms they work well on some types of problem but less well on others. This approach is entirely unlike any other for solving IP problems. The constraints of a problem are expressed not as equations or inequalities but through Boolean algebra. In some cases, this can give a very concise statement of the constraints, but in others it is large and unwieldy. As far as the author is aware no commercial packages capable of accepting practical problems use any of these methods.
These approaches have been developed by Hammer and are described in Hammer and Rudeanu (1968), Granot and Hammer (1972) and Hammer and Peled (1972).
It should not be thought that the specialized 0–1 PIP algorithms are only of relevance to 0–1 PIP problems. Methods have been developed for partitioning a MIP problem with 0–1 variables into its continuous and integer portions. It then becomes necessary, at stages in the optimization, to solve a 0–1 PIP problem as a subproblem. Clearly, these specialized algorithms might be applicable. Any discussion of this topic is beyond the scope of this book. The main reference to this partitioning method is Benders (1962).
8.3.4 Branch and bound methods
It is these methods that have proved most successful, in general, on practical MIP problems. Such methods are also sometimes classed as enumerative but we choose to distinguish them from the enumerative methods described earlier.
As with cutting plane methods, the IP problem is first solved as an LP problem by relaxing the integrality conditions. If the resultant solution (the continuous optimum) is an integer, the problem is solved; otherwise, we perform a tree search. Full details are given in Williams (1993).
A very good discussion of efficient solution strategies to use with the branch and bound method on practical models is given by Forrest et al. (1974). Geoffrion and Marsten (1972) put the branch and bound method, together with enumeration methods, which also use a tree search, into a general framework that makes the basic principles easy to understand. References to the various forms of the branch and bound method are given in that paper. More recent incorporation of Cutting Plane methods into Branch and Bound (‘Branch and Cut’) has proved very powerful.
A comprehensive survey of IP packages is given by Land and Powell (1979).