A Solver-free Framework for Scalable Learning in Neural ILP Architectures
Authors: Yatin Nandwani
Rishabh Ranjan
Mausam .
Parag Singla
Venue: NeurIPS 2022 Accept (2022)
Keywords: constraint learning
neural ILP

Abstract: There is a recent focus on designing architectures that have an Integer Linear Programming (ILP) layer within a neural model (referred to as \emph{Neural ILP} in this paper). Neural ILP architectures are suitable for pure reasoning tasks that require data-driven constraint learning or for tasks requiring both perception (neural) and reasoning (ILP). A recent SOTA approach for end-to-end training of Neural ILP explicitly defines gradients through the ILP black box [Paulus et al. [2021]] – this trains extremely slowly, owing to a call to the underlying ILP solver for every training data point in a minibatch. In response, we present an alternative training strategy that is \emph{solver-free}, i.e., does not call the ILP solver at all at training time. Neural ILP has a set of trainable hyperplanes (for cost and constraints in ILP), together representing a polyhedron. Our key idea is that the training loss should impose that the final polyhedron separates the positives (all constraints satisfied) from the negatives (at least one violated constraint or a suboptimal cost value), via a soft-margin formulation.  While positive example(s) are provided as part of the training data, we devise novel techniques for generating negative samples. Our solution is flexible enough to handle equality as well as inequality constraints. Experiments on several problems, both perceptual as well as symbolic, which require learning the constraints of an ILP, show that our approach has superior performance and scales much better compared to purely neural baselines and other state-of-the-art models that require solver-based training. In particular, we are able to obtain excellent performance in 9 x 9 symbolic and visual Sudoku, to which the other Neural ILP solver is not able to scale.

A Solver-Free Framework for Scalable Learning in Neural ILP Architectures
Yatin Nandwani; Rishabh Ranjan; Mausam Parag Singla Department of Computer Science, Indian Institute of Technology Delhi, INDIA (yatin. nandwani, rishabh. ranjaan cs118, mausam, parags)@cse iitd ac. in
Abstract
There is a recent focus on designing architectures that have an Integer Linear Programming (ILP) layer following neural model (referred to as Neural ILP in this paper). Neural ILP architectures are suitable for pure reasoning tasks that require data-driven constraint learning or for tasks requiring both perception (neural) and reasoning (ILP). A recent SOTA approach for end-to-end training Neural ILP explicitly defines gradients through the ILP black box (Paulus et al. 2021] - this trains extremely slowly, owing to a call to the underlying ILP solver for every training data point in minibatch. In response, we present an alternative training strategy that is solver-free, i.e., does not call the ILP solver at all at training time. Neural ILP has set of trainable hyperplanes (for cost and constraints in ILP), together representing polyhedron. Our key idea is that the training loss should impose that the final polyhedron separates the positives (all constraints satisfied) from the negatives (at least one violated constraint or a suboptimal cost value), via a soft-margin formulation. While positive example(s) are provided as part of the training data, we devise novel techniques for generating negative samples. Our solution is flexible enough handle equality as well as inequality constraints. Experiments on several problems, both perceptual as well as symbolic, which require learning the constraints of an ILP, show that our approach has superior performance and scales much better compared to purely neural baselines and other state-of-the-ar art models that require solver-based training. particular, we are able to obtain excellent performance 9 x 9 symbolic and visual sudoku, to which the other Neural ILP model not able to scale.
Introduction
There has been a growing interest in the community which focuses on developing neural models for solving combinatorial optimization problems. These problems often require complex reasoning over discrete symbols. Many of these problems can expressed in the form an underlying Integer Linear Program (ILP). Two different kinds of problem (input) settings have been considered in the literature: (a) purely symbolic and (b) combination of perceptual and symbolic. Solving an n-Queens problem given the partial assignment of queens on the board as input would be example of the former, and solving a sudoku puzzle given the image example of the latter. While the first setting corresponds to pure reasoning task, second involves combination of perception and reasoning tasks which need to be solved in a joint fashion. Existing literature proposes various approaches handle one or both these settings. One line of work proposes purely neural models [Palm et al., 2018 Nandwani et al. 2021 Dong et al. 2019) for solving these tasks representing the underlying constraints and costs implicitly. While standard CNNs used to
partially filled board as input would be an
"qqual contribution. Work done while IIT Delhi. Current email: rishabhr@ andrew.cmu.edu "oode available at: http://ggttub..om/dda compiiiiioomaiiiiiiiiiiilssssss
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

solve the perceptual task, neural models such as Graph Neural Networks (GNNs) take care of the reasoning component. In an alternate view, one may want to solve these tasks by explicitly learning the constraints and cost of the underlying IIP. While the perceptual reasoning would still be handled by using modules such as CNN, reasoning is taken care of by having an explicit representation in the form of an ILP layer representing constraints and costs. Such an approach would have the potential advantage of being more interpretable, and also being more accurate the underlying constraints could be learned in precise manner. Some recent approaches take this route, and include works by [Paulus et al. 2021 Pogancic et al. 2020 Berthet et al., 2020 We refer to the latter set of approaches as Neural ILP architectures.
Learning in Neural ILP architectures complicated by the fact that there is a discrete optimization (in the form of an ILP layer) at the end of the network, which is typically non non- con--fffereniibll, making the end-to-end learning of the system difficult. One of the possible ways is to instead use an iterative II. solving algorithm such as a cutting- p-aane method [Gomory] 2010] that uses a continuous relaxation in each iteration which is shown to be differentiable due to the introduction of continuous variables [eerber et al., 2020 Wilder et al. 2019]. Most of these works are concerned with learning only the cost function and assume that the constraints are given. Recent work by Paulus et al. [2021] has proposed an approach to directly pass the gradients through a black-box ILP solver. Specifically, they rely on Euclidean distances between the constraint hyperplanes and the current solution obtained by the ILP solver to produce gradients for backprop. Though this approach improves the quality of results compared to earlier works involving continuous relaxations, scalability gets severely affected since ILP has to be solved at every learning iteration, making the training extremely slow.
We are interested in answering the following question: is there a way to train a neural IIP architecture in an end-to-end manner, which does not require access to an underlying solver? Such an approach, if exists, could presumably result in significantly faster training times, resulting in scalability. In response, we propose novel technique to back-propagate through the learnable constraints as well as the learnable cost function of an unknown Integer Linear Program (ILP). During training, our technique doesn't solve the ILP to compute the gradients. Instead, we cast the learning of ILP constraints (and cost) as learning of a polyhedron, consisting of a set of hyperplanes, such that points inside the polyhedron are treated as positive, and points outside as negative. While positive point needs to be classified as positive by each of the hyperplanes, a negative point needs to be classified as negative only by at least one of the hyperplanes. Our formulation incorporates the learning of ILP cost also as learning of one of the hyperplanes in the system. We formulate a novel margin-based loss to learn these hyperplanes in joint fashion. A covariance based regularizer that minimizes the cosine similarity between all pairs of hyperplanes ensures that learned constraints (hyperplanes) are not redundant. Since the training data comes only with positive examples, i.e., solutions respective optimization problems, we develop several techniques for sampling the negatives, each of which is central to the effective learning of our hyperplanes in our formulation.
We present several experiments on problems which require learning of ILP constraints and cost, with both symbolic well as perceptual input. These include solving a symbolic sudoku as well as visual sudoku in which we are given an image of a partially filled board [Wang et al.] 2019 (perceptual); ILPs with random constraints (symbolic), Knapsack from sentence description (perceptual) and key- point matching (perceptual) from [Paulus et al. [021]] Our closest competitor, CombOptNet [Paulus) al. 2022), can not solve even the smallest of the sudoku boards sized x 4, whereas we can easily scale to 9 x 9, getting close to 100% accuracy. We are slightly better on key-point matching, and obtain significantly better accuracy on random ILPs and knapsack, especially on large problem sizes.
We also outperform purely neural baselines (wherever applicable).
2 Related Work
When the constraints of an ILP are known, many works propose converting such constraints over discrete output variables into equivalent constraints over their probabilities given by the model and backpropagate over them [Nandwani et al. 2019 Li and Srikumar, 2019]. Some works use an ILP solver with the known constraints during inference to improve the predictions [Ning et al. 2019 Han et al. 2019). When constraints have be learned, which is the focus of this paper, one line of work uses neural model, such as a GNN, to replace a combinatorial solver altogether and implicitly
Although these methods can also train Neural- -LP---ILPPPP Iee-rll architecture, studying this is beyond our scope.

---

encodes the constraints in model's weights and learns them from data. Nandwani et al. 2022 2021 Palm et al. [2018) train Recurrent Relational Network for learning to solve puzzles like sudoku, graph coloring, Futoshiki, etc: De::ong et al.
2019) propose Neural Logic Machines (NLMs) that learn lifted first order rules and experiment with blocks world, reasoning on family trees etc; Ranjan et al..
[2022) use a siamese GNN architecture to learn the combinatorial problems of graph and subgraph distance computation: Bajpai et al. 20118) Garg et al. [2019 2020], |Sharma et al. [2022] use GNNs to train probabilistic planners for combinatorial domains with large, discrete state and action spaces; Selsam et al. [2019]. Amizadeh et al. (2019a train a GNN for solving any CSP when constraints explicitly given in standard form such as CNF, DNF or Boolean Circuits. This is clearly different from us since we are interested in explicitly learning the constraints of the optimization problem.
Inverse Optimization [Chan et al. 2021] aims to learn the constraints (cost) of linear program (LP) from the observed optimal decisions. Recently [Tan et al. 2029 use the notion of Parameterized Linear Programs (PLP) in which both the cost and the constraints of an LP are parameterized by unknown weights. [Gould et al.) 2019] show how to differentiate through continuous constrained optimization problem using the notion of a "declarative node" that uses implicit function theorem [Mingari Scarpello and Ritelli 2002]. Similar to this are other works [Amos and Kolter 2017] Agrawal et al.) [019]] that define methods for differentiating through other continuous problems like convex quadratic programs (QPs) or cone programs. While all these techniques are concerned with learning the constraints (cost) for optimization problems defined over continuous variables, our focus is on learning constraints (cost) for an ILP which involves optimization over discrete variables and can be significantly harder problem.
In the space of learning cost for an IIP, several approaches have been proposed recently. [Pogancic]
et al.] [2020] give the gradient w.r.t. linear cost function that is optimized over a given discrete space.
[Rolnnek et al., 2020aa b) exploit it for the task of Deep Graph Matching, and for differentiating
through rank based metrics such as Average Precision/Recall respectively. [Berthet et al. 2020
replace the black-box discrete solver with its smooth perturbed version during training and exploit "perturb-andMMAP (Papandreou and Yuille [01T] to compute the gradients. On similar lines, [Niepert jet al. 2021] also exploit perturb-and and MAP but propose a different noise model for perturbation and also extends to the case when the output of the solver may feed into downstream neural model. These methods assume the constraints to be given, and only learn the cost for an ILP.
Other methods use relaxations of specific algorithms for the task of learning the constraints and cost for an IIP. IL.., [Ferber et al.] [2020] backprop through the KKT conditions of the LP relaxation created iteratively while using cutting-plane method [Gomory| 2010] for solving an MILP; Wilder et al. [2019) add a quadratic penalty term to the continuous relaxation and use implicit function theorem to backprop through the KKT conditions, as done in Amos and Kolter [2017] for smooth programs; Mandi and Guns| [2020] instead add a log-barrier term to get the LP relaxation and differentiate through its homogeneous self-dual formulation linking it to the iterative steps in the interior point method. |Wang et al. [2119] uses a low rank SDP relaxation of MAXSAT and defines how the gradients flow during backpropagation. Presumably, these approaches are limited in their application since they rely on specific algorithmic relaxations.
Instead of working with specific algorithm, some recent works differentiate through a black-box combinatorial solver for the task of learning constraints [Paulus et al.) 202T]. The solver is called at every learning step to compute the gradient. This becomes bottleneck during training, since the constraints are being learned on the go, and the problem could become ill-behaved resulting in a larger solver time, severely limiting scalability of such approaches. In contrast, we would like to perform this task in a solver-free manner. |an et al. (0200) propose learning of constraints for the task of structured prediction. They represent the linear constraints compactly using a specific two layer Rectifier Network [Pan and Srikumar 2016). A sigmificant limitation is that their method can only be used for learning constraints, and not costs. Further, their approach does not do well experimentally on our benchmark domains. |Meg and Chang 2021 propose a non-learning based approach for mining constraints in which for each training data (c, y), new constraint is added which essentially imply that no other target can have better cost than the given target for the corresponding cost c. We are specifically interested in learning not only the constraints, but also the cost of ILP from data. Convex Polytope Machines (CPM) [Kantchelian et al. 2014) learns a non linear binary classifier in the form of a polytope from dataset of positive and negative examples. In contrast, our goal is to learn the cost as well as constraints for an ILP where both the constraints and the cost could be parameterized by another neural network. Also, we do not have access to any negative samples.
3

---

3 Differentiable ILP Loss
3.1 Background and Task Description
We are interested in learning how to solve combinatorial optimization problems that can be expressed as Integer Linear Program (ILP) with equality well inequality constraints:
arg min c² subject to Uz v; Gz + h 2 0 xE2"
(1)
Here C E R" represents an n dimensional cost vector, the matrix U E R and v E R represent my linear equality constraints, and the matrix G Rmxxx and h E TR represent ma linear inequality constraints, together defining the feasible region.
Without loss of generality,
replace an equality constraint u V; by two inequality constraints: u z 2 V, and -u z -v, Here u, and v; represent the 7th row of the matrix U and
7th element of the vector respectively. Using this, one can reduce IIP in eq. I to equivalent form with just inequality constraints:
arg min c' subject to Az+b20 0
=EZ"
Here matrix A E _ is row-wise concatenation of the matrices G, U and -U. Vector b E R a row-wise concatenation of vectors h, -v and v, and m 2mm + m2 is the total number of inequality constraints. We represent the 1th constraint a z b, 0, as |a:/b.]. The integer constraints Z E Z" make the problem NP hard.
Neural ILP Architecture: In neural ILP architecture, the constraint matrix A, vector b, and the cost vector e are neural funetions Sa. fb: and fa (of input x:) parameterized by learnable = (OA, Ob. 0e), Le., A I'A (2; 0A); b = [b<a;; 0b); c fe(æ; 0e). This results in different IIP for each input æ. For an input x, the solution given by neural IIP model, Mg (4)) nothing but
the optima of the following paramterized ILP where A, b, are replaced by corresponding neural
functions fA, fb. fo evaluated at input x:
Me (x) = arg min (fe (z; fe))²² z subject to fa(:; + 86) 2 0, 1 Z
(3)
Example of visual-sudoku: In k x & visual-sudoku, the input x: is an image of a sudoku puzzle and y" E {0, 1 is the corresponding solution, represented as n k3 dimensional binary vector: the integer in each of the k2 cells is represented by a k dimensional one-hot binary vector. Function fe(1;0.) parameterizing the cost is nothing but neural digit classifier that classifies the content of each of the k² cells into one of the & classes. The neural functions FA and fu are independent of the input x as the constraints are the same for every ls x k sudoku puzzle. Therefore, fa; 0A) = AA. and fo (z: 0b) = b.. where 0g is just learnable matrix of dimension m x n and 6b is a learnable vector of dimension m. See Bartlett et al. (2008) for an ILP formulation of l sudoku with 462 equality constraints in n = 133 dimensional binary space (0, 1)..
Given training dataset D ((x,,y")) s E (1....S) with S training samples, the task is to learn the parameters = A0A, On. 0c), such that y Me(x.) for each To do so, aL ar. öL one needs to define derivatives JAA. 75 and ß w.r.f. A, b, and e respectively, of an appropriate loss function L. Once such derivative defined, one can easily compute derivatives w.r.1.0,, On, and Og using the chain rule: in the formulation below, we only worry about computing gradients w.r.t. the constraint matrix A, vector b, and the cost vector c.
Learning Task:
(I:0A), øL De DA d8 D6, ab 20
aL
@fr())))) and äL a1 (a:0e)) Hence, D0, De de.
The existing approaches. e.g., [Paulus et al. 2021 explicitly need access to current model prediction Me (x). This requires solving the ILP in eq. (3). making the lcarning process extremely slow. In contrast, we present 'solver-free' framework for computation of an appropriate loss and its derivatives w.r.f. A, b, and c. Our framework does not require solving any ILP while training, thereby making it extremely scalable as compared existing approaches.
3.2 A Solver-free Framework
Conversion to constraint satisfaction problem: As a first step, we convert the constraint optimiza- tion problem in eq. (2) to an equivalent constraint satisfaction problem by introducing an additional

---

"cost- constroont:in' c²z S y"y", equivalent to am+1 = cc and bm+1 =c"y' Note that the above cost-constraint separates the solution y" of the original ILP in eq. 2 from the other feasible integral points. This is because y" must achieve the minimum objective value cf y amongst all the feasible integral points and hence no other feasible integral point can obtain objective value less than or equal to c"y". The new constraint [am- 1 together with the original m constraints guarantee that y" is the only solution satisfying all of the (m + 1) constraints. This results in the following equívalent linear constraint satisfaction problem:
arg min O"2 z subject to xEZ"
b2+ c'z'c'y'
(4)
Constructing such an equivalent satisfaction problem requires access to the solution y" of the original ILP in eq. ( and that is already available to us for the training data samples. By rolling up the cost vector с into an additional constraint with the help y', we have converted our original objective of learning both the cost and constraints to just learning of constraints in eq. (4)
The main intuition behind framework comes from the observation that each of the m linear constraints defining the feasible region are essentially m linear binary classifiers (hyperplanes) in In separating the ground truth y* from the infeasible region. The additional cost-constraint in eq. (4) separates y" from other integral samples feasible w.t.. the original m constraints. Learning constraints of an ILP is akin to simultaneously learning m linear binary classifiers separating y from other infeasible points of the original ILP along with learning classifier for cost-constraint, separating y* from other feasible integral points.
For a vector y" to lie inside the feasible region, all the classifiers need to classify it positively, and hence it acts positive data point for all the m + 1 binary classifiers. In the absence of explicitly provided negative samples, we propose a couple of strategies for sampling them from Z" for each ground truth y We discuss them in detail in section 3.3] For now, let Ny- be the set of all the negative samples generated by all our sampling techniques for ground truth positive sample y". y" In contrast positive point which needs to satisfy all the m + constraints, negative point becomes infeasible even if it violates any one of the m + 1 constraints. As a result, it would suffice if any one of the m + 1 classifiers correctly classify it as negative sample (refer to appendix for an illustration). While learning, one should not assign a negative sample to any specific classifier as their parameters are being updated continuously. Instead, we make a soft assignment depending upon the distance of the negative sample from the hyperplane. With this intuition, we now formally define our ILP- Loss.
Formulating solver-free ILP-Loss: Let d(z; [a, bb])
af ba represent the signed Euclidean |a.
distance of a point E IR" from the hyperplane corresponding to the constraint [a. [b.]. We want the signed distance from all the hyperplanes to be positive for the ground truth samples and negative from at least one hyperplane for all the sampled negative points. We operationalize this via a margin
based loss function:
b,,,,,,,'WW, = Apos I, + Anogli~ + Avou where
(5)
1 m
L
max (0. pt da,";(a,[b;))) Σ
(6)
m
m+1
L_ = Wy
Σ
w max{0.1 pO + d(y [,,l,,))}
(7)
E.yy
1=1
m
a. aj
m
2
a,
Lo
(8)
|a.] [agl
az
iJ layi
wy (-dd(y ((/:/(/((:)))/))
(9)
We call T.,, T__,, and T.p as the positive, negative and covariance loss respectively. The average L4 ensures that ground truth sample is positively classified by all the classifiers. fut and μ are the hyperparameters representing the margins for the positive and the negative points respectively. w in
L_ represents the soft assignment of y to the tt constraint [a. and is computed by temperature
5

---

annealed softmax over the negative distances in eq. D.. Softmax ensures that the hyperplane which is most confident classify it as negative gets the maximum weight. When y lies inside the feasible region, then the most confident classifier is the one closest to y To avoid the pathological behaviour of decreasing the loss by changing the weights, we ensure that gradients do not flow through wy in
eq. (7).
The temperature parameter T needs to be annealed as the training progresses. A high temperature initially can be seen as 'exploration' for the right constraint that will be violated by y- This is important as the constraints are also being learnt and are almost random initially, so given negative y should not commit a particular hyperplane. Additionally, this encourages multiple constraints to be violated for each negative, which leads to robust set of constraints. As the training progresses, we reduce the temperature т, ensuring that the most confident classifier with the least signed distance gets almost all the weight, which can be seen as "exploitation' of the most confident classifier. y is correctly classified as negative with a margin μ by any classifier i.e. d(y : (b:l)) S -H for some i, then the corresponding negative loss, max(0, fr + d [a, becomes zero, and a low value of r ensures that it gets all the weight.
The last term Lo acts as regularizer and tries to ensure that no two learnt constraints are similar. We call it the covariance loss as it maximizes the covariance between the constraint unit vectors. Equivalently, it minimizes the cosine similarity between all pairs of constraints. The weights Apos, Angg. and Aeee are computed dynamically during training with multi-loss weighing technique using coefficient of variations as described in Groenendijk et al. [202T. Intuitively, the loss term with maximum variance over the learning iterations adaptively gets most of the weight.
Other details:
Parameterization of equality constraints: Recall that we replace an equality uf = v, by two inequality constraints: V: S u. z S v,, In practice, to enhance learnability, we add a small margin of e on both sides: V, - c S uf z S V; + c. We pick an c small enough so that the probability of the new feasible region to include an infeasible integral point is negligible, but higher than 2² so that the positive point can be inside the polyhedron by the specified margin.
Known boundaries: In many cases, the boundary conditions on the output variables are known, i.e., z y [1. u|"", where and u are the lower and upper bounds on each dimension of z. We handle this by adding known boundary constraints: S z; S u. Vi E (1...n).
of constraints: As done in Paulus et al., we also over wee-paaameterize each constraint hyperplane by an additional learnable offset vector o, which can be viewed as its own local origin. Radius r; represents its distance from its own origin og, resulting in the following hyperplane in the base coordinate system: a! z + r; of a alal 2 O.
Initialization of A: The way we initialize the constraints may have an impact on the learnability. While [Paulus et al., [222] propose to sample each entry of a; uniformly (and independently) between [-0.5, 0.5]. we also experiment with standard Gaussian initialization. The latter results in initial hyperplanes with their normal directions (a,'s s) uniformly sampled from a unit hyper-sphere. In expectation, such initialization achieves minima of Lo that measures total pairwise covariance.
3.3 Negative Sampling
A meaningful computation of ILP-Loss in eq. (5) depends crucially on the negative samples Ny- Randomly sampling negatives from 2n is one plausible strategy, but may not be efficient from the learning perspective: any point which is far away from any of the classifiers will easily be classified as negative and will not contribute much to the loss function. In response, we propose multiple alternatives for sampling the negative points:
Integral k-hop neighbours: We sample the integral neighbours that are an L1 Distance of from y For small k. these form the hardest negatives as they are closest to the positive point. Note that it is possible for few integral neighbours to be feasible w.r.t. the m constraints, but they must have worse cost than the given ground truth y". Such samples contribute towards learning the cost parameters fc..
2. Project and sample: We project the ground truth y" on each of the m hyperplanes and then randomly sample an integral neighbour of the projection, generating a total of m negatives. Sampling probability in the jth dimension depends on the jth coordinate of the projection: if value of the jth coordinate is r & Z, then we sample floor(r) and ceil(r) with probability ceal(r) - r and - floor(r) respectively. If r E Z, then sample r with probability 1. Projection samples are

---

Table 1: Board accuracy and training time for different board sizes of symbolic and visual sudoku (for CombOptNet, "." denotes time-out after 12 hours)
Symbolic Sudoku
Visual Sudoku
Board Accuracy (%)
Training Time (min)
Board Accuracy
(%)
Training Time (min)
4x4
6x6
9x9
4x4
6x6
9x9
4x4
6x6
9x9
4x4
6x6
9x9
Neural (RRN)
100.0
99.1
91.3
110
99.8
97.5
71.1
120
65
97
CombOptNet
0.0
0.0
0.0
0.0
0.0
0.0
SATNet
100.0
96.8
28.5
74
299
98.0
80.8
17.8
79
89
205
ILP-LLss (Ours)
100.0
100.0
100.0
2
52
99.7
98.8
98.3
3
11
92
close to the boundary of the currently learnt polyhedron, thus taking the training progress into account. Further, each hyperplane is likely to be assigned to close-by negative due to projection sampling. 3. Batch negatives: We consider every other ground truth y; s' + s in the minibatch as a potential negative sample for y This is particularly useful for learning the cost parameters 0g when the learnable constraints are the same for all the ground truth samples, such as in sudoku. In such cases, batch-negative y being a feasible point of the original ILP formulation, must always satisfy all of the m learnable constraints of the original ILP in eq. (2). Hence, the only way for y to be correctly classified negative for y is by violating the cost constraint in eq. (4), Learning cost parameters Oe that result in violation of the cost constraint for every batch-negative helps in ensuring that the ground truth y indeed has the minimum cost.
4. Solver based: Although our approach is motivated by the objective of avoiding solver calls, our framework easily extensible to solver-based training by using the solution the currently learnt ILP as a negative sample. This is useful when the underlying neural networks parameterizing A, b or are the bottleneck instead of the ILP solver. While we do not use solver negatives by default, we demonstrate their effectiveness in one of our experiments where the network parameterizing indeed takes most of the computation time.
Experiments
The goal of our experiments is to evaluate the effectiveness and scalability of our proposed approach compared to the SOTA black-box solver based approach. i.e.. CombOptNet (Paulus et al.) [202]]. We experiment on 4 problems: symbolic and visual sudoku [Wang et al., 2019]. and three problems from [Paulus et al., 2021]: random constraints, knapsack from sentence description and key-point matching, We also compare with an appropriately designed neural baseline for each of our datasets. To measure scalability, in each of the domains, we compare performance of each of the algorithms in terms of training time, as well as accuracy obtained, for varying problem sizes. For each of the algorithms, we report time till the epoch that achieves best val set accuracy and exclude time taken during validation. We kept a maximum time limit of 12 hours for training of each algorithm. We next describe details of each of these datasets, appropriate baselines, and our results. See the appendix for the details of the ILP solver used in our experiments, the hardware specifications, the hhper--arammee parameters, and various other design choices.
4.1 Symbolic and Visual Sudoku
This task involves learning the rules of the sudoku puzzle. For symbolic sudoku, the input vr is a matrix of digits whereas for visual sudoku, the x is an image of sudoku puzzle where a digit is replaced by a random MNIST image of the same class. A x k sudoku puzzle can be viewed as an ILP with 4 equality constraints over 33 binary variables [Bartlett al. 2008). For symbolic sudoku, each of the x2 cells of the puzzle is represented by a k dimensional binary vector which takes value of 1 at 2th dimension if and only the cell is filled by digit i, resulting in a A33 dimensional representation of the input x E R. where n = k3 On the other hand, for visual sudoku, each of the digit images in the 1.2 cells are decoded (using a neural network) into a dimensional real vector, resulting in 33 dimensional learnable cost c E R". The 1.3 dimensional binary output vector (solution) y* is created analogous to symbolic input. Our objective is to learn the constraint matrix A = SA (x; 0x) = O^ and vector b = [n(2;; 0,) = Ob. representing the linear constraints of sudoku. For symbolic sudoku, the cost vector e = -x is known, where as for visual sudoku, the cost vector (z; 0c) is function of the input image æ, parameterized by 0. which also needs to be learned.
7

---

Table 2: Mean of the vector accuracy (Ma(x) and training time over the 10 random datasets in each setting of Random constraints. Number of learnable constraints is twice the number of ground truth constraints. See appendix for std. err. over the 10 runs.
Vector Accuracy (%)
Training Time (min)
2
8
1
4
CombOptNet
97.6
95.3
84.3
63.4
8.2
13.5
26.5
40.8
Binary
ILP-Loss (Ours)
97.8
96.0
92.8
87.8
7.3
11.6
18.1
27.5
CombOptNet
89.3
74.8
34.3
2.0
9.9
16.8
24.7
48.2
Dense
ILP-L (Ours)
96.6
86.3
74.0
41.5
7.3
15.6
17.6
20.6
We experiment with 3 different datasets for k 4, 4,6, and 9. We first build symbolic sudoku puzzles with & digits, and use MNIST to convert puzzle into an image for visual sudoku. For 9 x sudokus, we use a standard dataset from Kaggle [Park] 2017), for k = 4 we use publically available we use the data generation process described in Nandwani et al. [2022]. We randomly select 10, 000 samples for training, and 1000 samples for testing for each k. To generate the input images for visual-sudoku, we use the official train and test split of MNIST Deng 2012]. Digits in our train and test splits are randomly replaced by images in the MNIST train and test sets respectively, avoiding any leakage.
Dataset:
data from Areot and Kalluraya (2019), and for
Our neural baseline is Recurrent Relational Networks (RRN) Palm et al. 2018: a purely neural approach for reasoning based on Graph Neural Networks. We use the default set parameters provided in their paper for training RRNs. We note that the RRN baseline uses additional information in the form of graph structure which not available to our solver. We make this comparison to see how well we perform compared to one of the SOTA techniques for this problem. We also compare against another neuro-symbolic architecture using SATNet [Wang et al. [019)] as the reasoning layer. The neural component in all the neuro-symbolic methods is CNN that decodes images into digits.
Baselines:
Results: Table 1 compares the performance and training time of our method against the different baselines described above. CompOptNet fails miserably on this problem, not being able to complete training for any of the sizes in the stipulated time. The purely neural model gives a decent performance and is competitive with ours for smaller board sizes. But for larger board size of 9 x 9, we beat RRN based model by a significant margin of about 25 points and points in visual and symbolic sudoku, respectively. While SATNet performs comparable on smaller 4 x 4 sudoku puzzles, its performance degrades drastically to 17.8% for x 9 board size on visual sudoku. See appendix for a comparison on the dataset used in Wang et al. [2019].
4.2 Random constraints
This is the synthetic dataset borrowed from Paulus al., The training data D = y(cs,y))ls e {1 [1..-S}} }}}
is created by first generating a random polyhedron P Y by sampling m' hyper- planes [[a[b/]] a', b' R",i E {1 [1...mm)} in an n dimensional bounded continuous space V. A cost vector C2 E R. is then randomly sampled and corresponding y is obtained as y = arg min c 2, z E Z". Objective is to learn a constraint matrix A and vector b such that for ground truth y") pair, y" = arg minzey c²z, z, E Z", and Az + b 0. 0.
Restricting )' to [0. 1J" and [-5, 5]th results in two variations, referred as 'binary' and 'dense" settings, respectively. For both of the output spaces, experiment with four different settings in n = 16 dimensional space by varying the number of ground truth constraints as m' = 1,2, 4, and 8. For each m', we experiment with all the 10 datasets provided by Paulus al. and report mean and standard error over the 10 models. The training data in each case consists of 1600 (c,y) pairs and model performance tested for 1000 cost vectors.
Dataset:
Baseline: Here we compare only against CombOptNet. A neural baseline (an MLP) is shown to perform badly for this symbolic problem in |Paluus et al.] Hence we exclude this in experiments.
Results: Table 2 presents the comparison of the two algorithms in terms of accuracy as well as time taken for training. While we perform marginally better than CombOptNet in terms of training time, our performance is significantly better, on almost all problems the dense setting, and the larger problems in the binary setting. We are roughly 25 and 40 accuracy points better than CombOptNet
8

---

Table 3: Mean accuracy and train-time over 10 runs for various knapsack datasets with different
number of items in each instance. For N = 25, 30. "-" represents timeout of 12 hours and we evaluate using the latest snapshot of the model obtained within 12 hours of total training. See appendix for std. err. over the 10 runs.
Vector Accuracy (mean in %)
Training Time (mean in min)
10
15
20
25
30
10
15
20
25
30
CombOptNet
63.2
48.2
30.1
2.6
0.0
41.0
61.4
153.0
ILP-Loss (Ours)
71.4
58.5
48.7
41.0
28.4
44.0
51.0
82.2
106.1
111.6
on the largest problem instance with 8 constraints in the binary and dense settings respectively. This result demonstrates that our approach is not only faster in terms of training time, but also results in better solutions compared to the baseline, validating the effectiveness of our approach.
4.3 Knapsack from Sentence Descriptions
This task, also borrowed from Paulus et al., is based on the classical NP-hard Knapsack problem. Each input consists of N sentences describing the price and weight of N items and the objective is to select subset of items that maximizes their total price while keeping their total weight less than the knapsack's 's capacity C:: arg maxp" z s.t. w z S C, Z E {0. 1). where p. w E R are the price and weight vectors, respectively. Each sentence has been converted into a d 4096 dimensional dense embedding using Conneau et al. [2017]. so that each input is N x d dimensional vector x. The corresponding output is y" E (0, 1 The knapsack capacity C' fixed for all instances in a dataset. The task is to learn the parameters fe. A and lb of a neural network that extracts the cost and the constraints from x. Note that here both the cost and the constraints need be inferred from the input.
The dataset in Paulus et al. has 4500 train and 500 test instances with fixed N = 10 items, extracted from a corpus containing 50, 000 sentences and their embeddings. In addition to experimenting with the original dataset, to demonstrate the scalability of our method, we also bootstrap new datasets with N 15, 20, 25 and 30, by randomly selecting sentences from the original corpus. Each bootstrapped dataset has 4500 train and 500 test instances.
Dataset:
Results: Table presents a comparison between the training time and accuracy of our method against CombOptNet. We significantly outperform the baseline in terms of accuracy across all the datasets. For the smallest problem size with only 10 items, our training time is comparable to the baseline. This is expected as for small problems, ILP may not be the bottleneck, and the relative speedup obtained by solver free method gets offset by the increased number of iterations it may require train. Our relative gain increases significantly with increasing problem size. CombOptNer fails to complete even a single epoch in the stipulated time and results in 0% accuracy on the largest problem.
4.4 Keypoint Matching
Here we experiment on a real world task of matching key points between two images of different objects of the same type Rolínek et al. [2020b). The input consists of pair of images (I1 I2) of the same type along with a shuffled list of coordinates (pixels) of & keypoints in both images. The task is to match the same keypoints in the two images with each other. The ground truth constraint enforces a bijection between the keypoints in the two images. The output y is represented as a l x k binary permutation matrix, i.e., entries in a row or column should sum to The cost is k sized vector parameterized by 0c. The goal is to learn A, b and 0c-
Dataset: We experiment with image pairs in SPair- 17k [Min al. 2019] dataset used for the task of keypoint matching in [Rolinek et al. 2020b). Since the neural ILP models can deal with a fixed size output space, we artificially create 4 datasets for 4, 5, 6 and 7 keypoints from the original dataset. While generating samples for i keypoints dataset, we randomly sample any i annotated pairs from input image pairs that have more than A keypoints annotated. See appendix for details dataset size.
We compare against a strong neural baseline which same as the backbone model parameterizing the 2²2 dimensional cost vector in [Rolínek et al. 2020b). It is trained by minimizing BCE loss between negative learnt cost (-c) and target y". We create an additional baseline by doing constrained inference with ground truth constraints and learnt cost ('Neural + CT)) in table 4
Baselines:

---

Table Average point-wise accuracy and training times over runs with different random seeds for varying # of keypoints. Neural + CI denotes ILP inference with known constraints over the cost learnt by neural model. See appendix for std. err. over the runs.
Pointwise Accuracy (in %)
Training Times (in min)
7
4
7
Neural Neural + CI
80.88
78.04
75.39
73.49
148
37
3
40
82.42
79.99
77.64
75.88
148
37
30
40
CombOptNet ILP-Loss (Ours)
83.86
81.43
78.88
76.85
41
67
144
279
81.76
79.59
77.84
76.18
115
92
106
109
ILP-Loss + Solver (Ours)
84.64
81.27
79.51
78.59
43
73
99
174
Table 4 presents the percentage of keypoints matched correctly by different models. In this experiment, the bottleneck w.z.. time is the backbone neural model instead of the ILP solver. Therefore, we also experiment with solver based negatives in our method (ILP-Loss + Solver). While ILP--Los using solver-free negatives performs somewhat worse than CombOptNet in terms of its aceuracy, especially for smaller problem sizes, using solver based negatives helps ILP--Lss surpass CombOptNet in terms of both the accuracy and training efficiency for large problem sizes (and makes it comparable on others). This is because a solver based negative sample is guaranteed to be incorrectly classified (as positive) by the current hyperplanes, and hence provides a very strong training signal compared to colver-free negatives in ILP-Loss. We obtain gain of up to points over the Neural baseline, which is roughly double the gain obtained by Neural CI.
Results:
5 Conclusion and Future Work
We have presented a solver-free framework for scalable training of a neural ILP architecture. Our method learns the linear constraints by viewing them linear binary classifiers, separating the positive points (inside the polyhedron) from the negative points (outside the polyhedron). While given ground truth acts as positives, trick using the available ground truth outputs in the training data, converts the cost vector into a constraint, enabling us learn the cost vector and constraints in similar fashion.
propose multiple strategies for sampling negatives. A simple
Future work involves extending our method to neural-11 Saai-------uurd architectures, i.e., where the output of ILP is an input to a downstream neural model (see appendix for a detailed discussion). Second, neural ILP model works with a fixed dimensional output space, even though the constraints for the same underlying problem are the same in first order logic, e.g., constraints for k x k sudoku puzzles remain the same in first order irrespective of Creating neural ILP models that can parameterize the constraints the basis of the size of the input (or learnt) cost vector is a potential direction for future work. Lastly, the inference time with the learnt constraints can be high, especially for large problems like 9 x 9 sudoku. In addition, the learnt constraints might not be interpretable even if the ground truth constraints are. In future, we would like to develop methods that distill the learnt constraints into a human inmmannitterpectbble form, which may address both these limitations.
Acknowledgements
We thank IIT Delhi HPC facility for computational resources. We thank anonymous reviewers for their insightful comments that helped in further improving our paper. We also thank Ashish Chiplunkar, whose course on Mathematical Programming helped us gain insights into existing methods for ILP solving, and Daman Arora for highly stimulating discussions. Mausam is supported by grants from Google, Bloomberg, 1MG and Jai Gupta chair fellowship by IIT Delhi. Parag Singla was supported by the DARPA Explainable Artificial Intelligence (XAD) Program with number 166001-17-2-400) Both Mausam and Parag are supported by IBM AI Horizon Networks (AIHN) grant and IBM SUR awards. Rishabh is supported by the CSE Research Accelcration fund of IIT Delhi. Any opinions, findings, conclusions recommendations expressed in this paper those of the authors and do not necessarily reflect the views or official policies, either expressed or implied, of the funding agencies.
hhap://sapercooputinggittt. iitd.accinnitt.ii
10

---

References
Ananye Agarwal, Pradeep Shenoy, and Mausam. End-to-end neuro-symbolic architecture for image- to-image reasoning tasks. CoRR, abs/2106.03121, 2021. URL httpl/ttpp:/aaiii.or/////// 03121
Akshay Agrawal, Brandon Amos, Shane T. Barratt, Stephen P. Boyd, Steven Diamond, and Zico Kolter. Differentiable convex optimization layers. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, ed- itors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrlPS 2019, December 8-14, 2019, Vancouver BC, Canada. pages 9558 9570, 2019. URL pattps::/proceeddee httpppoooeennnnn....iii.....e..s wt/ppper//019..99///////// 181 Abstract html
Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. Learning to solve circuit-sat: An unsupervised differentiable approach. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6.9, 2019. OpenReview.net, 2019a. URL https //opnnreveev.eer -
Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. PDP: A general neural framework for learning constraint satisfaction solvers. CoRR, abs/1903.01169, 2019b. URL http::/arxix: org/abs/11 1901/999090000999901
Brandon Amos and J. Zico Kolter. Optnet: Differentiable optimization as layer in neural net- works. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-1 I August 2017, vol- ume 70 of Proceedings of Machine Learning Research, pages 136-145. PMLR, 2017. URL htttp://proceedingg mw.. wal..press/vv00 vatess//v0//mm1111 m7mos1a... html
Vaibhav Arcot and Samarth Kalluraya. Data set of 4x4 sudoku puzzles and solutions. 2019.
https
//github. Btte/BBackPPoooo
Saag-Suuoku--ataane
Aniket Bajpai, Sankalp Garg, and Mausam. Transfer of deep reactive policies for MDP planning. In Advances Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 10988- 10998. 2018
Andrew Bartlett, Timothy Chartier, Amy Langville, and Timothy Rankin, An integer programming model for the sudoku problem. 04 2008.
Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Phinlppil Vert, and Francis Bach. Learning with differentiable pertubed optimizers. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9508 9519. Curran Associates, Inc., 2020. URL fappe//220//51e//6b555/22 /ttp://20...///66600000000006660
neurips cc/
pdf
Timothy C. Y. Chan, Rafid Mahmood, and Ian Yihang Zhu. Inverse optimization: Theory and applications. 2021.
Alexis Conneau, Douwe Kiela, Holger Schwenk, Loie Barrault, and Antoine Bordes. Supervised learning of universal sentence representations from natural language inference data. In Martha Palmer, Rebecca Hwa, and Sebastian Riedel, editors, Proceedings of the 2017 Conference Empirical Methods in Natural Language Processing, EMNLP 2017, Copenhagen, Denmark, September 9-11, 2017, pages 670 680. Association for Computational Linguistics, 2017. doi: 10.18653/v1/417-1007 URL htttps:///ol org/
argg/1...0 10. 10..1886///11110000
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6): 141-142, 2012.
Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic machines. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL /tll:tttp://oopeeeevieee wttp:e/wwwwweeeomteeimam BixY-hRcae

---

Aaron M. Ferber. Bryan Wilder, Bistra Dilkina, and Milind Tambe. Mipaal: Mixed integer program as a layer. In The Shirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The "hirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York NY,
USA, February 7-12, 2020, pages 1511-1511. AAAI Press, 2020. URL Sictps://ooj. aaai oxg/index.o php/ /tt.///aaaaieeeeiie////e////
Sankalp Garg, Aniket Bajpai, and Mausam. Size independent neural transfer for RDDI. planning. In Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling. ICAPS 2018, Berkeley, CA, USA, July 1 11-15, 2019, pages 631-636. AAAI Press, 2019.
Sankalp Garg, Aniket Bajpai. and Mausam. Symbolic network: Generalized neural policies for relational mdps. In Proceedings of the 37th International Conference on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 2397-3401 PMLR, 2020.
Ralph E. Gomory. Outline of an algorithm for integer solutions to linear programs and an algorithm for the mixed integer problem. In Michael Jünger, Thomas M. Liebling, Denis Naddef, George Nemhauser, William R. Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, and Laurence A. Wolsey, editors, 50 Years of Integer Programming 1958-2008 From the Early Years to the State-of- the-Art, pages 77-103. Springer, 2010. doi: 10. 10.1007/978-3-540--633 //doi.org// 10. 1007 /978- 3 540 68279-06827---44
4. URL https
Stephen Gould, Richard Hartley, and Dylan Campbell. Deep declarative networks: A new hope. CoRR,
2019. URL http://aaaiii.oogaa//////// 04866
org.
Rick Groenendijk, Sezer Karaoglu, Theo Gevers, and Thomas Mensink. Multi-loss weighting with coefficient of variations. In IEEE Winter Conference on Applications of Computer Vision, WACV 2021, Waikoloa, HI, USA, January 3-8, 2021, pages 1468-1477. IEEE, 2021. doi: 10.1 WACV48630.2021.00111 00155
URL https://ddoooo org 10. 1109/11C////A330 010330.2221.0000 00151
Gurobi Optimization, LLC.
Gurobi Optimizer Reference Manual, 2022. URL https://wwx
gurobi com
Rujun Han, Qiang Ning, and Nanyun Peng. Joint event and temporal relation extraction with shared representations and structured prediction. In Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan, editors, Proceedings of the 2019 Conference Language Processing and the 9th International Joint Conference on Natural Language Processing, E.NLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019, pages 434 444. Association for Computational Linguistics, 2019. doi: 10. 10.18653/1//119-111 1041. URL /ttpp://ddoi 18653/v1/D19-1041
Empirical Methods in Natural
Alex Kantchelian, Michael Carl Tschantz, Ling Huang, Peter L. Bartlett, Anthony D. Joseph, and J. Doug Tygar. Large-margin convex polytope machine. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger, editors, Ad- vances in Neural Information Processing Systems 27: Annual Conference on Neural In- formation Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada. wttprips.cc/pappe/214////// 311766111100/111999500000aaaaaa Abstract. html
pages 2248-2256, 2014. URL https: h/tp///eeceeeeeeeeeeeeeea htttpps//pprroeeiiinng
Tao Li and Vivek Srikumar. Augmenting neural networks with first-order logic. ACL, 2019, 2019, 2019.
Jayanta Mandi and Tias Guns. Interior point solving for 1p-based prediction-opiiiistion. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Con- ference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 12, 2020, virtual, 2020. URL https:://rocesd// wwwpeediiinnnnnnnns.oee httppps.ccpppp///p/epeepp httpp/ppppp/p/////eeeee 22020/2222/h// 13311002eesaae00032222e333311ee1 Abw.raeetee-tttt....t.....
Tao Meng and Kai-Wei Chang. An integer linear programming framework for mining constraints from data. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International
12

---

Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 7619-7631, PMLR, 2021. URL http https//1113mmmegg2mmm html
//proceedings.mlr
Juhong Min, Jongmin Lee, Jean Ponce, and Minsu Cho. Spair-7lk: A large-scale benchmark for semantic correspondence. CoRR, abs/1908. 10543, 2019. htRp:///://arrt http/axxvv..roo org/ org/abs//gaooo.oo/ooooooe abs/1908
10543
Giovanni Mingari Scarpello and Daniele Ritelli. A historical outline of the theorem of implicit functions. Divulgaciones Matemáticas, 10, 01 2002.
Yatin Nandwani, Abhishek Pathak, Mausam, and Parag Singla. A primal dual formula- tion for deep learning with constraints. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alcé--Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeuriPS 2019, December 8-14, 2019, Vancouver, BC, Canada. pages 12157-12168, 2019. URL https: ptttps://proceedingg
c
Abstract.
Yatin Nandwani, Deepanshu Jindal, Mausam, and Parag Singla. Neural learning of one-of-many solutions for combinatorial problems in structured output spaces. In International Conference on Learning Representations (ICLR), 2021.
Yatin Nandwani, Vidit Jain, Mausam, and Parag Singla. Neural models for output-space invariance in combinatorial problems. In International Conference on Learning Representations (ICLR), 2022. URL hwtph:ttttttttttee htg. ab2/2202. 03229
Mathias Niepert, Pasquale Minervini, and Luca Franceschi. Implicit mle: Backpropagating through discrete exponential family distributions. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34. neurips. cc/ Paper pdf
pages 14567-14579 Curran Associates, Inc., 2021. URL /t2pe//2227//22///33330002222220
Qiang Ning, Sanjay Subramanian, and Dan Roth. An improved neural baseline for temporal relation extraction. In Kentaro Inui, Jing Jiang. Vincent Ng. and Xiaojun Wan, editors, Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLE 2019, Hong Kong, China, November 3-7, 2019, pages 10.18653/v1/DI1 1642. URL /tgg///oo.oo//////////////////// 18653 11tp//////99114/////
Association for Computational Linguistics, 2019. doi:
Rasmus Berg Palm, UIrich Paquet, and Ole Winther. Recurrent relational networks. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada, pages 3782,332, 2018. URL httpttttp//ppprree nips
netwrrs
Xingyuan Pan and Vivek Srikumar. Expressiveness of rectifier networks. In Maria-Florin Balcan and Kilian Q. Weinberger, editors, Proceedings of the 33nd International Conference on Machine Learning. ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 2427-2435. JMLR.org, 2016. URL http::::::://eeeeeee/e v48/ panb16. html
mlr. www.e/reseeeee we//e////////eee/eeee.
Xingyuan Pan, Maitrey Mehta, and Vivek Srikumar. Learning constraints for structured prediction using rectifier networks. In Dan Jurafsky. Joyce Chai, Natalie Schluter, and Joel R. Tetreault, editors, Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACI 2020, Online, July 5- 10, 2020, pages 4843 4858. Association for Computational Linguistics. 2020. doi: acl-main 438
URI. https: htttps:///oi....... http::////ooooo/.....oo// 1815////1066533//22222
George Papandreou and Alan L. Yuille. Perturb-and map random fields: Using discrete optimization to learn and sample from energy models. Dimitris N. Metaxas, Long Quan, Alberto Sanfeliu, and Lue Van Gool, editors, IEFE International Conference on Computer Vision, ICCV 2011, Barcelona, Spain, November 6-13, 201 I, pages 193-200. IEFE Computer Society, 2011. doi: LLLL19/CCCV.201111222444 URL https: /oi. org/ 10. 1109/IICV.....// wwt.............. 6126242
13

---

Kyubyong Park. million sudoku games. https://ww.kkggle.. sudoku, 2017.
Anselm Paulus, Michal Rolínek, Vit Musil, Brandon Amos, and Georg Martius. Comboptnet: Fit the right np-hard problem by learning integer programming constraints. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, PMLR, 2021. URI http:ttt:ppppccceeiiiieee
pages
mlr wtwpss/vis////eeeee.. pttp://s///pauuuulaaaa paulus21a
html
Marin Vlastelica Pogancic, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Dif- ferentiation of blackbox combinatorial solvers. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
URL htttt::://pppseeee http:/ppwwweeeeeeeeeeeeereroeree http:///www.eeeeeeeedeedd-aeeeee dd-BummoJs--
Rishabh Ranjan, Siddharth Grover, Sourav Medya, Venkatesan Chakaravarthy, Yogish Sabharwal, and Sayan Ranu. Greed: A neural framework for learning graph distance functions. In Advances in Neural Information Processing Systems 35: Annual Conference Neural Information Processing Systems 2022, NeurlPS 2022, November 29-Decemer I, 2022, 2022.
Michal Rolínek, Vit Musil, Anselm Paulus, Marin Vlastelica P., Claudio Michaelis, Optimizing rank-based metrics with blackbox differentia-
and Georg Martius. tion. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recogni- tion, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pages 7617-7627. Computer URL
Vision Foundation / IEEE, 2020a. doi: 10. 10.1109/CVPR-2200020000 attps://openaccess. thecvf. com//ooneent_CVRR http:///PP..2220//mm/o/oooooooo wwceBooooiee____eee Bww.cllaacaaiiieeececcee
http:///woonneeee..pieeiiiiigen Saank-BBaed_Metriccscc htwp://werrootttt..ccccoooooeeee Baa.cbbox_DDffeereetiiatiioooo.t CVPR, 2020_paperr html.
Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vit Musil, and Georg Martius. Deep graph matching via blackbox differentiation of combinatorial solvers. In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm, editors, Computer Vision ECCV 2020 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XXVIII, volume 12373 of Lecture Notes in Computer Science, pages 407-424. Springer, 2020b. doi: 1007/ 978-3-030-58604-11222 URL htLLhhtts:
10.
1_25
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L. Dill. Learning a SAT solver from single-bit supervision. In 7th International Conference on Learning Representaatons, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https::/openrevvexx net/ forum?id=HJJC. _
Vishal Sharma, Daman Arora, Florian Geißer, Mausam, and Parag Singla. Symnet 2.0: Effectively handling non-fluents and actions in generalized neural policies for rddl relational mdps. In Proceedings of the Tiihth-Eighth Conference on Uncertainty in Artificial Intelligence, UAI 2022, Eindhoven, Netherlands, August 1-5, 2022, 2022.
Yingcong Tan, Andrew Delong, and Daria Terekhov. Deep inverse optimization. In Louis- Martin Rousseau and Kostas Stergiou, editors, Integration of Constraint Programming, Arti- ficial Intelligence, and Operations Research 16th International Conference, CPAIOR 2019, Thessaloniki, Greece, June 4-7, 2019, Proceedings, volume 1 11494 of Lecture Notes in Com- puter Science, pages 540-556. Springer, 2019. doi: 10. https://doo orgo/r///// 10.
URL
Yingcong Tan, Daria Terekhov, and Andrew Delong. Learning linear programs from optimal decisions. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: An- nual Conference on Neural Information Processing Systems 2020, NewrlPS 2020, December 6-12, 2020, virtual, 2020. URL Awttrrtttttrtttttoccooooo
Po-Wei Wang, Priya I.. Donti, Bryan Wilder, and J. Zico Kolter. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA,
14

---

volume 97 of Proceedings of Machine Learning Research, pages 6545-6554, PMLR, 2019. URL http://prroceedings mlr, walr.prese wwwpppesssss.pp veress//v///aagg9ee wwwglee........ html
Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision- focused learning for combinatorial optimization. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial In- telligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27- February 1, 2019, pages 1658-1663) AAAI Press, 2019. doi: 10.1609/aaai http:/aai.v3330....33333 1658.
URL https
7/doi.org//i 1609/ aaai.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]. In Conclusion and future works section 5
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [Yes] Code is now available at httpp::/gihuu....o////// cowoom/aaaiidiippplie
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Details are in experiments section under "Training Methodology' and in the appendix.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] In three out of four experiments.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] In the experiments section
4. If you using existing assets (e.g., code, data, models) or curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] Datasets are cited in the respective experiment sections.
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you' 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "btIGWvSoT3", "reviewer": "Reviewer_ZncX", "summary": "This paper introduces a solver-free approach for learning the constraint and cost parameters of an integer linear program from data. This means that the method does not rely on an expensive invocation of the ILP solver on the forward pass.\nInstead, it relies on the available ground-truth solutions to train a set of soft max-margin classifiers corresponding to the ILP constraints and one additional constraint representing the cost.\nThe classifiers are trained such that a ground truth solution is classified positively by all classifiers, and any other integer point (sampled to be difficult to classify) is classified negatively by at least one of the classifiers.\n\nThe presented method (ILP-Loss) is evaluated on three experiments, including visual sudoku, random synthetic constraints, and a real-world keypoint matching benchmark. The main competing method is CombOptNet [1], which relies on invoking the ILP solver on every forward pass.\n\nIn the visual Sudoku experiment, the authors also include an additional SOTA baseline (RRN [2]) which is based on a graph neural network. ILP-Loss outperforms the RRN baseline on the largest board instances and performs comparably on the smaller ones while training significantly faster. CombOptNet times out after a very long training time, presumably because the ILP solver invocations dramatically slow down the training.\nIn the random constraints experiment, ILP-Loss again outperforms CombOptNet in terms of accuracy and runtime.\nFinally, in the keypoint matching experiment, ILP-Loss is shown to achieve comparable performance to CombOptNet at a similar runtime, as the computational bottleneck of this experiment is in the neural network backbone.\n\n[1]: Anselm Paulus, Michal Rolínek, Vít Musil, Brandon Amos, and Georg Martius. Comboptnet: Fit the right np-hard problem by learning integer programming constraints. ICML 2021. \n\n[2]: Rasmus Berg Palm, Ulrich Paquet, and Ole Winther. Recurrent relational networks. NeurIPS 2018.", "questions": "See the suggestions in the quality section.", "limitations": "The authors discussed the limitation that currently a neural-ILP-neural architecture is not possible with the presented method. It would be great to include a short discussion of why this is not possible, and contrast it with some of the existing work which is applicable to this setting.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Originality\nThe authors present a method for learning the constraint and cost coefficients of an ILP as multiple soft max-margin classifiers. While this approach has already been used to learn a classifying convex polytope from data (as also mentioned by the authors in the abstract), this is to the best of my knowledge the first time that the cost terms have been learned as an additional classifier, thereby extending the setting to cover integer linear programs.\n\n### Quality\nOverall the quality of this paper is good.\nHowever, there is one major weakness in my opinion, which is a missing evaluation of the setting in which there is no single set of constraints describing the whole dataset, but in which instead the constraints depend on the input $x$. The presentation of the method suggests that this is doable (line 157), however, none of the experiments validates this. I am particularly surprised by the missing comparison as such an experiment has already been included in [1], and while all the other experiments from [1] were repeated this is the only one missing. I would ask the authors to include a comparison on this experiment, as I believe in any case (the presented method performing good or bad), the community would gain important insights. I will raise my rating of this paper if the authors include the missing comparison.\n\nIn addition, I would like to also point out that the papers [1,3,4], which are cited as neural-ILP architectures (line 44), are in fact capable of (and designed as) neural-ILP-neural architectures. This provides important context, especially for the experimental comparison to [1], and therefore should be corrected and discussed.\n\n### Clarity\nThe clarity of the paper is good, it is easy to read and understand the introduced method.\n\n### Significance\nI think this paper is significant, as it appears to be the currently best method for learning the constraint parameters of a neural-ILP architecture. The performance on Visual Sudoku outperforming the current state-of-the-art method is impressive and demonstrates the capabilities of the presented method.\n\n\n\n[3]: Marin Vlastelica Pogancic, Anselm Paulus, Vít Musil, Georg Martius, and Michal Rolínek. Differentiation of blackbox combinatorial solvers. ICLR 2020.\n\n[4]: Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Jean-Philippe Vert, and Francis Bach. Learning with differentiable pertubed optimizers. NeurIPS 2020.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JDu0hr3Y26E", "reviewer": "Reviewer_HE5s", "summary": "This work proposes a novel method for end-to-end training integer linear programming. The proposed method converts the ILP problem into a satisfiability problem, in which all constraints are transformed into inequalities. During the learning stage, the parameters of the inequality constraints can be learned via gradient descent given positive examples and randomly sampled negative examples. Experiments show that the proposed approach is effective and scalable. However, I am not an expert in integer programming, so I cannot judge the novelty of this work.", "questions": "1. Is it possible to recover the inequalities from the learned parameters?\n2. How does your method perform when comparing to SATNet?\n", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n1. The proposed approach is more scalable than previous methods, and the performance is good.\n2. This paper has covered extensive related works and provides a detailed discussion about them.\n3. The authors also propose several effective methods for sampling negative examples.\n\nCons:\n1. Compared to the solver-based method, the proposed approach abandons the explicit symbolic representation, so it will be difficult to generalize outside of the training examples, e.g., training on 4x4 sudoku and test on 9x9 sudoku.\n2. Converting the problem to a classification problem increases the sample complexity.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Bkka303lxl", "reviewer": "Reviewer_ZzdC", "summary": "This paper presents a method  to reduce the cost of adding a final ILP stage to a NN..", "questions": "Tab 3 should have running times?\nRRNs: the extra info  is? Is it used by the RRN resukts in the paper?\nDiid you consider the other benchmarks in the RRN paper?\n3.2 How does your system handle misclassified data? Can you introduce slack?\n3.3 and 4,1 Why 3.3, given 4.1?\n3.4 what is the difference?", "limitations": "The main limitations addressed in this paper is scalability; it would be nice to have more application ex.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper explains its ideas clearly, It essentially transforms a linear ILP classifier into a continuous derivable problem my moving using distances to the hyperplanes. One may argue that this is not an ILP problem any longer, but it still stems from the original formulation, The results on sudoku loook good, supporting the idea,\n\nWeaknesses:\n- How easy it is to encode problems in LP?The examples are rater limited,\n- The other  results are not as supportive, namely Table 3 (what happened to the run-times?)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept