Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes a GNN-based method for objective space decomposition (ODA) in IP problems.
ODA is relevant when multiple objectives are to be optimized, but solvers usually only consider a single objective at a time.
The ODA method decides which objective to optimize next to best (closest and fastest) approximate the true Pareto front.
The new method models the IP problem as a graph and applies a GNN to classify which objective to optimize next. The network is trained using behavioral cloning, i.e. supervised learning.
Experiments show that the new method is competitive to or outperforming existing ODA techniques and evolutionary multi-objective algorithms.
strengths_and_weaknesses: The method is strictly designed for the ODA approach to be solved, which allows it to gains the performance improvements, but does perhaps not leave much room for further generalization. However, since ODA is already a general problem, this should be okay.
The approach itself is well motivated and intuitive enough to understand, adopt and potentially reproduce.
An advantage is that the method is independent of the solver itself.
My main concern is on the training of the method which requires a dataset for supervised learning. I'd be curious to know more about the challenges and tradeoffs in building this dataset (it is briefly discussed, but it seems to be one of the main efforts in setting this up for practical use).

If I understood it correctly, the model is trained for a specific problem and instance size, e.g. MOKP with 3 objectives and 100 items.
Is it a limitation of the GNN that the size of the instances must be fixed? I understand it to some degree for the objectives, even though generalization is tested later, but one advantage of using GNNs should also be a more flexible structure in the instance sizes themselves.
While some generalization capabilities are shown, the method is, as described, mostly fixed to specific instance sizes. It is unclear if this is a necessity, a design decision, or so far the first step in generalizing the technique.

questions: 1. Can you elaborate on the tradeoffs for collecting the dataset? Do you think an online learning approach would be competitive?
2. Why do you fix the instance sizes for training?
3. What would it take to generalize the model further, i.e. being problem-independent and learning from a joint dataset for MOKP+MOAP+other problems?

limitations: Some limitations of the work are discussed (solving intractable problems) as well as the cases where the proposed method is outperformed by the comparison techniques.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This study proposes a learning-based solver for effectively solving multi-objective integer programming (MOIP) by improving the bounded-time performance of objective-space decomposition algorithms (ODAs). Existing ODA has to solve large amounts of IPs and it incurs unnecessary and redundant computation. To reduce unnecessary computation, the current study proposed Markov Decision Process (MDP) framework for modeling the reduction procedure and learning the optimum reduction policy using the graph representation learning-based state representation. 
strengths_and_weaknesses: <Strength>

It deals with the multi-objective IP problem that has not been dealt with relatively well in the field of artificial intelligence.


<Weakness>

The definition of MDP for solving the process of ODAs is not clear. The definition of the state and action sounds make sense; however, it is not clear how the reward can be defined. Is there any sequential effect in the ODA solving process? For example, the decision at the current step will have a compounding long-term effect in obtaining the final solution for MOIP?

It deals with the multi-objective IP problem that has not been dealt with relatively well in the field of artificial intelligence.

questions: 1. The definition of the state and action sounds make sense; however, it is not clear how the reward can be defined. Is there any sequential effect in the ODA solving process? For example, the decision at the current step will have a compounding long-term effect in obtaining the final solution for MOIP?

2. In line 228 of page 6, the paper says “We sample the state-action data in ODAs by using the optimal policy in Definition 3 as the oracle and then train the policy network in a supervised fashion”. Was the optimal policy is derived by solving the MDP formulated or the optimum policy can be always simply induced? 

3. What was the motivation for employing imitation learning instead of reinforcement learning? Since the paper presented the MDP formulation (although it is not complete), is it also possible to employ Reinforcement learning?
 
4. The imitation learning forces the GNN policy to overfit to optimum action (labels), which can possibly limit the generalization capability compared to the RL method inherently conducting excessive exploration. What do you think where the power of generalization capability comes from? 

5. How to choose a local upper point that will be discarded or retained by the learned policy? It seems that the set of nondominated points matters while the sequence for selecting them is not important in determining the next candidate solution. If it is true, how to impose such permutation invariance in the selected nondominated points?

limitations: •	It seems that ODA, one of the methods of solving the MOIP problem, has learned the policy to imitate the problem-solving method, but it did not clearly suggest how the presented method improved the performance and computation speed of the solution rather than just using ODA.

•	In order to apply imitation learning, it is necessary to obtain labeled data by optimally solving various problems. There are no experiments on whether there are any difficulties in obtaining the corresponding data, and how the performance changes depending on the size of the labeled data.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work proposes a learning-based approach to enhance objective-space decomposition (ODA) for solving multi-objective integer programs (MOIP). Specifically, it builds a novel two-stage GNN as a parameterized policy to learn the reduction rule for ODA by imitation learning. The proposed GNN model takes the instance information (decision variables, constraints, and objectives) as input, and then adaptively discards local upper bounds (to update the search region) without calling an IP solver in ODA. In this way, it can fast detect and eliminate the infeasible and repetitive IPs, and hence reduce redundant computation. Experimental results show that the proposed method can significantly reduce the runtime for a state-of-the-art ODA, and can be generalized well to solve problems with larger sizes or more objectives.
strengths_and_weaknesses: **Strengths:**

+ This work is generally well-written and easy to follow.

+ MOIP problems can be found in many real-world applications, while they are usually very hard to be solved optimally. Learning-assisted method for solving MOIP is an important research topic, and this work makes a timely contribution in this direction.

+ In my understanding, it is the first work on learning-assisted MOIP. The proposed GNN-based policy to enhance ODA is sound and novel, which can inspire more future work.

+ It is promising that the learned policy can generalize well to solve problem instances with different sizes and number of objectives, which could be important for real-world applications.

**Weaknesses:**

**1. Imitation Learning:** The proposed method needs to be trained by behavioral cloning, which means 1) it requires a carefully well-designed algorithm (e.g., ODA-T/B/K) to generate the supervised data set. 2) More importantly, the data generated by ODA with a time limit L is indeed not a perfect teacher for behavioral cloning. Since all the ODAs are not designed and optimized for bounded time performance, their behavior (the state-action pairs) for the first L time is not the optimal policy under time limit L. 

Since the generic algorithm procedure of ODA can be encoded as a MDP, is it possible to use reinforcement learning to train the model? Would the RL-based approach find a better policy for bounded time performance that is aware of the time limit T？

**2. Performance with Different Time Limits:** It seems that the proposed method is both trained and tested with a single fixed time limit T = 1000s for all problems. However, in practice, the applications could have very different run time limits. Will the proposed method generalize well to different time limits (such as 1/10/100/2000/5000s)?

**3. Comparison with PMOCO:** PMOCO is the only learning-based approach in the comparison, but it has a very small cardinality (feasible points) for most problems. Its approximated Pareto front is also relatively sparse (which means a small set of solutions) in Figure A.3. This result is a bit counter-intuitive. 

In my understanding, PMOCO is a construction-based neural combinatorial optimization algorithm, of which one important advantage is the very fast run time. The PMOCO paper [1] reports it can generate 101 solutions for 100 MOKP(2-100) instances (hence 10,100 solutions in total) in only 15s, and 10,011 solutions for 100 MOTSP(3-100) instances (hence 1,001,100 solutions in total) in 33 minutes (~2000s). In this work, with a large time limit of 1,000s, I think POMO should be able to generate a dense set of solutions for each instance.

In addition, while a dataset with 100 instances could provide enough supervised ODA state-action pairs (with a time limit L = 1000s for each instance) for imitation learning, it is far from enough for PMOCO's RL-based training. Since PMOCO does not require any supervised data and the MOKP instances can be easily generated on the fly, is it more suitable to train PMOCO under the same wall-clock time with the proposed method? 

[1] Pareto set learning for neural multi-objective combinatorial optimization. ICLR 2022.

questions: - In my understanding, the proposed method is only trained with the data generated by ODA-T. Is it possible to train it with data from ODA-T/B/K at the same time? Will this approach lead to more robust performance?

- The proposed method can outperform all ODAs with a bounded time, but it is also interesting to know its unbounded performance. Given enough run time, how many valid IPs could be wrongly eliminated by the proposed method?
limitations: The limitations of this work are 1) the requirement of ODAs and a well-designed IP solver; 2) it loses the guarantee for finding the whole Pareto front. They have been properly discussed in the paper (see remark at the end of Section 4.1 and Conclusion).

I do not see any potential negative societal impact of this work.
review_title: null

Meta-review: metareview: 
In this paper, the authors exploit imitation learning with a two-stage GNN to learn the reduction rule for ODA to accelerate the solver and reduce the unnecessary computation. The authors evaluate the performances of the proposed method and demonstrate the advantages. 


In sum, this paper consider an interesting application of machine learning for optimization and provide a promising solution. All reviewers provide relatively positive feedback of this submission. 

Please consider the reviewers' suggestions to improve the submission:

- Justify the MDP modeling with concrete definition of the state and action for the reduction rule for ODA. 

- Specify the data set construction and justify the generalization ability in the imitation learning. 
- Provide comprehensive comparison, especially with PMOCO. 
 
confidence: Less certain
Decision: Accept