Optimization Online


Solving Cut-Generating Linear Programs via Machine Learning

Atefeh Rajabalizadeh(alizadeh***at***iastate.edu)
Danial Davarnia(davarnia***at***iastate.edu)

Abstract: Cut-generating linear programs (CGLPs) play a key role as a separation oracle to produce valid inequalities for the feasible region of optimization problems. When incorporated inside of branch-and-bound, the cutting planes obtained from CGLPs help to tighten relaxations and improve dual bounds. Running CGLPs at nodes of the branch-and-bound tree, however, 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 the CGLP, which is the deciding factor in generating cutting planes. 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 train data sets for the corresponding classification problem based on the CGLP structure. We conduct computational experiments using classification methods such as logistic regression, support vector machines, and neural networks. Computational results suggest that the outcome of the approximate CGLP obtained from classification achieves a high accuracy rate in a significantly smaller amount of time compared to modern LP solvers. 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 running the CGLP---a feature that can be implemented at the preprocessing phase of any branch-and-cut algorithm to improve solution time and bound quality.

Keywords: cut-generating linear programs; machine learning; deep learning; data classification; function approximation

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Applications -- Science and Engineering (Data-Mining )

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 08/15/2021
Entry Accepted: 08/16/2021
Entry Last Modified: 08/15/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society