Differentiable Integer Linear Programming
Authors: Zijie Geng
Jie Wang
Xijun Li
Fangzhou Zhu
Jianye HAO
Bin Li
Feng Wu
Venue: ICLR 2025 Spotlight (2025)
Keywords: Integer Linear Programming
Learning to Optimize
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We propose a differentiable approach for learning to solve integer linear programming (ILP) problems with unsupervised learning.

Abstract: Machine learning (ML) techniques have shown great potential in generating high-quality solutions for integer linear programs (ILPs).
However, existing methods typically rely on a *supervised learning* paradigm, leading to (1) *expensive training cost* due to repeated invocations of traditional solvers to generate training labels, and (2) *plausible yet infeasible solutions* due to the misalignment between the training objective (minimizing prediction loss) and the inference objective (generating high-quality solutions).
To tackle this challenge, we propose **DiffILO** (**Diff**erentiable **I**nteger **L**inear Programming **O**ptimization), an *unsupervised learning paradigm for learning to solve ILPs*.
Specifically, through a novel probabilistic modeling, DiffILO reformulates ILPs---discrete and constrained optimization problems---into continuous, differentiable (almost everywhere), and unconstrained optimization problems.
This reformulation enables DiffILO to simultaneously solve ILPs and train the model via straightforward gradient descent, providing two major advantages.
First, it significantly reduces the training cost, as the training process does not need the aid of traditional solvers at all.
Second, it facilitates the generation of feasible and high-quality solutions, as the model *learns to solve ILPs* in an end-to-end manner, thus aligning the training and inference objectives.
Experiments on commonly used ILP datasets demonstrate that DiffILO not only achieves an average training speedup of $13.2$ times compared to supervised methods, but also outperforms them by generating heuristic solutions with significantly higher feasibility ratios and much better solution qualities.

Published as a conference paper at ICLR 2025
DIFFERENTIABLE INTEGER LINEAR PROGRAMMING
Zijie 2 Jie Wang" 1:1 Xijun Li", Fangzhou Zhu", Jianye Hao Bin Li', Feng Wul
University of Science and Technology of China
2 MoE Key Laboratory of Brain- brain-inspired Intelligent Perception and Cognition
3 Shanghai Jiao Tong University Noah's Ark Lab, Huawei
$ Tianjin University
z ji piegengemai .us.c.eeu..co {jiewangx, binli, fengwu) edu cn
1 xi junésjtu.en jtu.edu.cn, {zhufangzhou, haojianye (ayaeeehuwwwe coo
ABSTRACT
Machine learning (ML) techniques have shown great potential in generating high- quality solutions for integer linear programs (ILPs). However, existing meth- ods typically rely on a supervised learning paradigm, leading to (1) expensive training cost due repeated invocations of traditional solvers to generate train- ing labels, and (2) plausible yet infeasible solutions due to the misalignment be- tween the training objective (minimizing prediction loss) and the inference ob- jective (generating high-quality solutions). To tackle this challenge, we propose DiMIL (Differentiable Integer Linear Programming Optimization), an unsuper- vised learning paradigm for learning to solve ILPs. Specifically, through a novel probabilistic modeling, DifiILO reformulates ILPs ILPs discrete and constrained op- timization problems- problems-into continuous, differentiable (almost everywhere), and unconstrained optimization problems. This reformulation enables DiffILO to si- multaneously solve ILPs and train the model via straightforward gradient descent, providing two major advantages. First, it significantly reduces the training cost, the training process does not need the aid of traditional solvers at all. Second, it facilitates the generation of feasible and high-quality solutions, as the model learns solve ILPs in end-to-end manner, thus aligning the training and in- ference objectives. Experiments on commonly used ILP datasets demonstrate that Di not only achieves an average training speedup of 13.2 times compared supervised methods, but also outperforms them by generating heuristic solutions with significantly higher feasibility ratios and much better solution qualities.
INTRODUCTION
Integer linear programs (IL.s) are powerful tools in various areas such operations research, math- ematics, and engineering (Bixby et al., 2004, Bengio et al., 202I). They are able to model a broad range of combinatorial optimization (CO) problems and find diverse real-world applications, includ- ing scheduling (Ryan & Foster 1981), planning (Beyer et al. 2016). and network design (Koster et al. 2010). Despite their significant importance, ILPs inherently exhibit a complex combinatorial nature and are known as quintessential --rhhard problems, posing substantial challenges in solv- ing them efficiently. Therefore, extensive research and development efforts have been dedicated to advancing ILP solvers, such as SCIP (Achterberg) 2009) and Gurobi (Gurobi Optimization (02T). These solvers are mainly based on traditional algorithms such as Branch-and uund-Bound (B&B) (Land & Doig, 2010) and Branch-an Sach--nn--uuu (B&C) (Mitchell 22022,, which are meticulously enhanced with various heuristies to improve efficiency and accuracy.
Machine learning (ML) techniques, especially deep neural networks (DNNs), have recently shown great potential in solving or aiding the resolution of ILPs (Zhang al., 2023 Li al.) 2024a). In practice, ILPs within specific scenarios often exhibit similar structures patterns across instances, enabling ML methods to automatically identify and exploit these patterns to reduce computational complexity in data-driven manner (Gasse et al. 2019). When trained on dataset of instances,
"This work was done when Zijie Geng was an intern at Huawei.
1 "Correponndigg author.

---

Published as a conference paper at ICLR 2025
Problem
Gradient
min c²a s. t. Ax 1 b (0.
Descent
Predicted Solutions
Differentiable
Predictor
Loss
Labels
(b) DiffIL
Unsupervised Learning
Cone--Cnnnming
Gurobi
Solutions
(a) Previous Methods Supervised Learning
(a) Previous works mainly use supervised learning, They employ Gurobi to obtain solutions that serve training labels, which is time-consuming. (b) Our proposed DifILL is an unsupervised learning approach. Its key idea is to design a differentiable loss function, enabling straightforward gradient descent methods to optimize the problems and the predictor simultaneously.
Figure 1:
DNNs able to generalize novel but similar instances, making decisions according to past periences in short time frame. The growing intersection of CO and MI. has attracted considerable attention due its potential to drive innovation and offer mutual benefits both fields. Research efforts in this area can be generally categorized into two main streams. Some studies integrate ML into the traditional branch-and-bound framework, enhancing components such branching deci- sions Gasse et al. 2019 Kuang et al., 2024a b) Liu et al. 2023 2024b), separation processes (Li al. 2023a), presolving (Kuang et al., (023). and cut selection (Wang et al. [202c]] [ing et al., Wang et al.) (2024b). Another line of research, which is the focus of this paper, directly employs ML to predict solutions (Khalil et al., 2022 Liu et al.) 2024a 2025). Recent advance- ments, such Neural Diving (Nair al. 2220; Yoon (022) and Predict-and-Seare
2024
(Han et al., 2023 Huang et al. 2024 Zeng et al.) 2024). have shown effectiveness in reducing the solving time. These methods typically follow supervised learning paradigm, using traditional solvers like SCIP (Achterberg. 2009) and Gurobi (Gurobi Optimization 2021) to generate near-optimal solu- tions as training labels. A predictor is trained to predict the near-optimal solutions from the given instances. Sophisticated heuristics are then applied to exploit the predicted solutions, thus acceler- ating the solving process.
Despite these achievements, supervised learning methods still present significant challenges. First, they are time-extensive due to the need to repeatedly invoke traditional solvers to generate train- ing labels. This is a fundamental limitation of supervised learning approaches (Wang et al. (222a)), which has driven researchers across various fields to turn their attention towards unsupervised learn- ing approaches (Wang et al.) 2022). Second, there exists an inherent misalignment between the ob- jectives of minimizing prediction errors during training and generating high- high-quality solutions during inference. In other words, the predictor is trained to mimic the provided solutions rather than inde- pendently solving the problems. Consequently, these methods often yield plausible yet infeasible solutions (Zeng solving ILPs in an unsupervised learning paradigm becomes especially attractive. As illustrated in Figure D the core concept involves designing a differentiable loss function directly optimize the problems and the predictor using gradient descent methods. the field of CO, this differentiable loss intuitively expected align with the optimization objectives, thus enabling an end-to-end training framework that facilitates producing high-quality solutions. From a fundamental research perspective, such method aligns with the ongoing academic pursuit of unsupervised learning. From a practical perspective, this method promises significant advantages, significantly reducing training time while improving the quality of generated solutions (Chen al.) (2023).
al. 2024 In light of these issues, developing differentiable approach for
To tackle this challenge, we propose DiffILO (Differentiable Integer Linear Programming Optimization), novel unsupervised learning approach for learning to generate high-quality IIP solutions. To the best of our knowledge, DiffILO is the first method to employ pure ML tech- niques for training, without relying on traditional solvers, representing a front-line exploration of ML applications in the field of combinatorial optimization. Specifically, DiffILO first relaxes the binary variables into continuous ones via probabilistic modeling, where the constraints are trans- formed into the form of expected violation. We theoretically demonstrate the equivalence preserved in this transformation. DiffILO then adopts the penalty function method to convert the constrained problems into unconstrained ones. By further leveraging reparameterization trick to flow the gra-
2

---

Published as a conference paper at ICLR 2025
dient back- proppaagatt thus forming a differentiable (almost everywhere) loss function, DiffILO optimizes both the ILP problems and the predictor parameters simultaneously via straightforward gradient descent methods. The training process is entirely unsupervised, thus significantly reducing the training time by bypassing the collection of labeled data. Moreover, the end-to-end optimization aligns the objectives of training and inference, thus consistently producing feasible and high-quality solutions. Extensive experiments demonstrate that DifIILO not only achieves an average training speedup of 13.2 times compared supervised methods, but also outperforms them by generating heuristic solutions with much higher feasibility ratios and significantly improved objective values.
2 RELATED WORK
2.1 MACHINE LEARNING FOR INTEGER LINEAR PROGRAMS
Machine learning (MI) techniques have become increasingly prevalent in addressing combinatorial optimization (CO) problems, especially integer linear programs (ILPs) and mixed-integer linear pro- grams (MILPs) (Bengio et al. [202]] Li et al. 2023b Zhang et al., 2023 Huawei [021]. Some stud- ies incorporate ML models into heuristic components in modern solvers (He et al. [0114] Baltean- Lugojan et al., 2019 Kuang et al. 2023 Li et al., 2024a), such as branching (Gasse et al. 2019), separation (Li et al. 2023a), and cut selection (Wang et al., (023c). etc. Another line of research, which is the focus of this paper, employs ML to generate heuristic solutions (Nair et al. [020 Yoon
2022 Khalil et al. 2022: Ye et al.] 2023b Zeng et al. 2024). notable recent advancement the predict-and-scarcc (PS) framework (Han et al. [023] Huang et al. 22024), which first predicts initial solutions, and then employs solvers like Gurobi (Gurobi Optimization (021) or SCIP (Achterberg,
2009) to search within strategically designed trust region for solution improvement. Such research is similar to the decision-focuse
framework (Elmachtoub) & Grigas 2022 Ferber al., [2200] /Zhrmagammbetov et al.] (224),, which learns model map observable features into latent representation (e.g. coefficients in LP objective) used by solvers.
learning (DFL) or predict-hhen-opiinee
2.2 DIFFERENTIABLE APPROACHES
Differentiable approaches aim to construct differentiable optimization objectives, facilitating the straightforward application of gradient descent methods in an unsupervised, end-to-end manner. These methods have been effectively implemented in fields such Partial Differential Equation (PDE) (Holl et al. 2020; Belbute-Peres et al. 2020 and Density Functional Theory (DFT) vKaal al. 2014] Mathiasen al.) [024] Li et al. 2024b), showcasing their effectiveness in solving such continuous problems. Applying these techniques to CO problems poses challenges due to the discrete nature of these problems. In the field of CO, differentiable approaches have been tailored for some specific problems, such as Boolean Satisfiability Problem (SAT) (Amizadeh et al. 2018)
and Traveling Salesman Problem (TSP) (Gaile et al., 2022). Notably, Karalias & Loukas (0020)
explored differentiable approaches for combinatorial optimization on graphs and developed Erdōs Goes Neural, a differentiable and unsupervised learning framework that similar our approach.
This concept has been further explored by some following works (Wang et al.) 2022 Schuetz et al.)
2022 Wang & Li 2023). However, these methods are tailored for some specific problems and depend custom-designed differentiable loss functions specific these cases. To the best of our knowledge, extending these techniques to general ILPs remains non trivial.
3 METHODOLOGY
This section introduces our proposed DiffILO framework, with an overview depicted in Figure 2 In Section 3.1. we present the probabilistic approach that reformulates a discrete, constrained ILP problem into a continuous, unconstrained optimization problem. Next, in Section 3.2, we adopt the Gumbel Softmax technique for reparameterization, which makes the problem differentiable al- most everywhere (a.c.) and facilitates an efficient resolution via straightforward stochastic gradient descent. Finally, Section 3.3 details the implementation of the DiffILO model. including its train- ing and inference processes. The proofs and additional implementation specifics are available in A Appendix A and Appendix respectively.
3

---

Published as a conference paper at ICLR 2025
PP
Discrete Constrained
P2
Continuous
P3
Continuous
Constrained
Unconstrained
mine
min c² & + Σ o5(
Thm.
Thm. Sec.
Am S
E Eg- (8) [max[Ar 6.0)
10,1)"
Sec.
4 E 10"
L. de 10,1
Sec. Repurameterization
Sec 33
Thm.
Bipartite Graph
Differentiable a.c.
Gradients
Grudients
min 2 # (1(t)
GNN fa
Solution ab
Sec. 13
Sec 3
Sec.
10,
Method overview of DiffILO. We first transform the primal discrete and constrained problem into a continuous, unconstrained, and differentiable (a.e.) problem, as depicted by the blue arrows. DifILLO employs a graph neural network (GNN) predict solutions, depicted by the black arrows. It optimizes both the ILP problem and the GNN parameters simultaneously through gradient descent, as depicted by the red arrows.
Figure 2:
3.1 PROBABILISTIC MERIT FUNCTION
We focus on integer linear programs (ILPs) that take the form of:
(P1) where denotes the number of variables, e F" denotes the objective coefficients, the matrix A (a1, a2,-.. amm) E mm denotes the constraint coefficient matrix, denotes the number of constraints, and b I denotes the right-hand-side biases of the constraints.
min { Ax < b, {0,1)")
Remark 1. Without loss of generality, we focus ILPs with binary integer variables, also ferred to as 0-1 programs. This simplification is reasonable given the fact that any bounded integer program can be converted into binary (0-1) form (Dantzig 2016 Ye et al. 2023a).
An ILP is quintessentially a discrete and constrained optimization problem. Our first step to reformulate it into continuous problem. An intuitive approach is to relax the binary variables x E (0, 1 into continuous variables & [0, 1]".. which is commonly known as the linear pro- gramming (LP) relaxation (Agmon, 1954 Bixby al. 2004). However, clearly such relaxation alters the original solution space. To achieve an equivalent reformulation, we adopt a probabilistiic approach (Karalias & Loukas 2020), interpreting the continuous variables
probabilities associ- ated with the binary variables. Specifically, each binary variable I; is assumed to follow a Bernoulli distribution, writing x; ~ Bernoulli(ā:). The distribution of denoted as æ p(-(ā:). Based on the probabilistic modeling, we reformulate the primal problem (PI) into:
min { /E [max(Ax b, 0)] 0, e [0. 1]").
(P2)
The novel reformulation in P2 is motivated by the intuition that minimizing the ex- pected constraint violations can restrict the distribution' support the set of optimal solutions. For example, if component 2; E (0, 1), then the constraint Ez-Bernoulitt,,, ( [max(ax b, 0)] will ensure that ax & holds for both x = O and x = 1. Otherwise, if i; 0 or n; = 1. Bernoulli(2.) becomes deterministic distribution and it indicates that a²; holds.
Remark 2.
We now present the fundamental theoretical properties of (22). establishing equivalence with the primal problem (PI). Theorem demonstrates the equivalence betweeen the two problems in terms of feasibility and solvability. Then. Theorem 2 shows that, loosely speaking, the optimal solutions
PP2 coincide with the optimal solutions
(PT)
Theorem 1. The problem (P2) is feasible (and solvable, i.e., it admits at least one optimal solution)
and only if (PT) is feasible (and solvable).
4

---

Published as a conference paper at ICLR 2025
Theorem 2. Let _ {i E [n] :4 03. Then the following statements hold:
Suppose x" E {0, 1 is an optimal solution to P1
Then x" is also an optimal solution to (P2) and satisfies 22 22 for all i E Ie, then x²
If a vector o² E [0. 1I"H is feasible solution to is an optimal solution to P2
P2
2. Suppose x' E [0. 1 is an optimal solution to
P2
Then we have 2 E (0. for all E Ic. {0, 13" satisfies x = 3 for all i Ig.,
Let Ig- = {i E [n] 2 (0. 1)) If a vector then x" is an optimal solution to PPA.
We can now conclude that transforming (P) into its continuous format P2 is well-justified. The next step is to apply the penalty function method to recast the constrained problem (P2 into an unconstrained format. We define (xr)) max by. 0) and क ( Ee--p-1() ( (2:) for each constraint indexed by j E [m]. Plugging these penalty functions into the optimization objective results in the following unconstrained problem:
[iin a c cJ a ++ > 20 ())
② E [0,
(P3)
Here, the function Fj. (z) is referred to as merit function (Nocedal & Wright 1999). Its exactness supported by the following theorem, which states that for a sufficienlly large penalty coefficient Jr, the penalty function method preserves the optimal solutions of the original problem.
Theorem 3. There exists a positive scalar v* > such that for any P > p", any optimal solution
to (P3) is also an optimal solution to (P2).
Remark 3. The conclusion in Theorem differs from the established exact penalty function theory, which typically assumes the existence of first-order Karush-Kulis Tucker (KKT) point (Di Pillo & Grippo 1989). In contrast, our proof leverages the combinatorial properties of the primal problem. The probubilistic modeling and penalty function approuch have been used in some previous studies for combinatorial optimization problems (Karalias & Loukas 2220 Wang et al. 2022). However, these methods depend on predefined closed-form constraint penalties, which are hard to derive for general ILPs. As a result, they are applicable to some specific problems rather than general ILPs. Our key technical innovation lies in the transformation of constraints into an expectation form in P2 eliminating the need for closed-form penalty designs.
Remark 4.
3.2 GRADIENT BACK-PROPAGATION FOR OPTIMIZATION
We are now interested in how to apply gradient-based methods, such as Stochastic Gradient Descent (SGD), to optimize (P)). This involves estimating the gradients V Eg (a) (0)=- Since è appears in the sampling distribution and it is hard to derive closed-form expression for the expectation in general II.ss estimating the gradients non-trivial. To address this, we employ the reparameterization trick to enable accurate and low-variance gradient estimates, thus facilitating efficient gradient back-propase proppppppa.t
Remark 5. An alternative approach for handling such non-differentiaale computation graphs in- volving sampling is REINFORCE (also known as the score function estimator) (Williams 1992). However, REINFORCE falls short as it does not explicitly propagate gradients from ,,(x), lead- ing to a potentially less efficient optimization process (Jang et al. (017). Therefore, we favor the reparameterization trick in our approach. See Appendix D.2 for more details.
We adopt the relaxed Bernoulli distribution (Maddison et al. 2016 Wang & Yın 2020) for repa- rameterization, which is based on simple observation illustrated in the following lemma. We denote the sigmoid function (22) P i-e-s. and its inverse, known as the logit function, as
Tpp) (p) = log(T=p) We also denote the uniform distribution over (0, 1) as U(, 1).
Lemma 1. (Restated from (Maddison et al. 20161) Let & E (0,1) and be random variable sampled from U(, 1). We define E 2 ( + (e)). follows that P (g(ă;)) > 0.5) = 2. Remark 6. The distribution of {(;;e) is the so-called relaxed Bernoulli distribution. serves as a "soft" approximation of the discrete Bernoulli distribution, enabling the gradient flow during back- propagation. It is also a specific application of the Gumbel- Gumbel-Softmax trick (Jang et al. (017). and is also relevant to the random perturbed optimizers (Berthet et al. 2020)
5

---

Published as a conference paper at ICLR 2025
Building Lemma] 1 present the following theorem for reparameteriization.
Theorem 4. Let a (i1, .nn) E (0, and e = "aa) be random vector, where each & independently and identically distributed (i.i.d)) as C, ~ U(0, 1), writing e pe(.). where & = E(5;; 62) is defined as Lemma [ Let ap(i;; 6) -
Let E(ic;)) 6) - (61,.... ...) _n)_.
($1,'.. Va) where the = [5:] is the binary rounded value of & It follows that:
و az) ()) [0)()r)] (e) () (oy (#b(dr; e)]]
Theorem validates the effectiveness of the relaxed Bernoulli to reparameterization, in the sense that, the term (2) can be accurately calculated by sampling random variables e from non- parametric distribution Pe(.). However, note that the gradients derived from ab, due to the existence of the rounding function, vanish everywhere. Therefore, while &b can be used to compute the values of Φj. we use & to flow gradients from Φ to æ. Formally, we observe:
Φ5 ( e)) = max(a, (b); e) b3,00
(a vb (0: e) b,) 1(a) ( - by 0)
~ (aj & (á;e) b,) I[(a) ((; - b, > 0),
where I(-) denotes the indicator function. In Equation 2 zb is used to accurately determine whether the constraints are violated, thus preserving the combinatorial properties, while acts as surrogate flow the gradient back- pack-propagation. Consequently, can approximate Φ (.)
)+)+) R (.) A Be
(3)
where
( E) A (a] (x: bi) T(aj ( E) by >0) 0).
(4)
The advantage of (.) is that it is differentiable almost everywhere (a.c.). allowing for efficient gradient pack-propagation. Therefore, we define the new surrogate problem as:
min (F)
+
()) i ]].
(P4)
The merit function ( defined in [4 is differentiable a.e., and thus (P4 can be resolved through gradient descent. Formally, we have the following theorem.
Theorem S. The merit function F, defined P44 is differentiable almost everywhere (a.e.) in (0, 1)", At the differentiable points, the grudient given by:
Σ j=1 caj -(
aj O
Oa 2 E(
pe pe(e)de,
(5)
where O denotes the element-wise product.
Remark 7. Though not differentiable everywhere, modern deep learning frameworks such as Py- Torch can properly handle such cases, even at non-differentiable points.
Remark 8. We consider â E (0, 1)" as gradiens calculations are only necessary within the interior of the solution space. In practice, we output logits and apply a sigmoid function to map to (0,1)² 1) to represent the probabilities. As noted in Equation 4 we use the sampled binary solutions x ~ ((-()) compute constraint violations. Therefore, information from the exact solutions, rather than relaxed ones, is also properly carried out, preserving the combinatorial nature of the problem.
3.3 MODEL IMPLEMENTATION
So far, we have transformed the original ILP problem into a continuous, unconstrained, and differen- tiable (a.e.) problem that can be efficiently solved using straightforward gradient descent. Building on this transformation, we introduce the model implementation of DiffILO, which simultaneously optimizes both the problem and the predictor parameters through direct gradient back mack-propagation, eliminating the need for labeled data. In line with the established practices the field (Gasse et al.) bipartite
2019 Han al. 2023), represent each II. instance- which formulated (PT

---

Published as a conference paper at ICLR 2025
graph G (VUW.E) where V and W denote the sets of variables and constraints, respectively, and & denotes the edges corresponding to the coefficients. Further details on the data representation
available in Appendix [B.1 The predictor fo. which is parameterized by 0 and assumed to be differentiable with respect to 6, outputs the predicted variable probabilities á fo (.) The model Graph Neural Network (GNN) (Kipf & Welling) 2017: [hi al., 2023 2024, 2.25), followed by a multilayer perceptron (MLP). The final layer applies a sigmoid
architecture is implemented
function ensure that the output probabilities ø are provided in Appendix B.2
(0, 1)". More details on the model architecture
Model Training During training, we update the parameters by optimizing the merit function Ff(f(())) defined in (P4), through gradient descent. Specifically, let D (G...... . be batch of ILP instances, each represented as a bipartite graph Gi with n, variables and m, constraints. Let (.),(-) be the penalty function innction-correspondiig the thh instance i.., E)) (a. (á: - b (aa - bis 0),
the previously defined 4g5()) for
(6)
where Oig and bay denote the coefficients and the right-hand-side terms of the j constraints, spectively. For each instance 9;, we sample K random vectors c! ~ U(0, 1)m, where K is hyperparameter. The training loss for this batch defined as:
[D|
1 a2 [D]
m74 K
L(0, D) &
1
Σ
C():G.)
Σ
c felG)
+ + pas (fo(C))))
(7)
D
The gradient of the loss function is then given by
VoL(0;D)
1
Vefe(g.)
c+ 1
Σ
ai 2
( a da O (Fo(G))e(()
ISiSm, (T,""(
We stabilize the training process through three useful techniques. First, to accommodate instances with ranging sizes and coefficient ranges, apply normalization to modify the loss function. Second, we find cosine annealing (Loshchilov & Hutter (016) to be beneficial for optimizing the learning schedule. Third, since the penalty coefficient fJ critical hyperparameter in training, introduce dynamic and adaptive method for adjusting μ. These training techniques are further explained in detail in Appendix C.2
Model Inference During inference, for a given instance G, we can sample heuristic solutions from the predicted distributions (()))o())) which are immediately available. Generating heuristic solutions is particularly valuable in time-sensitive tasks scenarios that require rapid decision- making, such as route planning and production scheduling.
Moreover, the generated heuristic solutions can be used to improve the behavior of existing ILP solvers to find high-quality solutions within a constrained time frame. DiffILLO can theoretically be integrated into any framework that benefits from initialization with heuristic solutions, such as neural diving (Nair et al. 2020). large neighbourhood search (Huang et al.) 2023). or Predict-and- Search (Han al. 2023), which are complementary our approach. In this paper, inspired by Han et al. (2023) but with further simplification, we add the following constraint to the initial problem
Σ F;=0
((-
where is the generated heuristic solution, and is a hyperparameter. This constraint defines a which are different from the predicted ones to be fewer than A. Besides, we provide á for the solver as an initial solution. Further details on the inference process can be found in Appendix C.3
trust region by limiting the number of variables which

---

Published as a conference paper at ICLR 2025
SC
15
CA (maas)
3000
700
MM My pAppl
600
2000
500
2000
W Nw M
1500
400
300
10000
Figure 4: The objective values of solutions generated by different approaches across the 100 test instances. "BKS" denotes the best known solutions. "Gurobi" denotes the heuristic module Gurobi that searches for heuristic solutions before the exact resolution process. For a better visualization, objective values for the instances with no feasible solution found are assigned as 3000, 300, and 10000, respectively on these datasets.
4 EXPERIMENTS
This section presents empirical results to demonstrate the effectiveness of our proposed DiffILO in (1) generating feasible and high-quality heuristic solutions in end-to-end manner, and (2) improv- ing the overall performance of traditional solvers to find high-quality solutions within a constrained time frame. We then conduct case study provide some additional insights into the optimization process of DiftILO. All training and evaluations are performed using the same hardware configura- tion, specifically an Intel(R) Xeon(R) Gold 6246R CPU @ 3.40GHz, and an NVIDIA GeForce RTX 3090 GPU. Code is available at More experimental details can be found in Appendix
Benchmarks We evaluate our method mainly on three widely used ILP problem benchmarks: set covering (SC) (Balas & Ho 1980), maximum independent set prob- lem (IS) (Bergman et al. 2015), and combinatorial auctions (CA) (Leyton- et al. 22000). The datasets are generated using the code from Gasse et al.a (2019). Following the settings described in the PS paper (Han et al. 2023), we generate 400 instances for each benchmark, 240 for training, 60 for valida- tion, and 100 for testing, respectively. Additional details about these datasets can be found in Appendix [.I To demonstrate the effectiveness of DiffILO on realistic datasets, we conduct experiments on two subsets of MIPLIB 2017 (Gleixner et al.
PS (duu collection)
PS (raining
250
Deffil .I (tmining)
Time th
200
100
50
SC
15 CA
2021 More details are in Appendix D33
Figure 3: Training times of PS and DiffILO on different datasets. Data collection refers to the time spent on solving training and validation instances to obtain labels, while training denotes the time spent on training the neural networks.
Baselines We compare method against two main cat- egories of baselines. First, we include traditional solvers, SCIP (Achterberg) 2009) and Gurobi (Gurobi Optimization 2021) to evaluate whether the heuristic solutions generated by DiffILO can accelerate the solving process. Second, we compare DiffILO with the Predict-and-Search (PS) frame- work (Han al. 2023). which first predicts solutions and then employs SCIP or Gurobi to search within a trust region for further improvement. PS and Neural Diving (ND) (Nair et al. (020)) are both representative supervised learning methods. However, since the prediction components in PS and ND are the same, we primarily include PS as our baseline. Some more recent supervised learning ap- proaches such as those based on contrastive learning (Huang et al. 2024) or diffusion models (Zeng et al.) 2024) have not been implemented. Although these methods can enhance the performance of supervised learning, they also lead to additional training time. For fairness, DifiILO does not employ similar additional tricks either. The comparison includes capabilities of both methods to generate feasible solutions and to improve the performance of Gurobi and SCIP. We provide the results of some additional baselines, including ablation studies, in Appendix D.2
8

---

Published as a conference paper at ICLR 2025
Table I: Average objective values obtained by different approaches 10, 100, and 1, 000 seconds. We mark the best values in bold and underline the second-best values. Best known solution (BKS) refers to the solution obtained by running Gurobi for 3,600 seconds.
SC (min, BKS:
86.45)
IS (max, BKS:684.14)
CA (max, BKS:22272.55)
10s
100s
1000s
10s
100s
1000s
10s
100s
1000s
Gurobi
1031.39
87.09
86.52
682.02
684.12
684.13
22090.76
22242.58
22272.03
PS+Gurobi
131.87
125.26
125.26
684.13
684.13
684.13
22140.65
22243.12
22272.47
DifilLO+Gurobi
95.65
86.78
86.48
684.00
684.12
684.14
22177.82
22260.48
22272.55
SCIP 96.15
89.91
86,93
660.79
679.80
684.05
21013.73
22151.71
22272.55
PS+SCIP
125.26
125.26
125.26
664.50
684.09
684.13
21712.73
22248.55
22272.55
DiffILO+SIIP
94.16
87.47
86.57
674.30
684.06
684.13
21948.70
22256.08
22272.55
SC
1.0
0.000
0.000
0.000
Aragge
0.4
0000
0.0
101
112
90
0.000
10P
(a) cvsl 6r1066 6--006-7222
0100
0.00
0.02
0.2
0.00
0.3
0.8
101
10?
0:00
1g!
10'
103
0.00
100
10
Time
Tixe
Tix
Grohi
SUP
PS4Gavdh
PSASCIP
(b) cvsl 111--1188-89
Figure 5: The relative primal gap of different approaches as the solving process proceeds. The results are averaged across 100 test instances.
Figure 6: The relative primal gap test instances.
Training and Inference We train DiffILO for 1, 200 epochs on the SC and IS datasets, and 2, 400 epochs on the CA dataset. After each epoch, we use the trained model generate solutions for the validation instances, recording the best feasible solutions and selecting the best epoch based on their average objectives. We train the PS predictor for 2, 400 epochs on all datasets, selecting the best epoch based validating prediction loss. To improve traditional solvers, PS adds constraints to restrict the solution space within a trust region, which is controlled by some key hyperparameters. Finding suitable hyperparameters trast, as shown in Formula 9 DiffIL.O employs simpler approach that does not require extensive hyperparameter tuning. In our experiments, we simply set A 200. More details about the training respectively.
different datasets is challenging and labor-intensive. In
and inference processes can be found in Appendix C.2 and Appendix C.3
Training Time Comparison Figure 3 shows a comparison of the training times for DifilLO and PS. The results show that supervised learning methods like PS spends much more time collecting training labels than training the neural networks. In contrast, DiffILO bypasses the labeling process, achieving average speedup of 13.2 times across the three datasets.
Generating Feasible Solutions We evaluate the ability of different methods to generate high- quality feasible solutions. The evaluation is performed on the 100 test instances. Figure 4 for PS and DiffILO, sample 30 solutions from the predicted distribution for each instance, select the best feasible solution, and report the obtained objective value. The average feasible ratio for Dif- #leasible )/ (#iintnncces) is 50.8%, 97.1%. and 99.4%, on SC, IS, and CA datasets, respectively. The results show that DiffILO consistently produces high-quality feasible solutions even without solver assistance on almost all instances, while PS struggles to generate fea- sible solutions many instances. Gurobi has heuristic module to find heuristic solution before
fILO, computed as (Σ Einsttaaee 30

---

Published as a conference paper at ICLR 2025
(a)
521
4.2
(b) #sampling=1
(c) #sampling=10
(d) Closed Form
Figure 7: An illustrative example. (a) shows the objective function. (b) and (c) visualize the opti- mization processes of DiffILO, which converge to the optimal solution. (d) visualizes the optimiza- tion process of optimizing the closed-form objective, which converges to sub-optimal solution.
executing the exact resolution process. We further assess the solutions found by combining these methods with this heuristic module. Results show that both PS and DifiLLO can improve Gurobi's s heuristic solutions, but Difiooi+Gurobi significantly outperforms PS+Gurobi, with objectives very close to the best known solutions.
Improving traditional Solvers We then evaluate the capability of the generated solutions to ac- celerate the traditional solvers like Gurobi and SCIP find better solutions in constrained time frame. The results are in Table and the solving processes are in Figure [ The results demonstrate that DifIILO consistently outperforms PS on the SC and CA datasets. We present the solving curves on the CVS dataset in Figure 6 and report the solving time on 3 neos test instances in Table / in Appendix D.3 Other additional experiments, including ablation studies and additional baselines, can be found in Appendix D
Case Study We present an illustrative example demonstrate DifiTLO's optimization process. We consider a simple ILP problem
min (-5z) 4x² (0.1)
Φ1
x2 S 1}.
(10)
This case is non-trivial for gradient descent, as its optimal solution (1, 0) and an sub-optimal solution (0, 1) have very close objectives. Figure 7 (a) displays the objective function -5x 1 4x2. The transformed continuous unconstrained optimization problem is:
min Be 0.1] {Fa(21, 22) & -51 422 μ Ex,,,, [max(<] + x2 1.01]
(11)
where ~ Bernoulli((:). The closed form of (61, .22) is derived as Fa( 5 4 + μ f22
(12)
We first set f 20. Figures (b) and (c) visualize the optimization process of DiffILO, which samples D1 and 22 with the reparameterization trick for optimization. The numbers of sampled solutions (#sampling) solution 0), Moreover, increasing the number of samples stabilizes the optimization process. However, shown in Figure 7 (d), when we directly optimize the smoothed function, i.e., the closed form of F,. it converges to sub-optimal solutions (0, 1). We conduct experiments with 20 different random seeds. In 11 out of 20 runs, the optimization of the closed-form objective derives sub-optimal solutions. In contrast, DiffILO's optimization approach derives the optimal solution in all the 20 runs. However, using the foosed-form penalty function will always perform penalties. We further conduct experiments to investigate the influence of μt, and the results are shown in Table 9 Appendix D More discussions about this paper can be found in Appendix
1 and 10 in (b) and (c), respectively. They both converge the optimal
CONCLUSION
This paper proposes DiMILO, novel Differentiable Integer Linear Programming Optimization approach for learning to predict ILP solutions under an unsupervised learning paradigm. is to our knowledge the first method that employs pure ML techniques solve general ILPs entirely without the aid of traditional solvers. Experiments on commonly used ILP datasets demonstrate the effectiveness of DiffILO O in reducing training time and producing high-quality solutions.
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
We provide the following information for the reproducibility of our proposed DiffLLO. The method detailed in Section with the proofs for theorems available in Appendix A The implementation details, including data representation and model architecture, are provided in Appendix B The ex- The code
perimental details and results are in Section | and further elaborated in Appendix publicly available at
C
com htt.://www...ccaaaaaaaaaaaaa--a0
ACKNOWLEDGMENTS
The authors would like thank all the anonymous reviewers for their insightful comments. This work was supported in part by the National Key R&D Program of China under con- tract 2022ZD01 19801, National Nature Science Foundations China grants U23A20388, and 62021001. This work was supported in part by Huawei as well.
REFERENCES
Tobias Achterberg. Seip: solving constraint integer programs. Mathematical Programming Compu- lation, 1:1-41, 2009.
Shmuel Agmon. The relaxation method for linear inequalities. Canadian Journal of Mathematics, 6:382-392, 1954.
Saced Amizadeh, Sergiy Matusevych, and Markus Weimer. Learning to solve circuit-sat: An un- supervised differentiable approach. In International Conference on Learning Representations, 2018.
Anonymous, reoptimization framework for mixed integer linear programming with dynamic pa- rameters. In Submitted to The Thirteenth International Conference on Learning Representations, 2024.
under review.
Egon Balas and Andrew Ho. Set covering algorithms using cutting planes, heuristics, and subgra- dient optimization: a computational study. Springer, 1980.
Radu Baltean- Baltean-Lugojan. Pierre Bonami, Ruth Misener, and Andrea Tramontani. Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks. preprint: hup://www. optimization-online org/DB HTMI/2018/1//62 1/6943. html, 2019.
Filipe De Avila Belbute- Peres, Thomas Economon, and Zico Kolter. Combining differentiable pde solvers and graph neural networks for fluid flow prediction. In international conference on ma- chine learning, pp. 2402-2411, PMLR, 2020.
Yoshua Bengio. Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: methodological tour d' d'horizon. European Journal of Operational Research, 290(2): 405 2021.
David Bergman, André Augusto Ciré, Willem Jan van Hoeve, and Hooker. Decision diagrams for optimization. Constraints, 20:494 495, 2015.
Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, PhillPhl Vert, and Francis Bach. Learning with differentiable pertubed optimizers. Advances in neural information process- ing systems, 33:9508-9519, 2020.
Hawthorne Beyer, Yann Dujardin, Matthew Watts, and Hugh P Possingham. Solving conser- vation planning problems with integer linear programming. Ecological Modelling, 328:14-22, 2016.
Robert E Bixby, Mary Fenelon, Zonghao Gu, Ed Rothberg, and Roland Wunderling. Mixed Mixed-integer programming: A progress report. In The sharpest cut: the impact of Manfred Padberg and his work, pp. 309-325. SIAM, 2004.
11

---

Published as a conference paper at ICLR 2025
Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties self-supervied vision transformers. In Proceedings of the IEEE/CVF international conference computer vision, pp. 9650-96600 2021.
Ziang Chen, Jialin Liu, Xinshang Wang, and Wotao Yin. On representing mixed-integer linear programs by graph neural networks. The Eleventh International Conference on Learning Rep- resentations, 2023. htLhhtts:/// http///ppeeeeeeeeeeeeeeeeee net/ wwweeeeeeroneaaepeeeee dtt.rummrridde4gegG2raaaaa
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.
George B Dantzig. Linear programming and extensions. In Linear programming and extensions.
Princeton university press, 2016.
Gianni Di Pillo and Luigi Grippo. Exact penalty functions in constrained optimization. SIAM Journal on control and optimization, 27(6):1333-1366 1989.
Adam N Elmachtoub and Paul Grigas. Smart "predict, then optimize". Management Science, 68(1): 9-26, 2022.
Aaron Ferber, Bryan Wilder, Bistra Dilkina, and Milind Tambe. Mipaal: Mixed integer program as layer. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp- 1514-151, 202.0
Elīza Gaile, Andis Draguns, Emils Ozolinš, and Kärlis Freivalds. Unsupervised training for neural tsp solver. In International Conference Learning and Intelligent Optimization, pp. 334-344-- 346.
Springer, 2022.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combi- natorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019.
Zijie Geng, Xijun Li, Jie Wang, Xiao Li, Yongdong Zhang, and Feng Wu. A deep instance generative framework for milp solvers under limited data availability. In Advances in Neural Information Processing Systems, 2023.
Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, et al. Miplib 2017: data- driven compilation of the 6th -ixeeeinteger programming library. Mathematical Programming Computation, 13(3):443-490, 2021.
LLC Gurobi Optimization. Gurobi optimizer. URL http://www. gurobi. com, 2021.
Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al. Soft actor-critic algorithms and appli- cations. arXiv preprint arXiv: /8/2.0/8// 2018.
Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang. Ruoyu Sun, and Xi- aodong Luo. A gnn- gnn-guided predict-and-seant framework for mixed-integer linear programming. In The Eleventh International Conference on Learning Representations, 2023.
He He, Hal Daume III, and Jason M Eisner. Learning to search in branch and bound algorithms. Advances in neural information processing systems, 27, 2014.
Philipp Holl, Vladlen Koltun, Kiwon Um, and Nils Thuerey. phiflow: A differentiable pde solving framework for deep learning via physical simulations. In NewrIPS workshop, volume 2, 2020.
Taoan Huang, Aaron M Ferber, Yuandong Tian, Bistra Dilkina, and Benoit Steiner. Searching large neighborhoods for integer linear programs with contrastive learning. In International Conference on Machine Learning, pp. 13869-13890. PMIR, 2023.
Taoan Huang, Aaron Ferber, Arman Zharmagambetov, Yuandong Tian, and Bistra Dilkina. Contrastive anddecc-and-search for mixed integer linear programs. In Forty-first International Conference on Machine Learning, 2024. URL https:://////..... http:::////peeeeeeew.. net forum?id
12

---

Published as a conference paper at ICLR 2025
Huawei. Optverse solver. https://www. hww.tcaoudooopopiccccoooooooeese 2021.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparametrizatioon with gumble-softmax. In International Conference on Learning Representations (ICLR 2017). OpenReview. net, 2017.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: unsupervised learning framework for combinatorial optimization on graphs. Advances in Neural Information Processing Systems, 33: 6659 6672, 2020.
Elias B Khalil, Christopher Morris, and Andrea Lodi. Mip-gon: A data-driven framework for guid- ing combinatorial solvers. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 10219-10227, 2022.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017. URL https:
//openreview. wwt.:nottttddaaaaaau--
Arie MCA Koster, Manuel Kutschka, and Christian Raack. Towards robust network design using in- teger linear programming techniques. In 6th EURO-NGI Conference on Next Generation Internet, pp. 1-8. IEEE, 2010.
Yufei Kuang, Xijun Li, Jie Wang, Fangzhou Zhu, Meng Lu, Zhihai Wang. Jia Zeng, Houqiang Li, Yongdong Zhang, and Feng Wu. Accelerate presolve in large-scale linear programming via reinforcement learning. arXiv preprint arXiv:2310. 11845, 2023.
Yufei Kuang, Jie Wang, Haoyang Liu, Fangzhou Zhu, Xijun Li, Jia Zeng, Jianye Hao, Bin Li, and Feng Wu. Rethinking branching on exact combinatorial optimization solver: The first deep symbolic discovery framework. In The Twelfth International Conference on Learning Represen- www//eeruunneeee seett/oorumidddjRhBBBB NMh
tations, 2024a. BtLLtttss////pereeee
Yufei Kuang, Jie Wang. Yuyan Zhou, Xijun Li, Fangzhou Zhu, Jianye Hao, and Feng Wu, Towards general algorithm discovery for combinatorial optimization: Learning symbolic branching policy from bipartite graph. In Forty-first International Conference on Machine Learning, 2024b. URL
htttps://openrev//
net htt////orummmuuuomme SirrummiddULLeelDtee
Simen Kvaal, Ulf Ekström, Andrew M Teale, and Trygve Helgaker. Differentiable but exact formu- lation of density-fuuctiions theory. The Journal of chemical physics, 140(18), 2014.
Ailsa H Land and Alison G Doig. An automatic method for solving discrete programming problems. Springer, 2010.
Kevin Leyton Brown, Mark Pearson, and Yoav Shoham. Towards a universal test suite for combina- torial auction algorithms. In Proceedings of the 2nd ACM Conference on Electronic Commerce, pp. 66-76, 2000.
Sirui Li. Wenbin Ouyang, Max Paulus, and Cathy Wu. Learning to configure separators in branch- and-cut. In Thirty-sevnnthh Conference on Neural Information Processing Systems, 2023a.
Xijun Li, Fangzhou Zhu, Hui-Ling Zhen, Weilin Luo, Meng Lu, Yimin Huang, Zhenan Fan, Zirui Zhou, Yufei Kuang, Zhihai Wang, et al. Machine learning insides optverse solver: Design principles and applications. arXiv preprint arXiv:2401.052 2024a.
Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. From distribution learning training to gradient search in testing for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023b.
Yang Li, Zechen Tang, Zezhou Chen, Minghui Sun, Boheng Zhao, He Li, Honggeng Tao, Zilong Yuan, Wenhui Duan, and Yong Xu. Neural-network density functional theory. arXiv preprint arXhv:2403.11287 2024b.
Haotian Ling, Zhihai Wang, and Jie Wang. Learning to stop cut generation for efficient mixed- integer linear programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 20759-20767. 2024.
13

---

Published as a conference paper at ICLR 2025
Haoyang Liu, Yufei Kuang, Jie Wang, Xijun Li, Yongdong Zhang, and Feng Wu. Promoting general- ization for exact solvers via adversarial instance augmentation. arXiv preprint arXiv22310.14161, 2023.
Haoyang Liu, Jie Wang. Wanbo Zhang, Zijie Geng, Yufei Kuang. Xijun Li, Bin Li, Yongdong Zhang, and Feng Wu. MILP-StuDio: MILP instance generation via block structure decomposition. In The Thirtt-eighth Annual Conference on Neural Information Processing Systems, 2024a. URL.
net Forum? (atrrrmmmm--w333310000
Haoyang Liu, Jie Wang, Zijie Geng, Xijun Li. Yuxuan Zong, Fangzhou Zhu, Jianye Hao, and Feng Wu. Apollo-MILPP: An alternating prediction-correction neural solving framework for mixed- integer linear programming. In The Thirteenth International Conference on Learning Represen- tations, 2025. URL https:://///mm httt::ttt////ott http:////pppeeeiee.eome /
net forum?ide mFYOEPDWKS
Hongyu Liu, Haoyang Liu, Yufei Kuang, Jie Wang, and Bin Li. Deep symbolic optimization for combinatorial optimization: Accelerating node selection by discovering potential heuristics. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 2067- 2075, 2024b.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint (atp::66000099833. 2016.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint arXiv:1611.00712, 2016.
Alexander Mathiasen, Hatem Helal, Paul Balanca, Adam Krzywaniak, Ali Parviz, Frederik Hvilshøj. Blazej Banaszewski, Carlo Luschi, and Andrew William Fitzgibbon. Reducing the cost of quantum chemical data by backpropagating through density functional theory. arXiv preprint arXiv:2402.0400 04030, 2024.
John Mitchell. Branch-and-cus algorithms for combinatorial optimization problems. Handbook of applied optimization, 1(1):65-77, 2002.
Vinod Nair, Sergey Bartumov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Bren- dan O' D'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, al. Solving mixed integer programs using neural networks. arXiv preprint 2rXiv:2012.13349 2020.
Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 1999.
David M Ryan and Brian A Foster. An integer programming approach to scheduling. Computer scheduling of public transport urban passenger vehicle and crew scheduling, pp. 269-280, 1981.
Martin JA Schuetz, J Kyle Brubaker, and Helmut G Katzgraber. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4):367-377, 2022.
Zhihao Shi, Xize Liang and Jie Wang. LMC: Fast training of GNNs via subgraph sampling with provable convergence. In The Eleventh International Conference Learning Representations, 2023.
Zhihao Shi, Jie Wang, Fanghua Lu, Hanzhu Chen, Defu Lian, Zheng Wang. Jieping Ye, and Feng Wu. Label deconvolution for node representation learning on large-scale attributed graphs against learning bias. IEEE Transactions Pattern Analysis and Machine Intelligence, 46(12):11273- 11286, 2024. doi: 10.110/TPAAM.2044.45554444
Zhihao Shi, Jie Wang, Zhiwei Zhuang, Xize Liang, Bin Li, and Feng Wu. Accurate and scal- able graph neural networks via message invariance. In The Thirteenth International Confer- Learning Representations, 2025. URL https:/ /opps////epeeeiiewee http:/nee///eeeee fordmiir UgrFPhcmFp
Lawrence Stewart, Francis Bach, Felipe Llinares-López and Quentin Berthet. Differentiable clus- tering with perturbed spanning forests. Advances Neural Information Processing Systems, 36, 2024.
14

---

Published as a conference paper at ICLR 2025
Aaron Van Den Oord, Oriol Vinyals, al. Neural discrete representation learning. Advances in neural information processing systems, 30, 2017.
Haoyu Wang and Pan Li. Unsupervised learning for combinatorial optimization needs meta- learning, arXiv preprint arXiv:2301.03116 2023.
Haoyu Wang, Jialin Liu, Xiaohan Chen, Xinshang Wang, Pan Li, and Wotao Yin. Dig-milp: deep instance generator for mixed-integer linear programming with feasibility guarantee. arXiv preprint arXiv:2310. 10200.33266 13261, 2023a.
Haoyu Peter Wang, Nan Wu, Hang Yang, Cong Hao, and Pan Li. Unsupervised learning for com- binatorial optimization with principled objective relaxation. Advances in Neural Information 2022.
Processing Systems,
Hong Wang. Zhongkai Hao, Jie Wang. Zijie Geng, Zhen Wang, Bin Li, and Feng Wu. Accelerat- ing data generation for neural operators via krylov subspace recycling. In The Twelfth Interna- tional Conference on Learning Representations, 2024a. Eorum??d=UppRVWeekDD
/tstps://openrevate
Jie Wang, Zijie Geng, Xijun Li, Jianye Hao, Yongdong Zhang, and Feng Wu. G2MILPP: Learning to generate mixed-integer linear programming instances for milp solvers. Authorea Preprints, 2023b.
Jie Wang, Zhihai Wang, Xijun Li, Yufei Kuang, Zhihao Shi, Fangzhou Zhu, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning via hierarchical sequence/set model for efficient mixed-integer programming, IEEE Transactions on Pattern Analysis and Machine Intel- ligence, pp. 1-17, 2024b. doi: 10.1 10.100//AAAM.22044433377
Xi Wang and Junming Yin. Relaxed multivariate bernoulli distribution and its applications to deep generative models. In Conference on Uncertainty in Artificial Intelligence, pp. 500-509, PMLR, 2020.
Zhihai Wang. Xijun Li, Jie Wang. Yufei Kuang, Mingxuan Yuan, Jia Zeng. Yongdong Zhang, and Feng Wu. Learning selection for mixed-integer linear programming via hierarchical sequence model. In The Kleventh International Conference on Learning Representations, 2023c.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8:229-255 256,, 1992.
Huigen Ye, Hua Xu, and Hongyan Wang. Light-milpopt: Solving large-scale mixed integer linear programs with small-scale optimizer and small training dataset. In The Twelfth International Conference on Learning Representations, 2023a.
Huigen Ye, Hua Xu, Hongyan Wang, Chengming Wang, and Yu Jiang. GNN&GBDT-guided fast optimizing framework for large-scale integer programming. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp.
PMLR, 23-29 Jul 2023b.
Taehyun Yoon. Confidence threshold neural diving. arXiv preprint arXiv: arXiv:2202.07506, 2022.
Hao Zeng. Jiaqi Wang, Avirup Das, Junying He, Kunpeng Han, Haoyuan Hu, and Mingfei Sun. Effective generation of feasible solutions for integer programming via guided diffusion. In Pro- ceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp- 4107-41 18, 2024.
Jiayi Zhang, Chang Liu, Xijun Li, Hui-Ling Zhen, Mingxuan Yuan, Yawen Li, and Junchi Yan. A survey for solving mixed integer programming via machine learning. Neurocomputing, 519: 205 217, 2023.
Arman Zharmagambetov, Brandon Amos, Aaron Ferber, Taoan Huang, Bistra Dilkina, and Yuan- dong Tian. Landscape surrogate: Learning decision losses for mathematical optimization under partial information. Advances in Neural Information Processing Systems, 36, 2024.
15

---

Published as a conference paper at ICLR 2025
A PROOFS
Theorem 1. The problem ( is feasible (and solvable, i.e., it admits at least one optimal solution) and only if PP) is feasible (and solvable).
Proof. First, we show the equivalence of the feasibility. It is obvious that any feasible solution to (P) is also a feasible solution (P2). Conversely, let us consider s' as solution to (P2). It follows that (x="p(-1k")) [max( Az b, 0)) = O. Notably, supp is not empty, and for
Va E supp pl (²)) we have max Ax b, 0) = O, and thus Ax - b. Consequently, æ is a feasible solution to
Next, we show the equivalence of solvability. Notice that the domain of (P1 is {0, 1J", which is a finite set. Therefore, [PI is solvable if and only if it feasible. Similarly, as the objective of (P2) is a continuous function over the compact set [0, 1]". (P) is solvable if and only if it is feasible, Based on these observations, we conclude that (P2) is solvable if and only if (PT) is solvable.
Theorem 2. Le A fir [n] c + 0}. Then the following statements hold:
1. Suppose x" {0, 1 is an optimal solution
P1
Then x" is also optimal solution to (P2 and satisfies až = x for all E Te, then x²
If a vector 8" E [0, 1]"h is a feasible solution to P2
an optimal solution
P2
Suppose x" E [0, 1]"h an optimal solution to
P2
Then we have at [0, for all E Ic.
Let Iz- = {i E [n] 2 E 1)) If vector x
E
{0, 13"h satisfies xt = 3 for all i E Ia.,
then x² is an optimal solution P7
Proof 1. Let x" E 10. "d be an optimal solution to P1 Obviously it is also feasible solution
to (P2). Assume x" E [0, 1]"h is a feasible solution to P2 and satisfies # = x for all i E Ip.
[0, 1] be any feasible solution to (2 For Var supp p(-()), we have max( Aa b, 0) 0. and thus Ar < b. which indicates that
follows that c "' = x² Let
x is a feasible solution
to (P1) and thus cT S c. T.r. Then we have e x= S <c _T
ac = T. It follows that
lab
c =c= x=' <c² &, indicating that 2" is an optimal solution to (P2 This conclusion, combined with the feasibility of x", gives that xx is also an optimal solution
(P2).
2. Let x" E [0. 1]" be an optimal solution to P2 Consider if i E (0,1) for some E Ic- Without loss of generality, we assume C; > O. Define ø' such that 4t 0 and i 3. for
j t Then suppp(-lá") C supp p(-l@"), and a' remains feasible solution P2 However, C s' <e t", contradicting the optimality of x" Therefore 2 E {0, 1] for all i Ie.
Let xx E {0, 1) satisfies x. = = for all i Ig.. Then x² E supp ((pp"(-)=") and thus it is feasible solution to (P)). We also have c x= =T."" Let Vo {(0, 1)" be feasible solution to P1 Then it is also a feasible solution to (22). indicating that c = < c CTx. In follows that
T 1 <c x, indicating that x is an optimal solution to (PIp.
Theorem 3. There exists a positive scalar μ² > 0 such that for any p >> n², any optimal solution to also an optimal solution P2).
Proof. We define
(xx)
ES 0zxr and )(x) A
E, (t), which leads to 3(t)
=
Ex ([(((( The domain of o(-) is 13", a finite set. Therefore, we can find
min Φ(x).
(13)
It follows that d(x)= 2 p for Vo supp o(.). We set n* 2yHeell and assume μ p². Let
x" E [0, 11"h be an optimal solution to (P3 and & be any feasible solution to PP3 suffices to show that -(0²)= = ",t) = 0 and that c x <ec T..
We denote X A arg min ( fc JT x + p (())). The optimality of Æ' indicates that supp p(-pp)())))))) X², and that
o0 + ).) < e a 2(0).
(14)
16

---

Published as a conference paper at ICLR 2025
The feasibility of 0 indicates that @(z)) 0, and thus
c o" + x(x") S c.aa. st.
(15)
Therefore, for Va E x = supp p( (-=) we have
p. v(1((=)) c. (a: x²) - ||||[[| + ||x0 S 2/
(16)
Consider if ((#") > 0, which implies that supp ( x(-) * 0. Let xt E suppp((12")) (-)p Then we have
C (2 x²) x()))
|||||[||||| + 12)
2/ n²,
(17)
p
P
leading to a contradiction. Therefore, we have ((ă²) = 0. Plugging it into Equation 14 completes the proof.
Lemma 1. (Restated from (Maddison et al. 2016 Let & E (0, 1) and e be random variable sampled from u0, 1). We define E(ă; 6) = (T
+ r()).. follows that P (E(#;; > 0.5) = 2.
Proof. We have
P ((E(:: c) 0.5)
log( 1
=P
log( 6 0)
(18)
=P
1 1-6 >1
= =P (E > 1 - 1) 2.
Theorem 4. Let a = (f1, (nn) E (0, 1)n, and 6 (61, (a)) be random vector, where each 4 is independently and identically distributed (i.id.) as 6, (0, writing Pe(.). Let É( E) A (E1,... Ex) where & E(ogi e,) is defined ($1,1.. " where uh = [E.] is the binary rounded value Ef It follows that:
Lemma [ Let ab( E)
&s. )5++)) Ex-p(-12) [x))) Benpa [0, (xb(z;;)) (d:)))]
(1)
Proof. By Lemma] 1 we have
P(u: 1) P(e, > 0.5) = 2., which implies that p(x) (á: E) a m.) Therefore,
(19)
(x)) = Ex (a) [x)(
(
Σ
())))(())))
# "0.1)
Σ
(x)p(((( x(²)
*E(0.1)"
Σ
/
plalft ())ee
(20)
((:==((
=E(0,11"
Σ (x)
Pe (e(d)
x==((E)))
= -)enpe() (1)()b(0 g))].
17

---

Published as a conference paper at ICLR 2025
Theorem 5. The merit function Fu( defined in P4) is differentiable almost everywhere (a.e.) in (0, 1)". At the differentiable points, the gradient given by:
(
aj
@((z:)) pe pe(e)de,
(5)
c0j 0,
dz
where 3 denotes the element-wise product.
Proof. We have
FaF)(()== V
(8)
/=1
=C + P
( = = μ
V Bempe (2;ee)
j=1
j=1
=C + p
B Ber-pel))
((a)
E (6; E) - b1) II (a] 6)(()) 0))
(21)
Oa:
j=1
dz (a E (z:C) - by) pe(c)de
=C + /
j=1 c.a (((:;))
m
( dæ
0
=C P
a 0
о E( Pe (e)d)
f=1 c:a (6:66)
18

---

Published as a conference paper at ICLR 2025
B IMPLEMENTATION DETAILS
B.1 DATA REPRESENTATION
Following previous works (Gasse et al. 2019 Han et al. 2023 Geng al. 2023 Wang et al.
2023b), we represent each ILP problem as a weighted bipartite graph 9 = (VU W.&) E) where V and W denote the sets of variables and constraints, respectively. The graph equipped with a tuple of feature matrices (V, W, E), and the description of these features can be found in Table
Table 2: Description of variable, constraint, and edge features in our bipartite graph representation.
Tensor
Feature
Description
Objective
Normalized objective coefficient.
Variable coefficient
Average variable coefficient in all constraints.
Variable degree
Degree of the variable node in the bipartite graph rep- resentation.
Maximum variable coefficient
Maximum variable coefficient all constraints.
Minimum variable coefficient
Minimum variable coefficient in all constraints.
Constraint coefficient
Average of all coefficients in the constraint.
W
Constraint degree
Degree of constraint nodes.
Bias
Normalized right- saaht-hhnd-siiee side of the constraint.
E
Coefficient
Constraint coefficient.
B.2 MODEL ARCHITECTURE
We employ graph neural network (GNN), parameterized by 0, as the predictor. Specifically, given a bipartite graph = (V E) equipped with the feature metrices (V, W, E), we use MLPs as embedding layers obtain the initial embeddings:
U1 MLPP((,)) h. MLPo(w,), hey MLPo
(22)
After that, we perform K graph convolution layers, with each layer the form of two interleaved half-convolutionns (Gasse al. 2019). defined as follows:
h 11-1) 10
-MLP
(k) Σ
MLP & (nlt) Bee (a(())
h (k+1) - MLP
(K) (K)
Σ
MIP
(k+1)
heep (k)
(23)
KEEEEE
Each convolution layer followed by two GraphNorm layers, one for variables and the other for constraints. We employ concatenation Jumping Knowledge layer to aggregate information from all K layers and obtain the final node representations:
hog MLP,, CONCAT
(1))
)
hmg MLPa (CONCAT (n )n=)))
(24)
k==
k= RK
Subsequently, we use another MLP to output the predicted logits for each variable:
Zu, MLP3 (h..).
(25)
The logits are then used for resampling module, followed by sigmoid function to output the gen- erated solutions.
19

---

Published as a conference paper at ICLR 2025
C EXPERIMENTAL DETAILS
C.I DETAILS OF THE BENCHMARKS
We use three commonly used ILP benchmarks in our experiments. The data instances are generated using the code from ht https:://// ///ggtthubbb com/ ds 4dm wwt//2brannnacchh com//ssdd//LLann22aaannd We list the benchmark information in Table 3 including the generation algorithms, average numbers of constraints and average numbers of variables.
Table 3: Statistics of the benchmarks.
Datasct
Generation
Number of Constraints
Number of Variables
SC
(Balas &
1980
3000
2000
(Bergman ci a 2015
1500 5943
CA
(eeyton Brown et al. 2000
576
1500
C.2 TRAINING DETAILS
As mentioned in Section 3.3 in the main text, here we introduce three useful techniqques in our training process.
Normalization In practice, we conduct a normalization and modify the loss function on each instance G. as
C
my
(f,((o(()); 1K)
(o()
+
M. 0,
||c||2
Millaijil2
((0 A
(26)
c fe().).
M, 0,
||c||2
where M; is the number of constraints violated.
Learning Rate Annealing To facilitate continuing model optimization and alleviate local opti- mum, we adopt a cosine annealing scheduler for the learning rate (Loshchilov & Hutter (0166). with a period denoted as Ir T. The training curves in Figure T0 in Appendix D.4 demonstrate the influece of the cosine annealing of learning rate on the training progress.
Adaptive Penalty Coefficient The penalty coefficient l an important hyperparameter in Dif- fILO, which influences the convergence of the training process. It is not set on per-instance level, but setting it as single value is enough. Our probability modeling approach can some- how reduce the influence of (m)axxx(( x - O)]. Notice that the penalty is only activated when when the con- straint is violated. Thus, even if the penalty parameter is set relatively large, the penalty term is less likely to dominate the loss function significantly if the constraints not violated.
Specifically, the penalty term in method is defined as
E,-((((())) [max(a]
To reduce the need for manual parameter adjustment for μ. we use a dynamic and adaptive μ,, which is inspired by the adaptive temperature in soft actor-critic algorithm (Haarnoja et al. 2018). Specifically, after each epoch, we update the coefficient 4 according to the updating rule
#4+1 14 + mu_step (cons cons_targ).
(27)
where cons denotes the average constraint violation in this epoch, and cons_targ the target value of the average constraint violation. Empirically the hyperparameter mu-targ is set as more than (according to the range of coefficients), as this indicates that there exist solutions with no con- straint violation in probabilistic sense. This dynamic way for tuning y can effectively improve the algorithm robustness against the choice μ. We present the training curves with different val- ues the parameter μ and analyze the influence of the adaptive strategy for μ. The results in Appendix D.5
Some important hyperparameters of the model training are provided in Table
20

---

Published as a conference paper at ICLR 2025
Table 4: Hyperparameters in experiments.
Hyperparameter
SC
18
CA
Description
embed_size
32
32
32
The embedding size the GNN predictor.
depth
3
10
10
The depth of the GNN predictor.
batch_sit size
5
5
5
Number of ILP problems in each training batch.
num sum_ss
15
15
15
Number of sampled solutions for reparameterization.
num epochs
1,200
1,200
2,400
Number max running epochs.
optimizer
Adam
Adam
Adam
Optimizer for training.
learning rate
le-4
8e-5
8e-5
Leaning rate for training.
lr_T
200
200
200
The period for learning rate cosine annealing.
mu_init
5.0
100.0
15
The initial value of μ..
mu_step
0.01
1.0
0.001
Step size for optimizing μ..
cons targ
1.0
0.1
0.1
Target value of average constraint violation.
C.3 INFERENCE DETAILS
To incorporate the heuristic solutions into traditional solvers like Gurobi and SCIP, we define a trust region by limiting the number of variables- whiih are different from the predicted ones to be fewer than 200. In practice, we add the following constraint to the original problem
Σ S4 + =1- <A,
(28)
2
where è denotes the provided heuristic solution, and A is hyperparameter. In our experiments, we simply set A 200.
We also supply our best-found solution as an initial solution to the solver. For Gurobi, this is implemented as:
for i, in enumerate (m. getVars )
v.Start best_x(i)
and for SCIP it implemented as:
sol mm.reatteaattillllllll ()
for i, v in enumerate (m. ()) m. setSolalll (sol, v, best_x(i]) m. m.adSol (sol)
Only one best solution is provided to the solver. Specifically, for each instance, we sample 1,000 solutions from the predieted distribution. We select the best feasible solution, if any, based on the objective value. If no feasible solution found, we select the one with the minimal merit function.
During inference, SCIP 8.1.0 (Achterberg) 2009), Gurobi 10.0.1 Gurobi Optimization 2021) are used for solving instances. Following Han et al. 2023). we configure the solvers towards the Cheuristic-fisst" mode tte "MiPFoeus" parameter for Gurobi and the "AGGRESSIVE" parameter in SCIP-so that they will focus on finding better pri- Specifically, we set 'm. Params. MIPFoous 'm. set inteursstii iesiiccs ics (SCIP PARAMSETTING ING ACCRESSIVE) for SCIP, respectively. The time limit for running each experiment is set 1, 000 seconds.
mal solutions.
for Gurobi and
To improve traditional solvers, PS (Han et al. 2023) adds constraints to restrict the solution space within trust region. The trust region search algorithm controlled by three key hyperparameters, kn, k1, and A. Searching for suitable hyperparameters for PS on different datasets is challenging and labor-intensive. For IS and CA, we use the default hyperparameters specified in the original paper. For SC, which is not included in the original paper, we conduct the hyperparameter search as follows: we first fix kg and k to 100 and experiment with A values {5, 10, 15, 20). We then experiment with ku and kj values in {100, 200, 300} with fixed A.
21

---

Published as a conference paper at ICLR 2025
D ADDITIONAL RESULTS
D.1 SHIFTED GEOMETRIC MEAN OF RELATIVE GAPS
To better understand the results, we also report the shifted geometric mean (SGM) of relative gaps of the instances Table which a usually used metric to measure the model performance in the ILP community. Specifically, suppose the dataset contains N instances, the ith instance's best know objective is BKS,, and a method achieves an objective value OBJ, Its relative gap is defined as
OBJ, BKS,
gap;
BKS;
The shifted geometric mean across all instances is defined as
SGM = exp
Σ
log(gap, + 1.0) - 1.0.
(30)
N
Table 5: Shifted geometric mean (SGM) of relative gaps of different methods on all datasets. Lower SGM indicates better performance. second-best results.
We mark the best results bold and underline the
SC
IS
CA
10s
100s
1000s
10s
100s
1000s
100s
1000s
Gurobi 10.6222
0.0070
0.0008
0.0031
2.97E-05
1.50E-05
0.0059
0.0013
3.48E-06
PS+Gurobi
0.5085
0.449
0.449
1.50E-05
1.50E-05
1.50E-05
0.0044
0.0009
3.61E-10
DiflLO+Gurobi
0.1046
0.0037
0.0005
0,0002
2.96E-05
0
0.0042
0.0005
4.10E-10
SCIP
0.11
0.0373
0.0052
0,0341
0.0063
0.0001
0,0563
0.0054
1.0067
PS+SCIP
0.449
0.449
0.449
0.0286
7.36E-05
1.50E-05
0.0249
0.0011
1.00E-07
DiffILOSCIIP
0.0873
0.0112
0.0015
0.0143
1.00E-04
1.50E-05
0.0145
0.0007
1.00E-07
D.2 RESULTS OF ADDITIONAL BASELINES
In the main text, our main baseline the PS method, which is a representative supervised learning approach. In this section, we include three additional baselines as follows, and the experimental results on the dataset are shown in Table and Figure
CL-LNS (Huang et al. 2023) is large neighborhood search (LNS) approach, different frame- work from branch and bound (BnB). We compare with CL-LNS to demonstrate the effectiveness of DiffILO compared with LNS-based methods.
ConPaS (Huang et al. 2024) adopts contrastive learning for enhancing the PS framework. As they have not provided publicly released code, implement the approach based on the paper's details.
DDIM ZZng al. 2024 adopts diffusion models to learn generate feasible solutions. We used the authors' released code.
Naive Relaxation We include a naive relaxation baseline for the ablation study demonstrate the effectiveness of our proposed relaxation approach. Specifically, in this baseline, we di- rectly optimize the penalty term E, max(aJ & by, 0) instead of proposed probabilistic one by, 0)]. The parameter f is further tuned to achieve good convergence.
Ex [max((] Different from our approach, the naive baseline views the problem as simple continuous one with- considering the discrete nature of the original problem.
x (I)e:pp()))/mxx((]]
22

---

Published as a conference paper at ICLR 2025
REINFORCE rather than reparameterization As noted in Remark alternative approach for handling non con-differentiable computation graphs involving sampling is the REINFORCE method. To demonstrate the effectiveness of using reparameterization, we implement REINFORCE method as a baseline. It computes gradients as
TaBa=pp(1a) = Ex (x) logp(-1()].
(31)
where C(x) denotes the merit function as defined in P3 We find that all models collapse to- wards minimal objectives but significant constraint violations, even we set very large μ. This tendency underscores the well-known training challenges associated with RL models. Specifically, the REINFORCE method relies on random exploration without gradient guidance. When solution is reached, the model receives only reward signal but is unaware of the inherent components of the reward or the gradient information at the current point. In the vast search space, the absence of muddient-directed exploration lead models to converge to trivial yet infeasible solutions. The results further demonstrate the necessity of e--arameterization trick for this task.
Table 6: Results of additional baselines. We report the objective values achieved at 10s, 100s, and 1000s, respectively. The results show that DifILL still outperforms these baselines. Another baseline, REINFORCE, has failed to derive meaningful results and thus is not reported.
SC (Min, BKS: 86.45)
10s
100s
1000s
CL-LNS
203.27
91.96
86.77
Naive Relaxation
132.1
94.71
87.05
DifiLLO 95.65
86.78
86.48
We test the abilities of DiffILO, ConPaS, and DDIM to generate feaisble solutions. The results are shown in Figure The results show that ConPaS still fails to generate feasible solutions across most instances. DDIM demonstrates strong feasibility rates and successfully generates feasible solutions for all instances. However, when considering solution quality, DifilLO still outperformed DDIM in terms of objective values. This highlights the strength of DiffILO in producing higher-quality solutions.
SC (min)
1000
BKS
DFL
Objextive Value
ConPuS
600
DDIM
400
50
75
100
Figure 8: Results of DinILO, ConPaS HHang generating feasible solutions on SC.
2024). and DDIM (Zeng et al. 2024) on
D.3 RESULTS ON MIPLIB DATASETS
To demonstrate the effectiveness of DifIILO on more complex and realistic dataset, we conduct additional experiments on the MIPLIB 2017 benchmark (Gleixner et al., 2021), which is well known as a collection of challenging real-world MILP instances. Notice that MIPLIB contains instances across many different scenarios, and many of the large-scale problems do not have isomorphic coun- terparts, learning directly on the full MIPLIB is extremely challenging. Following |Wang et al. 2023a), we first construct subset of MIPLIB, called "MIPLIB-CVS" to validate the effectiveness of DiffLLO. Specifically, contains five capacitated vertex separator (CVS) problem instances from MIPLIB 2017. They cva08r139-1 94, cvsl 7070 62, cvsl 6r89 60, cvsl 6 06-72,
23

---

Published as a conference paper at ICLR 2025
and cvs 6r128-89. We use the first three instances for training DiffILO,, and then test the model on the last two instances. The total training process takes about only 9 minutes. we use supervised learning, it will take more than three hours to solve the training instances for providing labels. The solving progresses are shown in Figure 6 which overall demonstrate that DifiILO can accelerate the solving process achieves the optimal solution (which is -97.0) in 1, 000 seconds, which even surpasses the result obtained by running Gurobi for 3, 600 seconds (which is 96.0).
complex realistic datasets. Notably, the cvs 6 18 DifiLL
0.40
0.40
Gandi
Guak Dili.eeCamk
0.5
0.30
0.30
Prinud Gue
0.30
0.30
0.10
0.00
010
0.00 44
Time
(a) cvs16r106s
(b) cvs 62128-82
Figure 9: The relative primal gap on the two test instances.
We have conducted an experiment on another subset of MIPLIB. We construct a subset of MIPLIB, called "neos", to validate the effectiveness of DifILO. Specifically, we collect all binary instances with "neos" in their names and select the instances whose .mps" files contain no more than 500,000 lines. We identify 25 such instances total. Then, we randomly select 20 instances for training and and neos-438278 1-144-uuvuaa derive no feasible solutions solved by Gurobi in 1,000 seconds. We report the solving time on the other test instances, neos 929552, neos-831 1888 neasi in Table 7
another 5 for test. Among these 5 instances, aeos-95299
Table 7: Solving time on the test instances from neos.
neos- -oos-829552
ncos-831
ncos 18
Gurobi Gurobi+DiftILO
44.83
63.24
4.24
43.08
60.91
4.28
While there were slight overall improvements, they sions. We attribute this to the inherent heterogeneity of the neos dataset. According to the MIPLIB website, the neos instances originate from diverse scenarios with unknown applications. This poses significant challenges for ML-based approaches, which rely on common patterns and generaliza- tions across instances. Additionally. we find that the heterogeneity among training samples led to unstable training processes, further complicating evaluation. The results demonstrate that training on heterogeneous datasets still pose challenges DifiILO.
significant enough to draw firm conclu-
D.4 TRAINING CURVES
We present the training curves of DiffILO in Figure 10 The consistent progress of training and validation curves shows that DiffILO exhibits good generalization. The consistent progress of losses and objectives shows that DifiILO effectively aligns the training and inference objectives.
D.5 INFLUENCE OF ADAPTIVE PENALTY COEFFICIENT
We present the training curves with two different settings of the penalty coefficient y in Figure III The results show that with our proposed adaptive penalty strategy, the training process is robust to different configurations of μr, and the coefficient μ can adjust itself towards reasonable value.
24

---

Published as a conference paper at ICLR 2025
171
1800
15
3000
1900
300
-200
1200
1000
1781
2000
0000
1300
Figure 10:
The learning curves of DiffILO on different datasets. Objs denotes the objective values of the best-found solutions at each step.
Traning Clavell
Traniig Caree Best Fesiille Sccedion
Thening Curve Crn Vodases
Tranning Carre Oljectto Loss
43
154
155
3500 300 4000 500
600
100
Figure 11: Training curves for different configurations of the penalty parameter μs. In the two experiments, we set the initial value of y as 1.0 and 5.0 (with miximum set as 5.0), respectively. The parameter j is dynamically adaptive during training. Even if we set small initial value for μt, e.g., 1.0 here, can be adaptively adjusted towards proper value, i.e., 5.0 here.
D.6 ABLATION STUDIES
We have conducted experiments to evaluate key choices, and the results are in Figure 12 The number of samples. We conduct experiments on a SC dataset, with results shown Figure a). We evaluated sample sizes of 5, 10, 15, 20, and 25. While larger sample sizes resulted in slightly smoother training curves and smaller sample sizes led to a little early convergence in the early stage of training, the overall results do not show significant differences. This demonstrates the robustness DifiILO to this parameter. For the main experiments, we just empirically set the sample size to 15. We also compared performance with and without the proposed normalization techniques. The results, presented in Figur show that our normalization method significantly accelerates convergence compared directly summing all penalty terms. We also tested averaging the constraint penalties instead of summing them, which resulted in worse validation performance and thus is not presented in the figure.
D.7 GENERALIZATION RESULTS
We further test the zero-shot generalizability of PS and DiffLLO. Specifically, the models are trained on small SC instances (with 3, 000 constraints an 2, 000 variables). and tested large SC instances (with 6, 000 constraints and 4, 000 variables). The results are in Table demonstrating that DifilLO generalizes well large-sized instances. This may be because the unsupervised training approach
25

---

Published as a conference paper at ICLR 2025
Table Generalization to large-size datasets. The models are trained small SC instances (with 3000 constraints an 2000 variables), and tested on large SC instances (with 6000 constraints and 4000 variables). Results show that DifiLLO performs well on large-sized instances, indicating its generalization ability.
SC-small (BKS:
86.45)
SC-l (BKS: 79.35)
10s
100s
1000s
10s
100s
1000s
Gurobi PS+Gurobi
1031.39
87.09
86.52
993.65
85,92
79.58
131.87
125.26
125.26
144.76
131.45
131.45
DiflILO+Gurobi
95.65
86.78
86.48
97.83
84.72
79.55
sample115
10P
1001
700
900
700
4102
6001
800
1000
(a) numsample
(b) normalization
Figure 12: Ablation studies on (a) number of samples in each step and (b) the normalization trick used for training.
encourages the model to learn the fundamental mechanisms needed to solve problems, instead of merely memorizing simple statistical patterns in the data, thus outperforming supervised methods.
D.8 CASE STUDY
We have conducted additional experiments to investigate how the penalty parameter i affects the success rate. The results are in Table 9 In this table, we report the number of successes out of 20 trails with different random seeds. The results show that optimizing closed-form merit function is robust against changes in Interestingly, its performance is mainly determined by the random seed. However, it consistently underperforms compared DifiILO across a broad range of μ values. With properly chosen DiffILO achieves 100% success ratio.
Table 9: The influence of on the success ratio in the case study.
8
10
11
12
13
14
15
16
17
50
100
closed-form DiffILO
0
0
9
9
9
9
9
9
9
0
0
0
0
2
7
17
20
20
20
20
20
20
19
16
26

---

Published as a conference paper at ICLR 2025
E DISCUSSIONS
E. LIMITATIONS
Sub-optimality DifILLO is an unsupervised learning approach, which does not learn from the op- timal solutions found by traditional solvers, but instead learns to produce solutions itself. There are reasonable concerns that DiffILOO may tend generate sub-optimal solutions, especially when com- pared with supervised learning approaches. Sub-optimality is essentially fundamental challenge for most optimization approaches. Therefore, more attention should be paid to addressing this issue and reducing the risk of sub-optimality.
Research scope DifiILO mainly focuses on solving integer linear programs (ILPs). Currently, we focus on ILPs with binary variables. More general ILPs with integer variables and mixed-integer linear programs (MILPs) are out of the scope of this paper. This extension poses new challenges, especially in dealing with the unbounded integer and continuous variables. However, we believe that DifiILO provides an avenue for such directions, and we plan to explore the use of differentiable approaches for solving general ILPs and MILPs in future work.
Waiting for more sophisticated designs The differentiable ILP solving is still in its early stage and lacks sophisticated designs. For example, the sampled solutions can stored in a buffer for better sample efficiency. The specific gradient optimization algorithm for such task is not yet de- veloped. Moreover, the current bipartite graph representation and GNN architecture are still simple, and can be further designed in the future.
E.2 FUTURE AVENUES
Used for large-scale pretraining The unsupervised nature of DifiILO makes it suitable for pre- training tasks on large-scale datasets.
Combination with supervised learning DiffILO is based unsupervised learning and may be stuck in sub-optimal. It is promising to combine it with small amounts of supervised data to better overcome the sub-optimality issue.
Better optimization algorithm In this work, we use simple Adam for gradient-based optimiza- tion. Better and more specificly-used optimizers could be developed in the future. Moreover, integrating traditional methods such as branch-and-boung or large-neighborhood search into our framework could bolster its robustness and help the model navigate complex solution landscapes effectively.
Extension to more general problems We note that a contemporaneous ICLR submission (Anony- mous 2024) reports and attempts tackle the similar limitations. They stated: "Most existing end-to-end machine learning-based methods primarily focus on predicting solutions for binary vari- ables." Their approach involves converting integer variables into binary representations and pre- dicting these binary bits iteratively. This iterative binary prediction approach could be extended to our framework, though it would require additional modifications. We plan to explore this direction in future work. Moreover, While this paper primarily focuses on ILPs, the underlying principles can be extended to non-linear problems. The key lies in the design of the probabilistic model for و (x) Exxp(-183) ()) (x)], where d (x) can adapted for non-linear constraints. Exploring such extensions is an exciting direction for future work.
Better model architectures In the future, better model architectures will be expored to replace the GNN in the current methodology. Some potential practices include soft matching between nodes (Cuturi 2013 Caron et al. 2021). differentiable clustering for a soft cluster assignment (Stew- art et al. 2024). ) and vector quantization for assigning discrete values (Van Den Oord al. 2017).
27


Reviews:
[{"review_id": "ur7S76r4xH", "reviewer": "Reviewer_FT2F", "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.", "questions": "see weakness.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 4, "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.", "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.\n\nGradient 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.\n\nTo 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "kXFHLtJcXd", "reviewer": "Reviewer_y4sA", "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.\n\nOverall, the work is interesting while there is some room for improvement, if the authors address my comments I am eager to increase my score.", "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?\n\nWhy are the Zheng 2024 and Huan 2024 baselines not included as they seemed to surpass the PS approach and provide implementations.\n\nHow 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?\n\nHow does the approach generalize to different kinds of problems? Either to larger instances or out of distribution instances e.g. MIPLIB?\n\nWhat are the feasibility rates for PS? They are given for DiffILO but not present for the baseline. It seems figure 4 is missing.\n\nHow is mu determined? Is it determined as a hyperparameter? Or adaptively selected to ensure feasibility?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 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.\n\nThe approach itself is well motivated and the paper is well-written. \n\nThe illustrative toy example is helpful for giving intuition for how the approach works in a simple setting.", "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.\n\nTheorem 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? \n\nIt 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.\n\nSpecific comments:\n-\tRemark 2 ends in “Otherwise,” is something missing there?\n-\tFigure 4 is missing\n-\tToour is missing a space", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "4JOW1Hxf56", "reviewer": "Reviewer_LD6k", "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.\n\nUnlike 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.", "questions": "- typo in line 198;", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "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:\n\n- 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.\n- experimental results look convincing in terms of both runtime and solution quality. Although adding larger scale experiments would be beneficial;\n- the method is intuitive to understand and makes sense to me.\n- can be directly applied to speed up the runtime for traditional solvers;\n\n\n[1] A. N. Elmachtoub and P. Grigas. Smart “predict, then optimize”. arXiv:1710.08005\n\n[2] A. Ferber, B. Wilder, B. Dilkina, and M. Tambe. MIPaaL: Mixed integer program as a layer. \n\n[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\".", "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "ZcNeYA54lK", "reviewer": "Reviewer_NhwL", "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.", "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.\n\nThe 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?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and clear. \n2. Adequate theoretical support is provided for the key steps.\n3. 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.", "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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "k3W5loBJfT", "reviewer": "Reviewer_Rkn8", "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.\n\nThe mathematics corresponding to the methodology are clearly presented in detail. The methodology is evaluated empirically on three ILP benchmarks:\n\n- Set covering \n- Maximum independent set\n- Combinatorial Auctions\n\nand 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.", "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).\n\nI believe the following reference would be useful for the paper (regarding smoothing COs): [Berthet 2020] *Learning with Differentiable Perturbed Optimizers*", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "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.", "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.\n\n - 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*)\n- 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*.\n- Vector Quantization (not differentiable, but commonly used in practise to assign discrete values): **[van den Oord 2017]** *Neural Discrete Representation Learning*.\n\n\nAs 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)