Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper suggest the n-times coverage problem (a natural generalization of set-cover where items need to be covered n>1 times by the sets we choose) and motivates it with an application for the design of COVID vaccines. This application involves some ML pipeline, and this new combinatorial optimization problem helps with one of the steps.

The problem is shown to be not-submodular, and therefore the most standard methods don't quite work. Nonetheless, the authors present a greedy algorithm to get a reasonable approximation.

The paper evaluates the quality of their algorithm on artificial data and shows that it outperforms the more standard greedy method. Then they show the impact of this improvement for vaccine design.
main_review: The problem that they introduce and the solution are natural. I would say this part of the paper is interesting but unsurprising. Such generalizations are common and the tricks that this paper employes are not unusual. Still, it's a good contribution.

The stronger contribution in my view is the observation that this problem helps in the COVID vaccine design pipeline. I'm far from being an expert on this, so I'm not confident in my assessment, but it seems strong.




summary_of_the_review: This is a nice paper with good contribution for the (ML based) pipeline for COVID vaccine design.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Update: I have read the author feedback and other reviews. Based on the more detailed comparison to existing methods, I have updated several of my scores.

---

In this work, the authors propose a variant of the set covering problem which aim to formalize peptide-based vaccine design as an optimization problem. The authors first formulate the problem and then draw connections to other set covering problems; they then show that the problem is NP-complete. They then propose a greedy algorithm to perform the optimization. A set of experiments suggests the proposed approach outperforms the formulations considered by the authors.
main_review: The novelty of the proposed work is limited. A large number of existing approaches have formulated element-based vaccine design as a discrete optimization problem (e.g., [Malone et al., Scientific Reports 2020], [Theiler and Korder, Statistics in Medicine 2018], [Schulber and Kohlbacher, Genome Medicine 2016], [Oyarzun and Kobe, International Journal of Immunogenetics 2015], [Lundegaard et al., Proceedings of the $1^{st}$ ACM International Conference on Bioinformatics and Computational Biology 2010], [Toussaint et al., PLOS Computational Biology 2008]). While the proposed approach may have advantages compared to those formulations, the authors do not provide any context of how their formulation differs from the well-established approaches. So it is difficult to gauge the novelty of the proposed approach with respect to current approaches.

In terms of technical soundness, the theoretical contributions seem sound. I did not thoroughly verify the proofs of NP-completeness, but the argument seems sound. The greedy algorithm for addressing the optimization problem does not have any associated guarantees, but it also seems reasonable.

In terms of biology, the formulation is not very meaningful. For example, MHC (HLA in human) I leads to an entirely different immune response than MHC II (cytotoxic/cell killing for MHC I compared to recruiting various other immune cells for MHC II). A good T-cell vaccine should do both. Additionally, some haplotypes are more common than others, and the proposed approach ignores such pair-wise correlations. Thus, while it is clear that the formulated problem lends itself well to a set covering formulation, it is not clear to me that this formulation is meaningful.

Considering the experimental results, some obvious baselines are missing. For example, a greedy hill climbing with random restarts approach is a typical way to approach such discrete optimization problems, so it would be useful to show how much the proposed margin-based algorithm outperforms that. Further, since the exact solution to the problem can be formulated as an ILP, modern anytime solvers (which also offer guaranteed bounds), such as SCIP [Achterberg, Mathematical Programming Computation 2009] or LMHS [Saikko et al., SAT 2016], should be included in the comparison.

The paper is generally clear and well written. The references are inconsistently formatted. It would be helpful to increase the font size on the figures.

The reproducibility and provided resources of this work are in line with the field. An expert would likely be able to take the formulations in the paper and turn them into code.
summary_of_the_review: Considering the lack of theoretical novelty and biological accuracy, it is difficult for me to see the impact of the work as it is currently presented.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper introduces a variant/generalization of multi set multi cover problem, where the aim is to maximize the weight of the elements covered at least n times by up to k overlays (subsets of a given input familiy of sets over the elements' universe). The authors show that the objective function is not submodular, hence does not admit a classical greedy approach. They show an ILP formulation that provides an optimal solution but not efficiently. They propose a greedy approach based on maiximization of marginal gains endowed with a look-ahead tie breaking that should prevent failure to attain n-coverage because of wrong initial choices guided by the sole marginal gain maximization objective. 
The problem is meant to model vaccine design and show empirical evaluation on two toy data sets and presenting comparisons between the greedy approach and the ILP approach for a covid 19 vaccine. 
main_review: The new problem appears to be interesting. I am not aware of a problem with such a structure, although I would not be surprised if there were previous studies on this framework in the area of combinatorial design or also in one of the several variants of group testing.  
The experimental evaluation of the approach in on a currently hype area is also valuable. 
There are a couple of concerns I have: 
- the pseudocode for algorithm 1 is not clear to me. It seems that the two inner for loop will always end up constructing K^t = A.
- in the empirical study on the toy examples, the weights are not used, which is strange since it is what makes the problem different from the  classical variants of set cover. It is also not clear to me from the description where the weights enter in the evaluations of the design for covid 19. The authors only mention coverage and it is not clear whether that is meant in terms of sum of weights or what else. 
Due to these concerns I am not giving a fully acceptance to the paper but I am willing to receonsider my score on the basis of the authors' reply.

Minor problems: the figures are very small and it is very difficult to appreaciate on paper what they show. 
summary_of_the_review: Strenght: The paper offers an interesting and apparently unexplored variant of set cover that can model a vaccin design problem. The evaluation seem to show good performance. 
Weaknesses: there seems to be something unclear in the pseudocode of the greedy algorithm that prevents me from fully assess its behaviour; the importance of the weights in the experiments is not clearly discussed (without this, the problem reduces to known Multi-set multi cover)
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The submission is concerned with vaccine design and proposes to model the task as a combinatorial optimization problem that is essentially a generalization of set cover. The authors describe two algorithms: A marginally greedy algorithm using beam search and a mixed integer linear programming approach.

More precisely, the combinatorial problem consists in covering weighted elements (the population) with overlays (peptides) while maximizing the total weight of those elements that are covered at least n times. Each overlay may only be used once, but may cover the same element multiple times. In total, no more than k overlays may be chosen.

Additionally, the submission features a machine learning based tool that predicts the effectiveness of the designed vaccine.
main_review: As far as algorithms are concerned, the greedy approach is standard for set-covering type problems, even though it seems that it has not been used for this particular set covering version before. Most of the ILP formulation seems standard as well, however, it is not clear how the objective function may be linearized and this requires additional work and Big-M-constraints.

The vaccine design process seems sound, building on published work. Experimental results show that the ILP comes close close to the optimum solution. Finally, the resulting vaccine designs are succcessfully compared to designs from the literature.

As a minor comment, I did not fully understand the pseudo-code for the beam search: Initally, B^0 is empty, so the beam search (outer for-loop) iterates over an empty set and will not build a candidate set. Wouldn't then B^{t+1} be empty as well?
summary_of_the_review: The submission is built with a clear application in mind. It provides two reasonable approaches for a well-modeled problem. There are little theoretical contributions, but I found the practical contribution well-executed and convincing.
review_title: null

Meta-review: The paper introduces the maximum n-times coverage, a new NP-hard (and non-submodular) optimization problem. It is shown that the problem can naturally arise in ML-based vaccine design, and two heuristics are given to solve the problem. The results are used to produce a pan-strain COVID vaccine. 

The reviewers and I think that this is an interesting paper with a compelling application. There were some concerns about theoretical novelty and biological accuracy but these were addressed during the author response period. Given this, I am delighted to recommend acceptance. Please incorporate the feedback in the reviews in the final version of the paper.
Decision: Accept (Poster)