Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper combines the machine learning technique within the traditional column generation method for solving combinatorial optimization problems. Specifically, the authors propose to use machine learning algorithms to predict high quality columns that belong to an optimal integer solution. Here the machine learning model is trained using training instances that correspond to columns (MISs in the case of VCP), where the features of each instance are constructed from various perspectives. 

The main contribution of this paper is, it presents a nice integration of MIP technique with the prediction power of machine learning. Instead of fully replying on ML predict the optimal solution for combinatorial optimization problem, here in this paper it simply leverages the power of ML technique for column selection. This idea in alignment with many recent literatures about learning to branch, learning to cut in MIP, becomes an increasingly exciting area in both communities.

strength_and_weaknesses: Main strength: This paper is very nicely written with little typos and easy to follow. The numerical experiments are extensive and convincing. The main idea of this paper is novel and interesting and is extendable for many other types of combinatorial optimization problems, it provides another bridge between communities of ML and MIP. 

Main weakness: 1. The constructed features for training instances seem too arbitrary, a detailed explanation of the intuition and analysis can be helpful.     
2. In the numerical experiment, all the benchmark methods are variants of column generation. A more detailed comparison with other state-of-art methods for VCP should be considered (either based on tighter LP relaxations or combinatorial properties of VCP). Based on the same reason, since for many classic combinatorial optimization methods there have already been quite successful combinatorial algorithms in the literature, simply extending the same idea of this paper to tackle those other problems cannot be trusted to outperform other algorithms. 

minor comments/questions: 1. In the formulation given by (1)-(3), since in the graph of VCP, every node can only be colored exactly once, should the $\geq$ in (2) be equality?     
2. You mentioned that the set covering formulation (1)-(3) has a tight LP relaxation. Can you add a reference for this statement? Is it also true that, if you select a subset $\tilde{\mathbb{S}}$ of $\mathbb{S}$ and replace $\mathbb{S}$, the binary IP (1)-(3) still has a tight LP relaxation?  
3. In constraint (5), $\tilde{\mathbb{S}}$ should be $\tilde{\mathbb{S}}_v$, which has not been defined until later in Section 3.1.   
4. In Algorithm 1, at every iteration you keep the top $\epsilon$ percentage of MISs, here in convention $\epsilon$ is used to denote small constant. Here you should either say "top $\epsilon$ of " or use some other notation such as $\kappa$. 
clarity,_quality,_novelty_and_reproducibility: The clarity, quality, novelty and reproducibility of this work are all significant enough to be accepted as a conference preceding. 
summary_of_the_review: Overall, I think this paper has made significant contribution to the community of MIP or CO by leveraging the power of ML techniques. Even though this type of method is completely empirical-based and often times not the optimal method in practice, such attempt is still encouraging and in my opinion, it's not impossible to see major breakthroughs in combinatorial optimization in the future through unconventional approaches like ML. Based on the novelty and potential carried in this paper, I recommend this paper to be accepted.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose a Column Generation method for Vertex Coloring Problem, based on Machine Learning. The column in this case is a maximal independent set, which can potentially share the same color. Specific features were designed for this problem: 1) problem-specific features derived from the graph; 2) statistical measures computed from sample solutions; 3) linear program (LP) features. Various ML classifiers (KNN, Decision Trees, SVM) are trained on instances with known optimal solutions, in order to predict high quality maximal independent sets (MIS). The MLCG algorithm samples randomly generated MIS or uses a genetic algorithm like procedure to evolve new ones and keeps a subset of the highest quality ones. The generated columns are then fed into the Gurobi solver. A good sized experimental evaluation shows that MLCG outputs higher quality columns compared with other strategies, like random CG, Reduced Cost, MLF and Full. 
strength_and_weaknesses: Strengths:
For the specific Vertex Coloring Problem, the features that are defined are natural and prove to be relevant in characterizing the quality of MIS. The method is clear and combines well understood ML classifiers. The experimental evaluation confirms the quality of the method.

Weaknesses:
It is not clear how this method can be used for problems other than Vertex Coloring, although the authors claim that the method is generic, and mention in conclusion that vehicle routing may lend itself to a similar treatment. 
The size of the test graphs is small, with only 100 vertices. Any indication of how this method would scale for larger graphs?
clarity,_quality,_novelty_and_reproducibility: The ideas of the paper are explained very clearly. There is some novelty in the design of the features for ML algorithms, and in combining other existing algorithms.
summary_of_the_review: The paper shows an improvement in Column Generating quality with the help of ML classifiers, for Vertex Coloring. While there is some novelty in the design of the features and of the method, the scope is still very focused on a single type of problem (VC), and the experimental evaluation is still limited to a small number of graphs of modest size.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a machine-learning-based approach for generating columns for LP relaxations of vertex cover problems (VCPs). The paper (implicitly) assumes that the VCPs are generated from some distribution and it proposes to learn a classifier to predict if a MIS is a part of the optimal solution, given a training set of VCP problem instances. Then, the standard column generation algorithm is used with the learned classifier to choose columns. The experiments using real data sets show that the proposed approach tends to produce better solutions.
strength_and_weaknesses: Strength:
- A motivated new approach to combinatorial optimization


Weaknesses
- The approach is not general, i.e., specifically designed for a series of optimization problems generated from similar distributions
- The idea itself is interesting, but there is no new technique introduced

The proposed idea of learning relevant columns (MISs) from a series of problems would make sense when such similar problems are available. But, the approach has the limitation that it is not suitable to apply for new problems obtained from different distributions. The learning techniques themselves are quite standard. So, I feel that the technical contribution of the paper is not significantly strong though the idea itself is promising.
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written. The technical results seem novel. 
summary_of_the_review:  The idea itself is promising, but the technical contribution of the paper seem not significantly strong.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper introduces an approach for integrating machine learning predictions with the column generation approach for solving combinatorial optimization problems. Specifically, the paper designs a set of features that can be used to predict whether a column belongs to an optimal integral solution, leading to machine learning augmented algorithms that construct integral solutions for combinatorial optimization problems.

The reviewers appreciated the approach of the paper and the novel integration of machine learning predictions with classical integer programming approaches for combinatorial optimization. Some of the reviewers were concerned about the general applicability of the proposed approach, and these concerns were satisfactorily addressed by the author response. The reviewers also felt that the main idea is interesting and novel but the techniques are somewhat limited.
justification_for_why_not_higher_score: The paper makes an interesting contribution that bridges combinatorial optimization and machine learning. The idea itself is novel and interesting, but the techniques are somewhat limited.
justification_for_why_not_lower_score: The overall approach is broadly applicable and it may lead to further progress.
Decision: Accept: poster