Quality of the defined initial solution in column generation

Question

In the context of column generation, specifically, price and branch or delayed column generation like Gilmore-Gomory (GG-CG) procedure, it needs to define an initial feasible solution as a trigger of the optimization process on the master problem. It seems the solving process procedure highly depended on the quality of the provided initial solution. As an example, suppose in a scheduling problem that was solved by (GG-CG) when the initial solution sets as a worse case, the number of iterations of the algorithm increases very much, and also the quality of the final solution may not be good enough. While if we set an optimal or near-optimal solution, to test the algorithm execution, it was solved with a few number of iterations in contrast to the previous one and already proved the optimal solution. My main questions are:

• Has the provided initial solution had an impact on the solving process?

• May it be possible that the algorithm destroys a good initial solution?

Answer 1

If you are asking whether columns can be added to the LP relaxation of the master that will move the LP solution away from the initial incumbent, I assume that is possible. As long as the columns for the initial incumbent remain in the relaxed master, though, when you eventually restore the integrality requirements and do a final solve of the master you should get a solution as good as if not better than the initial incumbent, because the initial incumbent remains feasible in the expanded master problem.

Answer 2

The question is not clear to me, but I'll try to give an answer anyway.

Solving the linear relaxation of the Dantzig-Wolfe formulation

First, let's talk about the resolution of the linear relaxation of the Dantzig-Wolfe formulation using a column generation approach. The resolution provides a dual bound for the original problem.

The column generation procedure requires an initial set of columns that ensures that the LP is feasible; because if the LP is infeasible, no dual values are available.

The quality of the initial columns is likely to impact the number of iterations to converge. The extreme case being that an optimal solution of the linear relaxation is already in the initial set of columns and therefore, the solution of the first iteration is already optimal. In general, it is reasonable to expect less iterations if the initial columns are better.

Solving the restricted master

You mention "price-and-branch". I assume that you talk about the strategy to get an integer feasible solution by solving a MILP containing only the columns which have been generated during the column generation procedure that solved the linear relaxation. This is also called "solving the restricted master".

An important drawback of this approach is that no new column is generated during the process. If you consider the extreme case mentioned above where the initial columns of the column generation procedure already provide the optimal solution, then no additional column is available for the MILP, and it is likely to not find any integer solution at all. The better the initial columns are, the lesser iterations there will be, and therefore the lesser diversity there will be in the columns for the MILP. Thus, the MILP might struggle to find columns that fit well together.

There exists other approaches that allow generating new columns and usually work better than solving the restricted master. See

• Sadykov R, Vanderbeck F, Pessoa A, et al (2019) Primal Heuristics for Branch and Price: The Assets of Diving Methods. INFORMS Journal on Computing 31:251–267. https://doi.org/10.1287/ijoc.2018.0822