Differentiable Integer Linear Programming

## Abstract

Abstract Integer Linear Programming (ILP) has been proposed as a formalism for encoding precise structural and semantic constraints for Natural Language Inference (NLI).
However, traditional ILP frameworks are non-differentiable, posing critical challenges for the integration of continuous language representations based on deep learning. In this paper, we introduce a novel approach, named Diff-Comb Explainer, a neuro-symbolic architecture for explanation-based NLI based on Differentiable BlackBox Combinatorial Solvers (DBCS).
Differently from existing neuro-symbolic solvers, Diff-Comb Explainer does not necessitate a continuous relaxation of the semantic constraints, enabling a direct, more precise, and efficient incorporation of neural representations into the ILP formulation. Our experiments demonstrate that Diff-Comb Explainer achieves superior performance when compared to conventional ILP solvers, neuro-symbolic black-box solvers, and Transformer-based encoders. Moreover, a deeper analysis reveals that Diff-Comb Explainer can significantly improve the precision, consistency, and faithfulness of the constructed explanations, opening new opportunities for research on neuro-symbolic architectures for explainable and transparent NLI in complex domains. Keywords: Natural Language Inference, Neuro-Symbolic AI, Constrained Optimization

## 1.   Introduction

Given a question and a possible candidate answer expressed in natural language (which we refer to as *hypothesis*), ILP-based Natural Language Inference (NLI) aims to construct an explanation graph consisting of interconnected sentences to support and deduce the hypothesis (Figure 1).

To contrast the lack of interpretability of large deep learning models, ILP has been proposed as a formalism to build transparent and explainable NLI models, able to leverage explicit semantic constraints to address downstream inference tasks. ILP-based solvers, in fact, provide a viable mechanism to encode explicit and controllable assumptions about the structure of the explanations (Khashabi et al., ; Khot et al., ; Khashabi et al., ; Thayaparan et al., ).

However, existing ILP frameworks are non-differentiable and cannot be integrated as part of a broader deep learning architecture (Paulus et al., ; Pogančić et al., ). Therefore, these approaches have been so far limited by the exclusive adoption of hard-coded heuristics and cannot be easily optimised end-to-end to achieve performance comparable to deep learning counterparts (Thayaparan et al., ; Khashabi et al., ). At the same time, existing solutions for the integration of combinatorial solvers and deep learning require a continuous approximation of the semantic constraints, which inevitably lowers the expressive power of the ILP formulation and, as a consequence, the precision in the downstream inference process Thayaparan et al. ().

Figure: Figure 1: Example of a hypothesis (i.e., question + answer) and an explanation graph constructed via an ILP-based NLI model (Xie et al., ; Jansen et al., ).

To address these challenges, this paper proposes an end-to-end methodology for the integration of Differentiable BlackBox Combinatorial Solvers (DBCS) (Pogančić et al., ) into explanation-based NLI architectures. DBCS, in fact, enables an efficient approximation of the gradient for end-to-end optimisation, without the need for a continuous relaxation of the original ILP formulation. Specifically, we demonstrate how a combinatorial optimization solver can be adopted as a composable building block in a broader NLI architecture with Transformers Devlin et al. ().

In summary, the contributions of this paper are as follows:

- 1.
We propose Diff-Comb Explainer, a novel ILP-based NLI solver that combines a differentiable black box combinatorial solver with Transformer-based encoders, enabling end-to-end differentiability without the need for a continuous relaxation of the ILP formulation.
- 2.
We empirically demonstrate that Diff-Comb Explainer achieves superior performance on both explanation generation and answer selection when compared to differentiable and non-differentiable counterparts.
- 3.
We demonstrate that thanks to the preservation of the original ILP formulation, Diff-Comb Explainer better reflects the underlying explanatory inference process leading to the final answer prediction, outperforming existing combinatorial solvers in terms of faithfulness and consistency.(^1^11Code and data available at [https://github.com/neuro-symbolic-ai/diff_comb_explainer](https://github.com/neuro-symbolic-ai/diff_comb_explainer))

## 2.   Related Work

#### Constraint-based multi-hop inference

ILP has been applied for structured representation (Khashabi et al., ) and over semi-structured representation extracted from text (Khot et al., ; Khashabi et al., ). Early approaches were unsupervised. However, recently Thayaparan et al. () proposed the ExplanationLP model optimised towards answer selection via Bayesian optimisation. ExplanationLP was limited to fine-tuning only nine parameters and used pre-trained neural embedding. Diff-Explainer (Thayaparan et al., ) was the first approach to integrate constraints into a deep-learning network via Differentiable Convex Optimisation Layer (Agrawal et al., ) by approximating ILP constraints using Semi-definite programming. (Lovász and Schrijver, ). Differently from our approach, however, *Diff*-Explainer requires a continuous approximation of the semantic constraints, a feature that inevitably affects the precision in the downstream inference process.

#### Hybrid reasoning with Transformers

Clark et al. () proposed “soft theorem provers” operating over explicit theories in language. This hybrid reasoning solver integrates natural language rules with transformers to perform deductive reasoning. Saha et al. () improved on top of it, enabling the answering of binary questions along with the proofs supporting the prediction. The multiProver (Saha et al., ) evolves on top of these conceptions to produce an approach that is capable of producing multiple proofs supporting the answer. While these hybrid reasoning approaches produce explainable and controllable inference, they assume the existence of natural language rules and have only been applied to synthetic datasets. On the other hand, our approach does not require extensive rules set and can tackle complex scientific and commonsense NLI problems.

## 3. Diff- Comb Explainer: Differentiable Integer Linear Programming Solver for Explanation-Based Natural Language Inference

Figure: Figure 2: End-to-end architectural diagram of Diff-Comb Explainer. The integration of Differentiable Blackbox Combinatorial solvers will result in better explanation generation and answer prediction.

ILP-based NLI is typically applied to multiple-choice question answering problems (Khashabi et al., ; Khot et al., ; Khashabi et al., ; Thayaparan et al., ). Given a Question ($Q$) and a set of candidate answers $C=\{c_{1},~{}c_{2},~{}c_{3},~{}\dots,~{}c_{n}\}$ the aim of the task is to select the correct answer $c_{ans}$.

In order to achieve this, ILP-based approaches convert question-answer pairs into a list of hypotheses $H=\{h_{1},~{}h_{2},~{}h_{3},~{}\dots,~{}h_{n}\}$ (where $h_{i}$ is the concatenation of $Q$ with $c_{i}$) and typically adopt a retrieval model (e.g: BM25, FAISS (Johnson et al., )), to select a list of candidate explanatory facts $F=\{f_{1},~{}f_{2},~{}f_{3},~{}\dots,~{}f_{k}\}$. Then construct a weighted graph $G=(V,E,W)$ with edge weights $W:E~{}\rightarrow~{}\mathbb{R}$ where $V=~{}\{\{h_{i}\}~{}\cup~{}F\}$, edge weight $W_{ik}$ of each edge $E_{ik}$ denote how relevant a fact $f_{k}$ is with respect to the hypothesis $h_{i}$.

Given this premise, ILP-based NLI can be defined as follows (Thayaparan et al., ):

###### Definition 3.1 ( ILP-Based NLI ) .

Find a subset $V^{*}\subseteq V$, $h\in V^{*}$ and $E^{*}\subseteq E$ such that the induced subgraph $G^{*}=(V^{*},E^{*})$ is connected, weight $W[G^{*}=(V^{*},~{}E^{*})]:=\sum_{e\in E^{*}}W(e)$ is maximal and adheres to set of constraints $M_{c}$ designed to emulate multi-hop inference. The hypothesis $h_{i}$ with the highest subgraph weight $W[G^{*}=(V^{*},~{}E^{*})]$ is selected to be the correct answer $c_{ans}$.

As illustrated in Figure 2, Diff-Comb Explainer has 3 major parts: Graph Construction, Subgraph Selection and Answer/Explanation Selection. In Graph Construction, for each candidate answer $c_{i}$ we construct a graph $G^{i}=(V^{i},~{}E^{i},~{}W^{i})$ where $V^{i}=\{h_{i}\}\cup\{F\}$ and the weights $W^{i}_{ik}$ of each edge $E^{i}_{ik}$ denote how relevant a fact $f_{k}$ is with respect to the hypothesis $h_{i}$. These edge weights ($W^{i}_{ik}$) are calculated using a weighted ($\theta$) sum of scores calculated using transformer-based ($STrans$) embeddings and lexical models.

In the Subgraph Selection step, for each $G^{i}$, Differentiable Blackbox Combinatorial Solver (DBCS) with constraints are applied to extract subgraph $G^{*}$. In this paper, we adopt the constraints proposed for ExplanationLP (Thayaparan et al., ) for ensuring a fair comparison between different models. ExplanationLP explicit abstraction by grouping facts into abstract ($F_{A}$) and grounding ($F_{G}$). Abstract facts are the core scientific statements that a question is attempting to test, and grounding facts link concepts in the abstract facts to specific terms in the hypothesis (e.g. taxonomic relations). For example, in Figure 1 the core scientific fact is about the nature of convex lens and how they refract light ($F_{1}$). Grounding Facts $F_{2},F_{3},F_{4}$ are usually is-a relations that help to connect abstract concepts to concrete instances in the hypothesis.

Finally, in Answer/Explanation Selection the model predicts the final answer $c_{ans}$ and relevant explanations $F_{exp}$. During training time, the loss is calculated based on gold answer/explanations to fine-tune the transformers ($STrans$) and weights ($\theta$). The rest of the section explains each of the components in detail.

###### Definition 3.1 ( ILP-Based NLI ) .

### 3.1.   Graph Construction

In order to facilitate the construction of inference chains, the retrieved facts $F$ are classified into grounding facts $F_{G}=\{f^{g}_{1},f^{g}_{2},f^{g}_{3},...,f^{g}_{l}\}$ and abstract facts $F_{A}=\{f^{a}_{1},f^{a}_{2},f^{a}_{3},...,f^{a}_{m}\}$ such that $F=F_{A}\cup F_{G}$ and $l+m=k$ Thayaparan et al. ().
Here, We use two relevance scoring functions to calculate the edge weights: semantic and lexical scores. We use a Sentence-Transformer (STrans) (Reimers et al., ) bi-encoder architecture to calculate the semantic relevance. The semantic relevance score from STrans is complemented with the lexical relevance score. The semantic and lexical relevance scores are calculated as follows:

#### Semantic Relevance ( s 𝑠 s italic_s )

: Given a hypothesis $h_{i}$ and fact $f_{j}$ we compute sentence vectors of $\vec{h_{i}}^{\,}=STrans(h_{i})$ and $\vec{f_{j}}^{\,}=STrans(f_{j})$ and calculate the semantic relevance score using cosine-similarity as follows:

$$ $s_{ij}=S(\vec{h_{i}}^{\,},~{}\vec{f_{j}}^{\,})=\frac{\vec{h_{i}}^{\,}\cdot\vec {f_{j}}^{\,}}{\|\vec{h_{i}}^{\,}\|\|\vec{f_{j}}^{\,}\|}$ (1) $$

#### Lexical Relevance ( l 𝑙 l italic_l )

: The lexical relevance score of hypothesis $h_{i}$ and $f_{j}$ is given by the percentage of overlaps between unique terms (here, the function $trm$ extracts the lemmatized set of unique terms from the given text):

$$ $l_{ij}=L(h_{i},~{}f_{j})=\frac{|trm(h_{i})\cap trm(f_{j})|}{max(|trm(h_{i})|,| trm(f_{j})|)}$ (2) $$

Given the above scoring function, we construct the edge weights matrix ($W^{i}$) for each hypothesis $h_{i}$ as follows:

$$ $\small W^{i}§§_{jk}=\begin{cases}-\theta_{gg}l_{jk}&(j,k)\in F_{G}\\ -\theta_{aa}l_{jk}&(j,k)\in F_{A}\\ \theta_{ga}l_{jk}&j\in F_{G},k\in F_{A}\\ \theta_{qgl}l_{jk}+\theta_{qgs}s_{jk}&j\in F_{G},k={h_{i}}\\ \theta_{qal}l_{jk}+\theta_{qal}s_{jk}&j\in F_{A},k={h_{i}}\\ \end{cases}$ (3) $$

Here relevance scores are weighted by $\theta$ parameters which are clamped to $[0,1]$.

### 3.2.   Subgraph Selection

Given the above premises, the objective function is defined as:

$$ $\min~{}\qquad-1(W^{i}\cdot y^{i})$ (4) $$

We adopt the edge variable $y^{i}\in\{0,1\}$ where $y^{i}_{j,k}$ ($j\neq k$) takes the value of 1 if edge $E^{i}_{jk}$ belongs to the subgraph and $y^{i}_{jj}$ takes the value of 1 iff $V^{i}_{j}$ belongs to the subgraph.

Given the above variable, the constraints are defined as follows:

#### Answer selection constraint

The candidate hypothesis should be part of the induced subgraph:

$$ $\displaystyle\sum_{j~{}\in~{}\{h_{i}\}}y^{i}_{jj}$ $\displaystyle=1$ (5) $$

#### Edge and Node selection constraint

If node $V^{i}_{j}$ and $V^{i}_{k}$ are selected then edges $E^{i}_{jk}$ and $E^{i}_{kj}$ will be selected. If node $V^{i}_{j}$ is selected, then edge $E_{jj}$ will also be selected:

$$ $\displaystyle y^{i}_{jk}\leq$ $\displaystyle~{}y^{i}_{jj}$ $\displaystyle\forall~{}(j,k)\in E$ (6) $\displaystyle y^{i}_{jk}\leq$ $\displaystyle~{}y_{kk}$ $\displaystyle\forall~{}(j,k)\in E$ (7) $\displaystyle y^{i}_{jk}\geq$ $\displaystyle~{}y_{jj}+y_{kk}-1$ $\displaystyle\forall~{}(j,k)\in E$ (8) $$

#### Abstract fact selection constraint

Limit the number of abstract facts selected to $M$:

$$ $\displaystyle\sum_{i}y^{i}_{jj}\leq$ $\displaystyle~{}M$ $\displaystyle\forall j\in F_{A}$ (9) $$

### 3.3.   Adopting Differentiable Blackbox Combinatorial Optimisation Solvers

The subgraph selection problem can be written in the following ILP canonical form:

$$ $\min_{y^{i}\in\{0,1\}}\,-(W^{i}\cdot y^{i})\qquad\text{subject to}\qquad Ay^{i }\leq b,$ (10) $$

where $A=[a_{1},\ldots,a_{m}]\in\mathbb{R}^{m\times n}$ is the matrix of constraint coefficients and $b\in\mathbb{R}^{m}$ is the bias term. The output of the solver $g(W^{i})$ returns the argmin${}_{y^{i}\in\{0,1\}}$ of the integer problem.

Differentiable Combinatorial Optimisation Solver (Pogančić et al., ) (DBCS) assumes that $A$, $b$ are constant and the task is to find the $\mathrm{d}L/\mathrm{d}y^{i}$ given global loss function $L$ with respect to solver output $y^{i}$ at a given point $\hat{y}^{i}=g(\hat{W}^{i})$. However, a small change in $W$ is typically not going to change the optimal ILP solution resulting in the true gradient being zero. DBCS provides a theoretical framework that can potentially make any black box combinatorial solver differentiable. In this paper, we adopt the proposed algorithm as following to design the forward/backward pass:

Figure: Algorithm 1 Forward and Backward for DBCS

Here the hyper-parameter $\lambda_{dbcs}>0$ controls the trade-off between informativeness of the gradient and faithfulness to the original function.

### 3.4.   Answer and Explanation Selection

The solved adjacency variable $\hat{y}^{i}$ represents the selected edges for each candidate answer choice $c_{i}$. Not all datasets provide gold explanations. Moreover, even when the gold explanations are available, they are only available for the correct answer with no explanations for the wrong answer.

In order to tackle these shortcomings and ensure end-to-end differentiability, we use the softmax ($\sigma$) of the objective score ($\hat{W}^{i}\cdot\hat{y}^{i}$) as the probability score for each candidate answer.

We multiply each objective score $\hat{W}^{i}\cdot\hat{y}^{i}$ value by the temperature hyperparameter ($T$) to obtain soft probability distributions $\gamma^{i}$ (where $\gamma^{i}=(\hat{W}^{i}\cdot\hat{y}^{i})\cdot T$). The aim is for the correct answer $c_{ans}$ to have the highest probability.

In order to achieve this, we use the cross entropy loss $l_{c}$ as follows to calculate the answer selection loss $\mathcal{L}_{ans}$ as follows:

$$ $\begin{split}\mathcal{L}_{ans}=l_{c}(\sigma(\gamma^{1},~{}\gamma^{2},~{}\cdots ~{}\gamma^{n}),~{}c_{ans})\end{split}$ (11) $$

If gold explanations are available, we complement $\mathcal{L}_{ans}$ with explanation loss $\mathcal{L}_{exp}$. We employ binary cross entropy loss $l_{b}$ between the selected explanatory facts and gold explanatory facts $F_{exp}$ for the explanatory loss as follows:

$$ $\mathcal{L}_{exp}=l_{b}(\hat{y}^{ans}[f_{1},~{}f_{2},~{}\dots,~{}f_{k}],~{}F_{ exp})$ (12) $$

We calculate the total loss ($\mathcal{L}$) as weighted by hyperparameters $\lambda_{ans}$, $\lambda_{exp}$ as follows:

$$ $\mathcal{L}=\lambda_{ans}\mathcal{L}_{ans}+\lambda_{exp}\mathcal{L}_{exp}$ (13) $$

## 4.   Empirical Evaluation

### 4.1.   Answer and Explanation Selection

**Table 1: Comparison of explanation and answer selection of Diff-Comb Explainer against other baselines. Explanation Selection was carried out on the dev set as the test explanation was not public available.**
| Model | Explanation Selection (dev) | Answer Selection (test) |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Precision | Explanatory Consistency | Faithfulness |  |  |  |  |  |
| @2 | @1 | @3 | @2 | @1 |  |  |  |
| Baselines |  |  |  |  |  |  |  |
| BERTBase | - | - | - | - | - | - | 45.43 |
| BERTLarge | - | - | - | - | - | - | 49.63 |
| Fact Retrieval (FR) Only | 30.19 | 38.49 | 21.42 | 15.69 | 11.64 | - | - |
| BERTBase + FR | - | - | - | - | - | 52.65 | 58.06 |
| BERTLarge + FR | - | - | - | - | - | 51.23 | 59.32 |
| ExplanationLP | 40.41 | 51.99 | 29.04 | 14.14 | 11.79 | 71.11 | 62.57 |
| Diff-Explainer | 41.91 | 56.77 | 39.04 | 20.64 | 17.01 | 72.22 | 71.48 |
| Diff-Comb Explainer |  |  |  |  |  |  |  |
| - Answer selection only | 45.75 | 61.01 | 49.04 | 29.99 | 18.88 | 73.37 | 72.04 |
| - Answer and explanation selection | 47.57 | 63.23 | 43.33 | 33.36 | 20.71 | 74.47 | 73.46 |

We use the WorldTree corpus (Xie et al., ) for the evaluation of explanation and answer selection. The 4,400 questions and explanations in the WorldTree corpus are split into three different subsets: *train-set*, *dev-set* and *test-set*. We use the *dev-set* to assess the explainability performance since the explanations for *test-set* are not publicly available. The background knowledge consists of 5000 abstract facts from the WorldTree table store (WTree) (Xie et al., ) and over 100,000 is-a grounding facts from ConceptNet (Speer et al., ).

#### Baselines:

We use the following baselines to compare against our approach for the WorldTree corpus:

- 1.
BERTBase and BERTLarge (Devlin et al., ): To use BERT for this task, we concatenate every hypothesis with $k$ retrieved facts, using the separator token [SEP]. We use the HuggingFace (Wolf et al., ) implementation of BertForSequenceClassification, taking the prediction with the highest probability for the positive class as the correct answer. Notice that Diff-Comb Explainer adopts the same neural architecture for sentence representation and inference.
- 2.
ExplanationLP: Non-differentiable version of ExplanationLP. Using the constraints stated in Section 3, we fine-tune the $\theta$ parameters using Bayesian optimization and frozen STrans representations following Thayaparan et al. (). This baseline aims to evaluate the impact of end-to-end fine-tuning over the non-differentiable solver.
- 3.
Diff-Explainer: Diff-Explainer has already exhibited better performance over existing ILP-based approaches including TableILP (Khashabi et al., ), TupleILP (Khot et al., ) and graph-based neural approach PathNet (Kundu et al., ) and represents the current state-of-the-art combinatorial solver in the field. To allows for a direct comparison with our approach, we use the ExplanationLP constraints with Diff-Explainer. We adopt the same set of hyperparameters and knowledge base reported in Thayaparan et al. ().

#### Evaluation Metrics.

The answer selection is evaluated using accuracy. For evaluation of explanation selection, we use Precision$@K$. In addition to Precision$@K$, we introduce two new metrics to evaluate the truthfulness of the answer selection to the underlying inference. The metrics are as follows:

#### Faithfulness

The aim of faithfulness is to measure the extent to which correct answer predictions are indeed derived from correct explanations and, vice-versa, wrong answer predictions are derived from wrong explanations. Given the set of correct answers $A_{Q_{c}}$, wrong answers $A_{Q_{w}}$, answers with at least one correctly retrieved explanation sentence $A_{Q_{1}}$ and set of questions where no correct explanation fact is retrieved $A_{Q_{0}}$, the faithfulness score is defined as follows:

$$ $\frac{|A_{Q_{w}}\cap A_{Q_{0}}|+|A_{Q_{c}}\cap A_{Q_{1}}|}{|A_{Q_{c}}\cup A_{Q _{w}}|}$ (14) $$

A higher faithfulness score implies, therefore, that the underlying inference performed by the model is more in line with the final answer prediction.

#### Explanation Consistency @ ⁢ K @ 𝐾 @K @ italic_K

As similar questions require similar underlying inference (Valentino et al., , ), we expect expect the explanations to reflect the similarity between test instances. Specifically, given a test question $Q_{t}$ and the explanation constructed by the model $E_{t}$, we select the set of Questions $Q^{s}_{t}=\{Q^{1}_{t},~{}Q^{2}_{t},~{}\dots\}$ that have at least $K$ gold explanatory facts overlapping with the gold explanation for $Q_{t}$, $E^{s}_{t}=\{e^{1}_{t},~{}e^{2}_{t},~{}\dots\}$. Given this premise, we measure the explanation consistency$@K$ as follows:

$$ $\frac{\sum_{e^{i}_{t}\in E^{s}_{t}}[e^{i}_{t}\in E_{t}]}{\sum_{e^{i}_{t}\in E^ {s}_{t}}|e^{i}_{t}|}$ (15) $$

Specifically, explanation consistency measures the percentage of overlapping explanatory facts retrieved by the models between hypotheses that share at least $K$ similar gold explanations. Higher explanatory consistency, therefore, implies that the reasoning across similar questions tends to produce similar explanations.

### 4.2.   Results

Table 1 illustrates the explanation and answer selection performance of Diff-Comb Explainer and the baselines. We report scores for Diff-Comb Explainer trained for only the answer and optimised jointly for answer and explanation selection.
Since BERT does not provide explanations, we use facts retrieved from the fact retrieval for the best $k$ configuration ($k=3$) as explanations. We also report the scores for BERT without explanations.

We draw the following conclusions from the results obtained in Table 1 (The performance increase here are expressed in absolute terms):

(1) Diff-Comb Explainer improves answer selection performance over the non-differentiable solver by 9.47% when optimised only on answer selection and 10.89% when optimised on answer and explanation selection. This observation highlights the impact of the end-to-end differentiable framework. We can also observe that strong supervision on explanation selection yields better performance than weak supervision on answer selection only.

(2) Diff-Comb Explainer outperforms the best BERT model by 14.14% on answer selection. This increase in performance demonstrates that integrating constraints with Transformer-based encoders can lead to better NLI performance.

(3) Diff-Comb Explainer outperform the best Diff-Explainer configuration (answer and explanation selection) by 0.56% even in the weak supervision setting (answer only optimization). We also outperform Diff-Explainer by 1.98% in the best setting.

(4) Diff-Comb Explainer shows superior performance in selecting relevant explanations over existing combinatorial solvers. Diff-Comb Explainer outperforms the non-differentiable solver at Precision@K by 8.41% ($k=$1) and 6.05% ($k=$2). Moreover, the proposed approach outperforms Diff-Explainer by 3.63% ($k=$1) and 4.55% ($k=$2). This demonstrates the impact of preserving the original ILP formulation on downstream inference. Finally, the improvement of Precision$@K$ over the Fact Retrieval only (demonstrated with BERT + FR) by 16.98% ($k=$1) and 24.74% ($k=$2) underlines the robustness of our approach to noise propagated by the upstream fact retrieval.

(5) Diff-Comb Explainer exhibits higher Explanation Consistency over the other solvers. This performance shows that the optimization model is learning and applying consistent inference across similar instances. We also outperform the fact retrieval model based on Transformers and fine-tuned on gold explanations.

(6) Answer prediction by black-box models like BERT do not reflect the explanation provided. This fact is indicated by the low Faithfulness score obtained by both BERTBase/BERTLarge. In contrast, the high constraint-based solver’s Faithfulness scores emphasise how the underlying inference reflects on the final prediction. In particular, our approach performs better than the non-differentiable models and Diff-Explainer.

In summary, despite the fact that Diff-Explainer and Diff-Comb Explainer adopts the same underlying set of constraints, the results demonstrate that our model yields better performance, indicating that accurate predictions generated by ILP solvers reflect in better inference performance than sub-optimal counterparts.

### 4.3.   Comparing Answer Selection with ARC Baselines

**Table 2: ARC challenge scores compared with other Fully or Partially explainable approaches trained only on the ARC dataset.**
| Model | Explainable | Accuracy |
| --- | --- | --- |
| BERTLarge | No | 35.11 |
| IR Solver (Clark et al., ) | Yes | 20.26 |
| TupleILP (Khot et al., ) | Yes | 23.83 |
| TableILP (Khashabi et al., ) | Yes | 26.97 |
| ExplanationLP<br>(Thayaparan et al., ) | Yes | 40.21 |
| DGEM (Clark et al., ) | Partial | 27.11 |
| KG^2 (Zhang et al., ) | Partial | 31.70 |
| ET-RR (Ni et al., ) | Partial | 36.61 |
| Unsupervised AHE (Yadav et al., ) | Partial | 33.87 |
| Supervised AHE (Yadav et al., ) | Partial | 34.47 |
| AutoRocc (Yadav et al., ) | Partial | 41.24 |
| Diff-Explainer (ExplanationLP) (Thayaparan et al., ) | Yes | 42.95 |
| Diff-Comb Explainer (ExplanationLP) | Yes | 43.21 |

**Table 3: Example of predicted answers and explanations obtained from our model with different combinatorial solvers.**
| Question (1): Which measurement is best expressed in light-years?:<br>Correct Answer: the distance between stars in the Milky Way. |
| --- |
| ExplanationLP |
| Answer: the time it takes for planets to complete their orbits. Explanations: (i) a complete revolution; orbit of a planet around its star takes 1; one planetary year, (ii) a light-year is used for describing long distances |
| Diff-Explainer |
| Answer: the time it takes for planets to complete their orbits. Explanations: (i) a light-year is used for describing long distances, (ii) light year is a measure of the distance light travels in one year |
| Diff-Comb Explainer |
| Answer: the distance between stars in the Milky Way. Explanations: (i) light years are a astronomy unit used for measuring length, (ii) stars are located light years apart from each other |
| Question (2): Which type of precipitation consists of frozen rain drops?:<br>Correct Answer: sleet. |
| ExplanationLP |
| Answer: snow. Explanations: (i) precipitation is when snow fall from clouds to the Earth, (ii) snow falls |
| Diff-Explainer |
| Answer: sleet. Explanations: (i) snow falls, (ii) precipitation is when water falls from the sky |
| Diff-Comb Explainer |
| Answer: sleet. Explanations: (i) sleet is when raindrops freeze as they fall, (ii) sleet is made of ice |
| Question (3): Most of the mass of the atom consists of?:<br>Correct Answer: protons and neutrons. |
| ExplanationLP |
| Answer: neutrons and electrons. Explanations: (i) neutrons have more mass than an electron, (ii) neutrons have more mass than an electron |
| Diff-Explainer |
| Answer: protons and neutrons. Explanations: (i) the atomic mass is made of the number of protons and neutrons, (ii) precipitation is when water falls from the sky |
| Diff-Comb Explainer |
| Answer: protons and neutrons. Explanations: (i) the atomic mass is made of the number of protons and neutrons, (ii) precipitation is when water falls from the sky |

Table 2 presents a comparison of publicly reported baselines on the ARC Challenge-Corpus (Clark et al., ) and our approach. These questions have proven to be challenging to answer for other LP-based NLI and neural approaches.

In Table 2, to provide a fair comparison, we list the models that have been trained only on the ARC corpus. Here, the explainability column indicates if the model delivers an explanation for the predicted answer. A subset of the models produces evidence for the answer but remains intrinsically black-boxes. These models have been marked as Partial. As illustrated in the Table 2, Diff-Comb Explainer outperforms the best non-differentiable ILP solver model (ExplanationLP) by 2.8%. We also outperform a transformer-based model (AutoRocc) by 1.97%. While our improvement over Diff-Explainer is small, we still demonstrate performance improvements for answer selection.

### 4.4.   Qualitative Analysis

Table 3 illustrates some of the explanations constructed by ExplanationLP, Diff-Explainer and Diff-Comb Explainer. Both explanations and answer predictions in Question (1) are entirely correct for our model. In this example, both ExplanationLP and Diff-Explainer have failed to retrieve any correct explanations or predict the correct answer. Both the approaches are distracted by the strong lexical overlaps with the wrong answer.

In Question (2) Diff-Comb Explainer produces the correct answer with at least one explanation sentence marked as correct. Here, Diff-Explainer provides the correct answer prediction with both the retrieved facts marked as incorrect showing a lower faithfulness compared to our proposed approach.

In Question (3) both our model and Diff-Explainer provide the correct answer supported by an incorrect explanation. While, the aforementioned qualitative (Question 1 and 2) and quantitative measures (Explanatory Consistency$@K$, Faithfulness) indicate the superiority of Diff-Comb Explainer in generating supporting explanations, we still find cases where incorrect inference can lead to the correct answer. In most of the cases, we found that the inference is distracted by strong lexical overlaps with the question.

In general, however, we can conclude that Diff-Comb Explainer is more robust when compared to Diff-Explainer and existing ILP models.

Figure: Figure 3: Comparison of accuracy for different number of retrieved facts.
Refer to caption: extracted/2404.02625v1/images/plot_k_comb_2.png

### 4.5.   Knowledge aggregation with increasing distractors

One of the key characteristics identified by Thayaparan et al. () is the robustness of Diff-Explainer to distracting noise. In order to evaluate if our model also exhibits the same characteristics, we tested our model with an increasing number of retrieved facts $k$ from the KB and plot the resulting answer accuracy in Figure 3.

As illustrated in the Figure, similar to Diff-Explainer, our approach performance remains stable with increasing distractors. We also continue to outperform Diff-Explainer across all sets of $k$.

BERT performance, on the other side, drops drastically with increasing distractors. This phenomenon is in line with existing findings (Thayaparan et al., ; Yadav et al., ). We hypothesise that with increasing distractors, BERT overfits quickly with spurious inference correlation. On the other hand, our approach circumvents this problem with the inductive bias provided by the constraint optimization layer.

## 5.   Conclusion

This paper proposed a novel framework for encoding explicit and controllable assumptions as part of an end-to-end learning framework for explanation-based NLI using Differentiable Blackbox Combinatorial Solvers (Pogančić et al., ). We empirically demonstrated improved answer and explanation selection performance compared with the existing differentiable constraint-based solvers (Thayaparan et al., ). Moreover, we demonstrated performance gain and increased robustness to noise when combining precise constraints with transformer-based architectures. In this paper, we adopted a specific set of constraints to ensure fairness in the evaluation, but, in principle, it is possible to extend the proposed architecture with different inference constraints.

Diff-Comb Explainer improves upon recent work by  Thayaparan et al. () and investigates the combination of symbolic knowledge (expressed via constraints) with neural representations. We hope this work will encourage researchers to encode different domain-specific priors, leading to more robust, transparent and controllable neuro-symbolic inference models for NLP.

## 6.   Limitations

The ILP formulation is NP-complete. Therefore, as the number of variables in the problem increases the computational complexity also increases exponentially. However, this challenge can be alleviated with strong solvers and the relaxation of some constraints. The performance of the proposed approach is not yet comparable with the scores achieved by Large Language Models (LLMs)  Khashabi et al. (). However, it should be noted that, unlike LLMs, the proposed approach was trained only on the dataset it was tested on and exhibited higher performance compared to the same Transformer encoders integrated in the architecture. These types of neuro-symbolic models can potentially lead to smaller, domain-specific models that require little training data for more efficient and transparent natural language inference.

## Acknowledgements

This work was partially funded by the Swiss National Science Foundation (SNSF) project NeuMath ([200021_204617](https://data.snf.ch/grants/grant/204617)), by the EPSRC grant EP/T026995/1 entitled “EnnCore: End-to-End Conceptual Guarding of Neural Architectures” under Security for all in an AI enabled society, by the CRUK National Biomarker Centre, and supported by the Manchester Experimental Cancer Medicine Centre.
The authors would like to thank the anonymous reviewers and editors of LREC-COLING for their constructive feedback. Additionally, we would like to thank the Shared Facilities of the University of Manchester and Idiap Research Institute for providing the infrastructure to run our experiments.

## 7.   Bibliographical References

## 

- Agrawal et al. (2019)
Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and
J. Zico Kolter. 2019.
[Differentiable convex optimization layers](https://proceedings.neurips.cc/paper/2019/file/9ce3c52fc54362e22053399d3181c638-Paper.pdf).
In *Advances in Neural Information Processing Systems*,
volume 32. Curran Associates, Inc.
- Clark et al. (2018)
Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa
Schoenick, and Oyvind Tafjord. 2018.
Think you have solved question answering? try arc, the ai2 reasoning
challenge.
*arXiv preprint arXiv:1803.05457*.
- Clark et al. (2016)
Peter Clark, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Oyvind Tafjord,
Peter D Turney, and Daniel Khashabi. 2016.
Combining retrieval, statistics, and inference to answer elementary
science questions.
In *AAAI*, pages 2580–2586. Citeseer.
- Clark et al. (2021)
Peter Clark, Oyvind Tafjord, and Kyle Richardson. 2021.
Transformers as soft reasoners over language.
In *Proceedings of the Twenty-Ninth International Conference on
International Joint Conferences on Artificial Intelligence*, pages
3882–3890.
- Devlin et al. (2019)
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.
Bert: Pre-training of deep bidirectional transformers for language
understanding.
In *Proceedings of the 2019 Conference of the North American
Chapter of the Association for Computational Linguistics: Human Language
Technologies, Volume 1 (Long and Short Papers)*, pages 4171–4186.
- Jansen et al. (2018)
Peter Jansen, Elizabeth Wainwright, Steven Marmorstein, and Clayton Morrison.
2018.
Worldtree: A corpus of explanation graphs for elementary science
questions supporting multi-hop inference.
In *Proceedings of the Eleventh International Conference on
Language Resources and Evaluation (LREC 2018)*.
- Johnson et al. (2017)
Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2017.
[Billion-scale similarity
search with gpus](http://arxiv.org/abs/1702.08734).
*CoRR*, abs/1702.08734.
- Khashabi et al. (2016)
Daniel Khashabi, Tushar Khot, Ashish Sabharwal, Peter Clark, Oren Etzioni, and
Dan Roth. 2016.
Question answering via integer programming over semi-structured
knowledge.
In *Proceedings of the Twenty-Fifth International Joint
Conference on Artificial Intelligence*, pages 1145–1152.
- Khashabi et al. (2018)
Daniel Khashabi, Tushar Khot, Ashish Sabharwal, and Dan Roth. 2018.
Question answering as global reasoning over semantic abstractions.
In *Proceedings of the AAAI Conference on Artificial
Intelligence*, volume 32.
- Khashabi et al. (2020)
Daniel Khashabi, Sewon Min, Tushar Khot, Ashish Sabharwal, Oyvind Tafjord,
Peter Clark, and Hannaneh Hajishirzi. 2020.
Unifiedqa: Crossing format boundaries with a single qa system.
*arXiv preprint arXiv:2005.00700*.
- Khot et al. (2017)
Tushar Khot, Ashish Sabharwal, and Peter Clark. 2017.
Answering complex questions using open information extraction.
*arXiv preprint arXiv:1704.05572*.
- Kundu et al. (2019)
Souvik Kundu, Tushar Khot, Ashish Sabharwal, and Peter Clark. 2019.
[Exploiting explicit
paths for multi-hop reading comprehension](https://doi.org/10.18653/v1/P19-1263).
In *Proceedings of the 57th Annual Meeting of the Association
for Computational Linguistics*, pages 2737–2747, Florence, Italy.
Association for Computational Linguistics.
- Lovász and Schrijver (1991)
L. Lovász and A. Schrijver. 1991.
Cones of matrices and set-functions and 0-1 optimization.
*SIAM JOURNAL ON OPTIMIZATION*, 1:166–190.
- Ni et al. (2019)
Jianmo Ni, Chenguang Zhu, Weizhu Chen, and Julian McAuley. 2019.
Learning to attend on essential terms: An enhanced retriever-reader
model for open-domain question answering.
In *Proceedings of the 2019 Conference of the North American
Chapter of the Association for Computational Linguistics: Human Language
Technologies, Volume 1 (Long and Short Papers)*, pages 335–344.
- Paulus et al. (2021)
Anselm Paulus, Michal Rolínek, Vít Musil, Brandon Amos, and Georg
Martius. 2021.
Comboptnet: Fit the right np-hard problem by learning integer
programming constraints.
In *International Conference on Machine Learning*, pages
8443–8453. PMLR.
- Pogančić et al. (2019)
Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil, Georg Martius,
and Michal Rolinek. 2019.
Differentiation of blackbox combinatorial solvers.
In *International Conference on Learning Representations*.
- Reimers et al. (2019)
Nils Reimers, Iryna Gurevych, Nils Reimers, Iryna Gurevych, Nandan Thakur, Nils
Reimers, Johannes Daxenberger, and Iryna Gurevych. 2019.
Sentence-bert: Sentence embeddings using siamese bert-networks.
In *Proceedings of the 2019 Conference on Empirical Methods in
Natural Language Processing*. Association for Computational Linguistics.
- Saha et al. (2020)
Swarnadeep Saha, Sayan Ghosh, Shashank Srivastava, and Mohit Bansal. 2020.
Prover: Proof generation for interpretable reasoning over rules.
In *Proceedings of the 2020 Conference on Empirical Methods in
Natural Language Processing (EMNLP)*, pages 122–136.
- Saha et al. (2021)
Swarnadeep Saha, Prateek Yadav, and Mohit Bansal. 2021.
multiprover: Generating multiple proofs for improved interpretability
in rule reasoning.
In *Proceedings of the 2021 Conference of the North American
Chapter of the Association for Computational Linguistics: Human Language
Technologies*, pages 3662–3677.
- Speer et al. (2017)
Robyn Speer, Joshua Chin, and Catherine Havasi. 2017.
Conceptnet 5.5: An open multilingual graph of general knowledge.
In *Thirty-first AAAI conference on artificial intelligence*.
- Thayaparan et al. (2022)
Mokanarangan Thayaparan, Marco Valentino, Deborah Ferreira, Julia Rozanova, and
André Freitas. 2022.
[Diff-Explainer:
Differentiable Convex Optimization for Explainable Multi-hop Inference](https://doi.org/10.1162/tacl_a_00508).
*Transactions of the Association for Computational Linguistics*,
10:1103–1a119.
- Thayaparan et al. (2020)
Mokanarangan Thayaparan, Marco Valentino, and André Freitas. 2020.
A survey on explainability in machine reading comprehension.
*arXiv preprint arXiv:2010.00389*.
- Thayaparan et al. (2021)
Mokanarangan Thayaparan, Marco Valentino, and André Freitas. 2021.
Explainable inference over grounding-abstract chains for science
questions.
In *Findings of the Association for Computational Linguistics:
ACL-IJCNLP 2021*, pages 1–12.
- Valentino et al. (2022)
Marco Valentino, Mokanarangan Thayaparan, Deborah Ferreira, and André
Freitas. 2022.
Hybrid autoregressive inference for scalable multi-hop explanation
regeneration.
In *Proceedings of the AAAI Conference on Artificial
Intelligence*, volume 36, pages 11403–11411.
- Valentino et al. (2021)
Marco Valentino, Mokanarangan Thayaparan, and André Freitas. 2021.
Unification-based reconstruction of multi-hop explanations for
science questions.
In *Proceedings of the 16th Conference of the European Chapter
of the Association for Computational Linguistics: Main Volume*, pages
200–211.
- Wolf et al. (2019)
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue,
Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz,
and Jamie Brew. 2019.
[Huggingface’s transformers:
State-of-the-art natural language processing](http://arxiv.org/abs/1910.03771).
*CoRR*, abs/1910.03771.
- Xie et al. (2020)
Zhengnan Xie, Sebastian Thiem, Jaycie Martin, Elizabeth Wainwright, Steven
Marmorstein, and Peter Jansen. 2020.
Worldtree v2: A corpus of science-domain structured explanations and
inference patterns supporting multi-hop inference.
In *Proceedings of The 12th Language Resources and Evaluation
Conference*, pages 5456–5473.
- Yadav et al. (2019a)
Vikas Yadav, Steven Bethard, and Mihai Surdeanu. 2019a.
Alignment over heterogeneous embeddings for question answering.
In *Proceedings of the 2019 Conference of the North American
Chapter of the Association for Computational Linguistics: Human Language
Technologies, Volume 1 (Long and Short Papers)*, pages 2681–2691.
- Yadav et al. (2019b)
Vikas Yadav, Steven Bethard, and Mihai Surdeanu. 2019b.
[Quick and (not so)
dirty: Unsupervised selection of justification sentences for multi-hop
question answering](https://doi.org/10.18653/v1/D19-1260).
In *Proceedings of the 2019 Conference on Empirical Methods in
Natural Language Processing and the 9th International Joint Conference on
Natural Language Processing (EMNLP-IJCNLP)*, pages 2578–2589, Hong Kong,
China. Association for Computational Linguistics.
- Zhang et al. (2018)
Yuyu Zhang, Hanjun Dai, Kamil Toraman, and Le Song. 2018.
Kg^ 2: Learning to reason science exam questions with contextual
knowledge graph embeddings.
*arXiv preprint arXiv:1805.12393*.

## Peer Reviews

confidence: 4
contribution: 4
initial_rating: 6
presentation: 3
questions: see weakness.
soundness: 2
strengths: The idea of replacing solvers in the training pipeline is intriguing. Indeed, I can envision many problem classes where off-the-shelf solvers may underperform compared to simple gradient-descent-based algorithms. The proposed method could be highly effective for such problems.
summary: This paper proposes a new learn-to-optimize paradigm that trains a solution predictor without relying on traditional solvers to generate label data. As a result, the entire pipeline is significantly faster by avoiding solver runs. The paradigm is based on designing a Lagrangian loss for the predicted solution and iteratively updating the predictor using the gradient of the Lagrangian loss.
weaknesses: When comparing their results to existing methods based on solver-generated labels, the authors overlook an important limitation of their approach: their unsupervised learning method does not learn from optimal ILP solutions and may instead be trained to only produce significantly sub-optimal solutions.

Gradient descent algorithms for MILP problems are not new (e.g., see the paper "Feasibility Jump: an LP-free Lagrangian MIP heuristic") and they generally converge to a suboptimal, heuristic solution. By performing gradient descent on the Lagrangian loss, the unsupervised learning method proposed in this paper essentially learns from heuristic solutions, which may fall far short of optimality.

To ensure a fair comparison, I believe the authors should modify the solver-based supervised learning pipelines by setting limits on (i) the solving time and (ii) the number of branch-and-bound nodes. Most off-the-shelf solvers can find a good solution in a short time, with the extended solving time largely dedicated to ensuring optimality. Since the authors are not learning from optimal solutions, they should compare their approach to existing methods without optimality requirements.

---

confidence: 4
contribution: 4
initial_rating: 8
presentation: 4
questions: How different are the initial solutions compared to the solutions after one round of neighborhood search? (i.e. after solving the optimiazation problem with constraint (9) added?

Why are the Zheng 2024 and Huan 2024 baselines not included as they seemed to surpass the PS approach and provide implementations.

How many decision variables do the different settings have? It is somewhat unclear why this method would be more robust to changes in delta than baseline approaches. Is it the case that the predicted solution is already close to optimal, so a large neighborhood doesn’t need to be searched?

How does the approach generalize to different kinds of problems? Either to larger instances or out of distribution instances e.g. MIPLIB?

What are the feasibility rates for PS? They are given for DiffILO but not present for the baseline. It seems figure 4 is missing.

How is mu determined? Is it determined as a hyperparameter? Or adaptively selected to ensure feasibility?
soundness: 4
strengths: The strengths of the approach are that it doesn’t require expensive optimization solving for training time. Most of the literature hasn’t considered this as it is assumed that practitioners are willing to spend time upfront training a model that can be deployed on many instances, but nevertheless it can be impactful in some settings to require less training time, for instance it can be possible to train on many more problem instances given the same training time, or even larger instances given that training instances don’t need to be solved to optimality.

The approach itself is well motivated and the paper is well-written. 

The illustrative toy example is helpful for giving intuition for how the approach works in a simple setting.
summary: The authors propose an interesting approach for unsupervised learning in ILP. Evaluating it in several binary programming settings, and investigating the approach itself empirically in various ways. The approach itself relies on considering that a model predicts a continuous solution where each entry represents the probability of assigning a given decision variable to 1 or 0. The model is then trained to optimize a loss that combines the expected objective value with the expected constraint violation. The expected constraint violation is estimated by sampling several solutions and computing expected constraint violation using the samples. The benefit of the unsupervised approach is that it bypasses the need to expensively collect solutions from training instances. Additionally, the authors propose that the unsupervised approach helps improve predictive performance by encouraging the predicted objects to represent feasible solutions. The authors present theoretical motivations for the approach, as well as thorough empirical evaluation on toy examples to give insights as to how the approach works.

Overall, the work is interesting while there is some room for improvement, if the authors address my comments I am eager to increase my score.
weaknesses: The approach is proposed for general ILP; however, the approach seems to be tailored to binary programs. There is a remark stating that ILP can be reduced to binary programs; however, it would help strengthen the paper if there were experimental results validating that this approach can be used in general ILP tasks to make that claim (such as on MIPLIB instances other than the CVS dataset), or to rephrase the method as working for binary programs.

Theorem 2 statement 2: it seems that this direction of solvability/optimality doesn’t really apply in this setting since the predicted continuous x is always fractional as considered below in the approach. Is there any indication that the distribution being optimal for P2 has any implication about the optimality wrt P1 of the discrete solutions that the distribution represents? Is there any indication of whether the probability distribution puts weight on suboptimal solutions? 

It is unclear whether the approach would outperform baselines other than the single PS baseline considered here as more recent work with available code seems to have outperformed the predict and search approach such as the two cited works. However, it would be interesting to see if the unsupervised approach could be integrated in the settings considered in previous work as well.

Specific comments:
-	Remark 2 ends in “Otherwise,” is something missing there?
-	Figure 4 is missing
-	Toour is missing a space

---

confidence: 4
contribution: 4
initial_rating: 8
presentation: 4
questions: - typo in line 198;
soundness: 3
strengths: Overall, I think this is an interesting perspective into learning predictive models for obtaining approximation solution for combinatorial problems. Majority of previous approaches use a solver calls in some way to learn that predictive mapping, whereas here it is done by defining a differentiable (a.e.) function that serves as an objective to optimize. In this regard, I find it similar to the decision-focused learning (DFL) or predict-then-optimize framework [1,2,3] where the task is to learn a model which maps observable features into latent representation (e.g. coefficients in LP objective) used by solvers. Here, the training formulation is similar but the solution is predicted instead of latent representation. Particularly [3] draws this connection between these two domains and apply it for MINLPs. I encourage authors to add this line of research and elaborate on this. Other strengths of the paper include:

- theoretical justification of the continuous relaxation applied for this problem. Although ILP covers a lot of important class of problems, however I don't see these to be directly extended into non-linear case.
- experimental results look convincing in terms of both runtime and solution quality. Although adding larger scale experiments would be beneficial;
- the method is intuitive to understand and makes sense to me.
- can be directly applied to speed up the runtime for traditional solvers;


[1] A. N. Elmachtoub and P. Grigas. Smart “predict, then optimize”. arXiv:1710.08005

[2] A. Ferber, B. Wilder, B. Dilkina, and M. Tambe. MIPaaL: Mixed integer program as a layer. 

[3] A. Zharmagambetov, B. Amos, A. Ferber, T. Huang, B. Dilkina, and Y. Tian (2023): "Landscape Surrogate: Learning Decision Losses for Mathematical Optimization Under Partial Information".
summary: The authors proposes DiffILO, a new approach that uses machine learning to solve integer linear programs (ILPs) without supervision and without traditional solvers. DiffILO transforms ILPs into continuous, differentiable, and unconstrained problems through probabilistic modeling and applied the penalty based merit function, allowing for optimization using gradient descent directly. That is, there is no need in calling solver at all. Instead, the model (which predict solution to ILP) is trained via backpropagating the merit function.

Unlike supervised methods that require labeled data typically obtained by solving ILPs, DiffILO operates in an unsupervised manner, which reduces training time. The approach has been tested on small-to-medium scaled ILP datasets, demonstrating its ability to speed up the training process and produce feasible solutions. These solutions may differ from those generated by supervised methods.
weaknesses: Some are mentioned in Strengths above. Additionally, I think that the supervised approaches a bit underperforming here due to limited sample size. With enough data for supervision, I think those approaches should also improve drastically, especially for larger scale problems.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: I am interested in the results and analysis of the MIPLIB experiments. Why were the “neos” datasets chosen for experiments during the NeurIPS rebuttal but not included in the current submission? Instead, the “CVS” datasets were presented. During the NeurIPS rebuttal, after the authors fixed the bugs in the Gurobi configuration, the solving time for Gurobi changed from 1000 seconds to less than 100 seconds.

The experimental results on the neos18 dataset indicate that Gurobi+DiffILO requires a longer solving time than pure Gurobi, and I am curious about the reason for this. I reviewed the problem details of neos18 and the five “CVS” datasets presented in the paper, and found that the number of variables and constraints is smaller in the five “CVS” datasets. For example, neos18 has 11,402 constraints, while the five “CVS” datasets have fewer than 5,000 constraints. Does this suggest that DiffILO may not perform well on more complex benchmarks? Could you provide the experimental results on the “neos” datasets and explain why Gurobi+DiffILO performs worse than Gurobi?
soundness: 3
strengths: 1. The paper is well-written and clear. 
2. Adequate theoretical support is provided for the key steps.
3. As one of the NeurIPS reviewers for this paper, I am pleased to see that the paper includes many of the experimental results requested during the rebuttal period.
summary: This paper introduces Differentiable Integer Linear Programming Optimization (DiffILO), a novel learning method for predicting high-quality Integer Linear Programming (ILP) solutions in an unsupervised manner, without the reliance on traditional solvers. The proposed prediction model is a Graph Neural Network (GNN) module followed by a multilayer perceptron (MLP). By transforming ILPs into a continuous, differentiable, and unconstrained form through probabilistic modeling and the penalty function method, the authors enable the use of gradient descent for optimization. The approach avoids reliance on traditional solvers and labeled data, reducing training time.
weaknesses: 1. Given that there are various relaxations made during the conversion of the ILP to an unconstrained problem, the experiments do not ablate the effect of the choices made at each step. For example, for the relaxation converting the constraint violation into a sampling based objective, it is not clear what the effect of the number of samples is. In the Appendix, the training loss has been modified via some specific form of normalization, but it is not clear what happens to the empirical performance when such normalizations are removed.
2. SC, MIS and CA are easy combinatorial optimization problems and hence identifying feasible solutions without relying on MILP solvers is not challenging. Experiment results on more realistic ILPs (such as those from MIPLIB 2017) should be included in the main paper.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 4
questions: In Remark 5 you mention that you favour the relaxed Bernoulli over using REINFORCE, citing that it does not explicitly propagate the gradients from $\phi_j(x)$. Did you conduct experiments to verify that in practice this is indeed the case? If so this could be interesting to add to the Appendix, (appending a reference to Remark 5).

I believe the following reference would be useful for the paper (regarding smoothing COs): [Berthet 2020] *Learning with Differentiable Perturbed Optimizers*
soundness: 4
strengths: The paper is well written, with the methodology and experiments both presented in a clear and coherent fashion. As far as I am aware, the unsupervised learning approach is indeed completely novel. Whilst there is a wealth of literature for creating differentiable proxies of CO problems, (for which the paper calls upon multiple tools / results), I believe the overall methodology to be a significant contribution. The presentation of the mathematics underpinning the relaxation and reformulation was particularly well written.
summary: The paper concerns itself with integer linear programs (ILPs), a NP hard optimization problem. Previous works have trained models in a supervised manner to predict near optimal solutions as a heuristic guess to a problem instance. In this work, the authors propose a unsupervised method to train predictors: namely, by using a Bernoulli relaxation of the ILP variable, and reformulating the ILP as a unconstrained problem (via the introduction of a penalty function), a application of the Gumbel-Softmax trick (as a “relaxed Bernoulli”) enables for gradient flow suitable for back -propagation.

The mathematics corresponding to the methodology are clearly presented in detail. The methodology is evaluated empirically on three ILP benchmarks:

- Set covering 
- Maximum independent set
- Combinatorial Auctions

and compared to i) traditional solvers ii) Predict-and-search framework, as baselines. In this section the authors also provide practical results e.g. which hyper parameters are crucial, learning rate schedule, which are helpful for practitioners.
weaknesses: The methodology in its current form is constrained to using a GNN as a predictor for the Bipartite graph, which seems quite excessive ; the graph structure is simple and GNNs have a high computational complexity (and poor scalability). However, the ideas presented in the work are independent of this and it is nonessential to the method. Below are two suggestions for methods to replace the GNN in the current methodology, both of which would allow for more general architectures (e.g. transformer). These may be worth mentioning as future possible work.

 - Sinkhorn Knop for soft matching between nodes:  see  **[Cuturi et al 2013]** *Sinkhorn distances: Lightspeed computation of optimal transport*. (An example of such an implementation can be seen in **[Caron et al 2021]** *Emerging Properties in Self-Supervised Vision Transformers*)
- Differentiable Clustering for a soft cluster assignment (between a cluster for 0 and 1): see  **[Stewart et al 2023]**  *Differentiable Clustering with Perturbed Spanning Forests*.
- Vector Quantization (not differentiable, but commonly used in practise to assign discrete values): **[van den Oord 2017]** *Neural Discrete Representation Learning*.


As someone who is not familiar with ILPs, it would have been nicer to have further motivation on the real world applications of ILPs, and more intuition as to why DNNs are preferable to predict solutions over other established search methods (please note: I am not questioning either of these points, just pointing out that a more explicit clarification on these would be helpful to a non-expert reader).

Meta-review: This paper introduces DiffILO, a novel method for solving Integer Linear Programs (ILPs). It relies on a probabilistic modeling approach to transform ILPs into unconstrained, differentiable problems, enabling gradient descent optimization. Unlike supervised methods, DiffILO operates unsupervised, reducing training time. Tests on small-to-medium ILPs demonstrate its ability to accelerate training and produce feasible solutions. The reviewers are enthusiastic about this work, and recommend to accept.

Personally, I think that this work is interesting, but would strengthen the "related works" section, since the idea of gradient-based approaches for LPs, and probabilistic relaxations are not new, as pointed out by some of the reviewers.

Decision: Accept (Spotlight)