# Integer column generation without branch & price

Consider the following situation. I have an integer program which I want to solve using column generation. After a suitable decomposition, the master problem has decision variables that select the columns to use in order to satisfy some constraint. Unlike in ordinary Dantzig-Wolfe (DW) reformulation, here the MP variables have to be integer. This suggests using Branch and Price where (DW) is used to solve the LP relaxations at the nodes and one adopts a suitable branching strategy to recover integrality.

Assume now that I do the following:

• I solve the LP relaxation of MP using DW
• I retain all the columns generated in the process
• I solve MP again as an integer program using those columns

My question is: Does this approach provide the optimal solution to the original problem, or it is just a heuristic? And why?

It is equivalent to the following question: is the gap between the optimal solution of the linear relaxation of the master problem and its integer solution $$0$$ ?
Consider for example a cutting stock problem with $$L=90$$, $$l_1=30$$, $$l_2=45$$, with demands $$d_1=d_2=1$$, and with columns $$c_1=(0,0)$$, $$c_2=(3,0)$$, $$c_3=(0,2)$$. The optimal solution is given by column $$c_4=(1,1)$$ which is a fractional convex combination of $$c_1,c_2,c_3$$: $$c_4 = \frac{1}{6}c_1+\frac{1}{3}c_2+\frac{1}{2}c_3$$ This means that this optimal solution cannot be returned by the master problem with integer variables, and branching is necessary to reach optimality.
However, it is a good heuristic. It is used in VRPy, a python module for solving a range of vehicle routing problems. In this paper, the authors show that asymptotically, for the VRP, the relative error using this price-and-branch strategy goes to zero as the number of customers increases. This is observed empirically: in this same paper, the authors mention other papers which report an average relative gap between the optimal solution to the linear relaxation and the integer solution of only $$0.73$$%.