DOGE-Train: Discrete Optimization on GPU with End-to-end Training
Authors: Ahmed Abbas
Paul Swoboda
Venue: NeurIPS 2022 Submitted (2022)
Keywords: Discrete optimization
Integer linear programming
Combinatorial optimization
Graph neural networks
End-to-end
Self-supervised
Backpropagation
Message passing

Abstract: We present a fast, scalable, data-driven approach for solving linear relaxations of 0-1 integer linear programs using a graph neural network.
Our solver is based on the Lagrange decomposition based algorithm of Abbas et al. (2022).
We make the algorithm differentiable and perform backpropagation through the dual update scheme for end-to-end training of its algorithmic parameters.
This allows to preserve the algorithm's theoretical properties including feasibility and guaranteed non-decrease in the lower bound.
Since the method of Abbas et al. (2022) can get stuck in suboptimal fixed points, we provide additional freedom to our graph neural network to predict non-parametric update steps for escaping such points while maintaining dual feasibility.
For training of the graph neural network we use an unsupervised loss and perform experiments on large-scale real world datasets.
We train on smaller problems and test on larger ones showing strong generalization performance with a graph neural network comprising only around $10k$ parameters.
Our solver achieves significantly faster performance and better dual objectives than its non-learned version of Abbas et al. (2022).
In comparison to commercial solvers our learned solver achieves close to optimal objective values of LP relaxations and is faster by up to an order of magnitude on very large problems from structured prediction and on selected combinatorial optimization problems.
Our code will be made available upon acceptance.

25 in fundamental way. particular, this holds true for LP solvers which are key component of most commonly used ILP approaches. LP solvers produce lower bounds on the optimal solution objective and are integral for many heuristics decode feasible integral solutions. For many problems the ILP solvers spend most of the time on solving multiple LP relaxations, hence any impact GPUs and ML DOGE-Train: Discrete Optimization on GPU with End-to-end Training
Anonymous Author(s)
Affiliation Address email
Abstract
We present a fast, scalable, data-driven approach for solving linear relaxations of 0-1 integer linear programs using graph neural network. Our solver is based on the Lagrange decomposition based algorithm []. We make the algorithm differentiable and perform backpropagation through the dual update scheme for end-to-end training of its algorithmic parameters. This allows to preserve the algorithm's theoretical properties including feasibility and guaranteed non-decrease in the lower bound. Since [1] can get stuck in suboptimal fixed points, we provide additional freedom our graph neural network predict non- parameereee update steps for escaping such points while maintaining dual feasibility. For training of the graph neural network we use an unsupervised loss and perform experiments on large-scale real world datasets. We train on smaller problems and test on larger ones showing strong generalization performance with a graph neural network comprising only around 10k parameters. Our solver achieves significantly faster performance and better dual objectives than its non-learned version []] In comparison to commercial solvers learned solver achieves close to optimal objective values of LP relaxations and is faster by up to an order of magnitude on very large problems from structured prediction and on selected combinatorial optimization problems. Our code will be made available upon acceptance.
10
12
14
16
18
Introduction
19
20
Integer linear programs (ILP) are a universal tool for solving combinatorial optimization problems. While great progress has been made improving ILP solvers over the past several decades, some fundamental questions for future improvements remain open: Can ILP solvers make effective use of the massive parallelism afforded by GPUs and modern machine learning meaningfully help? As of now the consensus seems that neither GPUs nor ML have yet helped general purpose ILP solvers
21
22
24
26
27
28
29 can have will directly translate into overall improvement of ILP solvers.
make little utility of modern machine learning but rather either hand-designed or auto-tuned parameters and update rules. Moreover, with the exception 32 of 18 these solvers are not open-source, hence researchers' ability to assess the potential of neural
30 State of the art LP solvers 23
33 networks for improving LP solvers is limited. From conceptual point of view traditional solver paradigms, e.g. simplex or interior point methods, are not GPU friendly and contain non-differentiable steps (such as pivot selection for simplex). Additionally, their high complexity further complicates
34
35
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

36 any effort at making them differentiable. This makes utilization of neural networks and GPUs for solver improvement difficult.
37
38 We propose a new way to use the potential of GPU parallefism and modern ML to obtain advances in LP relaxation solvers for ILPs. We argue that due to the difficulties in putting GPUs and MIL to work in traditional solver methodologies, investigation of new paradigms is called for. To this end we build upon the recent work of I which proposed a massively parallel GPU friendly solver for 0-1 integer linear programming using Lagrange decomposition, The solver exhibits faster performance than traditional CPU solvers on large-scale problems making good use of GPU parallelism. Also due to its comparatively simple control flow and its usage of simple arithmetic operations for all its operations can be made differentiable. This allows to train its parameters and predict update steps that will allow for faster convergence and overcoming fixed points from which the basic version of the algorithm suffers. This results superior performance as compared to the non-learned version [I] We obtain small gaps to (I)LP optima on a diverse range of large scale structured prediction problems, QAPLib 8 and independent set problems [39] We are up to an order of magnitude faster than traditional ILP solvers.
39
40
41
42
43
44
45
48
47
48
49
51
Contributions We propose to learn the Lagrange decomposition based algorithm 1 for solving LP relaxations of ILP problems and show its benefits. In particular,
52
58
We make the dual update steps of [ differentiable. This allows us to predict parameters of the update steps that faster convergence is achieved compared using hand-picked values.
54
55
We train a predictor for arbitrary non-parametric update steps that allow to escape suboptimal fixed points into which the parametric update steps of [ can fall.
56
We propose to train predictors for both the parametric and non non-parametrr updates in fully unsu- pervised manner. Our loss optimizes for parameters/update steps producing large improvements the dual lower bound over long time horizon.
58
80
We show the benefits of our learned massively parallel GPU approach on a wide range of problems. We have chosen structured prediction tasks including graph matching [29] and cell
61
62
tracking [24). From theoretical computer science we compare on the QAPLib [8] dataset and randomly generated independent set problems 33
63
2
Related Work
64
65
2.1
Learning to solve Combinatorial Optimization
ML has been used to improve various aspects of solving combinatorial problems. For the standard 66
67
branch-and-cut ILP solvers the works 11 2 35
learn variable selection for branching. The approaches [4 35| learn to fix subset of integer variables in ILPs to their hopefully optimal values to improve finding high quality primal solutions. The works 43 54] learn variable selection for
68
69
70
the large neighborhood search heuristic for obtaining primal solutions to ILPs. Selecting good cuts through scoring them with neural networks was investigated in 26 46) While all these approaches result in runtime and solution quality improvements, only a few works tackle the important task of
71
72
73 speeding up IIP relaxations by ML. Specifically, the work 11 used graph neural network (GNN) to predict variable orderings of decision diagrams representing combinatorial optimization problems.
74
75 The goal is to obtain an ordering such that a corresponding dual lower bound is maximal. To our knowledge it is the only work that addresses computing ILP relaxations with ML. For constraint satisfaction problems 40 47) train GNN while [47] train in an unsupervised manner. For narrow subclasses of problems primal heuristics have been augmented through learning some of their decisions, c.g. for capacitated vehicle routing [36] and traveling salesman
76
77
79
[55]. For a more complete overview of ML for combinatorial optimization refer to the detailed surveys 66 [0]
81
2.2 Massively parallel combinatorial optimization
82 Massively parallel algorithms running on GPU have been proposed for narrow problem classes,
83 including inference in [1 [6) and dense [45] Markov Random Fields, multicut (2) and for max-
84 flow 49 53]. The algorithm I on which our work is based is, to our knowledge, the only generic
ILP solver that can make adequate use of parallelism offered by GPUs.

---

86
2.3
Unrolling algorithms for parameter learning
87
Algorithms containing differentiable iterative procedures are combined with neural networks for improving performance of such algorithms. One of the earliest works in this direction is [2]] which embedded sparse coding algorithms in a neural network by unrolling. For solving inverse problems (57 [2] unroll through ADMM and non-linear diffusion resp. Overall, such approaches show more generalization power than pure neural networks based ones as shown the survey [34]. Slightly different than from the above works, neural networks were used to predict update directions for training other neural networks (e.g.
88
89
91
93
3 Method
94
We first recapitulate the Lagrange decomposition approach to binary ILPs from [1] and the deferred 95
mar-maaginal averaging scheme for its solution proposed in []]. We highlight possible parameters of the update steps which we will predict by training a graph neural network. Proofs are in the Appendix.
97
99
3.1
Lagrange Decomposition & Deferred Min-Marginal Averaging
100
Definition (Binary Program 31). Let a linear objective E IR" and m variable subsets Ij C [ri] of constraints with feasible set X3 (0, 1)2 for j E [m] be given. The corresponding binary program
102
min (c, s.t. VI, X3 Vj E [m]. =E(01))
(BP)
103
where VT, the restriction variables in Zz-
Any binary ILP min (0.1)= (c, 2) s.t. Ar S b where A E Rm** can be written as (BP) by associat- ing each constraint az x S by for E [m]] with its subproblem X,
104
106
In order obtain a problem formulation amenable for parallel optimization we consider its Lagrange dual which decomposes the full problem (BP) into a series of coupled subproblems.
107
Definition 2 (Lagrangean dual problem [3]). Define the set of subproblems that constrain variable i
109
as J. = (j [m] E I2}. Let the energy for subproblem j E [m]] w.r.t. Lagrangean dual variables
A = (Agg)ie,, E R be
110
E (A,)) min (Noj, ZER
Then the Lagrangean dual problem is defined as
max
E'()) s.t.
Σmy= JEJ:
vi [n].
(D)
5E[m]
112
The authors in [1] have proposed a parallelization friendly iterative algorithm for updating Lagrange multipliers for maximizing (D), see Algorithm [ We write
113
slightly adapted form since will allow us to easily describe its backpropagation. The algorithm assigns the Lagrange variables in u-many disjoint blocks BI...., B,, in such a way that each block contains at most one Lagrange variable from each subproblem and all variables within a block are updated in parallel. The dual update scheme relies on computing min-marginal differences i.c., the difference of subproblem objectives when a certain variable is set to minus its objective when the same variable is set to 0, see line TT) in Algorithm T These marginall differences are averaged out across subproblems via updates to Lagrange variables in line [1 in Algorithm[ [ The crucial ingredient allowing parallelization is that the man-marginal averaging step values from the last iteration are used (i.e. M M*",, making synchronization between subproblems unnecessary.
114
115
117
119
121
122
123
In the min-marginal averaging parameters of Algorithm were set as w = 0.5 and 0zj 1/1.,1 leading to uniform averaging. We generalize the min-marginal update step by considering more general parametric update steps. We allow w E (0, 1) and a-values to be arbitrary convex combinations. In the next section will show how to train these values to achieve faster convergence.
124
125
127
Proposition (Dual Feasibility and Monotonicity of Min-marge marginal Averaging). For any Oii with Ejeo, 0i = 1 and wa E [0, the min-marginal averaging step in line 77 in Algorithm retains dual feasibility and is non-decreasing in the dual lower bound.
128
129
3

---

Algorithm 1: Parallel Deferred Min-Marginal Averaging [
Input: Lagrange variables Xi E [n],j J,, damping factors wi E (0. 1) E |m].j E Ti
anisotropic min-marginal averaging weights Oij E 10, [m].] É Tr max. number of iterations T.
Initialize deferred min-marginal diff. M
2 for iterations do for block B (BI.... B.,) do
X, +- BlockUpdate (B, A, M, ()
for block B (Bu.... B1) do
M +- BlockUpdate (B, X, M, a,
return M
Procedure BlockUpdate (B, At M a, W)
for 2j E B in parallel do
10
Compute Mout Wiyl [min (Xa). 2) am bf
11
Update b5 = =
M + Oij Ene Mik
12
return Aour, Mout
130
3.2
Backpropagation through Deferred Min-Marginal Averaging
131
show below how to differentiate through Algorithm [ with respect to the parameters a and w. This will ultimately allow us to learn these parameters such that faster convergence is achieved. To this end we describe backpropagation for block update (lines S 12 of Alg. [ All other operations can be tackled by automatic diffcrentiation. For block B in { (B....., B.) we view the Lagrangean update as a mapping H (R|Bll Bl)4 (R (R/B1)2 (Aim, Min a, w) + (Aour, Mout).
135
135
Given a loss function L R + IR denote Oc/ac /r by i. Algorithm 2 shows backpropagation through H to compute the gradients iin Min, â and a. Proposition Algorithm 2 performs backpropagation through H.
138
139
Efficient Implementation Generally, the naive computation of min-marginal differences and its backpropagation are both expensive operations as they require solving two optimization problems for each dual variable. In [1]1 the authors represented each subproblem using binary decision diagrams (BDDs) for fast incremental computation of min- min-marginnal differences. Their algorithm results in computation graph involving only elementary arithmetic operations and taking minima over several variables. Using this computational graph we can implement the abstract Algorithm efficiently and parallelize on GPU. For details we refer to the Appendix.
140
142
143
144
155
Algorithm 2: BlockUpdate backpropagation
Input: Forward pass inputs: B, A3 S a,w, gradients of forward pass output: oot Mrot gradients of parameters d;
for ij E B in parallel do M = Evej, jout Mout = Mout oou
duj = - + AeB Exeg, Mi Wij = wis + Mggai [ /wiy] Compute minimizers s (1, arg min =3 ( 1...00 xx, VB E 1)
A oot + Mggu wiy (sf(1,,) 1) (i,) Up E I, pJ pj
return Āin Man Man,a
148
3.3 Non-Parametric Update Steps
Although the min-marginal averaging scheme of Alg. guauratttes non-decreasing lower bound, it can get stuck in suboptimal fixed points, see (50) for discussion for the special case MAP-MRF. To alleviate this shortcoming we allow arbitrary updates to Lagrange variables through vector
148

---

0 E R!A as
150
1
Asy f X15
cu. ViE [ Tr
(2)
RET
151
where the last term ensures feasibility of updated Lagrange variables w.r.t. the dual problem (
152
3.4
Graph neural network
153
We train a graph neural network (GNN) to predict the parameters o, of Alg. [ and also the non non-paranann parametric update 0 for (2). To this end we encode the dual problem (D) bipartite graph (V, 8). Its nodes correspond to primal variables I and subproblems J i.e., - J and edges & = {ij E I.j Jt} correspond Lagrange multipliers. We need predict values of Oij. Way and Oey for each edge ij in E. We associate features / JE) with each entity of the graph which capture the current state of Alg. [T Additionally, we encode number of quantities as features which can make learning easier. For example, history of previous dual objectives for each
155
156
157
158
159
180
subproblem is encoded in the constraint nodes and minimizers of each subproblem (which correspond to subgradient of the dual problem (D) are encoded in the edge features fe. A complete list of features provided in the Appendix.
162
163
Message passing To perform message passing we use the transformer based graph convolution scheme of [42]. We first compute an embedding of all subproblems j in I by receiving messages from adjacent nodes and edges
164
185
Wafs
aiglf, W.) WWf Wefyl, Σ <ijEE
(3)
where W (Wa, Ws, We, W.) are trainable parameters and a:y (zy(fz; Se; Wa) is the softmax attention weight between nodes i and j parameterized by Wa- Afterwards we perform message passing in the reverse direction to compute embeddings for primal variables I. Similar strategy for message passing on a bipartite graph was followed by [19
167
189
170
Recurrent connections Our default GNN as mentioned above only uses hand-crafted features to maintain history of previous optimization rounds. To learn summary of the past updates optionally allow recurrent connections through an LSTM with forget gate [20). The LSTM is only applied primal variable nodes I and maintains cell states sz which can be updated and used for parameter prediction in subsequent optimization rounds.
172
174
175
The learned embeddings from GNN, LSTM outputs and solver features from Alg. are consumed by multi-layer perceptron & to predict the required variables for each edge ij in E. Afterwards we transform these outputs so that they satisfy Prop. [
Prediction
177
178
The exact sequence of operations performed by the graph neural network are shown in Alg. 3 where
179
[ui.... ..]] denotes concatenation of vectors ....... Ug, denotes layer normalization S and
180
LSTMz stands for an LSTM cell which operates on each primal variable node.
Algorithm 3: Parameter prediction by GNN
Input: Primal variable features fi and cell states sz, Subproblem features fo. Dual variable (edge) features fe, Set of edges E.
h ReLU (LN (CONV.7 7 (Jz, So, E))
Compute subproblems embeddings
2 hi ReLU (LN (CONV (Jz, [J, he
// Compute primal variable embeddings
27, 8I LSTM, Toz, 8I)
// Compute output and cell state
fe. Qio Softmax (...). Vi I, Sigmoid(()) // Ensure non non-decreasing obj Prop.
(á, a, 0) = 4 ([fz, hz, zz), [fo, ffo,,,ll.tt
// Prediction per edge
return at a, Sz
5

---

Optimization round
fz
f
Or w
Graph NN
Non-param. update
Def. MMA
A
Loss
J2
fI,
13
Figure I: Our pipeline for optimizing the Lagrangean dual (D) The problem is encoded bipartite graph containing features fr. fi and f& for primal variables, subproblems and dual variables resp. graph neural network (GNN) predicts the non-parameteric update 0 (2) and parameters and for Alg. 1 In one optimization round current set of Lagrange multipliers À are first updated by the non- non-poranan con-aarmetrric update using Afterwards deferred min min-marginal averaging is performed parameterized by a and w. The updated solver features f (which also includes A) and LSTM cell states 8I are sent to the GNN in next optimization round. These rounds are repeated at most R-times during training and until convergence during inference.
3.5 Loss
182 Given the Lagrange variables À we directly use the dual objective D as an unsupervised loss to train the GNN. Thus, maximize the loss L defined as
((A) = Σ (2,))) 5Emm]
(4)
For a mini-batch of instances during training we take the mean of corresponding per-instance losses. 185 For backpropagation, gradient loss w.r.t. Lagrange variables of a subproblem j is computed by
184
186
finding a minimizing assignment for that subproblem, written as
OC ax
argminzex, (Noj. E 1
(5)
+j
187
The above gradient is then sent as input for backpropagation. For computing the minimizing assignment efficiently use binary decision diagram representation of each subproblem 31
188
3.6
Overall pipeline
190
Our overall pipeline combining building blocks from the previous sections is shown in Figure) We train pipeline which contains multiple dual optimization rounds in fashion similar that of recurrent neural networks. One round of our dual optimization consists of message passing parametric update step and 7 iterations of deferred min-marginal averaging. For computational efficiency we run our pipeline for at most dual optimization rounds during training. On each mini-batch randomly sample number of optimization rounds in [R], run without tracking gradients and backpropagate through the last round by computing the loss (4). For the pipeline with recurrent connections we backpropagate through last 3 rounds and apply the loss after each of these rounds. Since the task of dual optimization is relatively easier in early rounds compared later ones (where [ can get stuck) we use neural networks. The early stage network is trained the randomly sampled r is in [0, R/2] and the late stage network is chosen otherwise. During testing we switch to the later stage network when the relative improvement the dual objective by the early stage network becomes less than 10
192
by GNN,
194
rounds
196
198
199
200
201
202
Experiments
203
As main evaluation metric report convergence plots of the relative dual gap g(l) [0, 1] at time /
d(t) 1.0
g(t) = min
(6)
d' dinit

---

205
where d(t) is the dual objective at time t, d' is the optimal (or best known) objective value of the Lagrange relaxation (D) and diuit the objective value before optimization as computed by M.
206
207
Additionally we also report per dataset averages of relative dual gap integral gr = J g())dt 77. best
208
objective value (F)) and time taken (1) to obtain best objective. To cater the dominating effect of
209
worse initial lower bounds on 9r (as g(t) can be close to at & R 0) we start calculating Jz after few rounds of our solver are completed. This start time is then also used to evaluate other algorithms for a fair comparison. To evaluate CPU solvers use AMD EPYC 7702 CPU. For the GPU solvers we use either one NVIDIA RTX 8000 (48GB) or A10 (80GB) GPU depending on instance size.
210
212
213
4.1
Algorithms
Gurobi:
Results of the dual simplex algorithm from the commercial ILP solver (23]
215
FastDOC:
The non-learned baseline [ of Alg. with Waj = 0.5 and auj = 1/ T/l-
216
DOGE: Our approach where we learn to predict parametric and man-aaametric updates by using two graph neural networks for early and late-stage optimization. Size of the learned embeddings h computed by the GNN in Alg. 3 is set to 16 for nodes and 8 for edges. For computing attention weights in (3) we use only one attention head for efficiency. The predictor & in Alg. 33 contains 4 linear layers with the ReLU activation. We train the networks using the Adam optimizer 30) To prevent gradient overflow we use gradient clipping on model parameters by an 12 norm of 50. The number of trainable parameters is 8k.
217
218
219
220
221
222
223
DOGE-M: Variant of our method where we additionally use recurrent connections using LSTM. The cell state vector 8; for each primal variable node i I has size of 16. The number of trainable parameters is 12k.
225
226
We have not tested against specialized heuristics for our benchmark problems since M has shown them to be on par or outperformed by FastDOG. For training our approach we use the frameworks [T
227
228
16
38
and implement the Algorithms in CUDA 37 using (25 28
4.2
Datasets
230
Cell tracking (CT): Instances of developing flywing tissue from cell tracking challenge 48 pro-
231
cessed by (2 and obtained from [44]. We use the largest and hardest 3 instances, train on
232
the smaller instances and test on the largest one.
233
Graph matching (GM): Instances of graph matching for matching nuclei in 3D microscopic im-
ages 32 processed by [29] and made publicly available through 44 We train on 10 instances and test on the remaining 20 instances.
235
236
Independent set (IS): Random instances of independent set problem generated using 33 For
237
training we generate 240 instances with 10k vertices each and test on 60 instances with 50k vertices. We generating edges between vertices in the graph with a probability of 0.25.
238
QAPLib: The benchmark dataset for quadratic assignment problems used in the combinatorial
240
optimization community [8. We train on 61 instances having up to 40 nodes and test on 35 instances having up to 70 nodes.
For each dataset we use separate set of hyperparameters due to varying instance sizes given in T All our test datasets on average contain more than a million edges (i.c., Lagrange variables) while training instances are considerably smaller. For efficiency, during evaluation we
243
larger value of T in Alg. I than during training. For the CT dataset containing we learn only the non- parametric update steps (2) and fix the parameters in A their default values from [T]. Learning these parameters gave slightly worse training loss at convergence.
245
247
248
4.3
Ablation study
249
We perform an ablation study to test the importance of various components of our approach. Starting from [I] as a baseline we first predict all parameters w, 0 through the two multi-layer perceptrons & for early and late stage optimization without using GNN. Next, we report results of using one network
250
251
(instead of two) which is trained and tested for both early and later rounds of dual optimization. Lastly,
we aim to seek the importance of learning parameters of Alg- and the non-parametric update (2).
253
To this end, we learn to predict only the non-parametric update and apply the loss directly on updated
7

---

Table 1: Hyperparameters our approach and dataset statisties. variables and constraints in each dataset (# vertices in GNN); > Dn Jal: Average number of Lagrange multipliers (# edges in GNN); T: Number of iterations of Alg. lin each optimization round; Rt max.
|J
Average number of
number of training rounds; itr. train: Number of training iterations.
Dataset
[ + [5] (x10%)
Σj-1 (x10%)
T
R
hatch size
learn. rate
# itr.
train time
train
[hrs]
train
train
train
CT
3.7
12.4
8.5
28
100
400
1
le-3
500
14
GM
1.7
3.3
3.3
20
200
20
le-3
400
0.05
0.4
0.1
20
20
1o-3
2500
QAPLib
0.1
2.8
0.5
500
1o-3
1600
Table 2: Ablation study results on the Graph matching dataset. w/o GNN: Use only the two predictors & without GNN for early and late stage optimization; same network: both early and late stage; only non-param., param.: predict only the non-parametric update or the parametric update (Alg. Tp: w/o a, wt does not predict a or w resp.
network (GNN, ②) for
w/o learn
w/o
same network
only non-param
only
w/o
w/o
DOGE
DDGE-M
(L)
GNN
param.
(4)
21
0.42
0.95
2.3
0.7
0.36
0.35
0.33
0.19
(f)
18912
48440
484444
48476
48444
484439
48439
48439
48436
[ss] (J)
61
29
24
51
74
30
30
17
21
without requiring backpropagation through Alg. [ We also try learning subset of parameters i.e., not predicting averaging weights a or damping factors w. Lastly, we report results of DOGE-M which uses recurrent connections. The results
258
257
Table
258
Firstly, from our ablation study we observe that learning even one of the two types of updates i.c., non-pane con-parametric parametric already gives better results than the non-learned solver [.]. This is because non-parne con-aaraettrcc update can help in escaping fixed-points of [ when they occur and the parametric update help Alg. in avoiding such fixed-points. Combining both of these strategies further improves the results. Secondly, we observe that performing message passing with GNN gives improvement over only using the predictor 4. Thirdly, find using separate networks for early and late stage optimization gives better performance than using the same network for all stages. Lastly, using recurrent connections gives the best performance.
280
262
264
285
286
4.4
Results
287
Convergence plots of relative dual gaps change w.r.t wall clock times are given in Figure 2 Rest of the evaluation metrics are reported in Table For further details we refer to the Appendix.
268
Discussion As compared to the non-learned baseline FastDOG reach order of magnitude
270
more accurate relaxation solutions, almost closing the gap to optimum as computed by Gurobi We retain high speed afforded by exploiting GPU parallelism. Interestingly,
can often outperform FastDOG also in the early stage where optimization is easy. Our LSTT version DOGE-M has shown improved performance than the non-LSTTM version. Especially it shows much improvement the most difficult QAPLib dataset. On QAPLib Gurobi does not converge on instances with more than
272
274
Table 3: Results comparison on all datasets where the values are averaged within dataset. Numbers in bold highlight the best performance.
Cell tracking
Graph matching
Independent set
QAPLib
E(x10*)
t[s]
gr
E(x10")
[[s]
E(x10*)
t[s]
gr
E(x10")
f
Gurobi
23
18
3.852
809
9
4,8433
278
14
-2.4557
522
3472
0.9
2618
FastD0G
7
-3.80 -3.863
1005
21
-4.8912
61
42
-2.4913
9
276
5.7
1680
DOGE
2.4
-3.854
1015
0.3
-48439
17
0.3
-2.4460
8
320
12.1
720
DOGE-M
2.1
-3.854
730
0.2
-4.8436
21
0.2
-24459
131
14.5
861

---

Gurobi
FastDOG
DOGE
DOGE-M MM
10P
Relattve daal gap
10-1
10-2
10
10
10
10a
10
10
10
(a) Cell tracking
(b) Gruph matching
10P
10"
Relative dual gap
10-1
10
10-2
10-5
10
10-1
10P
10'
10
10
10
10a
time
(c) Independent set
(d) QAPLib
Figure 2: Convergence plots for g(t) defined in 66) the relative dual gap the optimum (or maximum suboptimal objective among all methods) of the relaxation (D) Both axes are logarithmic.
40 nodes within the time limit of one hour. We show convergence plots for smaller instances in the Appendix. The difference to Gurobi is most pronounced w.r.t. anytime performance measured by gr. since our solver reaches good solutions relatively early.
276
278
While our approach gives solutions of high accuracy for the presented datasets, we have also tried approach other datasets (small cell tracking instances, MRFs for protein folding [27] and shape matching 52)) where we were not able to obtain significant improvements w.r.t. the non-learned baseline []]. For small cell tracking instances FastDOG already found the optimum in a moderate number of iterations, making it hard to beat. On shape matching and protein folding the parallelization of FastDOG did not bring enough speed-upe ups due few large subproblems resulting in sequential bottlenecks. This limited the number of training iterations we could perform within a reasonable time.
Limitations
280
282
284
285
have set some hyperparameters in a dataset-dependent way. This was partly necessitated due 286
to problem sizes e.g., training on long time horizons was not possible with very large instances. Moreover, these instances only permitted a limited number parameters in our neural networks.
288
Conclusion
289
We have proposed a learning approach for solving relaxations to combinatorial optimization prob- lems by backpropagating through and learning parameters for the non-learned baseline [Н. We demonstrated its potential in obtaining close optimal solutions faster than with traditional methods.
291
293
Our work raises interesting follow-up questions: (i) Contrary many approaches for backpropagation which replace non-smooth operations with smoothed variants (e.g. (3] we directly compute (sub-) gradients for the non-smooth solver updates. Can smoothing of the solver help obtain a better backpropagated supervision? (ii) We argue that predicting good update steps for our solver is in itself an interesting and challenging problem
294
295
297
GNNs. We hope that our work can become a testbed for GNN architectures. (iii) There are few desiderata for future learned solvers, including training universal models that generalize across different problem classes. Possibly more powerful GNNs and more involved training regimes needed for this.
299

---

References
301
302
Ahmed Abbas and Paul Swoboda. FastDOG: Fast discrete optimization GPU. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, 2022.
303
304
[2]
Ahmed Abbas and Paul Swoboda. RAMA: A Rapid Multicut Algorithm on GPU. In Proceedings of the JEEE Conference on Computer Vision and Pattern Recognition, 2022.
305
306
[3] Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingfor,, and Nando De Freitas. Learning learn by gradient descent by gradient descent. Advances neural information processing systems, 29, 2016.
308
309
[4] MOSEK ApS. 9.0. 9.0.105,20 2022.
310
[5] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv: 1607.064000 2016.
arXiv preprint
312
[6] Yoshua Bengio. Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodooogical tour d' d'horizon. European Journal of Operational Research, 290(2):405 2021.
313
314
[7]
Timo Berthold. Measuring the impact of primal heuristics. Oper. Res. Lett., 41(6):61 1-614, nov 2013.
315
[8] Rainer E Burkard, Stefan E Karisch, and Franz Rendl. QAPLIB-a quadratic assignment problem library. Journal of Global optimization, (0(4):391-400) 1997.
318
[9] Chris Cameron, Rex Chen, Jason Hartford, and Kevin Leyton- Browon. Predicting Propositionnl Satisfiability via End-to-End Learning. Proceedings of the AAAI Conference Artificial Intelligence, 34(04):3324-331,, Apr. 2020.
318
319
320
[10] Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković, Combinatorial optimization and reasoning with graph neural networks. arXiv preprint arXiv:2102.0960 2021.
321
323
[11] Quentin Cappart, Emmanuel Goutierre, David Bergman, and Louis-Martin Rousseau. Improving optimiza- tion bounds using machine learning: Decision diagrams meet deep reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1443-1451, 2019.
324
325
326
[12] Yunjin Chen and Thomas Pock. Trainable nonlinear reaction diffusion: A flexible framework for fast and effective image restoration. IEEE Transactions Pattern Analysis and Machine Intelligence, 19(5) 1272, 2017.
328
329
[13] Cplex, IBM ILOG. CPLEX Optimization Studio 12.10, 2019.
330
[14] Jian-Ya Ding. Chao Zhang, Lei Shen, Shengyin Li, Bing Wang. Yinghui Xu, and Le Song. Accelerating primal solution findings for mixed integer programs based on solution prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 1452- 1459, 2020.
331
338
[15] William Falcon and The PyTorch Lightning team. PyTorch Lightning, 3 2019.
334
[16] Mathhas Fey and Jan E. Lenssen. Fast graph representation learning with Py Torch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
335
336
[17] FICO. FICO Xpress Optimization Suite, 2022.
337
[18] Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, Gregor Hendel, Christopher Hojny, Thorsten Koch, Pierre Bodic, Stephen Maher, Frederic Matter, Matthias Miltenberger, Erik Mühmer, Benjamin Müller, Mare Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Christine Tawfik, Stefan Vigerske, Fabian Wegscheider, Dieter Weninger, and Jakob Witzig. The SCIP Optimization Suite 7.0. Technical Report 20-10 10, ZIB, Takustr. 7, 14195 Berlin, 2020.
339
340
341
[19] Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. arXiv preprint arXiv: 1906:.1900002999 2019.
344
345
[20] F.A. Gers, J. Schmidhuber, and F. Cummins. Learning to forget: continual prediction with LSTM. In 1999 Ninth International Conference on Artificial Neural Networks ICANN 99, (Conf. Publ, No. 470), volume 2, pages 850-855 vol.2, 1999.
348
10

---

348
[21] Karol Gregor and Yann LeCun. Learning fast approximations of sparse coding. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML' 10, page 399-406. Madison, WI, USA, 2010. Omnipress.
350
351
[22] Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. Advances in neural information processing systems, 33:18087-18097, 2020.
352
353
[23] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2021.
354
[24] Stefan Haller, Mangal Prakash, Lisa Hutschenreiter Tobias Pietzsch, Carsten Rother. Florian Jug, Paul Swoboda, and Bogdan Savchynskyy. A primal-dual solver for large-scale tracking- laongg-byasste by-assignment. In AISTATS, 2020.
356
357
[25] Jared Hoherock and Nathan Bell. Thrust: A parallel template library, 2010. Version 1.7.0.
358
[26] Zeren Huang, Kerong Wang, Furui Liu, Hui-Ling Zhen, Weinan Zhang, Mingxuan Yuan, Jianye Hao, Yong Yu, and Jun Wang. Learning to select cuts for efficient mixed-integer programming. Pattern Recognition, 108353,,,, 2022.
359
360
[27] Ariel Jaimovich, Gal Elidan, Hanah Margalit, and Nir Friedman. Towards integrated protein protein interaction network: relational markov network approach. Journal of Computational Biology, 13(2):155- 164, 2006.
382
363
364
[28]
Wenzel Jakob, Jason Rhinelander, and Dean Moldovan. pybindll Seemlles operability between C++1l and Python, 2017. http://ggthubb.oo/yyybn///////
385
366
[29] Dagmar Kainmueller, Florian Jug, Carsten Rother, and Gene Myers. Active graph matching for automatic joint segmentation and annotation of C. elegans. International Conference on Medical Image Computing and Computer- Assisted Intervention. pages 81-88. Springer, 2014.
388
369
[30] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint urXiv:1412.6000 2014.
370
371
[31] Hendrik Lange and Paul Swoboda. Efficient message passing for 0-1 ILPs with binary decision diagrams. In International Conference on Machine Learning, pages 6000 6010. PMLR, 2021.
[32] Fuhui Long, Hanchuan Peng. Xiao Liu, Stuart K Kim, and Eugene Myers. A 3D digital atlas of C. elegans and its application to single-cell analyses. Nature methods, 6(9):667-672, 2009.
374
375
[33] Arthur Mensch and Mathieu Blondel. Differentiable dynamic programming for structured prediction and attention. In International Conference on Machine Learning, pages 3462-3471, PMLR, 2018.
376
377
[34] Vishal Monga, Yuelong Li, and Yonina C. Eldar. Algorithm unrolling: Interpretahle, efficient deep learning for signal and image processing. IEFP Signal Processing Magazine, 38(2):18-44, 2021.
[35] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' DDnogguue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint 2xXiv:2012.13349 2020.
380
381
382
[36]
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
383
[37] NVIDIA, Péter Vingelmann, and Frank H.P. Fitzck. CUDA, release: 11.2, 2021.
[38] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, High-Performance Deep Learning I Library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d. Alché-Bue, F. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8025-8035. Curran Associates, Inc., 2019.
386
387
388
389
[39] Antoine Prouvost, Justin Dumouchelle, Lara Scavuzzo, Maxime Gasse, Didier Chételat, and Andrea Lodi. Ecole: A Gim-like Library for Machine Learning in Combinatorial Optimization Solvers. In Learning Meets Combinatorial Algorithums at NewrIPS2020. 2020.
392
393
394
[40] Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang. Leonardo de Moura, and David L Dill. Learning SAT solver from single-bit bit supervision. arXiv preprint arXiv:1802.03683 2018.
11

---

396
[41] Alexander Shekhovtsov, Christian Reinbacher, Gottfried Graber, and Thomas Pock. Solving dense image matching in real-time using discrete-come sascrete-contiuuuss optimization. In Proceedings the 21st Computer Vision Winter Workshop (CVWW), page 13, 2016.
396
399
[42] Yunsheng Shi, Zhengjie Huang. Shikun Feng. Hui Zhong. Weajing Wang, and Yu Sun. Masked label prediction: Unified message passing model for semi-supervised classification. In Zhi-Hua Zhou, editor, Proceedings the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 1548-1554, International Joint Conferenees on Artificial Intelligence Organization, 2021. Main Track.
400
402
403
[43] Nicolas Sonnerat, Pengming Wang, Ira Ktena, Sergey Bartunov, and Vinod Nair. Learning a large neighborhood search algorithm for mixed integer programs. arXiv preprint arXiv: 2021.
404
[44] Paul Swoboda, Andrea Hornkkova, Paul Roetzer, and Ahmed Abbas. Structured prediction problem archive. arXiv preprint arXiv:2202.03577 2022.
406
407
[45] Siddharth Tourani, Alexander Shekhovtsov, Carsten Rother, and Bogdan Savchynskyy. MPLP++: Fast, parallel dual block-coordinate ascent for dense graphical models. In Proceedings of the European Conference on Computer Vision (ECCV), pages 251-267, 2018.
408
410
[46] Mark Turner, Thorsten Koch, Felipe Serrano, and Michael Winkler. Adaptive cut selection in mixed-integer linear programming. arXiv preprini arXiv:2202. 2022.
411
412
[47] Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe Graph Neural Networks for Maximum Constraint Satisfaction. Frontiers Artificial Intelligence, 2021.
414
[48] Vladimír Ulman, Martin Maška, Klas EG Magnusson, Olaf Ronneberger, Carsten Haubold, Nathalic Harder, Pavel Matula, Petr Matula, David Svoboda, Miroslav Radojevic, et al. An objective comparison of cell-tracking algorithms. Nature methods, 14(12): 141-11522 2017.
415
416
[49] Vibhav Vineet and PJ Narayanam. CUDA cuts: Fast graph cuts the GPU. 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, pages 1-8. IEEE, 2008
418
419
[50] Tomas Werner. A linear programming approach to max-sum problem: A review. IEEE transactions on pattern analysis and machine intelligence, 29(7): (9(7):1665-11 165-1179, 2007.
[51] Thomas Windheuser, Ulrich Schlickewei, Frank R Schmidt, Daniel Cremers. Geometrically consistent clastic matching of 3d shapes: A linear programming solution. In 2011 International Conference on Computer Vision, pages 234-2141. IEEE, 2011.
422
423
[52] Thomas Windheuser, Ulrich Schlickwei. Frank R Schimdt, and Daniel Cremers. Large-scale integer linear programming orientation preserving 3d shape matching. In Computer Graphics Forum, volume 30, pages 1471-1480, Wiley Online Library, 2011.
425
426
427
[53] Jiadong Wu, Zhengyu He, and Bo Hong. Chapter 5 efficient CUDA algorithms for the maximum network flow problem. In Wen mei W. Hwu, editor, GPU Computing Gems Jade Edition, Applications of GPU Computing Series, pages 55-66. Morgan Kaufmann, Boston, 2012.
429
430
[54] Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Learning large neighborhood search policy for integer programming. Advances in Neural Information Processing Systems, 34, 2021.
[55] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. KeuroL.HH Combining Deep Learning Model with Lin Lin- Kernighan Helsgaun Heuristic for Solving the Traveling Salesman Problem. Advances Neural Information Processing Systems, 34, 2021.
433
434
435
[56] Zhiwei Xu, Thalaiyasingam Ajanthan, and Richard Hartley. Fast and differentiable message passing on pairwise markov random fields. In Proceedings of the Asian Conference Computer Vision, 2020.
437
[57] Yan Yang. Jian Sun, Huibin Li, Zongben ADMM-CSNet. A Deep Learning Approach for Image Compressive Sensing. IEEE Trunsactions on Paltern Analysis and Machine Intelligence, 42(3):521-533 2020.
438
439
12

---

Checklist
440
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
443
contributions and scope? [Yes]
444
(b) Did you descrihe the limitations of your work? [Yes]
445
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We only solve ILP relaxations fast.
446
447
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
450
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
451
(b) Did you include complete proofs of all theoretical results? [Yes] Provided in the Appendix.
452
453
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi-
455
mental results (either in the supplemental material or as a URL)? [No] Will be provided after acceptance
457
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] Yes
458
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No] Due to lack of computational resources we do not report error bars. However we do report results on different variants of our method in Ablation study. The random seed is fixed to same value of 1 for all experiments on all datasets. (d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
460
462
463
464
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
486
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material URL? [No]
489
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
470
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
472
473
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
475
478
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
477
478
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "bbZtrYMvzVW", "reviewer": "Reviewer_ehgi", "summary": "Authors propose an extension of the work A.Abbas and P.Swoboda FasdDOG, 2022. New algorithm includes graph network, which allows to learn parameters for non-parametric update and parametric step of FastDOG, 2022. ", "questions": "1. How the neural network is trained? During the optimization process, or separately? \n2. For me it is unclear, why in Table 1 training time is in hours and significantly large compared to Figure 2.\n3. If training and performing optimization are separate processes, training time should be included in Figure 2. \n4. For table 2 it is also interesting to see the comparison in the number of iterations to understand the complexity of one iteration\n5. Line 246. As for me, it is unfair to fix parameters in Alg. 1 for the CT dataset. It creates a fake impression of the proposed approach.", "limitations": "-", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Modification of FastDOG algorithm, which allows for:\n    - graph NN for learning parameters\n    - GPU parallelization \n    - non-parametric step\n\nWeaknesses:\n1. The resulting algorithm includes a non-parametric step, but there are no theoretical guarantees for the non-parametric step. \n2. Experiments part seems to be a bit unclear for me. Questions are listed in the corresponding section.\n3. Experiments show that on 3 out of 4 datasets Gurobi shows better results and on two of them Gurobi does it in approximately the same time. \n4. The code is not attached. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UGe4d01mfCp", "reviewer": "Reviewer_jrD7", "summary": "This paper proposes a novel framework to speed up solving ILP problems through tuning parameters of Parallel Deferred Min-Marginal Averaging algorithm. This tuning is based on the gradients of the loss function w.r.t to these parameters, so the ILP solver is represented as a neural network that can be optimized with gradient-based optimization method. The los function here is explicit dual objective function. The parameters update preserves their feasibility and non-decrease of the lower-bound. Moreover, to prevent stuck in fixed point, non-parametric update step is also proposed and separate model to generate it is trained. The presented method is evaluated in four classes of combinatorial problems, shows faster convergence than Gurobi solver and establishes smaller relative duality gap.", "questions": "Please comment the following remarks and questions:\n1) In line 34, authors claim that simplex or interior-point methods are not GPU friendly, however, they consist of series of linear algebra operations, that can be speed up due to GPU architectures e.g. matrix multiplication in dense layers of neural networks is faster on GPU rather than on CPU. Please, provide more detailed explanation of this point. \n2) What is the motivation for forward and backward iterations over blocks $B_1,\\ldots, B_u$ in algorithm 1?\n3) Please provide more details about computing subgradients in eq 23 from Appendix. Since this is the single non-trivial operation in the differentiating of the considered method (others operations are just summation and subtraction), its detailed description is important for understanding the correctness of the proposed approach.\n4) Alg 2 solves two optimization problems (for $\\beta = 0$ and $\\beta = 1$), so it is not clear the difference with the naive implementation. Please, provide more details or explicitly present the naive form and highlight the difference.\n5) Please provide detailed description of datasets that are used in generating of Figure 2. Do these plots correspond to a picked instance of the corresponding problem class? Or some average over all considered instances are made? \n6) What solver do authors use inside the proposed framework to solve problems in line 10, Alg 1 and in line 4, Alg 2?\n7) Please explicitly describe how to transform standard constraints like $Ax \\leq b$ to the form in problem (BP) ?\n8) Please explicitly state and describe decreasing of what quantities can explain the observed speed up. Are they the overall number of iterations, acceleration of solving intermediate optimization problems with GPU, or anything else? Such comparison with other state-of-the-art methods helps to place the proposed framework in the proper context and improve understanding of the reasons for the observed gain. If such comparison is not possible for Gurobi since authors do not have access to its detailed statistics, it is possible for FastDog, which is non-differentiable version of the proposed approach with fixed parameters $\\omega_{ij}$ and $\\alpha_{ij}$.\n9) I assume that in line 123 $\\omega$ should be replaced with $\\omega_{ij}$ according to the line 10 in Alg. 1 ", "limitations": "The authors explicitly state the problems where the proposed framework does not show improvement and discuss the possible reasons for that.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) extensive computational experiments for evaluation of the proposed method\n2) the novel technique for differentiating optimization methods w.r.t. its parameters\n3) recipes how to escape from the fixed points\n4) unsupervised loss function eliminates any data preparation stage\n\nWeaknesses:\n1) hand-crafted features for GNN requires some approach to encode current state of Alg 1 in automatic way or some theory that explains the sufficiency of the presented set of features\n2) it remains unclear why such complicated procedure that computes gradients, updates parameters of optimizer in two-ways (parametric and non-parametric) and requires additional memory to store parameters of neural networks is still faster than the state-of-the-art solvers like Gurobi.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IFpEq1n5Bj", "reviewer": "Reviewer_TgLG", "summary": "The authors present DOGE, a learning-based method to solve relaxations to integer programs that exploits GPU parallelism. \nSpecifically, DOGE builds on a method based on Lagrangian decomposition, FastDOG, and proposes to improve its update step either by optimizing over its parameters, or by learning the update direction via a GNN.\nDOGE is shown to improve on FastDOG on 4 benchmarks.", "questions": "- Could the authors include the omitted negative results mentioned in lines 278-285?", "limitations": "The authors adequately and honestly address the limitations of their work.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and easy to follow. While the results appear to be convincing on the selected benchmarks, DOGE is an incremental improvement on FastDOG, which introduced the GPU-friendly dual formulation. I believe the originality of DOGE to be limited as it only proposes to learn the update steps of FastDOG, while keeping the same formulation. Given the extent of the improvement over FastDOG over the selected benchmarks, and lack thereof in the experiments mentioned in lines 278-285, I am not sure that the cost associated to training pays off in this context.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject