24.7. 24.7 Branch and Price

The Branch and Price method is the dual of B&C in a certain sense. If a problem has very large number of variables then it is often possible not to work explicitely with all of them but generate only those which may enter the basis of the LP relaxation. This is column generation and is based on the current values of the dual variables called shadow prices. Similarly to B&C the type of the generated columns is restricted. If it is not possible to find a new column then branching is made.

  Problems  

24-1 Continuous Knapsack Problem

Prove Theorem 24.1. (Hint. Let be a feasible solution such that there are two indices, say and , such that and , and . Show that the solution can be improved.)

24-2 TSP's relaxation

Decide if the Assignment Problem can be a relaxation of the Traveling Salesperson Problem in the sense of definition 24.5. Explain your solution regardless that your answer is YES or NO.

24-3 Infeasibility test

Based on the the second observation of Subsection 24.5.2 develop a test for the infeasibility of a linear constraint of binary variables.

24-4 Mandatory fixing

Based on the previous problem develop a test for the mandatory fixing of binary variables satisfying a linear constraint.

  Chapter Notes  

The principle of B&B first appears in [ 158 ]. It solves problems with bounded integer variables. The fast bounds were introduced in [ 22 ] and [ 272 ]. A good summary of the bounds is [ 80 ]. To the best knowledge of the author of this chapter the improvement of the fast bounds appeared first in [ 281 ].

B&B can be used as an approximation scheme, too. In that case a branch can be deleted even in the case if its bound is not greater than the objective function value of the current best solution plus an allowed error. [ 122 ] showed that there are classes such that the approximate method requires more computation than to solve the problem optimally. B&B is very suitable for parallel processing. This issue is discussed in [ 43 ].

Based on the theoretical results of [ 167 ] a very effective version of B&C method was developed for pure binary optimization problem by [ 252 ] and independently [ 14 ]. Especially Egon Balas and his co-authors could achieve a significant progress. Their method of lifting cuts means that a locally generated cut can be made globally valid by solving a larger LP problem and modify the cut according to its optimal solution.

The first integer programming method to solve an IP problem with general, i.e. non-bounded, integer variables is Ralph Gomory's cutting plane method [ 93 ]. In a certain sense it is still the only general method. Strong cuts of integer programming problems are discussed in [ 15 ]. The surrogate constraint (24.18) has been introduced by [ 92 ]. The strength of the inequality depends on the choice of the multipliers . A rule of thumb is that the optimal dual variables of the continuous problem give a strong inequality provided that the original problem is linear.

The DFJ model of TSP appeared in [ 60 ]. It was not only an excellent theoretical result, but is also an enormous computational effort as the capacities and speed of that time computers were far above the recent ones. One important cut of the TSP polyhedral set is the so-called comb inequality. The number of edges of a complete tour is restricted in a special subgraph. The subgraph consists of a subset of cities called hand and odd number of further subsets of cities intersecting the hand. They are called teeth and their number must be at least three. Numerical problems of TSP are exhaustively discussed in [ 240 ].

A good summary of Branch and Price is [ 20 ].

The European Union and the European Social Fund under the grant agreement no. TÁMOP 4.2.1/B-09/1/KMR-2010-0003.