Solving a Class of Cut-Generating Linear Programs via Machine Learning
Atefeh Rajabalizadeh Danial Davarnia
Cut-generating linear programs (CGLPs) play a key role as a separation oracle
to produce valid inequalities for the feasible region of mixed-integer
programs. When incorporated inside branch-and-bound, the cutting planes
obtained from CGLPs help to tighten relaxations and improve dual bounds.
However, running the CGLPs at the nodes of the branch-and-bound tree is
computationally cumbersome due to the large number of node candidates and the
lack of a priori knowledge on which nodes admit useful cutting planes. As a
result, CGLPs are often avoided at default settings of branch-and-cut
algorithms despite their potential impact on improving dual bounds. In this
paper, we propose a novel framework based on machine learning to approximate
the optimal value of a CGLP class that determines whether a cutting plane can
be generated at a node of the branch-and-bound tree. Translating the CGLP as an
indicator function of the objective function vector, we show that it can be
approximated through conventional data classification techniques. We provide a
systematic procedure to efficiently generate training data sets for the
corresponding classification problem based on the CGLP structure. We conduct
computational experiments on benchmark instances using classification methods
such as logistic regression. These results suggest that the approximate CGLP
obtained from classification can improve the solution time compared to that of
conventional cutting plane methods. Our proposed framework can be efficiently
applied to a large number of nodes in the branch-and-bound tree to identify the
best candidates for adding a cut.