previous				contents				next

8. Guiding the Search

8.1 Decisions which the IP Code Takes

There are three decisions which the Branch-and-Bound algorithm faces at each stage in seeking to move from a continuous solution in which some of the integer requirements are not met (integer infeasibilities) to an integer feasible solution:

• which sub-problem should it develop next?
• which integer structure within the sub-problem should it branch on?
• which branch should it take?

There is no clear answer to any of these, so the IP code provides you with mechanisms to influence these decisions. You can:

• use more powerful integer structures such as Special Ordered Sets;
• specify priorities on integer variables and structures which tell the IP code to attend to the high-priority ones first;
• control the "shape" of the search, i.e. whether the search is broad across many nodes or tries to proceed deep quickly to find a completely integer feasible solution;
• use targets and cutoffs to prune the search, possibly at the expense of not finding the best solution;
• assist with the estimation process.

Although it lies outside the scope of the IP code, another powerful technique is to:

• change your formulation so that you only require the most important integer variables and structures to be integer.

In effect this is an extreme form of priorities: it is saying "don't bother at all about the low-priority integer decisions". It can be very useful in helping you to understand about your problem and can assist in tightening the bounds on the value of the optimum integer solution.

Finally, if you run the IP code interactively, you can:

• use Control-C to interrupt the algorithm as it is running and reset parameters.

This can be very useful to counter the frustration of seeing the search going the wrong way. But in order for it to work it is imperative that you do not type ahead.

8.2 Special Ordered Sets

Special Ordered Sets have already been described. It remains only to say: "Use them". One instance where their use may not be obvious is in representing a relationship involving a discontinuity, as shown in Figure 6:

Figure 6: Representing a Discontinuity

y = Y0		if x = X0
y = Y1 + A (x - X0)	if X0 < x  £ X2

Normally it suffices to use a single binary variable, d, which is set to 1 if x > X₀. But if the relationship is required to be 2-way, i.e. we need to force x = X₀ implies y = Y₀ we need in any case to define a value, X₁, which is just greater than X₀ and implement the relationship as x < X₁ implies y = Y₀ (see section 3 above). In this case we can represent the relationship by an S2 set which interpolates the piecewise-linear function between the points (X₀, Y₀), (X₁, Y₁), (X₂, Y₂). It may be objected that this is a different relationship, because we are now interpolating between (X₀, Y₀) and (X₁, Y₁) instead of setting x = X₀ throughout this range of y. But the choice of Y₁ is arbitrary and we are likely to be in trouble elsewhere if the optimal solution is found to lie in this region.

previous				contents				next