1
$\begingroup$

I want to solve an integer linear programming problem using the branch-and-cut method, relaxing the original ILP problem to LP problem. If the LP solution contains a non-integer value of some variable I will branch. Is it possible to use the results of solving parent problem during branching? For example, let the original LP problem be p0 and let the LP solution variable x1 = 20.5 To obtain the next solutions, I will construct two branches: p1: x1>=21 and p2: x1<=20. Is it possible to solve p1 and p2 using the solution of p0 instead of solving p1 and p2 from scratch? If yes, could you please recommend LP solver that can do this? Is it possible to use GLOP for this purpose?

$\endgroup$

1 Answer 1

3
$\begingroup$

Yes, after branching, the basis from the parent node will be dual feasible to its children, so dual simplex is the natural choice to warm start the LP solver. That is how virtually every branch-and-cut algorithm is implemented.

$\endgroup$
1
  • $\begingroup$ Thank you very much! Could you please tell me the book or article or reference where I can look at the numeric example? $\endgroup$ Commented Jul 2 at 5:31

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.