5.8 Guiding the Search

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.

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, δ, which is set to 1 if x > X0. But if the relationship is required to be 2-way, i.e. we need to force x = X0 implies y = Y0 we need in any case to define a value, X1, which is just greater than X0 and implement the relationship as x < X1 implies y = Y0 (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 (X0, Y0), (X1, Y1), (X2, Y2). It may be objected that this is a different relationship, because we are now interpolating between (X0, Y0) and (X1, Y1) instead of setting x = X0 throughout this range of y. But the choice of Y1 is arbitrary and we are likely to be in trouble elsewhere if the optimal solution is found to lie in this region.

Priorities

[This and the next 2 sections relate specifically to XPRESS-MP but similar facilities exist in most industrial-strength IP codes and similar remarks apply there.]

Priorities are specified on integer variables and structures in the DIRECTIVES section of the formulation in XPRESS-MP. This generates a .dir file which is read by the IP code. By default the integer variables and structures have a priority of 500. You use the DIRECTIVES section to raise or lower the priority of particular integer entities by specifying their priority values between 0 and 1000. The numerical values which you use do not matter: the important thing is the relationships between them.

At any stage the IP code uses the priorities to decide which entity to branch on next within the sub-problem which it has decided to develop. It will look at each priority class in turn and, once it finds a class which contains integer infeasibilities, will select one of those integer entities for branching.

Unfortunately this doesn't ensure that an integer variable with a high priority won't find itself being moved a long way down the branching tree. The trouble is that the Branch-and-Bound algorithm doesn't seek to apply constraints to variables which happen to be at integer values already. So you can have a high-priority decision which appears to have been made by the LP, but which is actually free to be changed as a result of consequential branchings. And, so far as I know, there is no way to get the IP code to back-track up its branches and force the high-priority variable to its former value. Truly a case of the tail wagging the dog.

What this means is that if you have a true hierarchy of decisions, it can well be more effective to solve the problem with only the high-priority variables required to be integer and then fix these variables at their optimal values and re-solve the problem with the lower-priority variables required to be integer.

A by-product of this approach is that it yields a tighter bound on the value of the optimum integer solution. If you require only the high-priority variables to be integer, you create a much simpler problem for the IP code. You are therefore far more likely to be able to complete the Branch-and-Bound search. If you do, the value of this partial-integer solution provides a tighter lower bound (for a minimization) than the continuous optimum on the value of any full integer feasible solution. Such a lower bound is of interest in itself and it can be used to help the IP code further if the target (OBJTAR in XPRESS) is set to a value somewhat greater than it.

Controlling the Shape of the Search

The default approach which XPRESS adopts is to try to search downwards as fast as possible. Suppose that it has just selected a node to develop at some level in the tree. Then it selects an integer variable or structure from the highest priority class which is integer infeasible. It creates two sub-problems from this. It selects one of them and solves it. If this sub-problem can be solved but still has integer infeasibilities it is then taken as the node to be developed next. If the sub-problem has no solution (i.e. is infeasible when considered as an LP) the other sub-problem is solved. If that one can be solved but has integer infeasibilities it is taken as the node to be developed next. If that one also has no solution as an LP, XPRESS then considers all the nodes afresh.

This approach is often effective in finding integer feasible solutions quickly. But it does mean that a wrong turn early in the tree cannot be rectified until one finds both of a pair of sub-problems infeasible as LPs. Even then, the estimation procedure biases it against going back to a node early in the tree. So it is really a case of; "if it works, fine; if not, it probably won't produce anything much however long you wait".

The main alternative to the default is to set NDSEL1 = 2. This forces the IP code to consider all the nodes at each stage rather than just the deepest, i.e. a broad search. It is thus much less serious if a wrong decision is made early in the tree. Conversely it takes much longer to reach any integer feasible solutions. But once the integer feasible solutions are reached, they come quickly and you are far more likely to complete the Branch-and-Bound search than with a depth-first search.

The final option is NDSEL1 = 3, which forces a strict depth-first search. It is not recommended.

One disadvantage of the broad search is that if there are many low-priority integer variables, it can take an enormous amount of time to reach any integer feasible solution. Often what is required is a broad search on the high-priority integer entities followed by a deep search on the low-priority ones. This is not available yet in XPRESS (perhaps version 11 will have it!), so if you want to achieve it you must do so manually. If you are experimenting with the problem you can achieve this by setting NDSEL1 = 2 at the start, letting the search proceed and then interrupting it with Control-C and resetting NDSEL1 = 1 when it is time to switch from breadth-first to depth-first. Obviously this is not acceptable for a client, so you would have to create a problem with only the high-priority variables being required to be integer, solve it with a broad search and then create sub-problems in which the high-priority variables are fixed, the low-priority variables are declared to be integer and solve these with a deep search.

Targets and Cutoff

The target, OBJTAR, is the expected value of the objective in the global optimum solution. Set it to a sensible value if you can: it will improve the search, particularly before the first integer feasible solution is found. Once that happens, it is automatically reset to the value of the integer feasible solution and making further changes to it will achieve, at best, a minor improvement.

Suppose for the sake of argument that our problem is a minimization. If the objective of a sub-problem rises above the cutoff, CUTOFF, it is discarded. By default the cutoff is not set until an integer feasible solution is found, whereupon it is set to that value. This approach is conservative, in that it avoids excluding any possible integer solutions at the start and ensures that no integer solution is excluded which is better than the best one found so far.

You can improve the performance of the Branch-and-Bound algorithm by specifying a cutoff at the beginning and by tightening it after each integer solution is found. If you know an integer feasible solution (however poor) from consideration of the real problem, there is nothing to lose and a lot to gain by specifying its objective value as the cutoff at the start.

If you are concerned only to find an integer feasible solution whose objective lies within some tolerance of the true optimum, you can be more aggressive in resetting the cutoff each time an integer feasible solution is found. You can either do this manually or by using PERCUT and ADDCUT. The benefit lies in pruning the search tree more aggressively; the disadvantage in the potential loss of better solutions.

When doing Integer Programming, there are often many distinct solutions with the same objective value. If you wish to find these solutions, once you have reached an integer feasible solution you should reset CUTOFF to be worse than its current value.

Assisting the Estimation

In a word: don't.

previous contents next

Comments