previous				contents				next

8. Guiding the Search

8.3 Priorities

[Sections 8.3 - 8.5 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.

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

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

8.6 Assisting the Estimation

In a word: don't.

previous				contents				next