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.
- 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 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. |

LP Training > 5. Integer Programming >