10
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
11
$\begingroup$

This approach is sometimes referred to as price-and-branch (vs branch-and-price), or solving the restricted master, and it does not guarantee optimality.

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$%.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ It's also often called "solving the restricted master". I think its worth mentioning this paper which shows that other heuristics work generally better since it is not always the case that the columns generated by the column generation procedure can be efficiently recombined together without generating additional columns $\endgroup$
    – fontanf
    Jun 24, 2022 at 8:43
  • 6
    $\begingroup$ In fact, price-and-branch does not even guarantee feasibility. $\endgroup$
    – RobPratt
    Jun 24, 2022 at 12:02

Your Answer

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

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