Geometric Algorithms for Neural Combinatorial Optimization with Constraints
Authors: Nikolaos Karalias
Akbar Rafiey
Yifei Xu
Zhishang Luo
Behrooz Tahmasebi
Connie Jiang
Stefanie Jegelka
Venue: NeurIPS 2025 poster ()
Keywords: self-supervised learning
combinatorial optimization
learning with discrete constraints
algorithmic reasoning
Primary area: general_machine_learning
TL;DR: We present an end-to-end framework for self supervised combinatorial optimization under various constraints (cardinality, matroid, independent set, etc.).

Abstract: Self-Supervised Learning (SSL) for Combinatorial Optimization (CO) is an emerging paradigm for solving combinatorial problems using neural networks. In this paper, we address a central challenge of SSL for CO: solving problems with discrete constraints. We design an end-to-end differentiable framework that enables us to solve discrete constrained optimization problems with neural networks.  Concretely, we leverage algorithmic techniques from the literature on convex geometry and Carathéodory's theorem to decompose neural network outputs into convex combinations of polytope corners that correspond to feasible sets. This decomposition-based approach enables self-supervised training but also ensures efficient quality-preserving rounding of the neural net output into feasible solutions. Extensive experiments in cardinality-constrained optimization show that our approach can consistently outperform neural baselines. We further provide worked-out examples of how our method can be applied beyond cardinality-constrained problems to a diverse set of combinatorial optimization tasks, including finding independent sets in graphs, and solving matroid-constrained problems.

Geometric Algorithms for Neural Combinatorial Optimization with Constraints
Nikolaos Karalias" MIT
Akbar Rafiey" NYU ar95300nyu.com edu
Yifei Xu NYU
Zhishang Luo UCSD zluo@ucsd. edu
stalence@mit.edu
yx35900nyu.edu
Behrooz Tahmasebi MIT bzt@mit. edu
Connie Jiang MIT conniej eaaiiee@mmi..mm edu
Stefanie Jegelka TUM and MIT stefjefmit edu
Abstract
Self-Supervised Learning (SSL) for Combinatorial Optimization (CO) is an emerg- ing paradigm for solving combinatorial problems using neural networks. In this paper, we address a central challenge SSL for CO: solving problems with discrete constraints. We design end-to-end differentiable framework that en- ables us to solve discrete constrained optimization problems with neural networks. Concretely, leverage algorithmic techniques from the literature convex ge- ometry and Carathéodory's theorem to decompose neural network outputs into convex combinations of polytope corners that correspond to feasible sets. This decomposition-bass approach enables self-supervised training but also ensures efficient quality-preservee rounding of the neural output into feasible solu- tions. Extensive experiments in cardinality-constral approach can consistently outperform neural baselines. We further provide worked- out examples of how our method can be applied beyond cardinality pardinalty-constrainne constraiied problems diverse set of combinatorial optimization tasks, including finding independent sets in graphs, and solving cetrooddcoontraineed problems.
optimization show that our
Introduction
Combinatorial Optimization (CO) encompasses broad category of optimization problems where the objective is to find configuration of discrete objects that satisfies specific constraints and is optimal
given prescribed criterion. It has wide range of real-world applications [64, 58, 31, 7, 94, 73] while also being of central importance in complexity theory and algorithm design. These problems often non-convex, and solving them involves exploring large-scale discrete combinatorial spaces of configurations. To that end, neural networks have emerged as a powerful tool for designing CO algorithms as they can learn to exploit patterns real-world data and discover high-quality solutions efficiently. A compelling proposal in that direction is celf-supervised CO because it eschews the need to acquire labeled data, which can be computationally expensive for those problems. This usually involves training a neural network to produce solutions to input instances by minimizing a continuous proxy for the discrete objective of the problem [35, 84, 36, 90]. While the efficiency and scalability of this approach are appealing, it also harbors significant challenges.
Enforcing constraints the output of the neural network one of the primary obstacles. When training, this often done by including weighted term in the loss function that penalizes solutions that do not comply with the constraints. There are key considerations when doing this. Having
Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Trairing Data
CO Network
Combi natiraal Constrait
&.e. Diferantiable Decom Decorpostion postion
Supervised Loes
Constraint
Σ Pg(01g
FLO
Convex hull of feasibll salutins
(p(N)
Problem Enceder
OpCK)
Forward Pase
Network
OF
=f(g)
Combinstoris Constraint Layer
Decompostion
Pick best set: argmax f(l)) SU/0
Σ Pg000g
Rounding Guarantes: Alg F0O
Convex hall of fonsibla solutions
Problem Encadier
Network
Figure I: Overview of our framework. During training (top), the model learns to output point in the
convex hull of feasible solutions. A self-supervised extension loss computed by decomposing this point and evaluating the objective, which is then used to backpropagate, During inference (bottom), the model outputs relaxed solution, which decomposed and the best feasible set is selected with rounding guarantee.
access to differentiable function that encodes constraint violation for the discrete problem, and carefully tuning its contribution to the overall loss. Furthermore, at inference, it is important to guarantee that the output of the neural network is discrete and it complies with the constraints. In practice, this usually achieved with an algorithm that rounds the continuous output of the neural network feasible discrete solution. Such algorithms often heuristics and treat inference differently from training which may hurt performance. Despite recent developments that have enabled tackling new combinatorial problems in the self supervued setting, combining loss function design and rounding in a coherent fashion can still be highly nontrivial.
In this work, building on ideas from the literature on self-superviser CO and techniques from geometric algorithms and combinatorial optimization, we propose an approach to loss function design that seamlessly integrates training and inference while also providing rounding guarantee. The main idea to learn to map input instances to distributions of feasible solutions that maximize (or minimize resp.) the objective. Given input instance, we use the neural network to predict continuous vector in the convex hull of feasible solutions. Using an iterative algorithm, this vector is decomposed into distribution of discrete feasible sets. This algorithm draws from the literature Carathéodory's 's theorem [13] to express points in the interior of a convex polytope as a sparse convex combination of the corners of the polytope. This decomposition yields distribution that allows to tractably calculate the expected value the discrete objective. We use this expectation as our loss and minimize it with neural net and standard automatic differentiation in a self-supervised fashion. By backpropagating derivatives from this expectation, the neural network learns to generate outputs in the feasible set that optimize the expected objective. At inference time, the iterative algorithm generates candidate feasible solutions to the problem. The pipeline is summarized in Figure 1.
Our contribution. Our method generalizes previous work, and offers strong empirical benefits in efficiency and performance on large-scale CO instances. Our contributions can be summarized as follows:
We use a class of geometric decomposition algorithms to design end-to-end learning pipelines for constrained neural CO. Our main result establishes the applicability of our method to any problem whose feasible set polytope admits fast linear optimization oracle.
Our geometric algorithms effectively tackle both the challenge of loss function design for training with constraints, and the challenge of rounding neural network outputs at inference.

---

We show strong results in cardinality constrained CO on acge-scale instances with hundreds of thousands of nodes, often surpassing previous neural baselines and heuristics.
We conduct ablation studies to test the effectiveness of optimizing the extension with gradient descent and the contribution of the model in the overall performance.
2 Related work
Self-Supervised CO and continuous extensions. Our work follows long line of work on unsu- pervised CO [1, 2, 35, 84, 36, 82, 87, 30, 72, 24, 63, 78, 43, 60, 90]. Crucial components of those pipelines include the choice of model, the use of specific input features (positional encodings), the loss function, and the rounding algorithm. There has been extensive research on neural net architectures for combinatorial problems [57, 85, 74, 93] and the role of input features for well known classes of models [91, 53, 38). Our primary focus will be on loss function design and rounding. We build on previous work that proposed using continuous extensions of discrete functions as losses for neural CO [36. Following this blueprint, bespoke extensions have been used for learning on permutations [62]. hierarchical clustering [43] and interpretable graph learning [16]. However, there is no general extension design paradigm that can accommodate different constraints. We address this issue by proposing a template for extension design and show how it enables building the constraints into the distribution. This streamlines the process of building extensions and dispenses with the need to tune constraint terms in the loss function that is present in other approaches to supervipd CO.
Loss function design and enforcing constraints. The design of specific loss functions in self- supervised CO to enable smoother optimization, integration with different powerful architectures, and/or better rounding has been studied over the past few years. A common approach to adopt probabilistic perspective and parametrize a distribution of outputs with neural network that learns to optimize the expected cost and the probability of constraint violation [60, 87, 36, 72, 62]. Deriving and/or computing those expectations and probability terms for more complex problems can be difficult, which motivated the work by [10] that provides derivations and fast rounding techniques for cases such spanning trees and cardinality constraints. In our work, the constraints built into the distribution and the loss only has to handle the objective function. is challenging to craft such losses which has led to the development of techniques that improve training dynamics via annealed training [82, 33]. Other approaches to loss function design leverage ideas from physics [78, 79], and semidefinite programming [93, 32). Those cases also involve tunable constraint terms. Another major consideration is that of enforcing constraints on the outputs of the neural networks. Techniques in the literature typically involve calculating the projection of the neural net output onto the feasible set. This has been done for cardinality constraints using ideas from the theory of optimal transport [89], and general linear constraints with gradient-based techniques [18, 95]. In the continuous (potentially non-convex) optimization setting, several projection techniques have also been developed [51, 52, 50, 48].
Convex geometry and learning over polytopes. Our approach relies on fundamental results from convex geometry and geometric algorithms. Specifically, the Carathéodory Theorem states that any point in a polytope P _ IRd can be expressed as a convex combination of at most d + 1 points. The constructive versions of this result [25] have been adapted to yield efficient algorithms in polytopes for ranking [42] and scheduling problems [29, 21, 8). Approximate versions of the decomposition have been developed that do not explicitly depend on the ambient dimension d [4] and admit efficient algorithms with fast convergence rates [59, 17J. In the context of machine learning, polyhedral methods have been used extensively to impose constraints on the outputs of models for generative modelling [22], for learning with end-to-end differentiable sampling from exponential families using perturb-and and-map map techniques [67], for applications to differentiable sorting [6. 71] and learning to optimize over permutations [26, 56, 62]. For additional discussion, please refer to the appendix.
3 Problem formulation and learning setup
Let V = (ui,...., Un) be a set of variables, each assigned a value from a discrete domain D (1....,d) d). A combinatorial optimization problem consists of a universe of instances T, where each instance T E T can be represented by a tuple T = (V, D, f). The set C C D defines the feasible solutions to the instance. The real-valued function f D - IR is called the objective function.
3

---

The problem is then to find an optimal feasible vector x", i.e., to find a feasible vector x E D that maximizes the objective function f:
max fxx, s.t. XEC.
In this paper, we focus on CO problems with Boolean domain, i.e., D {0, and C C {0, 1J" This domain choice corresponds to combinatorial optimization problems that involve set functions, i..,, x indicates a subset S Ç V of ground set V = [ui,..., Fn of elements and x; = 1 if element i is in the subset, and f maps each subset to real number. The subsets can be, for instance, nodes or edges in a graph, and are central to many problems in applied mathematics and operations research [9]. The set C E {0, 1) includes all subsets of V that obey the constraints of the problem. Each subset S is identified with its indicator vector 1ş E {0, 1 1 and we use f(S) and f(1s) interchangeably throughout this paper. The objective function is the set function f: {0, ) -> R. The goal is to select an optimal feasible subset so Equation (I) takes the form maxsEc f(S).
Background polyhedral geometry. Define the encoding length of number as the length of the binary string representing the number. The encoding length of an inequality a aTx x S b, is the sum of encoding lengths of the entries of the vectors and b. Let P C R" be a polyhedron and let y be a positive integer. We say that P has facet-complexity at most if there exists a system of linear inequalities with rational coefficients whose solution set is P. and such that the encoding length of each inequality in the system is at most p. A well-described polytope is a triple (P; n, sp) where P S IR" is a polytope with facet-complexity most yp The strong optimization problem for a given rational vector x E Q and any well desc-dese (P; n, (p)
max x. PE
A strong optimization oracle returns maximizer c* for (2). Polytopes can be described as convex hulls of finitely many vectors or as systems of linear inequalities. Even though a description may require exponentially many vectors or inequalities, the polytope may admit fast optimization oracle. This is the case for submodular polyhedra [3] or the matching polytope [77, Chapters 25, 26].
Self-Supervised CO. Given a problem instance T and input features Zr E Raxd, we use neural network NN,, which we will often refer to as the encoder network, to map the instance data to an output prediction x E R by computing x = NNg (Zr: T). For example, the input instance could be a graph, the input features could be positional encodings for the graph, and the neural net a Multi-Layer Perceptron (MLP). The output may not correspond to a discrete feasible point. In those cases, a rounding algorithm will be used to map x to a feasible indicator vector of set. The goal is for the neural net to learn predict the optimal solution x". In self seff-supervised CO. this is done by training NN, on a collection of instances Ti, T,..... Tm- The neural net minimizes the problem-specific loss function LT computed for each instance L, TT)) and averaged over a batch (or the entire training set). Since there are no labels, how the loss function is designed to fit the constraints of the problem is of critical importance. At inference time, test instance is processed through the neural network to obtain a prediction. At this step, rounding heuristics are typically used to ensure that the solution is feasible and discrete. It should be noted that, it is possible directly optimize the model with gradient descent on the test instances since no labels are leveraged during training. In this case, the additional computational cost of backpropagation is incurred at inference time.
4 Proposed approach
First, we present an overview of the key components in the pipeline and then we discuss each component in more detail. Our proposed method focuses on the design of (x(x) that is used to train the model. The objective f is a set function with discrete domain and cannot be directly optimized. Following the literature, we construct a continuous extension of f, denoted by F(x): (0, 1|" - R. and use it as our loss function, i.e. L (x) = Fxx). The extension is defined as
F(x) == ESwDe(<) (S)).
where Dx(x) is a distribution parametrized by the output of the neural network and S E C for all S in the support of De(x). The key challenge lies how to tractably construct and parameterize such distribution on feasible sets in way that enables end-to-end learning. We achieve this using an

---

iterative algorithm that ensures De(x) is supported on (n) feasible sets and the probability of each set is an a.e. differentiable function of x. This allows us to efficiently compute the exact expectation in Equation (3) and to calculate its derivatives with standard automatic differentiation packages. At inference time, the geometric algorithm can be used as a rounding algorithm for since Dx(x) has a small number of sets in its support. Specifically, we can round x to the best set in the support and obtain a feasible integral solution whose quality is at least as good as F(x).
4.1
A general decomposition algorithm for extension design
For a feasible set C, consider the polytope P(C) = Conv((1s: S C}), i.e., the convex hull of the indicator vectors of the sets in C. Any point E P(C) is convex combination Esec as of feasible solutions from C. In fact, from Carathéodory's theorem we know that this convex combination requires most n 1 points where n. is the ambient dimension of the space. The coefficients of the convex combination can be viewed as the probabilities of distribution Dc(x) and hence x (x) [1s]. If can uniquely and efficiently decompose each point x E P(C) into such a convex combination, we can leverage that distribution to compute the extension in Equation (3). In Algorithm 1, we propose a general template for an iterative algorithm that yields such decompositions and forms the foundation for our approach.
Intuitively, the algorithm decomposes x iteratively by removing corner 1g weighted by suitably chosen coefficient in each iteration. This is done until the coefficients and the corresponding corners can be used reconstruct up some small error c.
Let X E P(C) and X₂- = x. In each iteration f, the algorithm finds feasible solution in C that is both an extremal point of the convex hull and lies in the support of x,. Here by the support
Algorithm 1 General decomposition algorithm
Require: x [0, 1]" in P(C).
1: f- x, +- 0.
of x, we mean supp(x,) := {S E C (i) * O Vi E S), that is all the feasible subsets S E C such that every corresponding entry of x in- dexed by i E S is nonzero. Let this point be 1s, E supp(x,) S {0.1)* 1)". Let a E [0, 1] be the coefficient iteration We express each iterate X as
2:
repeat
3:
1s, f- vertex from P(C) in the support of x,
4: at + g(x,, 1s,)
5:
X1+1 f- (xi az 1s) ) /(1 - ar)
6:
(S.) + a: I 0.)
7:
t ++t+1
8: until || Px, Px, (s.) Sc
9:
return All (Pxx (8t), 1s,)) pairs.
x, = at ss. + - at)
(4)
where a = g(x,, 1s,) is a function of x, and 1s., chosen such that X remains in P(C). We can recursively apply the same process to xx+1 until x has been decomposed into a convex combination of feasible sets. After the algorithm terminates,
can obtain distribution Dc(x) which is completely characterized by the sets S, and probabilities Px, (S.) de I (1 a;) of the decomposition. Determining the specific form of steps 3 and 4 in way that yields a polynomial time algorithm that usable in an end-to-end learning setting is a non-trivitt task that depends on the polytope. We prove the following theorem which relies on a constructive version of the Carathéodory theorem, also known in the literature as the GL.S method (from method establishes a decomposition for a large class of polytopes. Our result builds on top of the GLS method to show how this decomposition is also almost everywhere differentiable with respect to X.
-oveel-o-oov-ivvveeeee [29, 42]. The GLSS
Theorem 4.1. There exists a polynomial-ting algorithu that for any well-described polytope P given by a strong optimization oracle, for any rational vector x. finds vertex- probabbroobability pairs (Si), 1s, for f everywhere differentiable functions xf
0, 0.1...., 1 such that x= E Px. (S.)1s, and all px, (Si) are almost
Intuitively, at each iteration the decomposition algorithm leverages the strong optimization oracle to obtain a vertex for minimal face of the polytope that contains the current iterate. This corresponds to step 3 of our algorithm. At step 4, the largest possible a; is chosen that yields a new iterate that remains in the polytope. This means that X(+1 will intersect the boundary of the polytope. At each iteration, the iterate lies on a nower-dimensiont face of the polytope than the previous one, and hence the algorithm terminates in polynomial time, in most I iterations.
End-to-end learning with the decomposition. Drawing insights from the GL.S method, we aim to design& decomposition that can be integrated in gradient-basee based optimization pipelines. Here,
5

---

we summarize the basic requirements for the general decomposition to yield an extension that can be optimized with standard automatic differentiation, which will enable end-to-end learning. To obtain consistent tie breaks at the boundaries for the strong optimization oracle, we adopt a standard lexicographic ordering of the coordinates. This also ensures that the steps of the decomposition are deterministic and that the coefficients of the decomposition are uniquely determined for each point in the polytope. For our approach to be useful for end-to-end learning, we require:
1. A differentiable method that ensures our starting point x lies in the polytope P(C).
2. A routine that efficiently finds a vertex 1s, E P(C) in the support of X
3. An (almost everywhere) differentiable function g 1s,) that yields a valid decomposition.
Satisfying these conditions will allow us to tractably construct a distribution of feasible sets Dc(x), which will enable efficient calculation of the expectation in Equation (3). It also means that we can update the parameters of the neural network that is used to predict x by optimizing the extension via standard automatic differentiation packages. Our proof of Theorem 4.1 establishes that strong optimization oracle is sufficient to handle steps 2 and 3. See Appendix B. 1 and Appendix B.2 for detailed comments on the applicability of the method.
Practical considerations for step 3 and 4. Our GL-S-based construction offers canonical template that can instantiate Algorithm I, but deviating from GLSS can confer additional benefits. For example, g in Step 4 can be chosen so that the next iterate does not intersect lower dimensional face of the polytope. The difference now is that, instead of choosing the maximum coefficient possible, we will rescale it in each step by some fixed constant b E (0, 1]. Termination of the algorithm is ensured by the parameter e in step Algorithm and a lower bound on the minimum value of the coefficient.
Proposition 4.2. Let
de: a 2 l a <
ā.
(5)
at
be the coefficient we pick for step 3 in Algorithm 1. Then the reconstruction error of step 8 Algorithm 1 decays exponentially in k.
This approach allows for controlled approximation of x and the introduction of more vertices into the decomposition which can help exploration when optimizing the extension.
Neural predictions in the feasible set polytope. Suppose our encoder network outputs x E IR.. Since Algorithm 1 requires a point in the polytope x e P(C), we need a way enforce this constraint on the output of our neural network. This type of problem has received significant attention (see Section 2) both the optimization and machine learning communities. Commonly, this can involve projection-based techniques such as Sinkhorn's 's algorithm [80] and its various extensions [88] or other gradient-bar -aaeed approaches [95]. This can be a viable strategy but, depending on the polytope, may be difficult to integrate in differentiable pipeline. We will leverage appropriate but we also introduce a simple efficient alternative. We interpret the neural encoder output as perturbation of an interior point in P(C). More concretely, the neural net predicts perturbation vector z E R" such that x = z + u, where u E R" is an interior point of P(C). While this approach circumvents the need for projection, it requires access to interior point of the polytope. It also requires care so that the perturbed point z + u remains in the polytope. Nonetheless, we show that for several fundamental constraint camilies-includie and the spanning tree base polytope-it is possible to do this efficiently in a differentiable way (e.g.. Proposition 4.4).
coojection-based approach when
cardinality constraints, partition matroids,
Extension function, training, and inference. Once the decomposition algorithm provides Dc(x), we can use it to compute our loss function. For the extension to be well defined, the decomposition needs to deterministically map each point in the polytope to vertex- prrex--probabiliy pairs. This is guaranteed in our constructions. It is also straightforward to compute derivatives of the extension with respect to the neural network parameters. For simplicity, suppose the encoder network, parameterized by weights 6, outputs x E P(C). Then, we have aF aF 0n(x). ax where p(x) is the vector of probabilities returned by Algorithm 1.
ag öp(x) 8x
06

---

The extension F(x) = Be (xntDexxxf)ff [f(S]] Px. Px.
has several desirable properties that have been studied in the literature [36]. Since we are considering convex combinations of the objective over the feasible set, the extreme points are preserved i.e., maxxEP(C) F(x) max SEC J J((S:; moreover we have xrgmaxxeP(e) F(x)= E Conv([1s S E argmaxsee f(S))). The expectation formulation also provides a rounding guarantee. There exists at least one feasible solution S in the decomposition of x such that f(S*) 2 F(x). This property enables fast inference on the output of the encoder network without any degradation in solution quality.
4.2
Case studies
In this section we discuss how the decomposition can be generated for various constraints. We provide detailed treatment of the cardinality constraint build intuition and then discuss additional examples including spanning trees and independent sets. All proofs, additional details and additional experiments can be found in the Appendix.
4.2.1 Cardinality constraint
Here, we focus on combinatorial problems that involve optimizing a set function under an exact cardinality constraint. This setting is sufficiently general to encompass many fundamental and practical combinatorial optimization problems. Formally, let f 2 + IR be a set function that assigns real value to each subset of V {vi :0....... J. For a given positive integer k, the set of feasible solutions is defined as C = (S |S| = k C V}. which includes all subsets of V of size exactly k. The resulting constrained combinatorial optimization problem is:
x <lll).i".lll fxx).
max
(6)
The associated convex polytope, P(C) = Conv([1s : |S] = k)), is the convex hull of Boolean vectors with exactly & ones and n - k zeros and the matroid base polytope corresponding to uniform matroid on n elements of rank k. is known as the (k.n)- hyp-sshpessi and denoted by An, [70].
Designing the decomposition algorithm. For now, we assume that our predictions lic in the polytope of the feasible set, i.e. x E An To construct decomposition, in Algorithm comply with our conditions for efficient end-to-end learning. To obtain a vertex of the polytope in the support of x, for Step 3 in Algorithm 1, set
need to ensure that steps 3 and 4
ss
argmax X, c. cE ||el|i=
For step 4, we use Equation (4) to calculate the largest possible coefficient that keeps the iterate in the polytope. This yields
ar min min (1), max x (1) iES,
(8)
The following result shows that our decomposition algorithm produces valid convex decomposition of points in the hypersimplex and is suitable for end-to-end learning.
Theorem 4.3. For x Da,k, Algorithm with Step 3 according to Equation (7) and Step according to Equation (8), terminates in at most n iterations and returns probability-vereex pairs U(xx (Se), }s)) such that every S, is a set of size l and x E. 1s. Moreover, each Px. (S,) is an a.e. differentiable function of x.
At a high level, the result follows a similar strategy as Theorem 4.1. Our choice of coefficient ensures that the next iterate intersects the boundary of the polytope and lies in a lower-dimensional face. This in turn guarantees that the algorithm terminates in at most n + steps.
Generating neural predictions in the hypersimplex. The last concern address is that of obtaining a vector x E An, in an efficient and differentiable manner. We follow the perturbation strategy that outlined earlier and use the neural network to predict perturbation vector z E [0, 1]" for an interior point. The following result ensures that the perturbed point x remains in the polytope.
Proposition 4.4. Let [0, 1J" and 1 : ....,, &J. Let μ be the mean of z, and be the mean-centered version of v. For = min( k/n (m- R)/n and x = să + we have that x E An,k- I-p
This simple transformation efficient to compute and maintains differentiability of x with respect to the neural network parameters.
7

---

4.2.2 Decomposition for Partition Matroids, Spanning Trees, and Independent Sets
Partition Matroids. We extend our result to general constraints beyond cardinality. Let Vi,..., Ve be disjoint subsets with V = U V. The CO problem is maxe: [()). When e = 1, this reduces to the cardinality case. In step of Algorithm 1, we obtain vertex in the support of x, by setting 1s, = e "lo.)). x, C. Step 4 matches Equation (8). The encoder can similarly be constrained to the polytope, with scaling factor s being handled per partition.
Spanning Trees. Let G (V, E)) be graph with nodes and edges. The CO problem is maxscE.seF where F is the set of full spanning forests of G. The convex hull of feasible sets is the graphical matroid base polytope. In Step 3 of Algorithm 1, we obtain vertex in the support of X₁ by finding a maximum spanning forest. The encoder learns edge weights to perturb the uniform spanning tree distribution, where spectral graph theory.
Kirchhoff''s s Matrix-Ther Theorem [41] and results from
Independent Sets. The maximum independent set problem is an NP-hard problem where the goal is to find the largest subset of nodes in a graph G = (V, E) such that no pair of nodes in S is adjacent. The strong optimization problem for the independent set polytope is NP-Hard. Furthermore, there is no compact description of the polytope so this is a particularly challenging case. We circumvent those difficulties by considering its relaxation, which admits compact description and is known as the fractional stable set polytope [55]. We use a fast gradient-based approach to project to the polytope. Steps 3 and 4 are chosen according to the standard template set by the GLS decomposition.
5 Experiments
5.1 Experimental setup
We consider the Maximum Coverage problem [39], fundamental combinatorial problem with many variants that have been extensively studied. It appears in numerous applications, including document summarization [54] and identifying influential users in social networks [37, 15]. Let U = (eI....,,., be a set of n elements and V = [Ti..... .......... Tn be n subsets of U. Given & I n, the Max Coverage problem asks for & subsets whose union covers the largest number of elements. In the weighted version, each e has a weight, and the goal is to maximize the total weight of covered elements. This problem (e,. TT) E E iff Cj E T, A node u E U is covered by S V if it is adjacent to some vertex in if u is covered by S, and f(S, u) otherwise. The optimization problem is S. Set f(S,u) = maxscvi)sI Enev f(S, u). Next we provide details on the experimental results that are presented in Figure 2 and the code can be found in this link.
be represented
bipartite graph G VU, E), where
Problem Encoder: To encode the bipartite graph, we use three layers of GraphSage [27] followed by a fully-connected layer with our noise perturbation layer to map the output vector to the hypersimplex An,k. We add normalization and residual connections in between the GraphSage layers.
Baselines. We adopt the same baselines as prior work, including: random, which samples k candidates uniformly at random over multiple trials and selects the best within 240 seconds; Greedy algori ahgorithm thm [61] that iteratively adds the element with the largest marginal gain and achieves the well-known (1 ! >-approximation guarantee; Gurobi for exact bised solutions, with time limited to 120 seconds for each graph; CardNN [88] and its variants (with and without test-time optimization, following [10] approach); a naive version of EGN with a naive probabilistic objective construction and iterative rounding [35]; UCOM2 with variants [10]; and Reinforcement Learning (RL) baseline. For the RL bascline, we follow the instructions in [45, 69] to use GraphSage layers [28] as policy network with Actor-Critic [44] algorithm to train the same problem instances. We classify UCOM2 as a non-learning method because their incremental greedy de-randomization, when applied to uniform noise or all-zero input vector, performs as well as or in some cases better than-when applied to the output of their encoder network suggesting that its performance is mostly due to the greedy module.
Dataset and training. We use synthetic graphs for training and real-world graphs for testing. Two k values are chosen per dataset to assess method generalizability. (Due to space constraints, only one value of is shown; the full set is the appendix.) Random graphs: the number in front of "Random" indicates the size of U. Each group contains 100 graphs from either uniform or Pareto
8

---

distribution. Real-world graphs: Built from set systems like Twitch and Railway, each group includes multiple graphs from the same source for broader coverage. Due limited large-scale data, real-world datasets are used only for testing, with training done on synthetic data. We point out that scaling the probability weights in Equation (8) generates diverse decompositions, exposing the model to more sets during training and inference. We use a list of scaling factors to produce these decompositions in parallel. See Appendix C.I for details.
objective (higher is better)
Random 1000,
objective Dhigher is better))
Railway, k- 20
objecttive Dhigher Is better))
Random
objectton Dhigher Is better)
Twitch, 50
40000
20000
5950
30000
35000
5000
Leaming no
20000
20000
s200
20000
$180
12000
23
50
100
125
25
75
100
125
20000
23
50
73
100
23
50
73
inforence time (seconds)
inference time (seconds)
inforence time (seconds)
inforence time (seconds)
objectivv (hightr la better)
Random1000,
objecttive thighter is better)
Railway,
objecttive (higher ts betters
Random500,
objective thigher 15 betters
Twitch,
32000
swop
k0000
50000
Learning TTO
$1000
44000
8430
20000
00
8000
20000
5330
10000
10
15
20
23
30
30
60
20
40
do
60
100
inferance time (seconds)
inference
(seconds)
inferance time (saconds)
inferance time (seconds)
objective (higher to bestert
Random1000,
objjcctive (higher is betteri
k= 20
objective (higher is betteri
Random500, k= 50
ohjecttve (higher 1e betteri
Twitch, 50
22000
are0
45000
80000
10000
22000
5000
44000
40000
20300
2040
42000
20000
Leurning
20000
20000
10000
10000
28000
20
69
73
100
129
23
50
100
20
40
(seconds)
Gurobi (120s) Greedy
Ucom2-lang
CardNN--oTTO-HHN
CardNN-S CardNN-GS CardNN-HGS
Ours-short Ours-medlum
CardNN-noTTO-S
EGN-naive (120s) RL (GNN + Actor-Critic)
Ucom2-short
CardNN-noTTO-GS
Ours-long
Ucom2-medium
Figure 2: Performance comparison of our method against baseline approaches across three eval- uation settings Learning without Test-Time Optimization (TTO), Learning with TTO, and non- learning/traditinnal baselines- on multiple datasets. Metrics used are inference time (lower better) and objective value (higher is better). In the Learning without TTO setting, sistently outperforms all baselines in both inference time and objective value, demonstrating strong learning capability. When extended medium and long versions, our method surpasses most TTO- based baselines across datasets, with the exception of the Twitch dataset. It also outperforms the included the plots due to space
short version con-
greedy algorithm on multiple benchmarks. (Random(240s) constraints. Detailed result numbers can be found in Appendix G.6.)
5.2 Discussion
Learnability results. Our end-to-end pipeline shows a very strong learning ability in comparison to the existing learning baselines. In the setting where no method performs optimization at inference time, the short version of our method already shows strong performance compared baselines. In this variant, we apply our decomposition procedure to the output of the neural encoder and select the best set from the decomposition. Based on the rounding guarantees of our extension, the resulting discrete solution is provably at least good as the encoder's 's output. Compared to other baselines and CardNN -oTTO (across all three variants), our inference method achieves superior efficiency in both runtime and output quality. Note that we do not include the UCOM2 method in this comparison, as falls outside the scope of this setting: more details are provided later in the paper. Regarding the Twitch dataset, although our short method performs significantly better than other approaches this setting, we observe that all learning-baad -baed methods perform poorly overall on this dataset. As mentioned in the introduction, this underperformance is largely attributed to the
existing

---

architecture of the encoder network and the specific characteristics of the data distribution. This highlights a need for further investigation and suggests that adapting the model architecture to better suit such data is an important direction for future work.
Teme Optimization (TTO). In this setting, additional computational time is allowed during inference to improve solution quality. Specifically, we perform a simple optimization procedure: after selecting the best set from the decomposition of the encoder output, we apply local improvement by swapping a few elements with those from other sets in the decomposition 's support. This lightweight optimization step demonstrates that the encoder has successfully learned meaningful structure from the data, as reflected in the quality of the decomposition" 's support. This is the medium um variant of our method. In the long version we moreover perform data augmentation similar to [34]. These procedures yield noticeable improvements on the Random500 and Random100 1000 datasets, and produce reasonably good results on the Railway dataset. On the twitch dataset, the CardNN methods directly optimize the neural network output on the test sample with Adam, therefore overcoming the model architecture problem. For our methods, performance remains poor on the Twitch dataset, consistent with observations discussed earlier.
Comparison with Non-Learning methods. While greedy is an efficient baseline with strong approximation guarantee, our method performs competitively and is capable of outperforming it on datasets like Random500 for larger values of k. We are also able to outperform UCOM in several cases (e.g., Random1000 and Railway), though there are instances where greedy and/or UCOM perform the best, such as the twitch dataset.
Ablation. We conduct an ablation study on the NP-hard problem of finding a cardinalitycconstrained maximum cut. Given a graph G = (V, E), the goal is find a set S of k nodes such that the number of edges with exactly one endpoint in S' is maximized. We compare the following baselines on two datasets and two settings for the value k. Our decomposition- main parts: a NN to predict a point in the polytope, and a loss function to optimize it and aid in learning. To probe the effect of the loss function, we compare the quality of solutions obtained by the decomposition when the input is i) random point projected onto the polytope ti) a random point optimized with Adam on the loss. To probe the effect of the neural network, we test the solutions obtained by the decomposition of the predictions of neural network that has optimized the loss on the same data. Finally, to assess generalization, we compare the decomposed sets obtained from the predictions of neural net that has been trained on separate training set. As a sanity check, we also include greedy algorithm. The table and more details of the experiment are provided in Appendix H. We consistently observe that directly optimizing the extension the test set with Adam significantly improves the objective compared to decomposing a randomly chosen point and reporting the result of its best performing set. Furthermore, the neural net optimized directly on the test set improves consistently over direct optimization with Adam and is competitive with greedy pointing to the benefits of parametrization. Finally, the performance of the SSL approach is close to the competing neural baseline, suggesting that the model generalizes well.
method consists of two
6 Conclusion
We proposed a novel geometric approach to neural combinatorial optimization with constraints that effectively tackles the challenges of loss function design and rounding. Our method achieved strong empirical results against both neural baselines and classical methods, and opens up promising avenues for further research on incorporating classical geometric algorithms into neural net pipelines. It is important to note that the model architecture can play an important role in results; we have not focused on this aspect here but it merits further exploration in future work. Our framework is applicable whenever an oracle for the strong maximization problem exists, but its efficiency will vary based on the polytope. The structure of the polytope influences our ability to obtain interior points, to solve the strong optimization problem, and to compute intersections with its boundary. Nevertheless, we believe that the blueprint described in this work paves the way towards new hybrid algorithms that can effectively tackle complex combinatorial problems.
10

---

7 Acknowledgements
Stefanie Jegelka acknowledges support from NSF AI Institute TILOS and the Alexander von Hum- boldt Foundation. Nikolaos Karalias acknowledges support from the SNSF, in the context of the project "General neural solvers for combinatorial optimization and algorithmic reasoning" (SNSF grant number: P500PT_217999) and from NSF Al Institute TILOS.

---

References
[I] Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. Learning to solve circuit-sat: An unsupervised differentiable approach. In International Conference Learning Representations (ICLR), 2018. 3,
[2] Saced Amizadeh, Sergiy Matusevych, and Markus Weimer. Pdp: A general neural framework for learning constraint satisfaction solvers. arXiv preprint arXiv:1903.019900 2019. 3
[3] Francis Bach al. Learning with submodular functions: A convex optimization perspective. Foundations and Trends0) in Machine Learning, 6(2-3): 145-333 2013. 4
[4] Siddharth Barman. Approximating nash equilibria and dense bipartite subgraphs via ap- proximate version of caratheodory's 's theorem. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (STOC), pages 361-369, 2015.
[5] Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural com- binatorial optimization with reinforcement learning. arXiv preprint arXiv: 1.099999100000... 2016.
18
[6] Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Lean-Philippe Vert, and Francis R Bach. Learning with differentiable pertubed optimizers. In Proceedings of the 34th International Conference on Neural Information Processing Systems (NeurIPS), 2020.
[7] Lucio Bianco, Giovanni Rinaldi, and Antonio Sassano. A combinatorial optimization approach aircraft sequencing problem. Springer, 1987. 1
[8] Shaileshh Bojja Venkatakrishnan, Mohammad Alizadeh, and Pramod Viswanath. Costly circuits. submodular schedules and approximate carathéodory theorems. In Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, pages 75-88 88, 2016. 3
[9] Endre Boros and Peter L Hammer. Pseudo-boolcan ootiroiiaaaooomimiiitiiiooo.. Discrete applied mathematics, 1555522) 2002.
[10] Fanchen Bu, Hyeonsoo Jo, Soo Yong Lee, Sungsoo Ahn, and Kijung Shin. Tackling prevalent conditions in unsupervised combinatorial optimization: Cardinality, minimum, covering, and more. In 4/st International Conference on Machine Learning (ICML), pages 4696-4729, 2024. 8, 32, 33
[11] G. Calinescu, C. Chekuri, M. Pál, and Vondrák. Maximizing submodular set function subject to matroid constraint. SIAM J. Computing, 40(6), 2011. 24
[12] Quentin Cappart, Didier Chételat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Velickovic. Combinatorial optimization and reasoning with graph neural networks. J. Mach. Learn. Res., 24:130-1, 2023. 18
[13] Constantin Carathéodory. Über den variabilitätsbereich der koeffizienten von potenzreihen, die gegebene werte nicht annehmen. Mathematische Annalen, 64(1):95-115, 1907. 2
[14] Chandra Chekuri and Amit Kumar. Maximum coverage problem with group budget constraints and applications. International Workshop on Randomization and Approximation Techniques in Computer Science, pages 72-83. Springer, 2004. 24
[15] Wei Chen, Xiaoming Sun, Jialin Zhang, and Zhijie Zhang. Network inference and influence maximization from samples. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 1707-1716, 2021. 8
[16] Yongqiang Chen, Yatao Bian, Bo Han, and James Cheng. Interpretable and generalizable graph learning via subgraph multilinear extension. In ICLR 2024 Workshop on Machine Learning for Genomics Explorations, 2024.
[17] Cyrille Combettes and Sebastian Pokutta. Revisiting the approximate carathéodory problem via the folfe-wolfe algorithm. Mathematical Programming, 197():191-214, 2023. 2023,
12

---

[18] Priya L. Donti, David Rolnick, and J Zico Kolter. DC3: A learning method for optimization with hard constraints. In International Conference on Learning Representations (ICLR), 2021.
3
[19] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. arXiv preprini arXiv:21 10.07777, 2021. 42
[20] Adam N Elmachtoub and Paul Grigas. Smart "predict, then optimize". Management Science, 68(1):9-26, 2022. 18
[21] Yahya H Ezzeldin, Martina Cardone, Christina Fragouli, and Giuseppe Caire. Polynomial-time capacity calculation and scheduling for half-duplex 1-2-1 networks. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 460 464. IEEE, 2019. 3
[22] Thomas Frerix, Matthias Nießnne, and Daniel Cremers. Homogeneous linear inequality con- straints for neural network activations. In Proceedings of the IEEE/CVF Conference on Com- puter Vision and Pattern Recognition Workshops, pages 748-749, 2020. 3
[23] Tobias Friedrich, Andreas Göbel, Frank Neumann, Francesco Quinzan, and Ralf Rothenberger. Greedy maximization of functions with bounded curvature under partition matroid constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 2272-2279,
2019. 24
[24] Eliza Gaile, Andis Draguns, Emils Ozolinš, and Kärlis Freivalds. Unsupervised training for neural tsp solver. In International Conference on Learning and Intelligent Optimization, pages 334-346. Springer, 2022. 3
[25] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and com- binatorial optimization, volume 2. Springer Science & Business Media, 2012. 3, 18, 19, 23
[26] Aditya Grover, Eric Wang. Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. In International Conference on Learning Representations (ICLR), 2018. 3
[27] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems (NeurIPS), 30, 2017. 8
[28] Will Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. Embedding logical queries on knowledge graphs. Advances in Neural Information Processing Systems (NeurIPS), 31, 2018. 33
[29] Ruben Hoeksma, Bodo Manthey, and Mare Uetz. Efficient implementation of carathéodory's theorem for the single machine scheduling polytope. Discrete applied mathematics, 215:
145, 2016. 3.5
[30] Boong-Hyun Hong, Hyun- Kim, Zian Jang, Deunsol Yoon, Hyungseok Song, and Byung- Jun Lec. Unsupervised training of diffusion models for feasible solution generation in neural combinatorial optimization. arXiv preprint wxXi:2411.00003. 2024." 3
[31] Xiuzhen Huang, Jing Lai, and Steven F Jennings. Maximum common subgraph: some upper bound and lower bound results. BMC bioinformatics, 7:1-9, 2006. 1
[32] Jan Húla, David Mojžīšek, and Mikoláš Janota. Understanding gnns for boolean satisfiability through approximation algorithms. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, pages 953-961, 2024. 3
[33] Yuma Ichikawa. Controlling continuous relaxation for combinatorial optimization. Advances in Neural Information Processing Systems (NeurIPS), 37:71899 2024. 3
[34] Wei Jin, Tong Zhao, Jiayuan Ding, Yozen Liu, Jiliang Tang, and Neil Shah. Empowering graph representation learning with test-time graph transformation. In The Eleventh International Conference Learning Representations (ICLR), 2023. 10
13

---

[35] Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. arXiv preprint arXiv:2006. 106444, 2020. 1, 3, 8, 33
[36] Nikolaos Karalias, Joshua Robinson, Andreas Loukas, and Stefanie Jegelka. Neural set func- tion extensions: Learning with discrete functions in high dimensions. Advances in Neural Information Processing Systems (NeurIPS), 35:15338-15335 2022. 1, 7, 18
[37] David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), page 137-146. Association for Computing Machinery, 2003. 8
[38] Nicolas Keriven and Samuel Vaiter. What functions graph neural networks compute on random graphs? the role of positional encoding. Advances in Neural Information Processing Systems (NeurIPS), 36:1 1823-118499 2023. 3
[39] Samir Khuller, Anna Moss, and Joseph Seffi Naor. The budgeted maximum coverage problem. Information processing letters, 70(1):39 1999. 8, 24
[40] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 2014. 42
[41] Gustav Kirchhoff. Ueber die auflösung der gleichungen, auf welche man bei der untersuchung der linearen vertheilung galvanischer ströme geführt wird. Annalen der Physik, 148(12): 497-508, 1 1847. 8, 30
[42] Till Kletti, Jean-Michel Renders, and Patrick Loiseau. Introducing the expohedron for efficient pareto-optimal fairness-ttiiiy amortizations in repeated rankings. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pages -98-507, 2022. 3,5 5
[43] Marcel Kollovieh, Bertrand Charpentier, Daniel Zügner, and Stephan Günnemann. Expected probabilistic hierarchies. Advances in Neural Information Processing Systems (NeurIPS), 37: 1881--1850, 2024. 3
[44] Vijay Konda and John Tsitsiklis. Actor-critic algorithms. In Advances in Neural Information Processing Systems (NeurIPS), volume 12. MIT Press, 1999. 8, 18, 33
[45] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations (ICLR), 2019. 8, 18, 33
[46] Andreas Krause, Carlos Guestrin, Anupam Gupta, and Jon Kleinberg. Near-optimal sensor placements: Maximizing information while minimizing communication cost. In Proceedings of the 5th international conference on Information processing in sensor networks, pages 2-10,
2006. 24
[47] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 21 21188-21198 Curran Associates, Inc., 2020. 18
[48] Xinpeng Li, Enming Liang, and Minghua Chen. Gauge flow matching for efficient constrained generative modeling over general convex set. In ICLR 2025 Workshop on Deep Generative Model in Machine Learning: Theory, Principle and Efficacy, 2025.
[49] Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint /5t::::55/1000444 2015. 42
[50] Enming Liang and Minghua Chen. Efficient bisection projection ensure solution feasibility for optimization over general set. 3
[51] Enming Liang, Minghua Chen, and Steven H Low. Low complexity homeomorphic projection to ensure neural-network solution feasibility for optimization over (non-) convex set. In International Conference Machine Learning (ICML), pages 20623-20649, 2023. 3
14

---

[52] Enming Liang, Minghua Chen, and Steven H Low. Homeomorphic projection to ensure neural-network solution feasibility for constrained optimization. Journal of Machine Learning Research, 25(329): 2024. 3
[53] Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv preprini arXiv:2202. 13013, 2022. 3
[54] Hui Lin and Jeff Bilmes. A class of submodular functions for document summarization. In Proceedings of the 49th Anmual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 510-520, 2011. 8
[55] László Lovász. Semidefinite programs and combinatorial optimization. In Recent advances in algorithms and combinatorics, pages 137-194. Springer, 2003. 8, 31,
[56] Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permuta- tions with gumbel-sinkhorn networks. In International Conference on Learning Representations (ICLR), 2018. 3
[57] Yimeng Min, Frederik Wenkel, Michael Perlmutter, and Guy Wolf. Can hybrid geometric scattering networks help solve the maximum clique problem? Advances Neural Information Processing Systems (NeurIPS), 111-22713-22222 2022. 3
[58] Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Jiang, Ebrahim Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Sungmin Bae, et al. Chip placement with deep reinforcement learning. arXiv preprint arXiv:2004. 10746, 2020.
[59] Vahab Mirrokni, Renato Paes Leme, Adrian Vladu, and Sam Chiu-wai Wong. Tight bounds for approximate carathéodory and beyond. In International Conference on Machine Learning (ICML), pages
PMLR, 2017.
[60] Konrad Mundinger, Max Zimmer, Aldo Kiem, Christoph Spiegel, and Sebastian Pokutta. Neural discovery in mathematics: Do machines dream of colored planes? arXiv preprint arXiv:2501.18527 2025. 3
[61] George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approxima- tions for maximizing submodular set functions - I. Math. Program., 14(1):265-294, 1978. 8, 33
[62] Robert Nerem, Zhishang Luo, Akbar Rafiey, and Yusu Wang. Differentiable extensions with rounding guarantees for combinatorial optimization over permutations. arXiv preprint MrXiv:2411.10703 2024.
[63] Emils Ozolins, Karlis Freivalds, Andis Draguns, Eliza Gaile, Ronalds Zakovskis, and Sergejs Kozlovics. Goal-aware neural sat solver. In 2022 International Joint Conference on Neural Networks (IJCNN, pages 1-8. IEEE, 2022. 3
[64] Panos M Pardalos and Mauricio GC Resende. Handbook of applied optimization. (No Title), 2002.
[65] Anselm Paulus, Michal Rolínek, Vít Musil, Brandon Amos, and Georg Martius. Comboptnet: Fit the right np-hard problem by learning integer programming constraints. arXiv preprint arXiv:2105.02343, 2021. 18
[66] Anselm Paulus, Georg Martius, and Vit Musil. Lpgd: A general framework for backpropagation through embedded optimization layers. arXiv preprint 2rXiv:2407.05920, 2024. 18
[67] Max Benedikt Paulus, Dami Choi, Daniel Tarlow, Andreas Krause, and Chris J Maddison. Gra- dient estimation with stochastic softmax tricks. In Advances Neural Information Processing Systems (NeurIPS), 2020. 3
[68] Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations (ICLR), 2019. 18
15

---

[69] Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combinatorial optimization problems. Advances in Neural Information Processing Systems (NeurIPS), volume 35, pages 25531-25546, 2022. 8, 18, 33
[70] Fred Rispoli. The graph of the hypersimplex. arXiv preprint arXiv:081 1,20:181 2008. 7
[71] Michael Eli Sander, Joan Puigcerver, Josip Djolonga, Gabriel Peyré, and Mathieu Blondel. Fast, differentiable and sparse top-k: a convex analysis perspective. In International Conference on Machine Learning (ICML), pages 19919-299366 PMLR, 2023. 3
[72] Sebastian Sanokowski, Sepp Hochreiter, and Sebastian Lehner. A diffusion model framework for unsupervised neural combinatorial optimization. In Proceedings of the st International Conference on Machine Learning (ICML), pages 43346-43367, 2024.
[73] Aditya P Saraf and Gary Slater. An efficient combinatorial optimization algorithm for optimal scheduling of aircraft arrivals at congested airports. In 2006 IEEE aerospace conference, pages 11-pp. IEEE, 2006.
[74] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems, 2019. 3
[75] Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1998. 19
[76] Alexander Schrijver. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. Journal of Combinatorial Theory, Series B, 80(2):34-3355 2000. 29
[77] Alexander Schrijver et al. Combinatorial optimization: polyhedra and efficiency, volume 24.
Springer, 2003. 4
[78] Martin JA Schuetz, J Kyle Brubaker, and Helmut G Katzgraber. Combinatorial optimization with physics-inspinn graph neural networks. Nature Machine Intelligence, 4(4):367-377, 2022.
3
[79] Martin JA Schuetz, Kyle Brubaker, Zhihuai Zhu, and Helmut Katzgraber. Graph coloring with physics-inspired graph neural networks. Physical Review Research, 4(4):04313,, 2022.
[80] Richard Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matrices. The annals of mathematical statistics, 35(2):876-88 879, 1964. 6
[81] Daniel Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 563-568, 2008. 29
[82] Haoran Sun, Etash K Guha, and Hanjun Dai. Annealed training for combinatorial optimization on graphs. arXiv preprint arXiv:2207.11542 2022.
[83] Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in neural information Processing Systems (NeurIPS), pages 1057-1063, 2000. 18
[84] Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe Graph neural networks for maximum constraint satisfaction. Frontiers in artificial intelligence, 3:98, 2021. 1,
[85] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 28. Curran Associates, Inc., 2015. 3, 18
[86] J. Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In Symposium on Theory of Computing (STOC), 2008. 24
[87] Haoyu Peter Wang, Nan Wu, Hang Yang, Cong Hao, and Pan Li. Unsupervised learning for combinatorial optimization with principled objective relaxation. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
16

---

[88] Runzhong Wang, Li Shen, Yiting Chen, Xiaokang Yang, Dacheng Tao, and Junchi Yan. Towards one-shot neural combinatorial solvers: Theoretical and empirical notes on the cardinality- constrained case. In The Eleventh International Conference on Learning Representations (ICLR), 2022. 8, 33
[89] Runzhong Wang, Yunhao Zhang, Ziao Guo, Tianyi Chen, Xiaokang Yang, and Junchi Yan. Linsatnet: the positive linear satisfiability neural networks. In International Conference Machine Learning (ICML), pages 36605-36622 PMLR, 2023.
[90] Hao Xu, Ka-Hei Hui, Chi-Wing Fu, and Hao Zhang. Tilingnn: learning to tile with self- supervised graph neural network. ACM Transactions Graphics (TOG), 39(4): 2020. 3.3
[91] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR). 2019.
[92] Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. Proceedings of the 21th ACM SIGKDD international conference knowledge discovery and data mining, pages 1365-1374, 2015. 42
[93] Morris Yau, Nikolaos Karalias, Eric Lu, Jessica Xu, and Stefanic Jegelka. Are graph neural networks optimal approximation algorithms? Advances in Neural Information Processing Systems (NeurIPS), 37:73124-73181, 2024. 3
[94] Bülent Yener, Yoram Ofek, and Moti Yung. Combinatorial design of congestion-free networks. IEEE/ACM transactions on networking, 5(6):989-1000, 1997.
[95] Hongtai Zeng, Chao Yang. Yanzhen Zhou, Cheng Yang, and Qinglai Guo. Glinsat: The general linear satisfiability neural network layer by accelerated gradient descent. Advances in Neural Information Processing Systems (NeurIPS), 37:122584-122611 2024. 3,
17

---

A Additional discussion of related work
Reinforcement learning (RI))based construction heuristics have been one of the leading paradigms in neural CO. The first application to use RL with neural networks are [5], where they combined Pointer Network [85] with actor-critic reinforcement algorithm [44] to generate solutions for the Traveling Salesman Problem. Later works including [45], [47], and [69] have gained great success in solving larger-scale CO problems with RL algorithms, and also showed the ability generalize to large scale problem instances. There are similarities between our approach and the general approach followed in RL algorithms like policy gradient [83] that are worth discussing. In RL, one learns distribution that maximizes the expected reward. This is done by sampling solutions from the outputs of neural network which are treated as the parameters of a probability distribution, then calculating their reward and weighing it by their log probability, and finally backpropagating to the parameters of the neural network. Stochasticity is often at the core of RL, and the ways that one may sample solutions for a given problem differ. Our goal is to propose structured approach that relies on methods from polyhedral combinatorics and convex geometry. Concretely, the output of the neural network is transformed so that it yields a point in the convex hull of feasible solutions of the problem. Then, instead of sampling, we leverage the decomposition algorithm to explicitly construct the support of the distribution that is parametrized by the neural net output. The extension we maximize can be viewed as the expected 'reward' (objective), which is similar to how RL operates. In terms of differentiability, our approach is slightly different since extension is a.c. differentiable and we can directly use automatic differentiation while RL deals with this using techniques like the log-derivative trick. Importantly, extensions can be used to optimize any black-box objective which is also the case for RL.
Other related lines of work include the Predict then Optimize paradigm [20] which combines learned predictions with a deterministic optimization problem that is parametrized by them. The mathematical relationship to extensions originates from the fact that extensions can be viewed as feasible solutions to a linear program for the convex envelope that is parametrized by some neural net predictions [36]. Another line of work that combines predictive and algorithmic components is the work on backpropagating through solvers [68, 65, 66]. For a more complete reference on combinatorial optimization with (graph) neural networks we refer the reader to [12].
B Decomposition Theorem: extended discussion
We will provide an extended discussion of the GLS result and its implications for our decomposition approach. For that we will need some definitions as presented in [25] in order to provide self- contained discussion of the theorem, its proof, and its implications for our approach.
Definition B.1 (Defining properties of polyhedra). Let P C R" be a polyhedron and let and v be positive integers.
1. We say that P has facet-complexity at most yp if there exists a system of inequalities with rational coefficients that has solution set P and such that the encoding length of each inequality of the system is at most y. In case P = R we require & 2 n + 1.
2. We say that P has vertex-complexity at most v if there exist finite sets V, E of rational vectors such that
P conv (V) + cono(E) EE)
and such that each of the vectors in V and E has encoding length at most v. case P we require 2 n.
3. It can be shown that the vertex- complexty and facet-complexity are equivalent from the perspective of polynomial time algorithm design, i.e., one can be written as a polynomial of the other [25, Lemma 6.2.4]. Therefore, we will only use the facet complexity to simplify discussions.
4. A well-described polyhedron triple (Pin, s)) where P S E is a polyhedron with facet-complexity at most sp The encoding length (P) of a well-described polyhedron (P:n,
(P) +
18

---

Definition B.2 (Strong optimization problem), The strong optimization problem for given rational vector x in n dimensions and any well described polytope (P; n, (p) given by
max c x'x, CEP.
(9)
Next, we state the GLS result which forms the foundation for Theorem 4.1.
Theorem B.3. (GLS decomposition) There exists an oracle polynomial-tinn algorithm that for any desl-dese polyhedron (P; n. () given by a strong optimization oracle, for any rational vector x. finds affinely independent vertices 1s, ........ 1s, and positive rational numbers No, Xi,.... , XR such that = Ei X,
Proof. Set X x. The algorithm begins by finding the smallest face that contains x and then obtain a vertex 1s, of that face. If that vertex is Xy then the algorithm terminates. Otherwise, half-line is drawn from ss through X, until the boundary of the polytope is intersected. At the intersection point, we obtain a new iterate X1. Notice that the previous iterate X can be written as convex combination of X1 and S. since it is part of a line with endpoints x1 and Sp. Again, we find the smallest face containing x1 and obtain vertex 1, from it. it matches the iterate, we terminate, otherwise we repeat the process. Since each iterate belongs to the faces of all the previous iterates but not the subsequent ones, the iterates are affinely independent and hence the process has to terminate in at most k S steps. Given the starting vector and the vertices it is straightforward to compute the coefficients with linear algebra. Furthermore the encoding length each iterate polynomial since it is the unique point of intersection of affine subspaces spanned by and the vertices of the polytope.
B.1 Constructing a polynomial time and a.e. differentiable decomposition
Based on the GLS proof, we can identify two conditions that yield valid decomposition when satisfied. Assume we already have starting point in the interior of the polytope, then:
1. For each iterate, finding a minimal face that contains and retrieving a vertex from it.
2. The ability to find intersection points of half-lines with the boundary of the polytope.
Those requirements can be fulfilled via the strong maximization oracle.
Obtaining polytope vertex for Step 3 of Algorithm 1. The proof requires a vertex of a face containing the iterate x,, The oracle may return any maximizer of the optimization problem that not a vertex. The face F containing to the vectors of the face F, we need to be able to retrieve a vertex of that face. This can be done by simple technique, where make call to the oracle for the perturbed program
is the set of vectors attaining maXegp x, c. [75]. Given access
max C X1, CEP,
(10)
with ē= c (c, [c,ee,...,, for some small [25][Remark 6.5.2).
Obtaining boundary intersections. It is a well-known fact that an optimization oracle can be converted to separation oracle in polynomial time. The separation oracle can be used to perform line search across the ray sent from the vertex obtained in Step 3 that passes through the current iterate. The line search can be used to calculate the coefficient that yields the next iterate which lies on a lower- diver--imenssooal face of the polytope and this process can be performed repeatedly until the full decomposition is computed.
Almost everywhers differentiable decomposition. To enable lcarning- based approaches with the decomposition, the coefficients at each iteration have to be almost everywhere differentiable functions of the iterates. We show how this is possible in the context of the recurrence Equation (4) by building on the main idea behind the GLS theorem just by leveraging calls to the strong optimization oracle.
Theorem 4.1. There exists polynomial-time algorithm that for any well-described polytope PP given by a strong optimization oracle, for any rational vector x, finds vertex vertex- probability pairs (px, (S.), 1s. for 0, I,...., n such that x ==-1 Px, 1s)) and all Px, (St) are almost everywhere differentiable functions of
19

---

Proof. Let P C R", current iterate X, P. and the vertex 1s, given by the oracle in Step 3. Consider the recursive decomposition
0t 1s, (1-ar) a-) X
X P. 0 S az < 1.
First, we will focus on differentiability. Recall that we can view each iteration above as intersecting a ray that passes through the vertex given by the strong optimization oracle and the current iterate with the boundary of the polytope. To find the intersection, set the ray direction d, == Xt 1s. o 0 and let
y(7) = 1s, + r dd, so that x, = y(1). Note that we can recover the original iteration equation from (()) via
2 0,
1
1
Furthermore, note that the constraint X, 1s, * implies that the iterate cannot be vertex of the polytope. Indeed, the proof of the GLS result states that the decomposition terminates at a vertex, which is consistent with this constraint. The intersection point with the boundary is given by the largest coefficient allowed that can yield a point in the polytope
r" (x; 1s,) max 2 0: y(T)
To derive the maximum step that yields intersection with the boundary we will leverage the strong optimization oracle. For any с E R", the support function hp(c) == maxzep c z which can be computed using the strong optimization oracle satisfies
c y((T) c (1s, +rd)
S hp(c).
This implies
hp(c) c 1s. c d.
whenever e de 0.
Taking the best bound yields
hp(c) c 1s.
(xti 1s)
min
(11)
e: d:>0
c d,
Rewriting in terms of a* we obtain
(x, 18.)
a" (xi; 1s) =
max e: he(c)>e 1s, hp((c) 1ss
(12)
Note that for positive denominator, the maximum of the ratio is always between zero and one. To why that the case, notice that с c= X₁ 1s, always feasible and it always yields positive ratio. The ratio is upper bounded by because hp is the support function, so we have for x E P that
hp(c)= 2 T = hp(c) - c c1s. 2 c x 11s
The optimizer is a piecewise linear function of x, as maximum over linear functions. Piecewise linear functions are locally Lipschitz, and therefore differentiable almost everywhere. Note that 1s, the maximizer of the strong optimization problem from Equation (9). The maximizer depends on and its gradients are zero almost everywhere because it is piecewise constant function of x,- Given an optimal c", we can calculate a* and hence the probabilities in step 6 of Algorithm 1. Recall that the probabilities are given by Px, (S.) = az o function of its iterate and each iterate depends on the preceding iterate through the differentiable recursive update rule, Equation (4), we can calculate the derivatives of each Px, (St) with respect to the starting point in the polytope with standard automatic differentiation packages.
a.). Since each a; is an a.c. differentiable
Finally, we want to show that the a.e. differentiable decomposition can be computed polynomial time. Step 3 requires solving an IP and can be done in polynomial time. If we show that Step 4 is also computable in polynomial time, we are done. To so, we need show that the maximum coefficient for the bouudauy intersection is computable in polynomial time. We will show that the optimal
20

---

c" can be found by solving standard convex optimization problem. Observe that Equation (11) can be written
min hp(c) - cc- 1s., subject to c de 1,
(13)
by simple change of variables c - --../ c/(c de) because the ratio in Equation (11) is invariant to rescalings of Therefore, the objective a sum of the support function of the polytope (convex) and -c' 1s, which is just linear function (convex). Hence, the sum is also convex, so we have a convex minimization problem in subject linear constraint. This standard linear program that can efficiently solve with any of the well known algorithms to obtain the optimal c*.
Special case: Compact polytope description. An important special case that simplifies the design of efficient decompositions for end-to-end learning is when the polytope admits a compact description terms of polynomially many inequalities. Recall that for general polytope
p = fx E R 2 S bi, l....,m..
Again, pick the convex combination coefficient
a a, = max at E 10, x++1(a)) PP.
This choice of coefficient leads to the next iterate being far possible from the current one. This means the coefficient will be pushed until some constraints the polytope are tight for the new iterate and hence the boundary will be intersected. At iteration t, with current iterate and chosen corner 1, we may determine the coefficient by enforcing each face inequality. In particular:
X - Gt 1s.
2 X(+1 I b;
2
S b;
1 - 04
b: Z Xt
at S
whenever b; - -2, 1s. 0.
bi z, 1s.
Hence
b; z Xt b; 2, 1s.
max (xi)
min
(14)
2 1s,
which shows that the maximum feasible weight a, is a well-defined differentiable function of the current iterate X,. This is crucial because it allows us backpropagate through the coefficient and leverage the decomposition in gradient- based optimization.
Equation (14) and Equation (10) sufficient for our decomposition. Specifically, given access to a fast algorithm for Equation (14) and a fast algorithm for Equation (10) we can obtain a tractable decomposition that allows us to build Dc(x) in a differentiable manner. It should be noted that if the polytope is defined by exponentially many incqualities, then iterating over the inequalities to find the minimum becomes intractable.
B.2 On the applicability of our approach to different combinatorial problems
Computational complexity vs applicability. The existence of a strong optimization oracle for the feasible set polytope is a sufficient condition for the applicability of our approach. Superficially, this may seem to imply that our approach is only applicable to problems that are easy from a computational complexity standpoint. However, we are trying to solve is not sufficient to determine the applicability our method.
will explain, the computational complexity of the problem
Consider the Traveling Salesperson Problem (TSP) Polytope. The strong optimization problem for that polytope not solvable in polynomial time unless NP. Having such an oracle would be equivalent to having an oracle for the problem itself. Fortunately, we can still apply our method to TSP. combinatorial optimization, one can reformulate problem to "offload" some of its difficulty from the constraints to the objective. While TSP can be viewed as a linear optimization problem over the TSP polytope, can also be viewed as a quadratic optimization problem over permutation (Birkhoff) polytope. Linear maximization can be done in polynomial-time in Birkhoff polytopes,
21

---

which means we can efficiently construct extension of the quadratic objective over the Birkhoff polytope.
Polytope description vs applicability. Another important consideration is the size of the description of the polytope. Indeed, showed in Appendix B.1, if polytope admits compact description in terms of polynomial number of inequalities, then we can straightforwardly proceed with our decomposition. On the other hand, even when that is not the case our method can still be applied using just the optimization oracle as it can be seen in the proof of Theorem 4.1. An intuitive example the base polytope of submodular function. linear maximization over the polytope can be done efficiently with the greedy algorithm. The optimal value of the linear maximization problem the polytope fact given by the Lovász extension of the submodular function.
defined by exponentially many inequalities but
C Decomposition with controlled approximation
One of the limitations of the decomposition as presented in the approach is that the support of the distribution we obtain depends exactly on the ambient dimension of the space. There are a few reasons why this might not be desirable. First, an exact decomposition like this fixes at most sets in the support. That may be too restrictive in problems with 'sparse rewards', i.e., when good objective values achieved number of sets in the support of the distribution, which could in turn lead to better outcomes for optimization. We show how we can achieve this with a simple tweak that allows to control the reconstruction quality, which we also utilize in our max coverage experiments.
only few points. It would be preferable if we had more control
the
C.1 Decomposition via rescaling
Start with For each iteration / 1, 1,.,,...... k. we first pick the corner 1s, and compute the iteration coefficient
min min min x, (i), min(1 x,))))
:ES.
jæS:
The difference now is that instead of picking the maximum coefficient we will rescale the ā in each step by some fixed constant E (0, 1]. This means that the next iterate will not be intersecting the boundary and hence the algorithm will require more steps terminate, hence requiring a tolerance parameter e as we have described in Algorithm 1. Additionally, we fix some lower bound & on the rescaling that
bā
bā; 2 L
Ccs
bā, < E.
Using this coefficient we compute the new iterate using Equation (4).
Proposition C.1. Suppose we pick step 3 in Algorithm 1 according to Equation (5). Then the reconstruction error of the algorithm (step 8 in Algorithm 1) decays exponentially in k.
Proof. After iterations we may express x as
x
(1
a.) 1s. + (II a.)) X ==0
1=0
1=0
Pre (Si)
Recall from step of Algorithm 1 we have that the stopping criterion (given by the reconstruction error) is
Σ (x.( 1s, 1s Sc.
1=
Clearly, the term inside the nomn on the left hand side of the inequality is the residual
k
[I[
a:))
x
1=0
22

---

For the reconstruction error we just need to compute the norm of the residual and show that it decays exponentially in k. Hence, we calculate
rkt+ 12+11/2-1
[II ai)
||*++1l2
$ (1 f7 ||x||2
(1 fynn.
which completes the proof.
Given some tolerance parameter this allows us to control the number of sets considered in the iteration. We observed that using this approach helped with the training dynamics of the model as well as with achieving better approximate solutions.
D Deferred proofs from Section 4.2
Proof Theorem 4.3
Proof. The proof follows the same argument as the proof in [25][Theorem 6.5.11J. To make the result more intuitive may assume without loss of generality that the entries of x, sorted, i.e. (1) 2 (2) 2 ... 2 xx) Under this ordering,
1s. = arg max (E(0.))
X,
1=c
selects exactly the top coordinates. Since ||x,|| l and ||s k taking the -norm of both sides of Equation (4) gives
== a, (1 dx) ||x++|||,
so ||x++1111 = is and the sum-to-k constraint is preserved exactly. Apart from the norm constraint, we also have to ensure that each coordinate remains in the hypercube. To keep each coordinate in the hypercube we solve for the coefficient that satisfies 0 S Xx+1 S in our recurrence equation. First, we rearrange Equation (4)
X, a,1s.
X++1
and note that subtraction at the numerator affects only the top &o coordinates. It is clear that for i E S, coordinates cannot possibly exceed one because the denominator is always larger, but they may drop below 0. So we need to ensure
X
at 2
0,
(15)
which implies < minges, x+( and corresponds to constraint the k-th coordinate in this ordering. On the other hand, for $ S, they can only increase in magnitude, so they may exceed 1, which leads us to
X xi( a4
S 1,
(16)
and hence a, < 1 maxjes, xj( which constrains the (I: + 1)-th coordinate. Ensuring that both Equation (15) and Equation (16) are satisfied, and following the GLS proof, we pick the largest possible coefficient which leads us to Equation (8):
min min (i), 1 - max (i)). Ves.
JES.
a; = minges, (1), the k-th entry set to zero; otherwise (A: + 1)-th coordinate set to Note that from Equation (4), once coordinate has been fixed to either 0 or 1, it cannot change in subsequent iterations. Therefore, the process will terminate when the next iterate becomes corner of k Since there are & zeros and ones at the final iterate and each iteration fixes exactly
23

---

one coordinate, the process terminates after at most &t + (n - k) = n iterations. In line with the GLS proof, the next iterate intersects the boundary the polytope the minimum is guaranteed to fix coordinate either to 0 or to 1.
face of lower dimension because
Finally, because each 04 is defined via pointwise minima and maxima of the entries of xt, it is almost everywhere differentiable in X₁. By the chain rule, the resulting probability weights
Px. (St) = de [ a.)
i<t
are almost-everywhere differentiable in the original input Xo. This completes the proof.
Proof of Proposition 4.4
Proof. Let 2 E [0, 1]"h and x s2 + u, and define
# 1
k 7
Z
z=
pl,
1.
i=1
Since = - 11) = 0, we have
Σ
2 +
0 k,
1=1
i=1
so ||x|| 1 = k. Next, for each coordinate
k
24 (2) 11) +
Because 0 05a 24 1, we have
- S 2 1
μ.. Therefore
k k
11p1 20 0
24 2 - μ
+
n n
by S ny* and
k
k
n(1 - 11) n2 k
T; S 3 (1 - u))
1
5
by <
n m)
Hence 0 I r; S 1 for all i, and we conclude An,k-
E Case study: Partition Matroids and Spanning Trees
E.1 Partition Matroid
Partition matroids provide a powerful and flexible framework for modeling constraints in set function optimization problems. They capture scenarios where elements are divided into categories, and are allowed to select only limited number from each category many real-worke applications. This structure naturally arises in applications such as sensor placement, where sensors are partitioned by geographic regions and each region has an independent budget [46]; job allocation and welfare maximization, where tasks are categorized by required skills and only a bounded number of tasks from each skill category can be assigned [1 1, 86]; and many other theoretical and practical settings [23, 14, 39]. Partition matroids thus provide a flexible abstraction for modeling structured selection problems with heterogeneous constraints.
structure that arises naturally in
partition matroid or partitional matroid is matroid that is direct sum of uniform matroids. is defined over a ground set in which the elements are partitioned into different categories. For each category, there a cardinality constraint-a maximum number of allowed elements from this category. Formally, let Vi.... Ve be disjoint subsets such that V = L V. Let k; be integers with 0 S i; S [Vi]. Consider the following combinatorial optimization problem:
max f(S). 8:18nv,
(17)
24

---

Note that when 1. this reduces to the cardinality case. The convex polytope of feasible solutions known as the partition matroid base polytope and is described as follows:
B =
x AS
Σ x(e S rS)) and ||x||| cES
Σ ki
(18)
r(S)
Σ t=1
min k;),k)) AA C E.
(19)
The vertices of the matroid base polytope B are the indicator vectors of sets whose intersection with every block Vi has size exactly kę Hence, any vector x E B can be written as a convex combination of the indicator vectors of feasible sets. We prove that Algorithm given x E B, returns in polynomial time a distribution over feasible sets which is a.e. differentiable with respect to x. Note that Algorithm 2 is an explicit version our generie Algorithm with steps 3 and 4 specified.
Theorem E.1. Given x B, Algorithm terminates after at most O(n) iterations and returns (Pxx (St), 8,)} such that for every St and V, we have 1Se n Vil ki and E, Pxs (S,) 1 with S Px, (St) 1. Moreover, each px, (St) an almost everywhere differentiable function of x.
Proof of Theeorm E.I. Suppose Xy = x E B. We prove the correctness of our algorithm for every iteration t.. To obtain vertex of the polytope in the support of X,, set
1s.
argmax
x1 c
(E
The optimal solution for the above problem is S. U where for each block V,, T₃ is the indices of the top k; coordinates within x (V)). Define
min minxx;())... (i), maxx((1) } iES.
a, min
and
(20)
s4S,
Xx+1
T-o,
(x ag 1s))
(21)
For the correctness of Algorithm it suffices to show X is in fact inside the matroid base polytope B.
First, note that X,41 [0, 1 by the definition of a and the fact that x, E 10 Second, for both x
and 1s, we have [x|] = [1 Eiz k;. Hence, by the definition x, = a,ls, + (1 a (x)x+11
follows that |x ||| Σi=1 kg remains to show for all C V it holds that E.es X1+1 (e) S
r(S). Recall that r(S) Di min(IS Vil, k.) and
x()+(()== Σ (e)i(e)+.... Σ xe+1(e)
(22)
cES
cESsV,
eesnv.
We show each term Σ Zeesnn xx+1(e) < min([Sn[Vl,kk) First suppose min([SnV]]. k)) (S
Then since (c) [0. we have EeEsnv, x(+1(e) Ecesnv. 1 = |S Vil. Second, suppose min((S n Vil. ki- Note Ecesoy, (e) Ecey, x (e), hence suffices to show
Ecey, (e) k.
In this case we use the induction hypothesis that E B. being in B implies that Exev, x(e) S r(V)) k. By definition we have
25

---

4 E 1s. (c) + (1-at)
Σ x++1(e)= Σ
xx(c) S k;
(23)
<EV.
eEV
eEV.
>a|Sn + (1-
- ar)
Σ
xx+1(e) S ki
(24)
nEN
Dacks + (1 (1)
Σ
x(+1(e) (e) S hi
( n V.l = k; by the choice of S.)
<EV,
+1 a1) Σ (c) S - -aiiki
(25)
<EV,
x(+1(e) ki
(26)
This finishes the proof that Eees x(+1(e) S <r(S). thus X(+1 E B.
Algorithm 2 terminates in at most (n) iterations. At each iteration t, X++1 differs from x; by fixing one additional coordinate to either 0 or 1. Once a coordinate is fixed to 0/1, remains unchanged in all future iterates. The process terminates when X₁ has >im all coordinates are 0/1.
k zeros and > kg ones, meaning
Finally, because each is defined via pointwise minima and maxima of the entries of xx, it is almost everywhere differentiable in Xt. By the chain rule, the resulting probability weights
Px, (St) de II a:)
are almost-everywheree differentiable in the original input xo. This completes the proof.
Algorithm 2 Decomposition for partition matroid
Require: x E B.
Xo f-x
2: repeat
3: 1s.
(1. xJ'c
4: ar = min (minses. (i), 1-),,immm, 1 gas xx()))
5: Xx+1 + (x, a,1s, (1 ax)
6: (S,) + az IT= a:)
7: f
8: until x, 10,
9: return All (8)), pairs.
E.1.1 Generating neural predictions in the Partition Matroid Base Polytope
Similar to the cardinality constraint case, we need to map the output of the neural network to the polytope in differentiable and computationally efficient way that it can be passed to Algorithm 2. The general idea is similar to the one we proposed in Section 4.2.1, however it requires a more careful way of dealing with blocks.
Proposition E.2 (Block-wise scaling into a partitioned simplex). Let the index set [m]] f1.....1) n} be partitioned into disjoint blocks V,...., V. with Vi n, and Di n. = n. Given any vector 2 E [0, 1]", set
m; ==
Σ Z(E), eVV.
m(e) = my (e E Vi),
u(e) = k (e Vi),
n
8, = minl
Ke/ng RR)//n
s(e) = 8, (e E Vi),
1-ma
26

---

and define
x (z m) + u.
Then x E B3 that is, every coordinate of lies in [0, 1] and each block V; has the prescribed sum k;-
Proof. For each block Vi and every V; we have
ks n4
(e) s: s:(z(e) m.)
Since Enev((Z(e) - m.) 0. summing over Vi gives
Σ eE
x(e) = ks.
Because -m S <z(ee= m14 1 m,;
8;m, ki
his + s; m;).
x(e)
x(e) S
n4
By the definition 8; min(
ki/m:
[n: k. /ni
both right- sides lie [0. 1], so 0 S <x(e) $
my
1 m.
Thus every block sums to and every coordinate is in [0, 1]; hence x E B.
E.2 Graphical Matroid
In this subsection we turn our attention to graphical matroids and show that our framework can be extended beyond cardinality constraints. Graphical matroids core combinatorial objectives that have been studied for decades in combinatorial optimization. Some of the most basic combinatorial problems such as finding minimum spanning tree in connected graph to more complex problems like "does graph G contain & disjoint spanning trees?" which appears in many applications in Network Theory.
Let G (V, E) be graph with n nodes and m edges. The type of optimization problems that we consider here are expressed as follows
max f(S)
(27)
SCE:SE
where JF denotes the set of full spanning forests of G. We focus the convex hull formed by the feasible sets edges in F. That is, let 1r be the indicator vector of T' e F and define
B(G) conv : E
(28)
The combinatorial object B(G) is known as the graphical matroid base polytope. For any set of edges let the rank be r(S) = n - c(S)) where c(S) is the number of connected components of the subgraphs formed by the edges in S. For instance, if G is connected and S forms spanning tree then r(S) = n - known that (GG) can be defined in an equivalent way as follows
B(G) = (x [0.1] VS C X(S) S r(S), and ||x|| = - c(V)),
(29)
where use the notation x(S):= Ees x(e) for every subset S. Note that any vector B(G') can be written as a convex combination of the indicator vectors of feasible sets i.e, indicator vectors of spanning forests. We follow general template to design decomposition algorithm for the graphical matroid (Algorithm 3). We can then prove the following.
Theorem E.3. Given E Algorithmn terminates after at most O(m) iterations and returns ((xx, (S,), S.}} such every S, corresponds to a spanning forest in G and E, Px. (S.) = 1 with Px. (S.) [0, 1]. Moreover, each px, (S:) is an almost everywhere differentiable function of x.
Proof. The algorithm follows similar template as our main result, the only difference is on select- ing an appropriate vertex of the polytope at each step and selecting an appropriate coefficient at. Specifically in each iteration we define
X1+1 (xi a.ls;) /(1 at)
27

---

Algorithm 3 Decomposition for graphical matroid
Require: Graph G = (V,E) and B(G).
Xg 6-x
2: repeat
3: St < A maximum spanning forest using X; as the weights for edges (treat zero entries as
non-edges.)
4:
= min minees x(e). 1 - max.gs, x(e), minfÇE ((F)-18;71) 5: X1+1 t (xi - a,ls)) (11 at)
(FF)
6:
(S,) f 0z 11:100011 a;)
7: ++1+1
8: until X; E {0.1)m
9:
return All (St), pairs.
where S is maximum spanning forest using x as the weights for edges (treat zero en- tries non-edges). In order guarantee that X;+1 is in the polytope B(G) it must satisfy the rank inequalities and be in [0, 1mm To guarantee X,-1 E [0, 1J we enforce that de S min {minees, x(e), maxegs, x(e)}. To satisfy the rank constraints, for every F C E we must guarantee (F) $ r(F). That
(F)
= (x.(F) - 0z 1s (
- (F) - r(F)
r(F) (P)
a S r(F) - |s nF
Note that r(F) |S, F) and we can dismiss the case where r = 1Se FJ. This must hold for all subsets F C E. We therefore set
= min min x(e), 1 maxx(e), min r(F) - (F) egS. FCE r(F) - SS
(30)
CES.
is not immediate if we can compute 0r in polynomial-time as the third term in Equation (30) is troublesome and involves minimization over all the 2 subsets. There however exists polynomial
time algorithm to compute a, For a fixed À E [0, 1] define the set function 9(x.)) 2 + R
90. (P)
()r(F) (F) A/F n S.l
(31)
Then X is in the polytope iff:
1. I min (minees, x(e), max.gs, x(e)), and
2. min (a).)) 0. FCE
To this end. goal is to find the largest X [0, max {min.es. x(e), - max es, x(e) for which min .( (F) 2 0. Then a, = min (minges, x(i), 1 max;es, x(i),
FCE
We find such A by doing a binary search over the interval. To justify our binary search we need two things. First is monotonicity of d(A) == ((). w.r.t À and any fixed F. Second is computing
minrge ((A,)) (F) for fixed X.
Claim E.4. For a fixed F, @(A) = (F) is cunniicrrrasingg.untiooo in X.
Proof. Note that (1 - affine function of À with negative slope since r(F) > SSt Fl. This completes the proof. D
S - ( is an
28

---

Claim E.5. There is polynomial time algorithm, i.e. efficient oracle, that for a fixed X returns min (F). FCF
Proof. We point out that the set function I(A.t) for a fixed À is a submodular function. This is because the rank function r(F) submodular, -F² and X|F n Se] are modular functions. Hence, FC E 9(x,e) (F) can be found in strongly polynomial time by any submodular-function minimization (SFM) algorithm, for example the one provided in [76].
In the binary search, at fixed À using the efficient oracle we compute minfçe 9(x.e) (F). If this value is greater than zero, we increase À and continue the binary search in the right half interval. Else, we decrease À and continue the binary search in the left half integral. (Note that this approach finds X up to a desired precision 2 0.)
Finally, we argue that 0 as defined in Equation (30) is an a.e. differentiable function with respect to XG- The proof is similar to what we have in the cardinality cases. First note that for fixed maximum spanning tree St, a₂ is the minimum of finitely many affine functions of x;; hence, it piecewise linear function and almost everywhere differentiable. Second, the map that outputs a maximum weight spanning tree with respect to X; is almost everywhere constant (the resulting spanning tree changes only some edge weights are exactly equal.). These two together yield that at as defined in Equation (30) is an a.e. differentiable function with respect to Xt.
E.2.1 Generating neural predictions in the Graphical Base Matroid
We need to massage the output of the neural network a differentiable and computationally efficient way so that it obeys relaxed constraint and can be passed Algorithm 3. Algorithm 3 requires to lie within the graphical matroid base polytope BGG), which represents a relaxed version of the original constraints. Without loss og generality we assume G is connected graph. Every point inside the graphical matroid base polytope can be seen as a distribution over spanning trees. We first define the uniform distribution over the set of all spanning trees and forces encoder network generate a perturbation to this uniform distribution. Some notations are in order.
Fix an arbitrary orientation over the edges of G. For edge
(u, v), i.e. oriented from u to v, let
[1 v==
be = 1, 1y with la(v) = (0 otherwise
(32)
The Laplacian of (positively) weighted graph G is LG Eleewee)bely Let L'g denote the Moore-Penrose pseudo-inverse of Lg.
Generating a perturbation vector. Let T denote the set of all spanning trees of G and μ be a uniform distribution of all spanning trees of G. A uniform spanning tree distribution is a uniform distribution over all spanning trees of a given graph. the graph is weighted, then we can study the weighted uniform distribution of spanning trees where the probability of each tree is proportional to the product of the weight of its edges. For : E R,, we say u(w) a w-uniform spanning tree distribution, if for any spanning tree T TT
Pr[T] & w(e).
eET
Let (e(w))= := Prr jale E T] be the marginal probability of edge The following result gives way of writing an analytical expression for Pe-
Theorem E.6 ([81)). For any edge e
Pe b._ be
Moreover, for weighted graph G with : E + R+, if w(e) is the weight of e, then
(e(w) w())b Ligb..
29

---

The above Theorem E.6 suggests the following way of generating point inside the graphical matroid base polytope. Let w F. be the output an encoder network that assigns positive weight to every edge of graph G. We think of as a perturbation to the uniform distribution over the spanning trees. Then obtain vector x whose e-th entry is (*((w) according to the weight vector w and Theorem E.6. The vector x lies inside the graphical matroid base polytope B(G). Recall that B(G) = conv(1r T E ] and x = Br==u(w) [1r] is a convex combination of indicator vector of the spanning trees. We show that p(w) is continuous and differentiable with respect w.
Theorem E.7. Let G = (V, E, w) be connected, weighted graph with non-negative edge weights w E R20 and let
He(w) = PT~p(t) ET = =((e (w) (w) be,
6E E,
where be is the signed incidence vector of e and Lo(w) = Eser wff)byb] is the weighted Laplacian (with Moore-Penrose pseuloinverse Lig). Then
Me : 20 IR is continuous on the closed orthant:
it. He is C (indeed analytic) the open orthant B
ii. Me is differentiable everywhere on IR
Proof. Let (w) denotes the reduced Laplacian with any single row/column removed. By Kirch-
hoff's Matrix-Tree Theorem [41] ] we have
T(W) det( (o((w) = Σ
Il
w(f),
spanning trees T
fEr
For an edge e we have,
(e(w) = T(W e) T(w)
(33)
where w - denotes the weight vector with w(e) = O. Both numerator and denominator in (33) are (multivariate) polynomials; moreover r(w) > O whenever at least spanning tree has positive total weight, which is guaranteed by the connectivity of G. Hence the ratio is continuous on & proving part (i).
On the interior R the reduced Laplacian [o(w) is positive definite (PD). The maps
w - La(w) (affine map),
A A-1 (C on PD),
compose smoothly, so the formula (w)) = wle) b-_ La(w) -1b, is infinitely differentiable i.e., is C and indeed real-analytic on - giving (ii).
remains to show (iii) boundary points where some coordinates of w equal O. Let we be weight vector with at least one zero entry, and Z be the set of zero weight edges. There are two cases:
Case A: G - Z is connected. In this case the reduced Laplacian LG (wo) positive definite since G Z has least one spanning tree, the same smoothness argument used for (ii) applies; thus pe (wo) is differentiable (in fact is (o))
Case B: G Z is disconnected. Then every spanning tree of any nearby weight vector must contain the cut cut- edge whose weight vanished, so the term in Equation (33) equals in a whole neighbourhood; hence uı, is locally constant and therefore differentiable at wo with derivative O.
In either case one-sided (classical) derivatives exist and coincide with the interior derivative, complet- ing (iii).
F
Case study: Maximum Independent Set
For the maximum independent set problem, we want find the largest set S of nodes in graph G (V, E), where pair of nodes in the set is adjacent. Unfortunately, there is no known
30

---

compact description in terms of inequalities for the independent set polytope [55]. This immediately presents challenge for the design of the decomposition. Furthermore, linear optimization over the independent set polytope is NP-Hard since it amounts to solve the the maximum independent set problem. Therefore, in this case, we will consider a relaxation of the polytope which has a known description in terms of inequalities and for which the optimization problem can be solved efficiently.
First, let us assume that C, and that the graph G has no isolated nodes. In order be able to optimize over independent sets we are going to need access to a polytope description. The constraints are defining the polytope referred to
S 24 < for all and x(i) + x(j) I for (i.j) in the literature as FSTAB [55]. FSTAB is relaxation of the independent set polytope since it includes half half-integral vertices. We will explain how we will leverage FSTAB to explore the space of independent sets.
For step we use Equation (10) obtain vertex of the polytope FSTAB. Note that now the vertex may contain half-integral coordinates. This will affect our coefficient selection. We need to select < 1 imply the
coefficient that does not violate the polytope inequalities. The constraints same rule for the coefficient dg. However, we have an additional consideration. If we just choose the coefficients as in the cardinality constraint case, when the coordinates i,j S and (i,j) E E get rescaled by - ae, we may break the constraint for xii + x(j) < 1. This leads us to the following result:
Theorem F.1. Let
ag min
min (i), ieS;
min (1 x()i,,,
min (u,))E:: u.ogS,
(1 (xxx((u)= x()
(34)
JES:
x(1)20
x())51
(v)++(())
be the coefficient chosen at each iteration in the decomposition. Algorithm on FSTAB using coefficients from Equation (34) and Equation (10) for step 3, obtains an exact decomposition in at most n + 1 steps, and each coefficient an a.e. differentiable function of corresponding iterate in the decomposition.
Proof. At each step, a coordinate set to either 0, 1, or an edge inequality tightened. Since we use the same recurrence as with the cardinality constraint, if at any iteration a coordinate is set to 0 or then it cannot change. For the edge inequalities, suppose we have X (u) + Xx+1 (v) = 1, and
V (w) + (z+1(v)= = where Ve+1 is the vertex we obtain by the oracle iteration + 1. Thus
x1+ (v) ac+1 (ve+1(u) (u) + V141(1))
x142(u) + xx)=(1)=
(35)
ae+1
1 a:11-
(36)
a++1
(37)
so the edge equality persists. Each time we tighten an inequality, the dimension of the minimal face containing the current iterate is decreased by one. Thus, in at most steps the algorithm will land on a vertex (face of dimension 0) of the polytope, at which point the algorithm terminates. Finally, the coefficients are always a.e. differentiable functions of x, since the minimum function over x, is also everywhere differentiable.
Obtaining point on FSTAB. Since would like to build support that avoids half-integral points as much as possible we follow a simple gradient-basse projection scheme for FSTAB. We begin by defining the total edge-violation of point 1= with slack parameter 0 as
V(x)= = Σ max x(i) + x(j) s 1111.
(K,))E
which measures how much each edge (u, v) exceeds the bound x(i) + x(j) + 8 S 1. To correct all violations at once, compute V (x(x) (di,..., liy....ddyy .z),, where
d2 = Σ 1[x(1) + +
(1 (b
31

---

counts how many incident edges on node are violated. Next, for each violated edge (u, v) with violation amount
buv x(u) + x(e) + 1>> 0, we require step-size y satistying buv 17 (du, + d2) S 0. which implies
buv
1 2 du + de
Taking the maximum of these ratios over all violated edges gives the minimal that fixes every violation:
x(u) +
max 7 (u,o): : x())+(())++>11
du + dp
Finally, we compute x'= o (x))), where a is ReLU. This guarantees x' (x)+x S for every (u, v) E and x' 2 0, which ensures that we have a point in FSTAB.
Dealing with half-integral corners. The decomposition may still yield several half-integral corners which can affect the performance of our extension, since we need the support sets to be independent. There are two ways of dealing with half integral corners. One approach is to penalize them in the objective i.e., the function evaluated at half-integry corners returns O. Another approach is by tightening the relaxation with additional inequalities commonly found in the literature, including clique constraints and odd cycle constraints
[55]. In practice, many of those come down imposing an [.1 norm constraint on the point in the polytope. We may enforce both constraints (FSTAB and L.1) by alternating projections. It is easy then we can always obtain a decomposition into independent sets, so a valid decomposition always exists.
that if the norm is and the constraints all satisfied,
G Experiments
Here, we provide detailed experimental settings and some additional experimental results. All the datasets are public and our code is available at https://github: http.///m//raaae/////eeeeee Combinatorial_Opt iariiiaapppmiiiatiiiiie www.wwwwtttttiiiiieeeee Constraints.
Hardware. All experiments are run on 16 cores (32 threads) of Intel(R) Xeon(R) Platinum 8268 CPU (24 cores, 48 threads in total). 32 GB ram, with a single Nvidia RTX8000 48GB GPU.
Following previous work [10, 88], we evaluate our methods on both synthetic and real- world bipartite graphs (U, V, E), V is the ground set and the goal is to select & nodes from V so that we cover maximum number of nodes from U.
Datasets.
Random Uniform. The Random Uniform datasets include both the Random500 and Random1000 settings, and are used for both training and testing. Each dataset consists of 100 independently generated bipartite graphs, where [V| = 500, [ 1000 (Random500) or [V] 1000, |0' = 2000 (Random1000), Each u E is assigned a weight uniformly at random from 1 to 100. Each E V covers random subset of U, with the number of covered nodes for each v chosen uniformly at random between and 30.
Random Pareto. The Random Pareto dataset consists of 100 independently generated bipartite graphs with JU| = VV = 1000, used exclusively for training the Twitch experiments. In each graph, the number of covered nodes per covering node V follows a Pareto distribution, with the a parameter randomly selected between and 2, resulting in a heavy-tailed degree distribution (typically, 20% of covering nodes account for 80% of the edges). Each u E U is assigned a weight uniformly at random from to 100, and every u E U is covered by at least one E V.
Twitch. The Twitch datasets model social networks of streamers grouped by language, with U|= = V set to the number of streamers. The dataset includes: DE ((U) [ 9498), ENGB (7126), ES (4648), FR (6549), PTBR (1912), and RU (4385). The objective is to maximize the sum of logarithmic viewer counts over U.
Railway. The Railway datasets are derived from real-world Italian railway crew assignments.
We evaluate on three graphs: rail507 ([V 507, [U] = 63009), rail516 16 ((V) 516,
Ul 47311), and rail582 (VI 582, |0| 55515).
32

---

Baselines.
We adopt the same baselines as prior work, including:
Random. Samples candidates uniformly at random over multiple trials, selects the best within 240 seconds.
Greedy algorithm [61]. Iterativlly adds the element with the largest marginal gain, achiev- ing (1 1/e) approximation.
Gurobi. Exact MIP solver, time-limited 120 seconds per instance. The version used is Gurobi 12.01.
EGN [35]. Optimizes a probabilistic objective with naive rounding; does not guarantee feasibility during optimization.
CardNN [88]. One-shot neural solvers for cardinalit--oonstranee problems. Main vari- ants: CardNN-S (Sinkhom), CardNN-GS Houmbel-Sinkhomi CardNN -GG (Homotopy For each, CardNN-noTTO variant omits test-time optimization.
UCOM2 [10]. Combinatorial optimization using greedy incremental derandomization. Three variants differ only by test-time augmentation and running time: UCOM2-short (no augmentation, fastest), UCOM2-middle (moderate augmentation, medium time), UCOM2- long (maximal augmentation, longest time).
RL. For the RL baseline, we follow the instructions in [45, 69] to use GraphSage layers [28] as policy network with Actor- Critic [44] algorithm to train on the same problem instances.
G.1 Training
To enhance optimization stability and solution quality, we incorporate several training techniques.
scaling factor. A of scaling factors :[1.0, 0.8, 0.6, 0.4, 0.2, 0.1, 0.05, 0.02, 0.01] are used in the training and inference parallelly, helping get stable decompositions across different data distributions.
rescaling coefficient in Appendix C. 1.1 is referred
An entropy regularization term is applied with a cosine-decayed weight A, initialized at 0.05 and annealed to zero by the 30th epoch, promoting exploration within the hypersimplex.
Convergence speed is controlled via sharpness factor applied the noise perturbation layer when the sigmoid activation function is used in that layer (when using min-max scaling, it is ignored). The sharpness factor is linearly increased from 0.3 the onset of training 1.0 by epoch 80.
Gaussian noise is injected into the model logits throughout training to foster exploration and enhance robustness. The standard deviation of this noise is initially set 0.05 and is reduced to according to cosine decay schedule as training progresses.
The other hyperparameters are listed below:
Dropout: 0.1 (applied only during training).
Optimizer: AdamW.
Learning Rate: 5 10-3
Learning Rate Scheduler: warmup_cosine, with 50 warmup epochs, decaying to mini- mum of 10 10-5
Weight Decay: 1 10-4
Epochs: 80.
Batch Size: 4.
Seed: 42.
Workers: 16 CPU worker threads for data loading, preprocessing, and decomposition with multiple scaling factors.
G.2 Inference strategies and local improvement
We evaluate our model using three distinct inference strategies-Shhe Short, Medium, and Long- each balancing computational efficiency and local improvement:
33

---

Local improvement. To further refine the candidate solution, we employ a local search algorithm based on iterative element replacement. At each step, the algorithm considers replacing a single element in the current solution set with one from outside the set (within a defined candidate pool), accepting only replacements that yield a strictly improved objective value. The procedure terminates when no improving replacements are found or when the maximum iteration count is reached.
Short: For each instance, 50 decomposed sets are generated from cach scaling factor and
the best among them is chosen the result, with no further local improvement applied.
Medium:
For each instance, 100 decomposed sets are generated from each scaling factor and the best among them is chosen as the base set. The base set then undergoes the local improvement procedure, performed for up to 10 iterations. The candidate pool consists of the first nodes produced by the scaling factor 0.1 that is not present in the base set.
Long: For each instance, 5 additional augmented graphs are generated (with 0-30% feature noise and 0-30% random edge dropout). For each graph, decomposed sets are generated from each scaling factor and the best among them is chosen as the base set. Local im- provement is performed for up to k iterations on the original graph, with the candidate pool includes all nodes that appears in decomposed sets across from the scaling factor where the base set is selected. The best solution found among all augmented graphs is selected as the final result for the instance.
G.3 Ablation study: local improvement candidate pool selection
To demonstrate that the strategic selection of nodes in our candidate pool provides meaningful benefits, we conducted an ablation study comparing our decomposition based candidate pool against random alternative of equal size. In this ablation test, we maintain the same pre-local improvement solution (the base set) as the starting point for both approaches. The original candidate pool is constructed using our medium and long methods. The alternative candidate pool retains the same base set but replaces the remaining candidates with randomly selected nodes, ensuring both pools have identical size for fair comparison.
Table 1: Ablation study comparing decomposition- based candidate pool versus random alternative. Improvement percentages over the base set.
rand500 k=10
rand 1000
rand500 k=50
rand
Method
k=20
k=
Medium
Long
Medium
Long
Medium
Long
Medium
Long
Decomposition based (Ours)
2.41%
3.28%
5.15%
8.09%
2.11% 0.43%
3.89%
3.83% 2.84%
8.07%
Random Alternative
0.23%
1.02%
3.03%
5.74%
2.39%
5.79%
We evaluate both local improvement strategies across medium and long inference modes. The results, Table 1, demonstrate that our strategic candidate selection provides consistent improvements over random selection, validating that our local improvement procedure benefits specifically from the candidate pool construction from our decomposition rather than simply having access to additional nodes for local improvement.
G.4 Ablation study on Gurott
We also tested two versions of the "short+Gurobi" approach on the random datasets, one with a time limit near our "medium" method, and for some settings, an version given the time close to our "Iong" method. When the instance size and the cardinality constraint are small (k = 10 on Random 500), "short+Gurobi" performs slightly better than other methods. For larger instances like Random 500 with k = 50 and Random 1000, our "medium" and "long" approaches show their advantages and achieved similar or better results, indicating that our local improvement technique effectively constrains the solution space and works better even compared to the well-optimized Gurobi Solver. In addition, the Short+Gurobi method shows much better cost-efficiency compared to the pure Gurobi method, showing the potential of our method to serve as an efficient initial solution for structured solvers, significantly reducing overall computation time. The results of these tests can be found in Table 5 and Table 6.
34

---

G.5 Ablation tests for UCOM2
As stated in Section 5.2, we categorize UCOM2 as a non-leaming method and conduct several ablation studies to substantiate this classification. Specifically, we evaluate two variants: setting the neural network output zero (UCOM2-zerostat-sshon and 1 (UCOMM2-andomsstat) Both ablations disregard the output of the neural network. We find that UCOM2-7erostart- UCOM2-randommstar attains similar performance to all three UCOM2 variants, depending on the number of random samples generated. These results demonstrate that UCOM2's s effectiveness is in large part due to their greedy module and the fact that the maximum coverage objective is monotone submodular function.
and to random uniform values between
achieves results nearly identical to the standard short variant, while
Table 2: Ablation results for UCOM2 variants on Random500. Running time (time): smaller is better. Objective (obj): larger is better. Standard deviations capture variability.
Random500, & = 10
Random500, à = 50
Method
Time.
Objt
Time
Objt
UCOM2-2cnostatt-he
0.1089 + 0.0309s
15551.01 + 367.12
0.0885 + 0.1032s
44311.87 + 819.96
UCOM2-randosstarr
0.8862 0.1288s
15294.04
408.52
0.6957
169%
44237.92
824.05
UCOM2-randoristarr
1tt----annndosstt--meeediue medimu
3.8521 0.2770s
15586.95
360.89
15.4367
0.0493s
44867.19
741.85
UCOM2-randomsstare
35.9862 2.5628s
15672.89
351.74
30.5812
0.0850s
44923.74
754.78
UCOM2-shovt
1.0411 0.0827s
15253.35 + 370.00
0.7392 + 0.0150s
44208.95
768.68
UCOM2-medine
4.1891 + 0. 1150s
15589.25
+: 363.43
16.0005 +: 0.0408s
44852.82
765.11
UCOM2-long
39.2018 0.9474s
15779.45
358.41
31.7577 1 0.0811s
44906.50
761.75
Table 3: Ablation results for UCOM2 variants on Random1000 Running time (time): smaller is better. Objective (obj): larger is better. Standard deviations capture variability.
Random 1000, A: = 20
Random 1000, k 100
Method
Time$
Objt
Time!
Objt
UCOM2-Zerostat--Shor
0.2275 = 0.0164s
30991.19 19 + $28.97
0.1682 1: 0.0360s
88693.99 99 +: 1248.72
UCOM2--andomstarre short
1.6408 = 0.0329s
29878.53
601.10
1.5426 + 0.0449s
88549.61
1342.89
UCOM2-randemstarr medium
9.4358 0.0415s
30437.43 532.00
8.8802
0.0522s
89077.84
1244.72
UCOM2-randomstart-
89.8093 + 0.3444s
30752.49 + 529.91
84.3725 0.4054s
89386.56 + 1245.85
UCOM2-short
1.7342 + 0.0677s
29791.66 1616666-11 + 678.02
1.6216 + 0.0644s
88472.61 + 1261.36
UCOM2-medium
9.5523 1: 0.0620s
30420.69 1 552.66
8. 8.9956 1 0.0890s
89072.92 92 1: 1248.58
UCOM2-long
90.7475 + 0.3342s
30744.61 512.61
85,2663
0.6164s
89408.28 1232.74
On the twitch dataset, UCOM2 uses zero initialization (UCOM2-Zerostar)) in its original implemen- tation, fully ignoring the trained model. To assess the impact of the neural network, also evaluate UCOM2-withmodel on twitch, which yields markedly inferior results. This further supports our observation that all learning-based methods perform poorly Twitch due to the architecture of the encoder network.
Table Ablation results for UCOM2 variants on the Twitch dataset. Running time (time): smaller the better. Objective (obj): the larger the better. The standard deviations are captured to show the variability of the dataset and the method.
Twitch, à
Twitch,
Method
Time|
Ohjt
Time.
Ohif
Ucom2 withmodel short
73.2402
80.55534
18.67 :: 45.72
115.8045
126.7061s
573.67 :: 376.52
333.3645
333.4380s
102.00 41.71
532.9243
585.9112s
3018.17 + 5208.31
Ucom2 withmodel loog
659.8775 1 719 16588
150.00 1. 48.88
1054,5567 1 1160.6106s
3029.67 1 $202.21
1oom2-zerostart-shee
17.8031 18.4783s
25853.00 1112.59
30526.00
Ucom2-zerostare nomn---eostart-mmdiuum
19.6806 = 19,8771s
25858. 17 = 11206.89
21.6114 + 21.3478.
30544.17 + 13052.91
Ucom2- 2e12---eettrr-ooggg
22.0589 = 21.6869s
25858.17
= 11206.89
27.2170 1: 25. 56.6664s
30544.17 1 13052.91
G.6 Detailed results
Below are the plots and tables showing the full detailed test results. The raw numerical results are given in Table 5 to Table 8. The standard deviation are captured show the variability of the dataset and the method.
35

---

Figure Performance comparison of our method against baseline approaches across Learning without TTO, on multiple datasets. Metries used are inference time (lower is better) and objective value (higher better). the Learning without TTO setting, our short version consistently outperforms all baselines in both inference time and objective value, demonstrating strong learning capability.
objective better)
Random500, k= 10
objective (higher is better)
Random500, k= 50
16000
14000
12000
10000
8000
20
40
60
25
50
75
100
125
Inference time (seconds)
inference (seconds)
objective (higher better)
Random1000,
objective (higher is better)
Random1000, 100
90000
30000
85000
25000
80000
20000
65000
15000
Inference time (seconds)
Inference time (seconds)
(higher better)
Railway, k= 20
objective (higher better)
Railway, k= 50
7700
5600
5500
5400
7400
5300
7300
5200
7200
7100
25
50
75
100
125
50
75
100
125
Inference
(seconds)
Inference (seconds)
objective (higher better)
Twitch, 20
objective (higher is better)
Twitch, k=
30000
40000
25000
20000
30000
20000
10000
5000
inforence time (seconds)
inference time (seconds)
Gurobi (120s)
Ucom2-long
(120s)
CardNN-HGS
Ours-long
Greedy
CordreN-noTTo.s
RL (GNN + Actor-Critic)
Ours-short
short+Gurobl (medium) (long)
Ucom2-short
CardNN-S
Ours-medium
Ucom2-medlum
CardRN-nnTTO-HGG
CardNN-GS
36

---

Figure Performance comparison of our method against baseline approaches across Learning with TTO, on multiple datasets. Metrics used are inference time (lower is better) and objectíve value (higher better). When extended medium and long versions, our method surpasses most TTO-based baselines across datasets, with the exception of the Twitch dataset.
objective (higher better)
Random500, k= 10
objective (higher better)
Twitch, k= 50
16500
60000
50000
16000
40000
15500
30000
15000
20000
10000
14500
10
20
30
40
20
40
60
80
100
inference time (seconds)
Inference time (seconds)
(higher better)
Random1000, k= 20
objective (higher is better)
Random1000, 100
32000
90000
88000
31000
86000
30000
84000
29000
80000
Inference time (seconds)
Inference time (seconds)
objective (higher better)
Railway, k= 20
objective (higher better)
Railway, k= 50
5600
7650
7600
5500
7550
7500
5400
7450
5350
7400
15
20
25
0
10
20
30
40
Inference time (seconds)
Inference time (seconds)
Twitch, 20
objective (higher is better)
Twitch, k=
40000
60000
50000
objective (higher
40000
20000
30000
20000
10000
inforence time (seconds)
inference time (seconds)
(120s)
Ucom2-long
(120s)
CardNN-HGS
Ours-long
Greedy
CordreN-noTTo.s
RL (GNN + Actor-Critic)
Ours-short
short+Gurobl (medium) (long)
Ucom2-short
CardNN-S
Ours-medium
Ucom2-medlum
CardRN--nTTO-HGG
CardNN-GS
37

---

Figure 5: Performance comparison of method against baseline approaches across Learningttraditonall methods on multiple datasets. Metrics used are inference time (lower is better) and objective value (higher is better). While greedy is efficient baseline with strong approxima- tion guarantee, our method performs competitively and is capable of outperforming it on datasets like Random500 for larger values k. We are also able to outperform UCOM in several cases (c.g.. Random I (00 and Railway), though there are instances where greedy and/or UCOM perform the best, such the Twitch dataset.
objective (higher better)
Random500, k=
objective (higher better)
Random500,
16500
46000
15500
44000
15000
42000
14500
40000
100
125
Inference time (seconds)
inference time (seconds)
objective (higher is better)
Random1000, k= 20
objective (higher is better)
92500
Random1000, k= 100
32000
31000
87500
30000
85000
29000
80000
20
40
60
80
50
75
100
125
Inference time (seconds)
Inference time (seconds)
(higher better)
Railway,
objective (higher is better)
Railway, k= 50
7800
5700
7700
5600
7600
5500
7500
5300
50
100
125
Inference time (seconds)
Inference time (seconds)
Twitch, k= 20
objective (higher is better)
Twitch, k= 50
60000
40000
50000
objective (higher
30000
40000
20000
30000
20000
10000
20
40
60
20
40
60
80
Inference time (seconds)
Inference time (seconds)
Gurobi (120s)
Ucom2-long CordNN-noTTO-5
EGN-naive (120s)
CardNN-HGS Ours-short
Ours-long
Greedy
(GNN Actor-Critic)
short+Gurobi (medium)
Ucom2-short
CardNN-noTTO-55 CordNN-nOTTO-HGS
CardNN-S
Ours-medium
short+Gurohh (long)
Ucom2-medlum
CordNNIGG
38

---

Figure 6: Performance comparison of our method against all baseline approaches. Metrics used are inference time (lower is better) and objective value (higher better). Random500, k=
objective (higher is better)
Random500, k=
16000
14000
40000
12000
objective
10000
35000
8000
30000
Inference time (seconds)
Inference time (seconds)
objective (higher better)
Random1000, k= 20
objective (higher is better)
Random1000, k= 100
90000
30000
85000
80000
75000
20000
70000
65000
15000
0
25
50
75
100
125
50
75
100
125
Inference time (seconds)
Inference time (seconds)
Railway, k=
objective (higher is better)
Railway, k= 50
5600
7700
(higher is
7600
5400
7500
7400
5200
7300
5000
7200
inference time (seconds)
inference time (seconds)
objective (higher better)
Twitch, k= 20
objective (higher is better)
Twitch, k= 50
60000
50000
30000
40000
30000
20000
20000
10000
10000
50
100
50
100
150
inference time (seconds)
inference time (seconds)
Gurobi (120s)
Ucom2-long
EGN-naive (120s)
CardNN-HGS
Ours-long
CordNN--oTTO-S
short+Gurobi (medium)
Ucom2-short
CardNW-noTTO-GS
CardNN-S CardNN-GS
Ours-medium
short+Gurobi (long)
CordNW-noTTO-HGS
39

---

Table 5: Maximum Coverage rand500. Two budgets: k=10 and k=50. Time: lower is better;
Obj: higher is better.
Setup
A = 10
== 50
Method
Time
Obji
Time!
Obji
Non-learning / Traditional
Random (240s)
240.0000s 0.0000s
13372.76
308.83
240.0000s
0.0000s
36786.89 + 655.45
Gurohi (120%)
1.5744s 0.5376s
15714.90
346.84
120.0651s
0.0268s
44880.59 7.13
Greedy
0.0572s 0.0502s
15640.99
360.60
0.1210s
0.0563s
44597.56 1: 848. 28
Ucom2-short
1.0411s + 0.0827s
15253.35 +: 370.00
0.7392s
0.0150s
44208.95 + 768.68 68
-medium
4.1891s + 0.1150s
15589.25 + 363.43
16.0005s = 0.0408s
44852.82 = 765.11
Ucom2-long
39.2018s = 0.9474s
15679.45
358.41
31.7587s 0.0811s
44906.50 + 761.75
Learning (no TTO)
CardNN-noTTO-S
1.6880 + 0.0791
9231.54 + 827.09
1.7211s 0.0661s
33055.87 1211.03
CordNN-noTTO-GG
7,4571s +: 0.0300s
13635.05
303.36
9.5240s
0.5770s
37120.46 1: 610,25
CardNN-nOTTO-IIGS
9.6954s 0.0429s
13671, 19 302.84
12.2502s 1 0. 1068s
37164.81 1 678.19 19
EGN-naive (120s)
53.0409; + 5.3879s
15262.76
401.10
120.1361s 0.0796s
41272.68 + 737.36
RL (GNN+
0.0696s 0.0028s
14741.26
322.51
0.2471s 0.0290s
39510.96 975.21
Learning (with TTO)
CardNN-S
7.5387s 1 0.6576s
15381,66 60 1. 394.79
4.9843s 0.2941s
1197.222 1 814.87
CardNN-GS
26.3746s + 0.0831s
15683 40 +: 350.79 15685.39
26.8944s + 0.1131s
44724.42 + 773.70
CardNN-HGS
38.8875s + 0.1065s
349.83
39.6041s 0.1122s
44745.20 + 769.93
Ours
Ours-short
0.5786s + 0.0094s
15177.77 + 344.68
1.1078s
0.0149s
41247.80 + 965.48
Ours-medium
1.0546s + 0.0146s
15410.23
353.91
2.1212s
0.0096s
43152.87 1004,95
Ours-long
12.0878s 1 0.1365s
15714.63
354.22
24.9885s
0.3543s
44866.84 1 876.78
short+ Gurobi (medium)
2.0622s
0.1122s
44894.62 1 951,89
Gurobi (long)
2.31855 0.5136s
15738.62 343.40
25.0653s
0.0609s
45090.41 887.32
Table 6: Maximum Coverage on rand1000. Two budgets: k= and 1=100. Time: lower better;
Obj: higher is better.
Setup
k 20
100
Method
Time.
Objt
Time
Objt
Non-learning / Traditional
Random (240s)
240.0000s = 0.0000s
24133.50 +: 390.27
240.0000s +: 0.0000s
70S27.31 + 105187
Gurobi (120s)
37.2985s + 30.0300s
31347.62 509.75
120.1395s 0.0526s
89696.83
1231.76
Greedy
0.1905s 0.0998s
31105.89 506.23
0.4609s 0.1074s
88685.40) 1225.67
Ucom2-short
1.7342s = 0.0677s
29791.66 678.02
1.6216s + 0.0644s
88472.61 = 1261.36
Ucom2-mediug
9.5523s + 0.0620s
30420.69 + 552.66
8.9956s + 0.0890s
89072.92 + 1248.58
Ucom2-long
90.7475% 0.3342s
30744.61 512.61
85.2663s + 0.61
89408.28 1232.74
Learning (no TTO)
CurdNN-noTOO-SS
1.8693s 1. 0.0018s
18458.92 1: 1283.6
1.8810s 0.0453s
65793.40 1478.50
CardNN-no
14.1629k 0.0301s
24309.37
465.91
22.3352s + 0.0942s
71620.38 + 1026.81
CardNN-moTTO-HHC
19,3888 0.0532s
25135.52
436.21
28.3368x 4 0.1218s
71604.61
1010.17
EGN-naive (120s)
120.0105s 0.3980s
29968.04
563.02
120.3565s
0.1600s
81166. 12 1391.02
RL (GNN+AAtor-Critte
0.1021s 1 0.0029s
29912.14 571.12
0.4652s 0.0029s
81158.54 1215.23
Learning (with TTO)
CardNN-S
7.6054x 1 0.6608s
30461.73 7. 590.50
5.0909 0.3016s
83319.37
1324.81
CardNN-GS
57.5445s 0.0670s
31250.56
528.72
60.7239s 4 0.0665s
89269.41 1253.68
CardNN-HGS
85.4505s 0.0952s
31250.47 526.03
89.3385s = 0.1235s
89280.17 1261.34
Ours
Ours-short
0.8248s + 0.0312s
29810.12 + 586.05
1.906s + 0.0284s
81357.29 + 1277.84
Ours-medium
1.4175s + 0.0633s
30257.05 606.07
3.6669s 0.0582s
84186.79 79 1336.48
Ours-long
16.6007s 0.4632s
31230.26 476.25
46.1200s = 0.6998s
88796.03 1327.83
Short+Gurobi (medium)
2.0868s = 0.1001s
30098.64 + 767.38
5,2979: + 0.1202s
82200.65 + 2609,87
Short+Gurobi (long)
1.5.822& 2.8134s
31332. 18 + 471.59
46.2701s + 0.3331s
89509.90 1316.43
40

---

Table 7: Maximum Coverage on railway. Two budgets: 2= and k=50. Time: lower better; Obj:
higher better.
Setup
20
Method
Time|
Objt
Timel
Objt
Non-learning / Traditional
Random (240s)
240.0000s + 0.0000s
5291.67 + 73.92
240.0000s 0.0000s
7367.00 76.97
Gurobi (120s)
121.0590s + 0.0318s
5631.67 + 28.77
121.0329s 0.0613s
7604.67
62.38
Greedy
0.7271s 1 0.0251s
5617.00 1: 49.00
1.3196s +: 0.5774s
7630.00
72.19
Ucom2-short
2.2988s 1 0.2026s
5512.67 1 56.89
2,4537s 1 0.3920s
7594.67 1 68.72
Ucom2-medium
18.2307s 2.4105s
5560.33
+ 44.56
17.1635s 2.2504s
7618.00 79.76
Ucom2-long
18.3035s 2.4544s
5574.33
58.79
17.1988s = 2.2001s
7617.00 81.19
Learning (no TTO)
CardNN-no TTT-SS
1.9287s 1: 0.2161s
5074.33 + 59.41
2.1892x + 0.2505s
7193.00 80.72
CordNN-nTTOO
5,9863s 0.5143s
5269.00
7.3275s 0.3261s
7348.33 80.31
CardNN-noTTT-HGGS
8,8791s 0.7784s
5266.67 76.01
1082211
7359.00
70.89
FGN--naiv (120s)
120.6763s 0.2931s
5234.67
121,3351s
0.9133s
7408.33 72.82
RL (GNN+
0.2191s 0.0030s
$
0.2191s + 0.0031s
7456.67 57.14
Learning (with TTO)
CardNN-S
2.7580s 0.2705s
5462.00 + 56.00
3.0035s + 0.2782s
7433.33
63.34
CardNN-GS
8.6626s 1 0.5672s
5441.67 1 58.77
15 68.66666 1 1.0987s
7650.00 73.33
CardNN-HGS
15.2983s + 0.5441s
5535.67 1 64.52
24.7941s 0.9907s
7650.00 +: 88.71
Ours
Ours-short
1,8559 + 0.0458s
5343.00 + 89.17
2.0838s + 0.0142s
7411.67 1.61 + $5,08
Ours-medium
2.5628s 1 0.0418s
5437.00 1 66.84
3,4385: 1 0.0532s
7512.00 1: 63.85
Ours-long
27.0344s = 0.9617s
5613.33 + 55.58
43.2777s = 1.3728s
7631.00 + 75.19
Table Maximum Coverage on twitch. Two budgets: k=20 and k==00. Time: lower is better; Obj:
higher is better.
Setup
k 20
50
Method
Time
Obji
Time
Objt
Non-Icarning/ Traditional
Random (240s)
240.0000s
0.0000s
12889.17 17 5636.10
240.0000 + 0.0000s
16050..0 6715.32
Gurobi (120s)
0.8221s
0.5700s
25864.00 +: 10223.00
0.7961s + 0.6577s
30560.33 1: 11922.45
Greedy
0.25364
25855.50
11207.33
0.3883s
Ucom2-short
17.8031s
18.4783s
25833.00 + 11212.59
17.3739% = 18.1940s
30526.00 + 13043.86
Ucom2-medium
19.6806s
19.877
25858. 17 +: 11206.89
21.6114 = 21.34786
30544. 17 + 13052.91
long
22.0589h
25.6604s
Learning (no TTO)
CardNN noTSO-
0.8636s 0.2075s
77.00 51.47
0.9635s + 0.4585x
170.50 158.15
CarNNN-nTTOOGG.
L.574%s 0.3842s
376.00
L6334s 1 0.6782s
1574.33 6.04
CurdNN-noTTO-HGS
2,1831s 0.7328s
1242.33
499.23
2.3674s + 0.7858s
1898.00
506.67
BGN-naive (120s)
108. 30303
24.35694
152.67 12.22
105.46055 20.7886s
247.17 31.88
RL (GNN-
0.1694s 0.0028s
2379.50
1471.50
0.2905s 0.0030s
5435.50
3318.67
Learning (with TTO)
CardNN-S
5.1258s = 0.6503s
25863.83
11198.96
5.5767s + 0,5135s
30556.00
13063.12
CardNN-GS
10.1648s 1.1928s
25864.00 11198.73
9.5794s + 1,5230s
30560.67
13061.60
CardNN HGS
22.3602s 1. 1.2962s
25864.00 + 11198.73
19.7813s 3.4102s
30560.83 + 13061.35
Ours
Ours-short
1.0975s 0.7446x
7689.00 + 5712.56
1.1485s + 0.7596s
10227.04 $537.20
Ours-medium
1.6693s = 0.9268s
8887.83 1: 5087.20
1.9401s + 1.0147s
11858.50 = 4793.61
Ours-long
26.4401s 15.9632s
18526.83 8671.00
54.4778s + 32.5091s
24509.83 11171.33
41

---

H Max-k-Cut Ablation
Datasets. We conduct experiments on datasets. The IMDB-BINARY dataset [92] consists of 1000 graphs. The Erdös Rényi dataset consists of 1000 synthetic graphs generated under the G(n. p) model. For each graph, the number of nodes n is drawn uniformly from {50.... ...,, 100} and each candidate edge is included independently with probability p = 0.15. Our experiments use the following split for both datasets. 60% of the graphs are allocated for training, 20% for validation, and the final 20% for testing. Within each split, any graphs with fewer than k nodes are excluded. We compare in two settings, one of small and one of large ki where l is selected as a fraction of the average number of nodes in the dataset. For small & we pick the fraction to be 0.25 of the node average and for the large h we pick 0.75.
Random sampling + decomp. The purpose of this baseline is to highlight the contribution of optimization and the neural network in the performance. this baseline, we randomly sample single point in An,k, decompose it, and then report the value of the best performing set in the decomposition.
Direct optimization + decomp. In the direct optimization approach, we optimize a vector E R" using the perturbation method described Section 4.1, i.e., we treat it as an additive perturbation on the vector (k/n, k/n,...,K k/n) in A We optimize the perturbation x by decomposing the perturbed point and optimizing the value of the extension with gradient descent (Adam [40]). For IMDB-BINARY, we set the learning rate to 0.015, and for Erdōs-Rényi, the learning rate was set to 0.012. Each optimization run consists 150 update steps.
NN + Optimization + Decomp. The neural network approach proceeds in similar fashion as the direct optimization one. Here, we use a neural network to generate the perturbation vector E TR" for the perturbation approach described in Section 4.1. The perturbed interior point is decomposed and we updated the parameters of the neural network by gradient descent on the extension. Here, the neural network is an eight-layer GatedGraphConv network [49] followed by two linear layers. Node features include random-waid positional encodings generated with AddRandom walk length 10. The neural network in this case is optimized directly on the test data. The results presented in the table below.
[19] with
Standard SSL. In the standard SSL baseline, we train the same architecture separate training data and do model selection using a validation set. Then we report the performance of the selected model (without any finetuning) on the test set. We observe that while the trained SSL baseline is not able to match the performance produces performance that is competitive with direct optimization and greedy for large k.
neural net directly optimized on the test set, it consistently
Table 9: Test-set performance (mean + std) on IMDB-BINARY graphs (avg. nodes) and Erdös- Rényi graphs (avg. 75 nodes, edge density 0.15).
BMDB-BINARE ==
Erdös Rényi
Method
k= 15
k: == 15
k = 60
Greedy Algorithm
1.000 + 0.002
0,801 + 0.195
0.985 1 0.015
0.900 + 0.047
Random Sampling Decomp
0,881 1 0.140
0.850 : 0.179
0.753
1: 0.038
0.761 1: 0.041
Direct optimization Decomp
0.960 1 0.064
0.922
0.833 0.025
0.844 1: 0.043
NN + Optimization Decomp
0.971 + 0.041
0.932 0.089
0.910 0.045
0.902 + 0.041
Standard SSL + Decomp
0.956 + 0.049
0.905 0.117
0.035 0.899
0.889 + 0.044
42

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We claim to provide an end-to-end pipeline for neural combinatorial optimiza- tion with constraints (section 4), which has applications several fundamental constraint classes (section 4.2.1 and 4.2.2), all of which are clearly given in the paper. In section 5, we support our claims with experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The limitations are discussed in the experiment section and also in the con- clusion. Also, when we discuss the general pipeline we do not claim it covers all possible constrained CO problems.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
43

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Assumptions are stated in theorem statements and all proofs are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All the details of the experiments such as training and dataset details are provided either in the main body of the paper appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
44

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: All the datasets public. Our code is available https: Baaaaeee//eeuraaoombbbiieiaaa Combinatorial Optimizationnn wwtth__ Constraints 3aieee--445///8 3485/README... md
/ /aaonymmou poppnn www.n.sciencee.....eeeccppcpp
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines fattps://nips.om cc/ Sttps///ggiidee/deeeeuuaeee www.:/wwwwwsiisooooooooooooooeee onPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//n //nips.ccc wttp:/ccppppppp....eeeeeeeelepee http://ggiiieeeeeddunniieeeeeee CCodeSubmissseeeeeee aasssooooiccyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the details of the experiments such as training and dataset details are provided either in the main body of the paper appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: We do not report eтror bars or statistical significance due to computational and time constraints; is common in combinatorial optimization, we report mean results over multiple problem instances.
Guidelines:
The answer NA means that the paper does not include experiments.
45

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Details are provided the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: / httpea/www..ecppppp.t/ttttaaaaaa
Answer: [Yes]
Justification: Given the focus on foundations, we do not have human subjects or sensitive data and do not perceive risks of harm or misuse.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdictio).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The societal impact of improved combinatorial optimization or neural combi- natorial optimization techniques are minimal.
46

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not contain data or models that have a high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We provide citations to all data and code we use. All material is licensed for such use.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
47

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com comddatases has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
There are no new assets released this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
There were no human subjects in this work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
No human subjects or study participants were used in this research.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
48

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs were not used in the core methods of this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy http::://neurppae cc co/oomfereecece//22255555 for what should or should not be described.
49


Reviews:
[{"review_id": "d4VrxYn41h", "reviewer": "Reviewer_7pF1", "summary": "The paper introduces an end-to-end differentiable framework for combinatorial optimization with discrete constraints. The paper leverages geometric insights to decompose neural network predictions into convex combination of feasible sets.  During training, it learns to output a point within the convex hull of feasible solutions. The loss is computed by decomposing the point and evaluating the objective. During test time, the prediction is decomposed and the best feasible solution is selected. In experiment, it achieves good results over machine learning baselines and classical algorithms.", "questions": "1. Could you comment on how well this approach scale to larger instances? How computationally heavy is differentiating through the decomposition steps? \n2. Can you provide a summary of the results for other problem domains in appendix?\n3. Why did you choose to present ablation study results on max-cut which is different from the coverage problem?", "limitations": "See weakness 1.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper presents a novel idea of decomposing an interior point of the convex hull of solutions and develops an end-to-end framework for solving combinatorial optimization based on it. The claims are supported by both theoretical guarantees and empirical evidence.\n2. Overall, the presentation of the paper is easy to follow. \n\n\nWeaknesses:\n\n1. This method could only work well for problems where feasible solutions are easy to obtain. For some problems where feasible solutions are difficult to find, I can imagine that this method will struggle. \n2. Overall, the results look good for the coverage problem. But the results in appendix for other problems don’t seem to be impressive (also it is kind of hard to read, maybe I misinterpreted. See weakness 3).\n3. The experimental results in Table 1 are difficult to read, especially  for the last row where there is a cluster of crosses where same of them with similar colors are close to each other. It would be better to have a numerical representation of those figures. In addition, the result tables in appendix are how to read as well. For example, Table 11 is not well-formatted where some columns overlap with each other. Can you also highlight the best rows in bold and provide a text summary of the results.", "was_revised": true, "final_justification": "I have read the authors' rebuttal. Most concerns are resolved and want to maintain my score.", "rebuttal": "We would like to thank the reviewer for their thoughtful and constructive feedback on our work. \n\n- The reviewer makes a point about the applicability of the method to problems where feasible solutions are difficult to obtain. Indeed, not being able to efficiently construct feasible solutions poses a challenge and our proposed method works best when obtaining feasible solutions is computationally tractable. This allows us to construct a decomposition by fetching feasible sets at each iteration. On the other hand, there are plausible ways in which this approach can be naturally extended to the setting where feasible solutions are hard to construct. For instance, one could define a polytope of 'efficiently computable infeasible solutions' and optimize over them by scoring the amount of constraint violation. This could be used as warm-starts that are passed to a discrete search algorithm that then attempts to construct a feasible solution. This is an interesting future direction but it introduces an additional layer of complexity in terms of benchmarking and implementation so we decided to prioritize simpler problems.\n\nThe reviewer also asked for a summary of the results in the appendix, particularly for problems other than max coverage.\n\n- To summarize the results in the appendix, our method achieves strong empirical performance on the max coverage problem and is competitive with the greedy approach on the max k-cut problem. The appendix also includes several ablation studies that demonstrate the effectiveness of our medium and long methods, as well as the quality of candidate sets returned by the trained model. Additionally, we highlight our focus on the cardinality constraint and discuss the shortcomings of the best-known neural baseline. \n\n- Below, we expand on these points. \n \n\n  - While the appendix presents extensive experiments on the max coverage problem—using various cardinality constraints and datasets—as well as results on the max k-cut problem, we are also in the process of obtaining additional results for other problems. Below we provide preliminary results for another fundamental combinatorial problem: the Facility Location problem. Here we present the performance of our short method (with no Test-Time Optimization) against the Greedy, an RL baseline, and the CardNN approach without Test-Time Optimization (TTO). We consider two cardinality constraints cases that are k=5 and k=20 and report the objective function values. Note that Facility Location is a minimization problem and smaller objective values are better. The experiments are run on synthetic data where each instance contains 500 points. \n\n  | Method | k=5 | k=20 |\n  |-------|-------|-------|\n  |Ours short  |\t16.1775\t| 4.1373 |\n  | CardNN-S-NoTTO-NoKmeans |\t86.2816\t| 17.6436 |\n  |Greedy |\t17.3714\t| 2.9644 |\n  |RL\t| 35.9455\t| 6.8085 |\n\n   - In Appendix G.3, we run an ablation study to demonstrate that in the medium and long versions of our approach, the strategic selection of nodes in our candidate pool provides meaningful benefits. The results in Table 2 demonstrate that our strategic candidate selection provides consistent improvements over random selection, validating that our local improvement procedure benefits specifically from the candidate pool construction via our decomposition, rather than simply from having access to additional nodes for local improvement.\n\n   - Note that we heavily emphasized cardinality constraints in the experiments because they contain practically important problems like max-coverage. Despite the simplicity of the constraint, we found that existing solutions in the neural combinatorial optimization literature did not provide sufficiently simple and/or effective ways of tackling the constraint while achieving strong results. The ablation study we performed in page 31 (Appendix G.4)  highlights this issue with the best known neural baseline. Through our projection-decomposition-extension scheme, we provide an intuitive and empirically compelling approach to solving the problem in a differentiable way, and our experimental results support that.\n\n> It would be better to have a numerical representation of those figures. In addition, the result tables in appendix are how to read as well.\n\n- The reviewer also raises a valid point about the presentation of the results which we completely acknowledge. We conducted a comprehensive set of experiments on our method but also on the competing baselines to ensure a fair evaluation. There are several components to those comparisons. Different datasets, different parameters for the constraint, as well as the difference between baselines that involve learning and those that don't. While preparing the paper, it was not clear to us what is the best way to present these results, because the full table (as can be seen in the appendix G.5) is also quite dense and hard to read. We are going to do our best to reformat the results to highlight some of the key takeaways according to the reviewer's comment, but we welcome any further recommendations on how we could present the results.\n\n- We will change both the marker shapes and colors to improve readability. We will clean up Tables 9–11 and consider splitting the tables or reducing precision to improve readability. We also note Appendix G.5 contains larger versions of all plots for more detailed comparison as well as raw numbers for experiments in tables 9 to 11.\n\n>Could you comment on how well this approach scale to larger instances? How computationally heavy is differentiating through the decomposition steps?\n\n- Regarding computational efficiency, the detailed cost depends on the problem and the cost of the decomposition, which in turn depends on the algorithm used to obtain feasible sets and the ability to compute intersections with the boundary of the polytope. Given a point in the polytope, the decomposition applies iteratively a transformation to the point until the termination criterion is reached. For the examples we discussed, that is roughly $O(n)$ (in the worst case) iterations given by Equation (3). For the backprop step, the gradients are passing through the coefficients of the decomposition, where we have one coefficient per iterate. Therefore, the cost of gradient computation for each coefficient depends linearly on the number of iterations it took to compute the coefficient because the chain rule for a given coefficient will have to go through all the iterates before it. Crucially, the most costly part is actually the decomposition itself and the backward pass does not increase the overall time significantly. \nAs a general rule, the closer the neural net prediction is to a feasible solution, the fewer the decomposition steps and hence the method becomes more efficient. How close the predictions are to feasible depends on practical implementation, how the architecture aligns with the problem, etc.\nWe were able to run our experiments containing instances with several thousands of nodes on a single 48GB GPU.  To make the point about the cost of backprop clearer, we provide some time measurements in the coverage problem. \n\n| Setting | Back-prop time  |\n|----------|----------|\n| 1500 nodes, k = 10    | 17.08s    |\n| 1500 nodes, k = 50    | 10.42s    |\n| 3000 nodes, k = 20    | 12.54s   |\n| 3000 nodes, k = 100    | 10.49s   |\n| 6000 nodes, k = 100    | 16.32s   |\n| 6000 nodes, k = 300    | 9.98s    |\n\n- For a given instance size, the decomposition will run at most $n-k$ times which explains why for smaller values of $k$ the cost is larger. Overall, we see that the cost of backprop is not significantly increased as we scale up the instances.\n\n> Why did you choose to present ablation study results on max-cut which is different from the coverage problem?\n\n- Finally, the reason for choosing max k-cut for the ablation was to highlight another problem where our approach can work. It is also worth noting that the same ablation shows that our decomposition-based extension also works with direct optimization on the input space (i.e., without a neural network). Even though the constructed function is non-convex, one can just directly run Adam on a random starting point in the hypercube to find a solution for the problem. If the paper is accepted, we are planning to include even more results along those lines to further bolster our claims."}, {"review_id": "Kg8ysqLYSS", "reviewer": "Reviewer_6w4h", "summary": "This work aims to improve self-supervised learning to predict good feasible solutions for combinatorial optimization problems. This is done by decomposing predicted continuous solutions as convex combinations of integer solutions. By doing so, we can take the best integer solution from this decomposition, which is guaranteed to have objective value at least as good as the value of the continuous solution. The paper ensures that this decomposition is differentiable, so it can be integrated into the learning process. This decomposition relies on the classical Carathéodory's theorem, which guarantees that we can express any point in a polytope as a convex combination of n+1 vertices (in this case, integer feasible solutions), where n is the dimension of the polytope. Since this decomposition is hard, this requires some strong oracles for this decomposition to be possible, but the paper shows that this can be done effectively in some more tractable cases, in particular cardinality constraints, partition matroids, spanning trees, and a continuous relaxation of independent sets. Experiments are done on the maximum coverage problem, which uses cardinality constraints, and compared with both learning and non-learning baselines.", "questions": "1. Request for one more baseline: In my view, learned methods for combinatorial optimization can be very good at producing high-quality solutions, but often to close the gap to optimality, optimization solvers that do a more structured search such as Gurobi can perform better in practice. I would be interested in seeing what you get when providing to Gurobi the solution to the \"short\" method as an initial solution. Gurobi itself can be viewed as a way to perform test-time optimization, and I would interpret this as a TTO variant of your method rather than a comparison baseline. Would you be able to perform these experiments? This also will help contextualize the improvements that you get from the \"medium\" and \"long\" approaches. I would suggest keeping the time limit here low, so that the total time limit (your \"short\" + Gurobi) is in line with the set of learned approaches. Of course, this experiment would be more meaningful for the larger problems that you cannot solve to optimality with Gurobi.\n\n2. The beginning of Section 3 states that this method applies only to binary problems. It is perfectly fine to focus on binary problems, but could you please clarify what changes would be necessary if you want to apply this to a non-binary integer problem? Can this method be easily adapted, or is there any particular blocker for making this work?\n\n3. Could you add a clearer definition of g in Algorithm 1? I encountered it for the first time when reading Algorithm 1, and it was not clear what it was other than a function that produces the right boundary point.\n\n4. Figure 1 uses min when the rest of the paper uses max. Please make it consistent.\n\n5. Table 1 has a lot of room for improvement in presentation:\n    * I believe this should be a Figure, not a Table?\n    * Please add what TTO means in the caption, especially since this table appears before it is defined.\n    * Please clarify what the marker X means in the caption (average of both inference time and objective?).\n    * These plots are difficult to see: especially when printed, it is small and the individual dots are barely visible. I am not sure if there is any way to make it larger given space constraints, but please see if you can find ways to improve this. In particular, avoid using very bright colors such as yellow. Perhaps experiment with variations in marker shapes as well as color to distinguish between methods of the same type. Optionally, consider increasing the transparency of the dots.\n    * Please consider keeping both the x and y axis the same for each problem class. It is difficult to compare between them. If you do this, you may want to consider removing the Random (240s) result from the main text, and only keep it in the Appendix (with a note mentioning that). This is a very weak baseline dominated by everything else, and makes the plot more difficult to read by extending the axes.\n\n6. Tables 9-11 need cleaning up. Some times have s, others do not. The standard deviations are inconsistently in different lines. Some numbers are even overlapping. If possible, try to make them all be in the same line (perhaps further split the tables, or take away a digit of precision when it makes sense).\n\n7. I believe the references in the Appendix are not the same as the references in the main paper. For example, I see references going above 80, and I spot checked a few of them and they did not make sense. Please fix the Appendix references.", "limitations": "Limitations are addressed in the paper.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The decomposition idea explored in this paper is very interesting. While the existence of this decomposition is a classical result, it is rare to see a practical way to apply this decomposition as far as I know, since it is generally considered to be too expensive in practice for most types of constraints that appear in NP-hard problems. However, it can be made tractable for simple constraints. This makes sense in this learning context, where, 1, even handling simple constraints can be sometimes challenging, and 2, we can sometimes embed the \"hard part\" of the problem into the objective function, like it is done in the maximum coverage example, and leave only a simple constraint to consider. Furthermore, this framework also has the nice property that it provides a generic perspective that can be applied to multiple classes of constraints, which makes it easier for this work to be extended. On the other hand, along these same lines, perhaps a drawback of this method is that it may require a lot of effort to make this work effectively for new classes of constraints, but the paper shows positive results for at least maximum coverage.\n\nThe overall writing is careful, well-structured, and comprehensive, especially the theoretical and methodological portion. Unfortunately, I did not have time in this review to go through all the theoretical proofs in detail in the appendix, but it looks generally comprehensive and the basic ideas at a high level make sense. The computational portion has some room for improvement, but I believe it can be improved in this review process. The computational results are positive but not remarkably strong, which I believe is fine with given that the methodological ideas introduced in this paper are interesting and can potentially be extended to other scenarios. Overall, the quality of this paper is high. I have a few requests for improvement below, mostly on the computational experiments and on readability, but at its core I believe this paper is very solid.", "was_revised": true, "final_justification": "I continue to recommend acceptance. While I agree with other reviewers that there is room for improvement in presentation, I do not believe those issues to be sufficiently major as long as the authors can fix them for the final version. I also believe that this method has good potential for applicability, even if it requires effort to adapt the method to new problems. I acknowledge that there is room for improvement in discussing and providing supporting evidence for applicability, but the authors agreed to include further discussion on this topic.", "rebuttal": "We are thankful for the especially thorough review and their constructive comments. Below we respond to the bulleted questions in order.\n\n- We tested two versions of the “short+Gurobi” approach on the random datasets, one with a time limit near our \"medium\" method, and for some settings, an \"extended time\" version, given the time close to our \"long\" method. When the instance size and the cardinality constraint are small (k = 10 on Random 500), \"short+Gurobi\" performs slightly better than other methods. For larger instances like Random 500 with k = 50 and Random 1000, our \"medium\" and \"long\" approaches show their advantages and achieved similar or better results, indicating that our local improvement technique effectively constrains the solution space and works better even compared to the well-optimized Gurobi Solver.\nIn addition, the short+Gurobi method shows much better cost-efficiency compared to the pure Gurobi method, showing the potential of our method to serve as an efficient initial solution for structured solvers, significantly reducing overall computation time.\n\n**Dataset: Random500**\n| Method         | Time (k=10)           | Obj (k=10)            | Time (k=50)           | Obj (k=50)            |\n|----------------|-----------------------|------------------------|------------------------|------------------------|\n| Ours-short     | 0.5786s ± 0.0094s     | 15177.77 ± 344.68      | 1.1078s ± 0.0149s      | 41247.80 ± 965.48      |\n| Ours-medium    | 1.0546s ± 0.0146s     | 15410.23 ± 353.91      | 2.1212s ± 0.0096s      | 43152.87 ± 1004.95     |\n| Ours-long      | 12.0878s ± 0.1365s    | 15714.63 ± 354.22      | 24.9885s ± 0.3543s     | 44866.84 ± 876.78      |\n| Gurobi (120s)  | 1.5744s ± 0.5376s     | 15714.90 ± 346.84      | 120.0651s ± 0.0268s    | 44880.59 ± 7.132       |\n| short+Gurobi   | 2.3185s ± 0.5136s     | 15758.62 ± 343.40      | 2.0622s ± 0.1122s      | 44894.62 ± 951.89      |\n| short+Gurobi (Extended Time)              |        N/A*               |        N/A                | 25.0653s ± 0.0609s     | 45090.41 ± 887.32      |\n\n\\* Gurobi finishes search in less than 5 seconds, so extended time version is not applicable\n\n**Dataset: Random1000**\n| Method         | Time (k=20)           | Obj (k=20)            | Time (k=100)          | Obj (k=100)           |\n|----------------|------------------------|------------------------|------------------------|------------------------|\n| Ours-short     | 0.8248s ± 0.0312s      | 29810.12 ± 586.05      | 1.9076s ± 0.0284s      | 81357.29 ± 1277.84     |\n| Ours-medium    | 1.4175s ± 0.0633s      | 30257.05 ± 606.07      | 3.6669s ± 0.0582s      | 84186.79 ± 1336.48     |\n| Ours-long      | 16.6007s ± 0.4632s     | 31230.26 ± 476.25      | 46.1200s ± 0.6998s     | 88796.03 ± 1327.83     |\n| Gurobi (120s)  | 37.2985s ± 30.0300s    | 31347.62 ± 509.75      | 120.1395s ± 0.0526s    | 89696.83 ± 1231.76     |\n| short+Gurobi   | 2.0868s ± 0.1001s      | 30098.64 ± 767.38      | 5.2979s ± 0.1202s      | 82200.65 ± 2609.87     |\n| short+Gurobi (Extended Time)    | 15.8728s ± 2.8134s     | 31332.18 ± 471.59      |  46.2701s ± 0.3331s      | 89509.90±1316.43 |\n\n - In general, Carathéodory’s theorem applies to any convex hull. However, the specifics of obtaining an almost-everywhere (a.e.) differentiable extension can vary when moving beyond the Boolean domain and may require domain-specific techniques rather than direct generalization. In particular, Steps 3, 5 and 6 of our Algorithm 1 are tailored to the $\\{0,1\\}$ setting and may require modification in other domains. These steps are problem-specific, and obtaining analogous steps in non-Boolean settings would be a worthwhile contribution on its own. For example, in combinatorial problems over permutations—where we are no longer dealing with $\\{0,1\\}$ assignments—achieving an a.e. differentiable extension typically relies on the Birkhoff decomposition. This approach requires additional problem-specific algorithmic tools. Recent work by Nerem et al. [1] explores this direction in more depth.\n      \n- Thank you for the constructive feedback on the presentation—we sincerely appreciate it. We will incorporate your suggestions in the revised version of the paper.\n     - Clarification on the meaning of each \"X\" in the plots: In each plot, the x-axis represents runtime (where smaller values are better), and the y-axis represents the objective value (where larger values are better). Each colored cross (\"X\") corresponds to a method identified in the legend and indicates that method’s performance in terms of both runtime and objective. The relative positions of the crosses illustrate the trade-off between these two metrics. Across the various settings, our methods consistently appear on or near the Pareto front, demonstrating favorable performance in both dimensions.\n   - We will change both the marker shapes and colors to improve readability.\n   - We agree that standardizing the axis ranges can improve visual clarity. However, since we experiment with different values of $k$ (in the cardinality constraint), the optimal objective value naturally increases with larger $k$, which leads to differing y-axis scales across plots. This variation reflects meaningful differences in the problem instances rather than plotting inconsistencies.\n\t    That said, we appreciate the point about the Random (240s) baseline. Given its poor performance and the distortion it introduces in the axis scaling, we will move it to the appendix and add a note in the main text to guide the reader. We also note that larger versions of all plots are already available in the appendix for more detailed comparison.\n    -  We will clean up Tables 9–11 and consider splitting the tables or reducing precision to improve readability.\n    - The reason the reference numbers in the Appendix differ from those in the main paper is that we include additional related work and citations in the Appendix (Section A) that are not referenced in the main text. As a result, the numbering continues beyond what appears in the main paper. There are a few inconsistencies that we have fixed. Thanks for pointing this out.\n\n\nReferences:\n\n1. Robert R Nerem, Zhishang Luo, Akbar Rafiey, and Yusu Wang. Differentiable extensions with rounding guarantees for combinatorial optimization over permutations. arXiv preprint arXiv:2411.10707, 2024"}, {"review_id": "iNq5KdYP3p", "reviewer": "Reviewer_vkDa", "summary": "The paper proposes a theoretically grounded and practically effective framework for solving constrained combinatorial optimization (CO) problems using neural networks. The main contribution is an end-to-end differentiable method that leverages convex geometry and Carathéodory’s theorem to project neural outputs onto the convex hull of feasible discrete solutions. This ensures constraint satisfaction while maintaining differentiability. The method also includes a decomposition algorithm (Algorithm 1) to iteratively represent neural predictions as convex combinations of feasible sets. The authors provide useful theoretical guarantees (Theorems 4.1 and 4.2, Proposition 4.3), empirical evaluation on cardinality-constrained Maximum Coverage problem. Experimental results demonstrate improvements in both inference time and objective values over learning-based baselines, and competitive performance against non-learning methods.", "questions": "- What exactly is the MIP-based solution mentioned in line 310?\n- What value of $\\epsilon$ is used in Algorithm 1 in the experiments? How does performance vary with $\\epsilon$, and how was the appropriate $\\epsilon$ chosen to balance speed and accuracy?\n- In Theorem 4.1 or 4.2, does the value of $\\epsilon$ affect the theorem's validity? Can the theorems hold with $\\epsilon$ set to zero, or must $\\epsilon$ be a certain positive number?", "limitations": "- As mentioned above, the primary limitation of the method is that any change in the target CO problem requires adapting the projection and decomposition procedures specific to the new problem’s polytope.\n- While the proposed approach achieves strong results compared to learning-based methods, its performance can be less favorable when compared to non-learning methods or TTO-based baselines. However, as the authors suggest, there is potential to improve this by designing better neural architectures tailored to specific problems.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths\n---\n- The paper presents a well-structured framework based on solid theoretical foundations for handling CO problems with constraints.\n- To guarantee that neural network outputs lie on the polytope of feasible solutions, the network predicts perturbations on an n-dimensional hypercube rather than outputting directly. This clever approach resembles the reparameterisation trick in variational methods, which separates random perturbations from learned distribution parameters for gradient-based learning.\n- The method demonstrates strong performance compared to learning-based baselines. Inference is fast, and the objective values found by the method often surpass those of other approaches.\n\nWeaknesses\n---\n- In Algorithm 1, $x_0 \\leftarrow x$ should be replaced by $x_1 \\leftarrow x$. (I am not 100% sure with the replacement, but Algorithm 1 currently raises UndefinedError since $x_1$ is not defined in Step 3.) Some definitions (e.g., Steps 3–5) are not fully introduced until later in the paper. It would be helpful to provide earlier hints or comments so that readers are not confused when encountering them initially.\n- It would be useful to clarify the meaning of TTO (Test-Time Optimization) in Table 1. Table 1 may be more appropriately named as Figure 1. The figures are small to read. In the last graph (12th), the points for Greedy and Gurobi appear to coincide—this overlap should be explicitly noted.\n- The method’s most significant limitation is that if the target CO problem changes, the projection onto the polytope and decomposition algorithm must be adapted accordingly. However, the authors alleviate this concern by demonstrating that for a broad class of CO problems—including those with cardinality constraints, partition matroids, spanning trees, and independent sets—the projection and decomposition can be implemented efficiently.", "was_revised": true, "final_justification": "As I mentioned in the response for the authors rebuttal, I decided to maintain my rating.", "rebuttal": "We sincerely appreciate the reviewer’s thorough evaluation and constructive feedback. Below, we address the bulleted questions in the order they were presented.\n- Thank you for pointing this out. You are absolutely right—the initialization should indeed be $\\mathbf{x}_1\\gets\\mathbf{x}$, and we have corrected this accordingly. We also appreciate your suggestion regarding clarity: to improve readability, we will move the relevant definitions earlier in Section 4.1 so that Steps 3–5 are easier to follow when first encountered.\n\n - The details of TTO are given in Lines 346 to 357. The caption of the Table has been updated to include the meaning of TTO (Test-Time Optimization). Table 1 is now renamed as Figure 1. The figures have been enlarged for readability; an enlarged version of the plots was already included in the appendix. In the last graph (12th), the overlap between Greedy and Gurobi is now explicitly noted.\n    \n  - The MIP-based solution refers to the exact solution obtained by formulating the problem as a Mixed Integer Program (MIP) and solving it using Gurobi.\n   - A detailed discussion of how $\\epsilon$ serves as a tolerance parameter to control the size of the decomposition is provided in Appendix Section C. The main idea is to 'undershoot' each step in the Caratheodory decomposition by *rescaling* the coefficient choice at every iteration in order to control the number of iterations and hence the number of sets that are used in the decomposition. This helped with convergence during training and led to improved results. Please see the discussion in Lines 320 to 329 around *scaling factor* and lines 1103 to 1110 in the Appendix for the choices of scaling factors. The scaling factors influence the number of terms generated in the decomposition—specifically larger scaling factor results in fewer terms in the decomposition. In the experiments $\\epsilon$ is set to a very small value (e.g., $10^{-14}$) to account for numerical instability. \n    \n- In both Theorem 4.1 (due to Grötschel–Lovász–Schrijver) and our Theorem 4.2, we have $\\epsilon=0$. As stated in Theorem 4.2, instantiating Algorithm 1 with Equations (5) and (6) yields an exact equality; that is, $\\mathbf{x}=\\sum_{t}p_{\\mathbf{x}_t}(S_t)\\mathbf{1} _{S_t}$."}, {"review_id": "rQZ4j4RgG5", "reviewer": "Reviewer_gbDc", "summary": "This paper proposes a new pipeline to tackle combinatorial optimization problems with neural networks. The key novelty is to use a Caratheodory-type geometric algorithm in order to convert continuous solutions efficiently into sparse convex combinations of discrete solutions. This can be used both during training (in order to define a meaningful objective) and inference (in order to define a meaningful rounding procedure).", "questions": "no further questions", "limitations": "no concerns", "rating": 2, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The general idea of the paper makes a lot of sense and seems to be promising. Blindly applying neural nets to CombOpt problems certainly doesn't work well - and incorporating geometric insights is the right way to make things work.\n\nI am not entirely familiar with the practical side of neural combinatorial optimization. The results look decent, even if not totally mind-blowing. I cannot judge that much, how novel the work is compared to previous work on neural combinatorial optimization. What I can however judge well is the mathematical foundations of this work. On this side, while I think the general approach makes a lot of sense, I have do have doubts with respect to the broad applicability. I also think that the presentation is insufficient. My concrete concerns (with respect to that and more generally) are as follows:\n\n- While the authors make bold claims about \"incorporating geometric algorithms in deep learning pipelines\", all they do in the end is a standard Caratheodory decomposition. I recognize that it is a contribution to incorporate them into deep learning pipelines, but I would like to emphasize that this is not groundbreaking on a mathematical level and has been used in CombOpt algorithms for a long time.\n- Algorithm 1 is insufficiently described. Many points remain unclear: what exactly is the support of x_t? How to choose S_t? What is g? Shouldn't, by Caratheodory's theorem, the algorithm terminate after n+1 steps, with epsilon = 0, so why do you need this epsilon-test? Why should it output a *unique* Caratheodory decomposition (which is necessary to interpret the coefficients as probabilities)? How does this unique decomposition differ from all other possible decompositions?\n- Theorem 4.1 contains many undefined terms and is not helpful in this formulation. I understand that it is an informal version, but it does not help to build any intuition if formulated like this. Also it remains unclear why suddenly n terms are sufficient, while Caratheodory requires n+1.\n- It is questionable whether the proposed pipeline is broadly applicable to difficult problems. The example problems in the paper (optimizing over a uniform matroid, partition matroid, spanning trees) are all easy problems from a complexity perspective. Independent set is a hard problem, but here the authors actually discuss a relaxation instead of the actual problem and it remains unclear how to transform a vertex of the fractional stable set polytope into an actual independent set. In conclusion, I am not convinced that this pipeline generalizes to CombOpt problems with more complicated underlying polytopes.\n- line 107: I find it questionable to defer related work discussions to the appendix. If the work is relevant, put it in the main text. If not, leave it out.\n- As far as I understand, the authors have not submitted code for their experiments.\n\nMinor (no need to address in rebuttal):\n- line 20/21: \"These problems are often non-convex\" --> this statement is misleading. Are you talking about the domain? Or the objective function? The former is discrete, which induces challenges, but talking about convexity doesn't make much sense. The latter is often comparably simple, e.g., linear (not necessarily, but claiming it would be \"often non-convex\" is too general).\n- line 22-24: this sentence needs citations\n- line 24: eschew --> maybe use a more standard word?\n- line 27: \"discrete objective\" --> what exactly do you mean with that? The objective itself is usually not discrete, just the set of feasible solutions is. (same in line 49)\n- Figure 1: the graphic has low quality. Use vector graphic instead.\n- beginning of Sec. 3: I don't think it makes much sense to introduce the problem with general D if you then only focus on D={0,1} in the paper. A simpler problem setup would have been sufficient.\n- line 127: what are positional encodings? I don't think this term has been introduced before.\n- line 137: if you follow this strategy, do you need training data at all? Why?\n- line 139: add comma before \"which\"\n- around line 159: in general, there are many ways to write down a Caratheodory decomposition of an interior point in a polytope. So, in order to view the coefficients as probabilities, you need to define a *unique* way of finding a Caratheodory decomposition! I suppose you do that, but make it more explicit here.\n- line 183: if this method comes from GLS, why do you cite two papers by other authors? Is there no original reference corresponding to these three names?\n- line 195: and --> an (??)\n- In Alg. 1 and the text in section 4: please define what \"the support of x_t\" is supposed to be.\n- line 240/241: which problems are you referring to here? Please name them and add citations.\n- I would have liked more details in the main submission on the spanning tree case and fewer on the cardinality case. Reason: the cardinality case is a quite simple one, while spanning trees already possess interesting and non-trivial combinatorial structure.\n- line 285: \"There is no compact description of the polytope of independent sets of a graph\" --> this requires a citation. I suspect that this statement refers to an extension complexity lower bound (which would be the right thing to cite here).\n- line 312: one space too much before semicolon\n- lines 326-328: I don't understand what issue you are referring to here. Please explain better.\n- Table 1 should be referenced somewhere in the main text.\n- Why is the time limit for different approaches different? (I.e. Gurobi 240s, Random 120s)", "was_revised": true, "final_justification": "See my response to the rebuttal", "rebuttal": "We would like to thank the reviewer for their detailed response.\n> While the authors make bold claims about \"incorporating geometric algorithms in deep learning pipelines\", all they do in the end is a standard Caratheodory decomposition.\n\nThe reviewer adds \n>but I would like to emphasize that this is not groundbreaking on a mathematical level and has been used in CombOpt algorithms for a long time.\n\n- We believe that the statement of 'incorporating geometric algorithms in deep learning pipelines' is appropriate since the proposed method leverages constructive results from the literature on geometric algorithms to implement a differentiable pipeline for combinatorial optimization with neural nets.  The theorem that forms the basis of our approach is in the GLS book 'Geometric algorithms and combinatorial optimization'. Our wording choice in the line quoted by the reviewer is a direct reference to the title of the book. We cite the book and mention the theorem explicitly in the paper (see line 192). We do not attempt to present this as some kind of outstanding mathematical achievement. The contribution lies in leveraging such algorithms for the purpose of neural comb opt. In that context, the constructive Caratheodory decomposition is able to effectively deal with both loss function design and rounding. We also provide extensive benchmarking to show the empirical benefits of the method (see also response to reviewer 7pF1). Our ablation also shows how this can even work using direct optimization with Adam.\n\n- The reviewer acknowledges that such decompositions have been used in combinatorial algorithms for a long time. That is one of the strengths of this approach, since one can leverage results from the literature to adapt our method to other problems (e.g., scheduling, networking, etc.). To the best of our knowledge, the specific decompositions we describe have not been published but by no means constitute mathematical breakthroughs. That's because their existence essentially follows from the GLS result (theorem 4.1). They are valuable elements of our contribution, but they are not the central contribution of the paper. It is worth noting that the design of such efficient decompositions has been acknowledged as an interesting question in the literature (see for example section 4.3 in [1] or the introductory remarks in [2]).   Introducing this problem as an element of machine learning algorithm design and making progress on it could be beneficial for both machine learning communities and communities working on algorithms. We certainly do not intend to mislead with our claims so we welcome any corrections of specific sentences that the reviewer believes would alleviate the issue. \n\n>Algorithm 1 is insufficiently described...\n\nalso\n\n>Theorem 4.1 contains many undefined terms and is not helpful in this formulation. I understand that it is an informal version... \n\n- Here are are some clarifying comments that we will make sure to include in the final version of the paper:\n\n  - By support of $\\mathbf{x}$, we mean the nonzero coordinates of the vector. \n\n  - The function $g$ is the (a.e.) differentiable function that computes the coefficient of the current iterate given the current iterate and a vertex of the polytope. We will make sure to introduce it earlier in the paper since this was also confusing to another reviewer. For example, the cardinality constraint section of the paper provides a concrete example for $g$ (see Equation 6).\n\n  - Finding a vertex for the current iterate is problem dependent. In the most general case, according to the GLS theorem, we need to find a vertex of the smallest face of the polytope that contains the current iterate. This is further elaborated on in appendix B. For the problems we considered, a greedy algorithm can be sufficient. For instance, in the cardinality constraint we fetch the vertex corresponding to the the top-k coordinates. In some cases we may have to solve a linear program.\n\n> Why should it output a unique Caratheodory decomposition...\n\n- The reviewer raises a valid point about the uniqueness of the decomposition. The uniqueness is required in order to ensure a.e. differentiability of the extension and we achieve uniqueness by designing a deterministic decomposition algorithm that maps a point from the polytope to a distribution. The details of such deterministic algorithm are problem specific and we provide several examples such as cardinality constraints and other matroids. For example, if we have a problem defined on graphs, we need to fix an ordering of the vertices of the input graph so as to consistently obtain a vertex and a coefficent corresponding to the current iterate. The decomposition then yields a deterministic mapping from the point in the polytope to the coefficients. In the case of the cardinality constraint, the set corresponding to the top-k coordinates of each iterate is chosen. Each iterate is a deterministic function of the previous iterate. Hence, the collection of sets (corresponding to top-k coordinates) and their coefficients are consistently obtained from the inputs. The ordering may only become relevant in case of tie-breaks (a rare occurrence in practice).\n\n\n> Shouldn't, by Caratheodory's theorem, the algorithm terminate after n+1 steps, with epsilon = 0, so why do you need this epsilon-test? \n\n- The number of steps is always at most $n+1$ in theorem 4.1, which indeed has epsilon=0. Iterations should start from 1 and end at $n+1$ in the GLS theorem (Theorem 4.1). We apologize for the typo. Terms like strong optimization oracle are explained in the Appendix B but we will make sure to clear this up in the updated version.\n\n- In appendix $C$ the role of the $ \\epsilon $ test is discussed in more detail. The main idea is to obtain a decomposition that contains potentially more than $n+1$ sets by rescaling the coefficient choice at every iteration. This allowed for better exploration (and convergence) during training and led to improved results. Furthermore,  the $\\epsilon$ test is motivated by the existence of approximate versions of the Caratheodory decomposition that do not depend on the ambient dimension of the space. We mention those in the last paragraph of the related work section of the main paper (references [3,12,47]). We consider this as a promising future direction for this line of work. \n\n> It is questionable whether the proposed pipeline is broadly applicable to difficult problems. The example problems in the paper (optimizing over a uniform matroid, partition matroid, spanning trees) are all easy problems from a complexity perspective.\n-  First, we want to acknowledge that depending on the problem, it may indeed be challenging to implement our approach. We mention this in the conclusion and in the extended discussion in Appendix B. We want to emphasize that cardinality constrained problems like maximum coverage or max-k-cut are known to be NP-Hard. However, the computational complexity of the problem is not sufficient to decide whether our method is applicable. As another example, there exist efficient decompositions for permutation polytopes and permutation polytopes can be used to solve hard (in terms of complexity) combinatorial problems like travelling salesperson. More generally, the viability of our approach primarily depends on whether one can find vertices and coefficients for each iteration of the decomposition efficiently. Hence, implementing our approach will be challenging for cases where linear optimization over the polytope is computationally hard.\nThis is what is troublesome for independent set.  We included the independent set example to highlight that even in cases where it is not obvious how to construct an efficient decomposition due to the potential intractability of the polytope, there are compromises that can be made to yield a viable method (i.e., a relaxation like FSTAB).\n  FSTAB's corners are either integral vertices corresponding to independent sets or half-integral vertices. The decomposition will terminate but it may include some infeasible points (half-integral vertices). We may simply set the value of the objective to 0 for all non-integral points so that for an FSTAB extension the optimization will prioritize integral corners. Admittedly, this is not as mathematically clean as in other constraints but we wanted to bring up how one could deal with those harder cases.\n\n> I find it questionable to defer related work discussions to the appendix. If the work is relevant, put it in the main text. If not, leave it out.\n\n- Given the space limitations, it is not viable to include almost 2 pages of related work in the main paper. We chose to prioritize the papers from the literature that we find are the most pertinent in the context of our contribution. The approach we take to those problems is not widely known, so our view was that the additional discussion around related work that we provide in the appendix could help interested readers contextualize our contribution and improve the overall accessibility of the paper. \n\n>As far as I understand, the authors have not submitted code for their experiments.\n\n\n- We have submitted the code and the link can be found on page 17 of our corresponding NeurIPS checklist answer to this question. We will make sure to mention this in the updated main body of the paper too.\n\n\n References:\n 1. Cunningham, William H. \"On submodular function minimization.\" Combinatorica 5.3 (1985): 185-192.\n\n 2. Hoeksma, Ruben, Bodo Manthey, and Marc Uetz. \"Efficient implementation of Carathéodory’s theorem for the single machine scheduling polytope.\" Discrete applied mathematics 215 (2016): 136-145."}]

Author rebuttal:

Meta-review: The paper proposes a self-supervised method for predicting feasible points of combinatorial optimization problems by a decomposition approach. Reviewers note the novelty of the idea, good presentation. Reviewers have mixed opinions on the quality of the experimental results, ranging from ok but not impressive to strong. There is some excitement about the broad applicability and potential of the idea. The main negative issue is the writing. We ask the authors to incorporate the feedback from the review process.
All in all, the paper merits acceptance at NeurIPS.
The extensive rebuttal is positively acknowledged.
Decision: Accept (poster)