5.2 Is IP a Suitable Technique?

The first issue which must be addressed is whether IP is a suitable technique for tackling the problem. In many respects the criteria are similar to those for deciding whether the problem is amenable to LP. That is, there must be:

  • many potentially acceptable solutions;
  • some means of assessing the quality of alternative solutions;
  • some interconnectedness between the variable elements of the system.
In addition we must answer a crucial question:
  • how far from the LP optimum do we have to move to reach an integer solution?

This is because IPs are solved by first disregarding the requirement that the integer variables take integer values. The problem is solved as an LP to find what is known as the continuous optimum. The IP algorithms are then used to move away from the continuous solution in an attempt to find integer feasible solutions, i.e. solutions in which all the integer variables take integer values. Unfortunately the algorithms are not as powerful as those for Linear Programming and so they are not able to head directly for the optimum integer solution. Instead they try to find an integer feasible solution and then look for another one which is better. This gives rise to a tree search and it is only when the search is completed that one can know that the best integer feasible solution which has been found is the global optimum solution (or more properly, one of the global optimum solutions).

Because of the way that integer solutions are found, it follows that the less distance that we have to move from the LP optimum to reach integer solutions, the more likely that IP will be a suitable technique to find good, and possibly the best, solution.

Thus IP is good at solving problems which involve "rounding" the LP solution. This is usually true of problems in which a relatively small proportion of decision variables must be integer. It also applies to problems in which the integer variables are semi-continuous or take integer values greater than 1. Many problems involving special ordered sets are also relatively easy to solve, but some are not.

IP is less good where there is a significant "combinatorial" element, i.e. where some combination of items must be chosen and the costs (and feasibility) of the combination are more a function of the combination than of the component items. The Travelling Salesman Problem is a classic example. The problem is to find the shortest route visiting a set of points. This is hard to solve because the length of a route is essentially a function of the sequence of points visited. The number of such sequences of points rises as n! (factorial n) where n is the number of points. Yet despite this, IP-based techniques have been developed which are able to find the optimum solution routinely to problems with hundreds of points. This is discussed further in section 5.9 below.

Integer Programming works reasonably well where there is a hierarchy of decisions to be made. For instance, building a new factory enables various consequential activities to take place. Although the solution depends on the values of all the decision variables, setting the values of the most important ones restricts the values of the decision variables representing the consequential activities. In such a case the IP code will usually be able to work out for itself which are the most important decisions and determine those first, or you can assist it by specifying the hierarchy of decisions explicitly.

previous contents next

Comments