1
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ When you say “feasible solution” do you then mean feasible for the LP relaxation or for the integer program itself? I don’t have an example ready, but I can image situations where a high quality solution for the IP is a very low quality solution for the LP relaxation (think of cases where the DW bound is weak) $\endgroup$
    – Sune
    May 21, 2023 at 10:07
  • $\begingroup$ @Sune, thanks for the clarification. I meant actually by for the integer solution. $\endgroup$
    – A.Omidi
    May 21, 2023 at 10:44
  • $\begingroup$ Same question for "optimal", "near optimal" and "final", do you mean for the LP relaxation or for the integer problem? and what do you mean by "set"? do you mean add the corresponding columns to the column pool? $\endgroup$
    – fontanf
    May 22, 2023 at 9:04
  • $\begingroup$ @fontanf, I actually would like to know the impact of the provided initial solution, as a trigger of the master problem in a starting point of algorithm, to invoke the final integer solution after solving the master as a MIP. I meant by sets is feeding the initial solution in the solving process. Sorry if it is confusing. Also, Let me know if you want any information. $\endgroup$
    – A.Omidi
    May 22, 2023 at 12:01

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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
$\endgroup$
1
  • $\begingroup$ Dear Dr. Fontan, @fontanf, Many thanks for your useful answer and the provided link. As I am getting in touch with Prof. Rubin in advance, please, let me accept his answer and also upvote yours as well. Thanks once again for your time and response. $\endgroup$
    – A.Omidi
    May 27, 2023 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.