Towards One-shot Neural Combinatorial Solvers: Theoretical and Empirical Notes on the Cardinality-Constrained Case
Authors: Runzhong Wang
Li Shen
Yiting Chen
Xiaokang Yang
Dacheng Tao
Junchi Yan
Venue: ICLR 2023 poster (2023)
Keywords: deep learning
combinatorial optimization
facility location problem
max coverage problem
portfolio optimization

Abstract: One-shot non-autoregressive neural networks, different from RL-based ones, have been actively adopted for solving combinatorial optimization (CO) problems, which can be trained by the objective score in a self-supervised manner. Such methods have shown their superiority in efficiency (e.g. by parallelization) and potential for tackling predictive CO problems for decision-making under uncertainty. While the discrete constraints often become a bottleneck for gradient-based neural solvers, as currently handled in three typical ways: 1) adding a soft penalty in the objective, where a bounded violation of the constraints cannot be guaranteed, being critical to many constraint-sensitive scenarios; 2) perturbing the input to generate an approximate gradient in a black-box manner, though the constraints are exactly obeyed while the approximate gradients can hurt the performance on the objective score; 3) a compromise by developing soft algorithms whereby the output of neural networks obeys a relaxed constraint, and there can still occur an arbitrary degree of constraint-violation. Towards the ultimate goal of establishing a general framework for neural CO solver with the ability to control an arbitrary-small degree of constraint violation, in this paper, we focus on a more achievable and common setting: the cardinality constraints, which in fact can be readily encoded by a differentiable optimal transport (OT) layer. Based on this observation, we propose OT-based cardinality constraint encoding for end-to-end CO problem learning with two variants: Sinkhorn and Gumbel-Sinkhorn, whereby their violation of the constraints can be exactly characterized and bounded by our theoretical results. On synthetic and real-world CO problem instances, our methods surpass the state-of-the-art CO network and are comparable to (if not superior to) the commercial solver Gurobi. In particular, we further showcase a case study of applying our approach to the predictive portfolio optimization task on real-world asset price data, improving the Sharpe ratio from 1.1 to 2.0 of a strong LSTM+Gurobi baseline under the classic predict-then-optimize paradigm.

Published as a conference paper at ICLR 2023
TOWARDS ONE-SHOT NEURAL COMBINATORIAL SOLVERS: THEORETICAL AND EMPIRICAL NOTES
ON THE
CASE
Runzhong Wang', Li Shen', Yiting Chen', Xiaokang Yang', Dacheng Junchi Yan
Moo Key Lab of Artificial Intelligence, Shanghai Jiao Tong University 2JD Explore Academy
{runzheng. wang, situcyt, xkyang, (mathshenli, dacheng. e com
Code: https: /ttpt/gggtthh/t/// wtm/ htwpa//oo---ttooooo-oo-ooooaaaa-
ABSTRACT
One-shot non-autoregreesivve neural networks, different from RL-based ones, have been actively adopted for solving combinatorial optimization (CO) problems, which can be trained by the objective score in self-supervised manner. Such methods have shown their superiority in efficiency (e.g. by parallelization) and potential for tackling predictive CO problems for decision-making under uncer- tainty. While the discrete constraints often become a bottleneck for gradient- neural solvers, currently handled in three typical ways: 1) adding soft penalty in the objective, where bounded violation of the constraints cannot be guaran- teed, being critical to many constraint-sensitivv scenarios; 2) perturbing the input to generate an approximate gradient in black-box manner, though the constraints are exactly obeyed while the approximate gradients can hurt the performance on the objective score; 3) compromise by developing soft algorithms whereby the output of neural networks obeys relaxed constraint, and there can still occur an arbitrary degree of constraint-violatin
Towards the ultimate goal of establishing a general framework for neural CO solver with the ability to control an arbitrary- small degree of constraint violation, in this paper, focus on more achievable and common setting: the cardinality constraints, which in fact can be readily en- coded by differentiable optimal transport (OT) layer. Based this observation, we propose OT-based cardinality constraint encoding for end-to-end CO problem learning with variants: Sinkhorn and Gumbel-Sinkhon tion of the constraints can be exactly characterized and bounded by our theoretical results. On synthetic and real-world CO problem instances, our methods surpass the state-of-the-ee CO network and are comparable to (if not superior to) the com- mercial solver Gurobi. In particular, we further showease a case study applying our approach to the predictive portfolio optimization task on real-world asset price data, improving the Sharpe ratio from 1.1 to 2.0 of a strong LSTM+Gurobi base- line under the classic prediit-then-opimiize paradigm.
whereby their viola-
INTRODUCTION
Developing neural networks that can handle combinatorial optimization (CO) problems is a trending research topic (Vinyals et al., 2015; Dai et al., 2016; Yu et al., 2020). A family of recent CO networks (Wang et al., 2019b; Li et al., 2019; Karalias & Loukas, 2020; Bai et al., 2019) improves the existing reinforcement learning- based auto-regin uuto-regressive CO networks (Dai al., 2016; Lu et al., 2019) by solving the problem in one shot and relaxing the non-differentiable constraints, resulting in an end-to-end learning pipeline. The superiorities of one-shot CO networks are recognized in three aspects: 1) the higher efficiency by exploiting the GPU-friendly one-shot feed-forward network, compared CPU-based traditional solvers (Gamrath et al., 2020) and the tedious auto-regressive
Junchi Yan is the correspondence author. The work was in part supported by National Key Research and Development Program of China (2020A A01076000,) NSFC (U19B2035, 62222607, 61972250), STCSM (22511 1 105 105100), Shanghai Committee of Science and Technology (21DZI 100100).

---

Published as a conference paper at ICLR 2023
Table 1: Comparison among CO networks. Both theoretically and empiricalty, smaller constraint-
violation (CV) leads to better optimization results. Logarithm terms in CV bounds are ignored.
Erdos Goes Neural
name of self-supervised CO network
CardNN-S (ours)
CardNN-GS/HO (ours)
(Karalias Loukas, 2020)
enforce constraint in network urchitecture
No (loss penulty term)
Yes (by Sinkhom)
Yes (by Gumbel-Sinkhong m- (1+))
theoreticul bound of CV (notations from Sec. 2)
non-controlled
Ö [P -0-----1
Toi 2y 49"
empirical CV (results from Fig. 3(a)) empirical optimal gap (J)
8.44
6.71
0.09 0.023
0.152
0.139
CO networks; 2) the natural label-free, self-supervised learning paradigm by directly optimizing over the objective score, which is more practical than supervised learning (Vinyals et al., 2015) and empirically more efficient than reinforcement learning (Schulman et al., 2017); 3) the end-to-end architecture enabling tackling the important predictive CO problems, i.e. decision-making under uncertainty (Wilder et al., 2019; Elmachtoub & Grigas, 2022). In this paper, we follow the general paradigm of learning to solve CO in one-shot presented in the seminal work (Karalias & Loukas, 2020). A neural network CO solver is built upon problem encoder network. which firstly accepts raw problem data and predicts the decision variables for the problem. The decision variables are then passed to a differentiable formula to estimate the objective score, and finally, the objective score is treated as the self super-uueee loss. All modules must be differentiable for end-to-end learning.
As CO solver, the output of the network should obey the constraint of the CO problem, while still preserving the gradient. Since the input-output mappings of CO are piece-wise constant, where the real gradient is zero almost everywhere or infinite when the output changes, it is notoriously hard to encode CO constraints in neural networks. There are three typical workarounds available: 1) In Karalias & Loukas (2020), the constraints are softly enforced by penalty term, and the degree of constraint-viole viooatiio can be hardly theoretically characterized nor controlled, which limits their applicability in many constraint-critice
scenarios. Mcanwhile, in the obligatory discretization step, adding penalty terms means that the algorithu must search much larger space than if it was con- fined to feasible configurations, making the search less efficient and less generalizable (see Table 1). 2) The perturbation-basee black-box differentiation methods (Pogančić et al., 2019; Paulus et al., 2021; Berthet et al., 2020) resorts to adding perturbation to the input-output mapping of discrete functions to estimate the approximate gradient as such the strict constraints are enforced in brute force, yet their approximate gradients may hurt the learning process. 3) The soft algorithms (Zanfir & Sminchisescu. 2018; Wang et al., 2019;; Sakaue, 2021) encode constraints to neural networks by developing approximate and differentiable algorithms for certain CO problems (graph matching, SAT, submodular), which is followed in this paper for their efficiency, yet there still remains the possibility of facing an arbitrary degree of constraint-violation.
Towards the ultimate goal of devising general CO network solver addressing all the above issues, in this paper, we focus on developing a more practical paradigm for solving the cardinality-constraneed constrained CO problems (Buchbinder et al., 2014). The cardinality constraints ||x||o lo S k are commonly found in wide range of applications such as planning facility locations in business operation (Liu, 2009), discovering the most influential seed users in social networks (Chen et al., 2021), and predicting portfolios with controllable operational costs (Chang al., 2000). Under the cardinality constraint, we aim to find the optimal subset with size k. Likewise other discrete CO constraints, the cardinality constraint is non-trivial constraints to CO networks by topk selection over a probability distribution (which is the output of an encoder network). An intuitive approach is to sort all probabilities and select the k-largest ones, however, such process does not offer informative gradients. Inspired by Cuturi et al. (2019); Xie al. (2020), we develop soft algorithm by reformulating the topk selection as an optimal transport problem (Villani, 2009) and efficiently tackle it by the differentiable Sinkhorn algorithm (Sinkhorn, 1964). With a follow-up differentiable computation of the self-supervised loss, we present a CO network whose output is softly cardinalit-coonstrained
differentiate through. In this paper, we propose to encode cardinality
constrained and capable of end-to-end learning.
However, our theoretical characterization of the Sinkhorn-based soft algorithm shows its violation of the cardinality constraint may significantly grow if the values of the k-th and (k+ 1 1)-th probabilities are too close. Being aware of the perturbation- based differentiable methods (Pogančić et al., 2019; Paulus et al., 2021; Berthet al., 2020) and the Gumbel trick (Jang et al., 2017; Mena et al., 2018; Grover et al., 2019) that can build near-discrete neural networks, in this paper, we further incorporate the Gumbel trick which is crucial for strictly bounding the constraint- viooaaioo term to an arbitrary
2

---

Published as a conference paper at ICLR 2023
Network for Cardinality Constraint
Farward:
Backward
Problem Encoder (Sec, 48:5)
OT Cardiaaity Layer (Sec. 3)
Objective Estimator (Sec. 4&5)
Self-Supervised Loss
hallty
Mitimine protlan
sontosdeaaaa 72 J
isctic MCCP.
proMee::
Socal Networkos
trugport
mint (...A...)) T7T
Lus - maaar A....o0)
Pantalio
for
X- D0MIS
Gunieel
sample
Prrauccia Asaate
Figure Our CardNN pipeline. The problem encoder and our proposed optimal transport (OT) cardinality layer compose our CO solver network, which has the superiority of guaranteeing theo- retically bounded constraint-voolation The decision variables from the CO network are then utilized to estimate the objective score, i.c. the self-supervised loss. The implementation of the OT cardi- nality layer and its theoretical characteristics will be discussed in Sec. The other components are problem-dependent and will be discussed in Sec. 3 and Sec. 4 under the context of each problem.
small number. Our network takes both advantages of the high efficiency in soft algorithms (Zanfir & Sminchisescu, 2018) and the low constraint-violate in perturbation-base methods (Pogančié et al., 2019; Jang et al., 2017). A homotopy extension (Xu et al., 2016) is further developed where the constraint-violee violation term is gradually tightened. Following the self-supervised learning pipeline in Karalias & Loukas (2020),
cardinality constrraie CO networks are validated two repre- sentative deterministic CO tasks: facility location and max covering problems.
An important application of predictive CO is also addressed, where the problem parameters known at the decision-man making time. We present a ppredict-and-ottmninn predictor and neural network CO solver end-to-end over the final objective score, instead of the two-stage
network that jointly learns
which learns a predictor first and then optimizes separately, at the risk of optimizing performance being hurt by prediction error. Specifically, towards a practical and widely concerned task: portfolio optimization under uncertainty, we build an end-to-en predictive portfolio optimization model. Experimental results on real-world data show that it outperforms the paradigm. The contributions include:
classic "predict-then-optiiie
New End-to-end One-shot Neural Architecture for CO Problems. We propose the first (to our best knowledge) end-to-end cardinality coniinaaitt--costtainneeeed neural network for efficient CO problem- solving in one-shot, in the sense that the constraints are incorporated in the network architecture instead of directly putting them in the learning objective as penalty terms.
Theoretical and Empirical Advantages of the CO Architecture. The cardinality constraint is encoded in the differentiable optimal transport layer based the topk selection technique (Xie et al., 2020). While we further introduce the idea of perturbation as used blackbox differentiable CO (Pogančić et al., 2019; Paulus et al., 2021), by incorporating the Gumbel trick to reduce the constraint-violation and the violation bound is strictly guaranteed by our theoretical results. Empir- ical results two CO tasks: facility location and max covering also verify its competitiveness.
Paradigm. We show that our new network further enables an emerging end-to-end "predict-ane and paradigm in contrast to the traditional "predict-then optimize" pipeline. Its potential is demonstrated by a study on predictive portfolio optimization on real-world asset price data, with an improvement of Sharpe ratio from 1.1 to 2.0, compared with baseline: LSTM+GGurbbi.
Enabling "predict-and-opting
CARDINL CONSHARAIN COMBINATORIAL NETWORKS
An overview of our CardNN pipeline is shown in Fig. 1. Following the general paradigm (Karalias & Loukas, 2020) to tackle CO one-shot, we introduce an optimal transport (OT) cardinality layer in the neural network CO solver to enforce the constraints upon the output of the problem encoder network, wherehy the superiorities could be addressed both empirically and theoretically.
Recall that under cardinality constraint, the solution must have more than k non-zero elements:
min J (x) s.l. x
||x[|o < k.
(I)
3

---

Published as a conference paper at ICLR 2023
In this paper, enforcing the cardinality constraint in networks is formulated as solving OT with differentiable layers (Cuturi, 2013). Denote $ = [$1.... .mm] as the probability vector predicted by the problem encoder network, our OT layer selects & largest items from by moving & items to one destination (selected), and the other (m k) elements to the other destination (not selected). In the following, present two embodiments of OT layers and their theoretical characteristics.
2.1 CARDNN-S: SINKHORN LAYER FOR CARDINALITY CONSTRAINT
We follow the popular method Sinkhorn (1964) and define the OT problem as follows. The sources are m candidates in and the destinations are the min/max values of OT moves the topk items to Snax: and the others to Spin. The marginal distributions (c, r) and distance matrix (D) are defined as:
1
k
D
81
Snin
82
Spin
8m Spin
(2)
Snax
Spax $2
Snax 9m
my items
Then OT can be formulated as integer linear programming:
min mintrr(TDD D) T
s.t. Te {0, (0.1]axm, TI=
(3)
where T is the transportation matrix which is also feasible decision variable for the cardinality constraint, and is a column vector whose all elements are 1s. The optimal solution T to Eq. (3) should be equivalent to the solution by firstly sorting all items and then selecting the topk items. To
make the process differentiable by soft algorithms, the binary constraint on T is relaxed to continu- ous values [0, 1]. and Eq. (3) is modified with an entropic regularization:
min tT D) + T
s.f. T E [0, 1|2m T' FI= c
(4)
where ((TT) = Ei, T log is the entropic regularizer (Cuturi, 2013). Given any raalevalued
matrix D, Eq. (4) is solved by firstly enforcing the regularization factor r: T = exp(-D) Then T is row- and column-wise normalized alternatively:
D. diag(T T @r), T D.
diag 10c),
100c), T =TD (5)
where is clement-wise division. We denote T the converged solution, which is the optimal solution to Eq. (4). The second row of T is regarded as the relaxed decision variable for the cardinality constraint: T i] is regarded as the probability that x; should be non-zero. T further fed into the objective estimator. Note that T is usually infeasible in the original problem, and we define the following constraint violation to measure the quality of T
Definition 2.1 (Constraint Violation, CV). CV is the expected minimal distance between laxed solution t (from distribution T) and any feasible solution from the feasible set H: CV EEET [mimEeH ||t -]]/]. Apparently, h is the nearest feasible solution to t.
Remark 2.2 (Meaning of CV). Take the self-supervised CardNN-S as example, estimating the objective score (which is exactly the self-supervised loss) based on T necessary during training. In inference, the solution must be feasible in the original problem, the nearest feasible solution T returned. Actually, in training, the network learns to solve a relaxed, casier version of the original problem, and CV = T |r is important characteristic measuring the gap between the relaxed problem (in training) and the original problem (in inference). Here T means the distribution of all CardNN-S outputs and is omitted for simplicity. Such a meaning of CV also applies for other self-supervised CO networks. In the following, we theoretically characterize the CV of CardNN-S:
Proposition 2.3. Assume that Sinkhorn converged. The constraint-violatiie of the CardNN-S is
2m7 log 2
CV = | T -
(6)
1 Φ
Without loss of generality, ó is denoted as the descending sequence of s, i.e. du, Φx+1 are the k- th, (k + 1)-th largest elements of s. respectively. Proposition 2.3 is a straightforward derivation based on Theorem of Xie et al. (2020). and is better than Karalias & Loukas (2020) whose CV is non-controlled. However, Jox- d becomes smaller, and turns diverged under the extreme case that dR = Φ meaning that its CV cannot be tighten by adjusting the hyperparameter Such divergence is not surprising
we learn from Eq. (6), the CV of CardNN-S gradually grows if
4

---

Published as a conference paper at ICLR 2023
Algorithm 1: CardNN-GS: Gumbel-Sinkhorn Layer for Cardinality Constraint
Input: List with m items; cardinality k; Sinkhorn factor т; noise factor o; sample size #G.
for i E {1, 2, ... #G} do
for all 8j. 8j 8)
log( log(U) )), where "y is from (0, 1) uniform distribution;
D
$1 Spin
8m Sain Snax 5m
construct c, r following Eq. (2); T. - -D/))
Saxx 81
while not converged do
D, = diag (Tr) T, D. T.:
" D. diag 10c)) T. T.
Output: A list of transport matrices
(T T2, Tag].
because cannot decide whether to select dh or 0x+11 if they equal, which is fine if any direct supervision on T is available. However, as discussed in Remark 2.2, the importance of CV is non-negligible in self-supervised CO networks. Since working with solely the Sinkhorn algorithm reaches its theoretical bottleneck, in the following, we present our improved version by introducing random perturbations (Pogančié et al., 2019; Jang et al., 2017) further tighten the CV.
2.2 CARDNN-GS: GUMBEL-SINKHORY LAYER FOR CARDINALITY CONSTRAINT
In this section, we present our Gumbel-Sinkhorn Layer for Cardinality Constraint as summarized in Alg. I and we will theoretically characterize its CV. Following the reparameterization trick (Jang et al., 2017), instead of sampling from a distribution that is non-differentiable, we add random variables to probabilities predicted by neural networks. The Gumbel distribution is:
Jo (w) = o log( - log(m)))
where a controls the variance and u is from (0, 1) uniform distribution. We can update and D as:
== 8 + go (uy), D
81
Swin
82
Sain
8m
8min 8m
(8)
Bpx 81
Spax
82
Smax
Again we formulate the integer linear programming version of the OT with Gumbel noise:
mi D) s.t. T E [0, T 1=c,
where the optimal solution to Eq. (9) is denoted as T To make the integer linear programming problem feasible for gradient-base based deep learning methods, we also relax the integer constraint and add the entropic regularization term:
min tr T D) ((T) s.1. T [0, 10.m TI = T-.
(10)
T
which is tackled by the Sinkhorn algorithm following Eq. (5). Here we denote the optimal solution to Eq. (10) as T Since T is the nearest feasible solution to T we characterize the constraint- violation as the expectation of - - T F. and multiple Ts are generated in parallel in practice overcome the randomness (note that é is the descending ordered version of s):
Proposition 2.4. With probability at least (1 <), the constraint-violatioo of the CardNN-GS is
CV = E, ||T
T |1x]]
S (log 2)mr
Σ P((r 05.0
(11)
igj
20 log (0 16:-0;1 +20
10: Øj arctan
di-ds 2a
log(1- -c
where (j, (1 (()0 )2
2 + 40 (1 +1+++0 exp 6: 6 )1 exp
PE+1
Proof sketch: This proposition is proven by generalizing Proposition 2.3. We denote & Pmats as the k-th and (k + 1) -h largest items after perturbed by the Gumbel noise, and our aim becomes to prove the upper bound of E, [1(( @r. + go - density function of 9- (u,,)) 9o (ur. ) can be bounded by f(y) = 1/(1² + 4). Thus we can compute the bound by integration. See Appendix C. for details.
Jo (wzz..)) )D). where the probability
5

---

Published as a conference paper at ICLR 2023
Table Objective scoref among perturb- methods (Pogančić al., 2019; Berthet al., 2020; Amos et al., 2019) on MCP (k=50,m==50,n=11000 Bascline is Xie et al. (2020) used in CardNN-S.
CardNNPPggantic et al. (2019)
CardNN+Berthet et al. (2020)
CardNN+Amos et al. (2019) CardNN-S
CardNN-GS
32499.7
37618.9
38899.6
42034.9
44710.3
Corollary 2.5. Ignoring logarithm terms for simplicity, CV ConDNN-GS I Ö (see Appendixx for the proof).
[mr(lo (ar1110;;1110 0.1+0)
(di- =+o Vigj
We compare CV of CardNN-S and CardNN-GS by the toy example in Fig. 2: finding the top3 of [1.0, 0.8, 0.601, 0.6, 0.4, 0.2]. We plot CV w.r.t. dif- ferent 7, values. CV is tightened by larger a and smaller 7 for CardNN-GS, compared CardNN-S whose violation is larger and can only be controlled by т. These empirical results are line with Propo- sition 2.3 and Proposition 2.4.
condiansrraatto (2V)
1.30
3.25
3.20
Caidhh-
5.000)
Homotopy Gumbel-Sinkhorn. The Corollary 2.5 suggests that CV can be tightened by adjusting and G, motivating us to develop homotopy (Xiao & Zhang, 2013; Xu et al., 2016) Gumbel-Sinkhom method where the constraints are gradually tighten
0.25
0.20
e madel
Figure 2: Toy example.
(i.e. annealing and a values). In practice, is not considered because larger means increased variance which calls for more Gumbel samples. We name the homotopy version as CardNN-HEn -GS.
We also notice that CardNN-S (Sec. 2.1) and CardNN-GS (Sec. 2.2) can be unified theoretically: Corollary 2.6. CardNN-S is a special case of CardNN-GS when + 0+ (proof in Appendix C.3).
ONE-SHOT SOLVING THE DETERMINISTIC CO TASKS
In this section, present the implementation details and experiment results for learning to solve two deterministic CO problems in one-shot: facility location problem (FLP) and max covering problem (MCP). Deterministic CO means all problem parameters are known at the decision decision-making time. Readers are referred to Appendix for the algorithm details.
The Facility Location Problem. Given locations and want extend & facilities such that the goods can be stored at the nearest facility and delivered more efficiently (Liu, 2009). The objective to minimize the sum of the distances between each location and its nearest facility. mmx as the distance matrix for locations, the FLP
Problem Formulation: Denote A E 20
TTA
min
Vx; = 1})
s.1. x E (0, 13" ||x|o S.
(12)
Problem Encoder: For locations with 2-D coordinates, an edge is defined if locations are closer than threshold, e.g. 0.02. We exploit a 3-layer SplineCNN (Fey et al., 2018) to extract features. Objective Estimator: We notice that the min operator in Eq. (12) will lead to sparse gradients. Denote element-wise product of a matrix and tiled vector, we replace min by Softmax with minus temperature B: J, sum musssttmaax(-32
T J mean
JHa]).
The Max Covering Problem. Given m sets and n objects where each set may cover any number of objects, and each object is associated with value, MCP (Khuller et al., 1999) aims to find & sets (k < m) such that the covered objects have the maximum sum of values. This problem reflects real- world scenarios such discovering influential seed users in social networks (Chen et al., 2021). Problem Formulation: We build a bipartite graph for the sets and objects, whereby coverings are encoded edges. Denote IR" the values, A {0, paxn the adjacency of bipartite graph, I(x) as an indicator [[(x); = iffx 2 1 else ll(x); = O. We formulate the MCP as
max Σ
Σ Ais VJ)
s.t. 10,1) 11 S k,
(13)
6

---

Published as a conference paper at ICLR 2023
octenal (owee bettin
grondy
X
greedy
Sewver 22
SCI (2200)
<p x
Cursda (aplmma)
Gumbi tepeinoat
BSM
EGN nccu
Candiiu-
Cordhee (i
220
Infermnns tine Senoode
Inference time (seooodi))
nieoeee the joecordr
iiteence time (erceerr
(a) Fyythhtt (k=30, m=500)
(b) PLP-Synthetic (k=50, m=
1014
13
1.0
gresdy
smedy
X Gordb (200a)
SOF L100Q
45
SO* cl250
Cendiius
CardhWis
Candraiss
Cantul- -55
CardhN-445
130
50
100
156
100
360
(c) MCP-Synthetic (k=50, m=500, n=1000)
(d) MCP- ACCt-Synthetic (k=100. m=1000, n=2000)
Figure 3: Plot of objective score, gap w.r.t inference time on synthetic CO problems. Each scatter dot denotes problem instance, and the average performance is marked by "x" In terms of both ef- ficiency and efficacy, our CardNN-S outperforms the EGN CO network whose constraint-violation is non-controlled. The efficacy is further improved by CardNN-GS and CardNN-HGS, even sur- passing the state-of-the-art commercial solver Gurobi (better results with less inference time). The Gurobi solver fails to return the optimal solution within 24 hours for MCP, thus not reported here.
Problem Encoder: To encode the bipartite graph, we exploit three layers of GraphSage (Hamilton et al., 2017) followed by fully-comnected layer with sigmoid to predict the probability of selecting each set.
Objective Estimator: Based on Eq. (13), the objective value is estimated as:
J min (
v, J ([e Je... ..., Jea]).
(14)
Learning and Optimization. Based on whether it a minimization or a maximization problem, J or J is treated as the self-supervised loss, respectively. The Adam optimizer (Kingma & Ba, 2014) applied for training. In inference, the neural network prediction is regarded as initialization, and also optimize the probabilities w.r.t. the objective score by gradients.
Experiment Setup. We follow the self-supervised learning pipeline proposed by the state-of-the- art CO network (Karalias & Loukas, 2020), whereby both synthetic data and real-world data are considered. For synthetic data, we build separate training/testing datasets with 100 samples. We generate uniform random locations
unit square for FLP, and we follow the distribution in OR- LIB (Beasley, 1990) for MCP. Due to the lack of large-scale datasets, real-world datasets are only considered for testing (training on Starbucks locations in 4 cities worldwide with 166-569 stores, and we test MCP based on 6 social networks with 1912-9498 nodes collected from Twitch by Rozemberezki al. (2021).
synthetic data, testing on real-world data). We test the FLP based
Baselines. 1) Greedy algorithms are considered because they are easy to implement but very strong and effective. They have the worst-case approximation ratio of (1- 1/e) due to the submodular property (Fujishige, 1991) for both FLP and MCP. 2) Integer programming solvers including the sfate-of-the-art commercial solver Gurobi 9.0 (Gurobi Optimization, LLC, 2021) and the otate-of- the-art open-source solver SCIP 7.0 (Gamrath et al., 2020). The time budgets of solvers are set to be higher than our networks. For 3) CO neural networks, we compare with the state-of-the-a Erdos Goes Neural (EGN) (Karalias & Loukas, 2020) which is adapted from their official implementation: ht https: : / / ////ttin thub. con/ Stalence/ / /eerrrdd__eeeeeeeeeeeeeeeeeeeeee neu. The major difference between EGN and ours is that EGN does not enforce CO constraints by its architecture. Besides, we empirically find out that all self-supervised learning methods converge within tens of minutes. Since the RL methods e.g. Khalil et al. (2017): Wang al. (2021a) need much more training time, they are not compared.
Metrics and Results. Fig. 3 and 4 report results on synthetic and real- world dataset, respectively. The "gap" metric is computed as gap = |J 1/ max (J, J*), where J is the predicted objective
7

---

Published as a conference paper at ICLR 2023
optimal gap ilovar is batter)
gmedd
gap Uloer better)
10a
gready
optimal gap flower is better)
10
X
SCIP (50s)
SCIP (60s)
10-1
Gurobi (optimal)
Gurobi (60s)
Gurobi (60s)
Gurobi (optimal)
10-
X
SCIP (aptimal)
greedy
EGN
EGN
10-3
Gurobi toptimal)
EGN
10-7
Cardhiv-S
20-2
CardNN-S
10
Cardhii-S 65
CardNN- GS
CardNiv 5
x
CGS
1
CardNN-HGS
10:4
CardNN-GS
CardNN-HGS
100 200 inference time (seconds)
100
inference time (Seconds)
inference time (seconds)
(a) FLP-Starbucks (Euclidean)
(b) FLP-Starbucks (Manhattan)
(c) MCP- JCC--Twich
Figure 4: Plot of optimal gap w.r.t. inference time on real-world CO problems. Our CardNN models are consistently superior than EGN, and are comparative to oftthoffthheart SCIP/Gurobi solvers and sometimes can even surpass. On the FL.P-Starbucks problems, our CardNN-GS/HGS achieve a lower optimal gap with comparable time cost w.r.t. SCIP/Gurobi. On the MCP-Twitch problems, our CardNN- is slower than SCIP/Gurobi, but finds all optimal solutions.
and J is the incumbent best objective value (among all methods). one of the integer programming solvers proves an optimal solution, we name it as "optimal gap". Considering both efficiency and efficacy, the performance ranking of CO networks is CardNN-HGS EGN. This is in line with our theoretical result in Sec. 2: a lower constraint violation will lead to better performance
CardNN-GS > CardNN-S
CO. To justify our selection of Xie et al. (2020) as the base differentiable method, we also implement other perturbation baasd differentiable methods and report the MCP results in Table 2. See Appendix E for more details about our deterministic CO experiment.
ONE-SHOT SOLVING THE PREDICTIVE CO TASKS
In this section, we study the interesting and important topic of predictive CO problems where the problem parameters are unknown at the of predicting the portfolio with the best trade-off in risks and returns in the future, under the practical cardinality constraint to control the operational costs. Traditionally, such a problem involves two separate steps: 1) predict the asset prices in the future, probably by some deep learning models; 2) find the best portfolio by solving an optimization problem based on the prediction. However, the optimization process may be misled due to unavoidable errors in the prediction model. To resolve this issue, Solin et al. (2019) proposes to differentiate through unconstrained portfolio optimization via Amos & Kolter (2017), but the more practical cardinality constrained problem is less studied.
time. We consider the challenging problem
Problem Formulation. Cardinality constrained portfolio optimization considers a practical scenario where portfolio must contain more than l assets (Chang et al., 2000). A good portfolio aims to have a high return (measured by mean vector μ E " and low risk (covariance matrix Σ E Rm Here refer to maximizing the Sharpe ratio (Sharpe, 1998). The problem is formulated as
max (11 Tx
8.t. Σ
-== 1, |xx||o S k.
(15)
V Σx
where x denotes the weight of each asset, ry means risk-free return, e.g. U.S. treasury bonds. Note that Σ are unknown at the time of decision-making, and they are predicted by neural network.
Network Architecture. An encoder-decoder architecture of Long-Short Term Memory (LSTM) modules is adopted as the problem encoder (i.c. price predictor). The sequence of historical daily prices fed into the encoder module, and the decoder module outputs the predicted prices for the future. We append fully-connected layer after the hidden states to learn the probabilities for cardinality constraints, followed by our CardNN-GS layers.
Objective Estimator. Based on the network outputs μ, E, T. we estimate the value of x by lever- aging closed-form solution of unconstrained Eq. (15): x E ry), and then enforcing the constraints: x relu(x x @ :)),, x x/sum((x (6 means element-wise product). After obtaining x, we compute the Sharpe ratio based on x and 11tt Dst computed from the ground truth prices, and use this Sharpe ratio as supervision: J. (lust - -ry)_ Tx)
x)/ /
Σo(x
8

---

Published as a conference paper at ICLR 2023
14
CardNNNGGS: average retum=-00.0 40.0%
CardNIN GS: average 18.8%
12
history-opt average
pred-then-opt: average returm24, 24.1%
Expected Rikk Standard Deviation
pred-then-opt average riske 195k=19.5% 19.5%
history-ppt: average riske 16.2%
S8/5500 everage relumm23,50%%
0.3
Expected Anual
0.4
6.4
0.
0.7
4.1
20222/3
2022/275
2012/2/3
2002A42
2022/5/3
2003/002 3821/771
3023/121
2031/221
200//22
3020//21
2031/2/
2023/00 2324/721
Starting
Starting Date
Figure 5: Return (left) and risk (right) for portfolios by the classic "predict-then- then-optimizee" pipeline (by LSTM for prediction and Gurobi for optimization) and our CardNN-GS for end-to-end "predict- and-optimize.. The portfolios proposed by our CardNN-GS has higher returns and lower risks. Since the batch of S&P500 assets violates the cardinality constraint, it is unfair to compare the risk.
Table 3: Our "predict-and-optmiize" achieves better risk-return trade-off (Sharpe ratio) though the price prediction is less accurate (by mean square error) than "predict-hhen-opimiiie on test set.
Methods
predictortoptmmierr
prediction MSE + Sharpe ratio f
hitt
none+Gurobbi
prediction)
0.673
pred-then-opt pred-and-opt
LSTM+Gurobi
0.153
1.082
LSTM+CardNN-GS
1.382
1.968
Setup and Baselines. The price predictor is supervised with price labels but the optimizer self- supervised (no optimal solution labels). We consider portfolio prediction with the best Sharpe ratio the next 120 trading days (~224 weeks) and test with the real data the year 2021. The training set is built based on the prices of 494 assets from the S&P 500 index from 1018-01-01 to 2020-12-30. We set the annual risk-free return as 3% and the cardinality constraint = 20. The classic "predict- then-optimize" bascline learns the same LSTM model ours to minimize the prediction square error of the asset prices and optimizes the portfolio by Gurobi based on the price predictions. We also consider "history-opt" baseline, whereby the optimal portfolio in historical data is followed.
Results. The portfolios are tested on the real data from 01-01-2021 12-30-2021, and the results are listed in Fig. and Table 3. On av- erage, we improve the annual return of the port- folio from 24. 1% to 40%. The MSE in Table 3 denotes the mean square error of price predic- tions, and note that more accurate price predic- tions do not lead to better portfolios. We visual- ize the predicted portfolios in Fig. 6 and compare to the efficient frontier (portfolios with opti- mal risk-return trade-off). Being closer to the frontier means a better portfolio. Also, note that reaching the efficient frontier nearly impossi- ble as the prediction always contains errors.
0.0
cfficiett bustler
ContNN aneets
ConteN pormilte
Lakay- opt conots
0.0
Latayy-r ept portido
prod (hen opt assets prnd then ogi portiile
0.1
0.2
0.4
0.5
0.5
Figure 6: Visualization 2021-03-25 data of in- dividual assets. Larger dots mean higher weights. See more visualizations in Appendix G.
CONCLUSIONS
Towards the ultimate goal of developing general paradigms to encode CO constraints into neural net- works with controlled constraint-violatie bounds, in this paper, we have presented a differentiable neural network for ize the constraint-violltionn to mitigate the constraint-violate deterministic CO problems (on both synthetic and real-world problems) and end-to-end learning of predictive CO problems under the important predict-and-opimmize paradigm.
combinatorial optimization. We theoretically character- the Sinkhorn network (Sec. 2.1), and we introduce the Gumbel trick issue (Sec. 2.2). Our method is validated in learning to solve

---

Published as a conference paper at ICLR 2023
REFERENCES
Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J Zico Kolter. Differentiable convex optimization layers. Advances in neural information processing systems, 32, 2019.
Brandon Amos and Zico Kolter. Optnet: Differentiable optimization a layer in neural networks. In Int. Conf. Mach. Learn., pp. 136-145. PMLR, 2017.
Brandon Amos, Vladlen Koltun, and J. Zico Kolter. The Limited Multi-L.abel Projection Layer. arXiv preprint arXiv: /900099000000...0 2019.
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang- Simgnn: A ral network approach to fast graph similarity computation. In Proceedings of the Twelfth ACM International Conference Web Search and Data Mining, pp. 384-392, 2019.
John E Beasley. Or-library: distributing test problems by electronic mail. Journal of the operational research society, 41(11):1099-1072 1990.
Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Jean-Philippe Vert, and Francis Bach. Learning with differentiable pertubed optimizers. Neural Info. Process. Systems, 33:9508- 9519, 2020.
Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. Proceedings of the twenty-fifth annual ACM-SIAM symposium on Dis- crete algorithms, pp. 1433-1452 SIAM, 2014.
T-J Chang, Nigel Meade, John E Beasley, and Yazid M Sharaiha. Heuristics for cardinality con- strained portfolio optimisation. Computers & Operations Research, 27(13):1211-330, 2000.
Wei Chen, Xiaoming Sun, Jialin Zhang, and Zhijie Zhang. Network inference and influence maxi- mization from samples. In Int. Conf. Mach. Learn., July 2021.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion. Neural Info. Process. Systems, 32:6281-6299 2019.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Neural Info.
Process. Systems, pp. 2292-2300, 2013.
Marco Cuturi, Olivier Tehoul, and Jean-Philippe Vert. Differentiable ranking and sorting using optimal transport. In Advances in Neural Information Processing Systems, volume 32, pp. 6858- 6868, 2019.
Hanjun Dai, Bo Dai, and Le Song, Discriminative embeddings of latent variable models for struc- tured data. In Int. Conf. Mach. Learn., pp. 2702-2711. PMLR, 2016.
Adam N Elmachtoub and Paul Grigas. Smart "predict, then optimize". Management Science, 68(1): 9-26, 2022.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTord Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller. SplineCNN: Fast geometric deep learning with continuous b-spline kernels. In Comput. Vis. Pattern Recog., pp. 869-877, 2018.
Matthias Fey, Jan E Lenssen, Christopher Morris, Jonathan Masci, and Nils M Kriege. Deep graph matching consensus. In Int. Conf. Learn. Rep., 2020.
Satoru Fujishige. Submodular Functions and Optimization. Elsevier, 1991.
10

---

Published as a conference paper at ICLR 2023
Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, Gregor Hendel, Christo- pher Hojny, Thorsten Koch, Pierre Le Bodic. Stephen J. Maher, Frederic Matter, Matthias Mil- tenberger, Erik Mühmer, Benjamin Müller, Marc F. Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Christine Tawfik, Stefan Vigerske, Fabian Wegscheider, Dieter Weninger, and Jakob Witzig. The SCIP Optimization Suite 7.0. Technical report, Optimization Online, March 2020. URL http:// www. opt imi mamizatiinn onlonnnine org/De BIIBB_TML/// http///220000/000 html.
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. In Int. Conf. Learn. Rep., 2019.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2021. URL https://wwk,
gurobi... ccm.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. Neural Info. Process. Systems, 2017.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. In Int. Conf. Learn. Rep., 2017.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: unsupervised learning framework for combinatorial optimization on graphs. In Neural Info. Process. Systems, 2020.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. Neural Info. Process. Systems, pp. 6351-6361, 2017.
Samir Khuller, Anna Moss, and Joseph Seffi Naor. The budgeted maximum coverage problem. Information processing letters, 70(1):39-43 1999.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. Int. Conf. Learn. Rep., Dec 2014.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching net- works for learning the similarity of graph structured objects. International Conference on Machine Learning, pp. 3835-3845, 2019.
Baoding Liu. Facility Location Problem, pp. 157-165. Springer Berlin Heidelberg, Berlin, Heidel- berg, 2009. ISBN 778-3-540-894844 doi: 10.1007/978-2 1-77788--5------ 1440-89484-1111
Jing Liu, Fei Gao, and Jiang Zhang. Gumbel-softmax optimization: A simple general framework for combinatorial optimization problems on graphs. Arxiv, htts/199..0008.. 2019.
Hao Lu, Xingwen Zhang, and Shuang Yang. learning-based iterative method for solving vehicle routing problems. In Int. Conf. Learn. Rep., 2019.
G. Mena, D. Belanger, S. Linderman, and J. Snoek. Learning latent permutations with gumbel- sinkhorn networks. Int. Conf. Learn. Rep., 2018.
A. Nowak, S. Villar, A. Bandeira, and J. Bruna. Revised note on learning quadratic assignment with graph neural networks. In Data Science Workshop. 2018.
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, In Int. Conf. Mach. Learn., pp. 1443-8453, PMLR, 2021.
Marin Vlastelica Pogančié, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differ- entiation of blackbox combinatorial solvers. In Int. Conf. Learn. 2019. 2019.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-Scale Attributed Node Embedding. Journal of Complex Networks, 9(2), 2021.
Shinsaku Sakaue. Differentiable greedy algorithm for monotone submodular maximization: Guar- antees, gradient estimators, and applications. In International Conference on Artificial Intelli- gence and Statistics, pp. 28-36. PMLR, 2021.

---

Published as a conference paper at ICLR 2023
Paul-Edouard Sarlin, Daniel DeTone, Tomasz Malisiewicz, and Andrew Rabinovich. Superglue: Learning feature matching with graph neural networks. In Comput. Vis. Pattern Recog., pp. 4938- 4947, 2020.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 2017.
William F Sharpe. The sharpe ratio. Streetwise-the Best of the Journal of Portfolio Management, pp. 169-185, 1998.
Richard Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matri- ces. AoMS, 1964.
Mohammad Maholi Solin, Andry Alamsyah, Brady Rikumahu, and Muhammad Apriandito Arya Saputra. Forecasting portfolio optimization using artificial neural network and genetic algorithm. In 2019 7th International Conference on Information and Communication Technology (ICoICT), pp. 1-7. IEEE, 2019.
Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Neural Info. Process. Systems, pp. 2692-2700, 2015.
Po-Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. In Int. Conf. Mach. Learn., pp. 6545- 6554. PMLR, 2019a.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Learning combinatorial embedding networks for deep graph matching. In Int. Conf. Comput. Vis., pp. 3056-3065, 2019b.
Runzhong Wang. Junchi Yan, and Xiaokang Yang. Combinatorial learning of robust deep graph matching: an embedding based approach. Trans. Pattern Anal. Mach. Intell., 2020.
Runzhong Wang, Zhigang Hua, Gan Liu, Jiayi Zhang, Junchi Yan, Feng Qi, Shuang Yang, Jun Zhou, and Xiaokang Yang. A bi-level framework for learning to solve combinatorial optimization on graphs. Neural Info. Process. Systems, 2021a.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Neural graph matching network: Learning lawler's s quadratic assignment problem with extension to hypergraph and multiple-graph match- ing. Trans. Puttern Anal. Mach. Intell., 2021b.
Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision- focused learning for combinatorial optimization. In AAAI Conf. Artificial Intell., volume 33, pp. 1658-1665, 2019.
Lin Xiao and Tong Zhang. A mooximal-gradien homotopy method for the sparse least-squares problem. SIAM Journal on Optimization, 23(2): 2013.
Yujia Xie, Hanjun Dai, Minshuo Chen, Bo Dai, Tuo Zhao, Hongyuan Zha, Wei Wei, and Tomas Pfister. Differentiable top-k with optimal transport. In Neural Info. Process. Systems, volume 33, pp. 20520-20531. Curran Associates, Inc., 2020.
Yi Xu, Yan Yan, Qihang Lin, and Tianbao Yang. Homotopy smoothing for non-smooth problems with lower complexity than o1/c). Neural Info. Process. Systems, 2016.
Tianshu Yu. Runzhong Wang. Junchi Yan, and Baoxin Li. Learning deep graph matching with channel-indepenne embedding and hungarian attention. In Int. Conf. Learn. Rep., 2020.
A. Zanfir and C. Sminchisescu. Deep learning of graph matching. In Comput. Vis. Pattern Recog.. pp. 2684-2693, 2018.
Cong Zhang, Wen Song, Zhiguang Cao. Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. Neural Info. Process. Systems, 33, 2020.
12

---

Published as a conference paper at ICLR 2023
A RELATED WORK
CO Networks with Constraints Handling for Deterministic CO. Multi-step methods encode con- straints by manually programmed action spaces, and the networks can be learned by supervised labels (Vinyals et al., 2015) or by reinforcement learning (Khalil et al., 2017; Zhang et al., 2020; Chen & Tian, 2019). Controlling constraint-violation is less an issue for supervised or reinforce- ment learning because the supervision signals are directly passed to the output of neural networks. One-shot CO networks construct the solution by single forward pass thus being more efficient. The seminal work (Karalias & Loukas, 2020) aims to develop a general pipeline for one-shot CO networks. by softly absorbing the violation of constraint as part of its final loss. However, analy- sis shows that such a non-controlled constraint-violan also exist embodiments of constrained CO networks for tailored problems, e.g. the constraint can be encoded as doubly-stochastic matrices in assignment problems (Nowak et al., 2018; Wang et al., 202 lb; 2020). These methods can be viewed as special cases of our paradigm (yet the powerful per- turbation method is not fully exploited). Liu et al. (2019) can be viewed as a multi-step optimization variant of ours, yet learning not considered and the constraint-violatie issue is not theoretically characterized.
potentially harms problem-solving. There
Differentiable Optimizers for Predictive CO. The major challenge of joint prediction and opti- mization is making the optimizers differentiable. In Amos & Kolter (2017); Agrawal et al. (2019), a family of convex optimization problems is found feasible to differentiate by their KKT condi- tions. However, for non-convex CO problems, Pogančić et al. (2019) explains that the true gra- dients are meaningless for neural networks. One family of papers propose to incorporate existing solvers and estimate the informative and approximate gradients, including tailoring soft algorithms for specific problems (Zanfir & Sminchisescu, 2018; Wang et al., 2019a; Sakaue, 2021). or fol- lowing the perturbation based blackbox optimization pipeline (Pogančić et al., 2019; Paulus al., 2021; Berthet et al., 2020) with certain restrictions such as the formula must be linear. The other paradigm is incorporating neural-network solvers which naturally differentiable. For example, for graph matching on images (Fey et al., 2020; Sarlin et al., 2020), deep feature predictors and neural matching solvers are learned end-to-end under supervised learning, and their neural solvers leverage the Sinkhorn algorithm (Cuturi, 2013) as a neural network layer. In this paper, our neural network solver is incorporated for the new predictive portfolio optimization task, and our predict- and-optimize pipeline does not require the ground truth labels for the optimization problem.
B LIMITATIONS
We are also aware of the following limitations:
1) Our theoretical analysis mainly focuses on characterizing the constraint-violatin There is an unexplored theoretical aspect about the approximation ratios of our CO networks w.r.t. the optimal solution and the optimal objective score, and we plan to study it in future work.
2) The original EGN pipeline relatively general for all constraints, and we restrict the scope of this paper within cardinality constraints. We are aware of potential direction to extend our paper: the cardinality constraints are handled by our method (encoded in the network's output), and the other constraints are handled in way similar to EGN (encoded as Lagrange multipliers penalty terms). In such a sense, the cardinality constraints are handled efficiently while still preserving the generality of EGN.
3) In the predictive CO tasks, the predictor may be. in some degree, coupled with the follow-up neural network solver. In our predictive portfolio optimization experiment, our price predictor can- not generalize soundly for the Gurobi solver, and the Sharpe ratio degenerates to 1.002 if our price predictions passed to Gurobi.
C PROOF OF THEOREMS
Before starting the detailed proof of the propositions and corollaries, firstly we recall the notations used in this paper:
13

---

Published as a conference paper at ICLR 2023
T (D) is the optimal solution of the integer linear programming form of the OT problem Eq. (3), which is equivalent to the solution by firstly sorting all items and then selecting the topk items. If the k-th and (k + 1)-th largest items equal, the algorithm randomly selects one to strictly satisfy the cardinality constraint;
T = Sinkhorn(D) is the optimal solution of the entropic regularized form of the OT
problem Eq. (4) solved by Sinkhorn algorithm. It is also the output by CardNN-S;
T (D) is the optimal solution to the integer linear programming form of the OT problem after being disturbed by the Gumbel noise Eq. (9), which is equivalent the solution by firstly adding the Gumbel noise, then sorting all items and finally select the topk items. If the perturbed k-th and (k + 1)-th largest items are equal, the algorithm randomly selects one to strictly satisfy the cardinality constraint;
T = Sinkhorn(D) is the optimal solution the entropic regularized form of the OT problem after disturbed by the Gumbel noise Eq. (10) solved by Sinkhorn algorithm. It is also the output of our proposed CardNN-GS.
C.I PROOF OF PROPOSITION 2.4
We firstly introduce Lemma which will be referenced the proof Proposition 2.4:
Lemma C.1. Given real numbers Øs Qj. and us, uy are from i.i.d. (0, 1) uniform distribution. After Gumbel perturbation, the probability that oi + (u;) Øj + (u;) is:
P(o: + go( > oj + go
(16)
1 exp 0--0;
Proof. Since go (u) -o log(-log( log((log(u)), P(e: go (u.) probability that the following incquality holds:
Oj go (u,)) is equivalent to the
Φi - a log(- log(-log(u.)) > - ooog((log(u,))
(17)
And we have
Φ Φ, > o olog(- log(u,)) log( (og((u))
(18)
di Φj log
(og(u:)
(19)
σ
log(u,) (z)
log(u;)
(20)
log(uy)
Since My E (0, 1), log(u;) < 0. Then we have
21 bi-dy
log(u;) < log(u,)e
(21)
log (uz) < log
Ui
exp
(22)
di
U 11
exp
(23)
Since ue, uy are i.i.d. uniform distributions, the probability when the above formula holds is
du, du: = 1/'
d1
u,
exp
du: exp +;
(24)
Thus the probability that di + gr (w:) > Φú + go (u;)) after Gumbel perturbation is:
1
P(.: go > 05 go (uy))
(25)
1 + exp 21-0 o
14

---

Published as a conference paper at ICLR 2023
In the following present the proof of Proposition 2.4:
Proof of Proposition 2.4. Recall that denote + [0l, 22 Φ3, Pm) as the descending-orderel version of s. By perturbing it with i.i.d. Gumbel noise, we have
= |0 + go (u)), d2 + go (u2), + go (ua). ..., om + go (um))
(26)
where (u) = - (og(=))
the Gumbel noise modulated by noise factor a, and
W1, U2, U3, Um are i..dd uniform distribution. We define as the permutation of sorting & in descending order, i.c Oz, + D0 (u,, Rn + go (Uma): Pno + Do descending order.
g (Uzz). Pum + 9o (uzm) are in
Recall Proposition 2.3, for 01 Φ2 Ø3, ... om we have
2M log
(27)
10 Øk+1
By substituting + with T6 and taking the expectation over u, we have
2M log 2
Eng
T
1F S E.
(28)
O go (o(u
PrZei 9o (U
Based on Lemma C.I, the probability that Tu = i, Th+11 =
1
P(TK m1 j) 1 exp
9: 02
Ona 02
exp
b=k+2 exp
(29)
where the first term denotes di go (u:) > 0j + go( (uz). the second term denotes all conditions that there are (As 1) items larger than Φ5 + go (u,) and the rest items are smaller than Φj + go (u,).
In the following we derive the upper bound of Ex
We denote
too to
|
2o (u too pxx -
Aij as
Ui, Ny Ai.j. s.t. A go(()) Φ3 (o(()))
(30)
where e is a sufficiently small number. Then we have
En
Om + 1o (Um)) Prets Do (oouuae))
1 |d: + go(us)
P(TTE = i,+1 = BugayeAis
(31)
-0j go Uz))
1
1 1 exp
exp
-
+ exp
b= 1 exp
25 Oap
VT
a=1
1cb + Do (wx) - . - go (o,))
(32)
k-1
1
6- Σ
1 1
exp eep
I + eexp-
exp
or.
b=k+2 exxx
Vx
1
EugyEEAiis
(33)
10i -0--0000 oooo( -log(4;)
Φj + a log( log log(u;))
m
Σ
f(d: - 0,) Σ
(34)
+ exp
k+2 + exp
15

---

Published as a conference paper at ICLR 2023
We denote f (6, 0, 2) as:
I (0,0,2) 1 exp
Bunu 0 log( log( u4) + a log( log u ))
(35)
s.t. 8 o (1o(-)o((4)) log( ())( For the probability terms Eq, (34), for all permutations म, there must exist Tax Tbe such that
(36)
+ exp
Pra
+ exp -0:
(37)
exp
1 exp-
exp
mi 0
Thus we have
Eq. (34) S
[(0: - 0,
(38)
1 cxp- exp
1 exp
95- 9h+t1
iF
f(o: 0.)
(39)
de [(1 + exp
exp
By Eq. (16) Lemma C.I and substituting Φj Φb by y, we have
Eq. (16) = P(go(u,; Do (2²) > Øj - Φi) + exp
(40)
6
PP(g((u)) Jo (1y) y) 1 1 exp
(41)
( Io (uz) 3) + exp 2
(42)
1 exp
where the right hand side is exactly the cumulative distribution function (CDF) of standard Logistic distribution by setting 1:
CDF(g) 1 + exp (-y)
(43)
Thus - lololo(lloo log(u,)) logllogooo log(u)) is equivalent to the Logistic distribution whose probability density function (PDF) is
PDF(y) dCDF(v)
1
(44)
dy
exp (-y) + exp y +
and in this proof we exploit an upper bound of PDF(y):
PDF(w) exp (-y) expy +
(45)
12 +4
Based on the Logistic distribution, we can replace -a log(- log(u,)) + a log(- log(-log(u,)) by σy where y is from the Logistic distribution. Thus can derive the upper bound of f(ō a) as
16

---

Published as a conference paper at ICLR 2023
follows
( dao kotg //otz 8/ -y) y+2 dy
[6,
(46)
1 expp
(B-) dxe 16/042
+xxp 2 dy
exp kotg ( (-y)+ y+2 dy
1
= 1 exp
(47)
I#exp (0/0-)
-0/0+z
booy expl +xxp y+2 dy exp (8/0-2)
(48)
14 +xexp
1oxpp (6/0
[6/002 stoy expl 8) exp 4+ dy
(49)
1 1 expp-
1texp (-6/0(=
1 exp(
(x +2)
00
1
-8/042 8 8 oy -yyexpp (xp(-1) + exp +2 dy
(50)
1 1+exp exp-p-2 -
+ exeepp- (-p +2)
00
1 8 oy 112 +
dy
(51)
1+ exp
-6/0+z 8
+ exp
+
20 20 ((20 - -)2 + 40 25 arctan
=-6/0 2
44 log + n8
+ ++ep--
482 + 1662
(52)
14 exp(
(-pp-3 (-
2)
2o log ((zo + 181)2 + 40²) 20 arctan
2-5/0
4a log z + 5
1 + exp
402 + 16o²
(53)
+ (-
2o log ((zor + +0))2 + 40²)
26 aretan
3-8/0
2o log z² + 8
1 exx
48 + 16o2
(54)
+ exp (-p +))
(-)
2o log
400 (aa++10)) (6))
25 arctan
2-0/0
+ T
2²
(55)
1+ ++xp--
48
16o2
1 exe --2))
2o log
16|+11)+207) (sx
25 arctan
3-0/0 2
+ π
2²
(56)
1+exp-
45
166²
++ ++xxp( (-a + 2)
4a log
161-6
28 arctan
3-0000 2
+ +T0
(57)
1+ 1+exp- +xxp--
482 + 16g2
1 1 1xexp(-A
+2)
4a log
2 [6] 2n 2
2
+ π 2 arctan
3-0//0
2
(58)
1+ 1xexp-
482
1602
<
+ 1- +2)
4a log
2 16/+ 2n
2
|8| (T 2 arctan
2-8//0
2
(59)
1 1+exp-
482 + 1672
+ exp (-g +2)
4a log
200+001200 20
|8| (TT 2 2arctan
-)))
2
< 1+ -eexp-
(60)
482 + 16o2
1 1 (-g
5 + 2)
4a log
30 20+161-20 20
|0| (π + 2arrrtan (
(61)
1xexp-
482 + 16
17

---

Published as a conference paper at ICLR 2023
where Eq. (51) is because (-p(-1)) y+2 S 4² and Eq. (59) is because π - arctan( 220//0
0. With probability at least (1 t), we have
+ e E
log
2 - log (1 cc)
(62)
+ exp
(- 8 +2) 1
(63)
1 1+ exp
c
Thus
4a log
/50+101+20
+ |6| (TT + arcttn (o))
1
f(6,0,2) s Eq. (61)
(64)
1 E
48
+ 166²
40 log (a-
|6|+2o
+ |0| (T + 2 arctan
1
log( 1 1-
(65)
e
482 16
Thus we have
40 log (o 10.-0,1+22
log(1-+) + 100 - 15 T + 2 arctan
Σ Eq. (39) - i
2a
(66)
(1 - (44(0= 02)² + 16o2) (1 + exp Φi (1 + exp
Pa+1 03
In conclusion, with probability at least (1 c),, we have
(2 log 2)m (4o log [ ف 1+20 |0b /36 (TT 2 aarctan d1- log(1 -c)
Eg
T
T |F
20
(4(() - -,,)² + 111000)( (1 + exp
di Φz [1 + exp 0841-99)
(67)
(log 2)mr (20 log (0 lo 1,2-011-20
+ 10, ررو 1/8 + arctan Φe 04
log(l ()
(1 (1-)) oz)² + 20 + exp 0. )[1 exp
Sc+1 -
(68)
= (log 2) mr Σ 2(0s. 05.
(69)
it.
And we denote (dbi,
20 log (a 1 10.-0,1+20
log(1 () + 10x - و ( + arclan
2a
0,) = (1 - (1b) - 02 + 40 (1 + cxp di-de (( + cxp 06+1-0.
(70)
C.2 PROOF OF COROLLARY 2.5
Corollary 2.5 is the simplified version of Proposition 2.4 by studying the dominant components.
Proof. For a(or, o5, σ) E) in Proposition 2.4, we have
20 log
0 l0, 10-0,1+22 +2
+ 10: 131 _ + arctan Φe-dz
log(1 r)
00, 5
(71)
σ b c( - 0,)² + 402)
(1
20 log
log(1 () + 10: - 2
(72)
(1 - c)(( - 13)² 1 + 462)
o log (a + 10; - -by1) + 1dx Φب
0
(73)
(Ø: 02 + 02
+ |0: Φ,
Ō
(74)
(Ø: ò;)²² + d2
18

---

Published as a conference paper at ICLR 2023
Condition
(i
(Pk
4k+1
(P)
Condition 2
4Pk
@k+1
Condition 3
4kk
(p++
Condition 4
(Pk
Px++1
4P)
Figure 7: Four conditions are considered in our proof. It is worth noting that Φs. o must not lie between dx, Pk+1, because define Φk, 0k+1 two adjacent items in the original sorted list.
where we regard (1 1 <) as a constant (i.e. assuming high probability). and Ō(-) means ignoring the logarithm terms.
Then we have
E2
T
T 11
s (log 2)M
Σ
a 16: Φ,1
(75)
(0: oj)²
0 + ( Ø,
= (log 2) 2mmrr
(76)
(Ø: ),)2 + o² Vişj
Ō mT(( + 10: 03
(77)
(di ,;)² + vi+j
C.3 PROOF AND REMARKS COROLLARY 2.6
In the following, we prove Corollary 2.6 and add remarks about the relationship between the Sinkhorn and the Gumbel-Sinkhorn methods: the Sinkhorn method (CardNN-S) is a special case of the Gumbel-Sinkhorn method (CardNN-GS) when we set 0*, To more formally address Corollary 2.6, we have the following proposition:
Proposition C.2. Assume the values of dr, Φh-1 are unique', under probability least (1 (1-6). E), have
(it log 2)mr
lim E,
T
(78)
o a
(1- c) Ob Φ
which differs from the conclusion of Proposition 2.3 by only a constant factor.
Proof. Since 0+. the first term in a( oj or, c)'s numerator becomes O. For the second term, we discuss four conditions as shown in Fig. 7, except for the following condition: Φi = ΦR. 6j- dht1.
For a compact proof, we make this assumption that the values of Φb, db+1 are unique. If there are duplicate values of σt, 1L++, the bound only differs by constant multiplier, therefore, does not affect our conclusion: Sinkhorn method (CardNN-S) is special case of the Gumbel-Sinkhan method (CardNN-GS) when 0
19

---

Published as a conference paper at ICLR 2023
Condition 1. If o; 2 0k. 33 Øk+1 (equalities do not hold at the same time), we have least
6 0k > 0 or Øk+1 - 0j >
Then we have
lim
de 1x11 0
(79)
(1+ exp
di )11 + exp
7 lim ai0: 0, 0, =0 0-
(80)
Condition 2. For any case that Φi < oj. we have di θ < 0, thus
Φ 0 Φj
lim arctan
(81)
a a
2
Φ Φj
lim aretan
(82)
a a 2
0
= lim ll Φy o, o.c)
=0
(83)
a
Condition 3. If of 2 0j 2 0x (equalities do not hold at the same time), we have o; - 0x > Then have
lim a-00
(84)
exp
lim 20
(85)
Condition 4. If db+1 2 0i 03 (equalities do not hold at the same time), we have Øx+1 03 > 0. Then we have
1
lim
(86)
8 o + exp
P2+1-0,
lim
())
(87)
Therefore, if oi * Øx and oj + Φx+1, the second term S( (.. o)
o, degenerates to 0 when
+ 0+ Thus we have the following conclusion by only considering Φi = Φu, Φj Φk+11
(log 2)mr (l0e= Φ _ + arctan $
lim Ey 000
T
T [11] s
2
(88)
(1 - ( ox+1)²
(I log 2)TT
$ (1
(89)
c)lØx Φ
Remarks. Based on the above conclusion, if lox dx+1l to the bound in Eq. (6) and only differs by constant factor:
> O, with o - 0*, Eq. (1I) degenerates
(IT log 2)m7
lim En, | - - T -T S --
(90)
(1 - 6 0x+1
where strong assumption that 16+ 0k+1l > is made, and the bound diverges if dh 0k+11 Since Φk. Φk+1 are predictions by a neural network, such an assumption may not be satisfied. In comparison, given 0, the conclusion with Gumbel noise in Eq. (11) is bounded for any du, ΦR+1- The strength of the theoretical results is also validated in experiment (see Tables 5 and 4), including the homotopy version CardNN-HGS.
D ALGORITHM DETAILS FOR SOLVING DETERMINISTIC CO PROBLEMS
Due to limited pages, do not include detailed algorithm blocks on how to solve deterministic CO problems the main paper. Here we elaborate on our implementation for solving facility location problem (FLP) in Alg. 2, and max covering problem (MCP) in Alg. 3.
20

---

Published as a conference paper at ICLR 2023
Algorithm 2: CardNN-GSSHHGS for Solving the Facility Location Problem
Input: the distance matrix A; learning rate a; softmax temperature S: CardNN-GS parameters
T, a, #G.
Training then
Randomly initialize neural network weights 0;
if Inference then
L Load pretrained neural network weights 0; Jbest +00;
while not converged do
SplineCNN (A): [T T2, .... Tao o,
for all i, J1 sum softmax( -A A [2) A); mean [J,, J2. JHo]): if Training then
L update with respect to the gradient 10
8J and learning rate a by gradient descend; a0
11
Inference then
12
update with respect to the gradient
0J and learning rate a by gradient descend; 25
for all i, J, sum(min( A (2. ))); Joest min([J1, J2. Jucl Jbest):
if Homotopy Inference then
L Shrink the value of and jump to line 5;
15
Output: Learned network weights 0 (if training)/The best objective Joest (if inference).
Algorithm 3: CardNN-GS/HGS for Solving the Max Covering Problem
Input:
bipartite adjacency A; values v; learning rate a; CardNN-GS parameters k or, #G. Training then
Randomly initialize neural network weights 0:
if Inference then
Load pretrained neural network weights 0: Jbeet = O;
while not converged do s = GraphSage, (A); [Ti, T2,... Tag = CardNN-GS(s, k. T, T, HG); for all i, min 1I, v. mean (J Jz.... JaGl); Training then
L update with respect to the gradient if' Inference then update with respect the gradient @J and learning rate a by gradient ascent; for all i, J, (TopK (2) v;; Joest = max([J1, J2... Jag], Jiest);
3J and learning rate a by gradient ascent; 00
10
11
12
13 if Homotopy Inference then
14
Shrink the value of and jump line
Output: Learned network weights 0 (if training//hhe best objective Jbest (if inference).
E MORE DETAILS ABOUT DETERMINISTIC CO EXPERIMENT
E. DATASET DETAILS
The Starbucks location dataset for FLP. This dataset is built based on the project named Starbucks Location Worldwide 2021 version", which is scraped from the apen-accessible Starbucks store lo- cator 3 We analyze and select 4 cities with more than 100 Starbucks stores, which are London (166 stores), New York City (260 stores), Shanghai (510 stores), and Seoul (569 stores). The locations considered are the real locations represented as latitude and longitude. For simplic-
"https://www.kor http:/wwwwaggg.gecc com. www.o///wwaattta/oooooooooooooee http://kkukoo///// htt.oo/////aauucteoeoeooo Chttps://www.de
rbucks - locatiiiooooo ionsswor wowlldda 1dwi de 20-120211 2021- -version
com/ store- locator
21

---

Published as a conference paper at ICLR 2023
Table 4: Objective score J. optimal gap & and inference time (in seconds) & comparison of the facility location problem, including mean and standard deviation computed from all test instances. The problem is to select & facilities from m locations.
k=30, m=500
k=50, m=800
BGNYCardNN are CO networks
objective
optimal gap
time 1 (see)
objective
optinal gap 4
time (sec)
greedy
2.841=0.003
0.167+00.026
1.771=0.017
2.671=00.066
0. 1.16+00.018
4.779+0.005
SCIP 7.0 (==100/206s)
4.470=11.188
0.34820.295
118.068
5,258:11.088
0.552:0.146
243.9194:541188
Gurohi 9.9 (t=120//00ms)
2.453-10:122
0.02310..42
125.589 10,006
3.364110.268
0.005
214.360013,785
(optimal)
2.36520.063
0.00010.0000
314.7981116.858
2.221:20:041
0.00010.000
61N.21331194,166
EGN (efficient)
3.032=00.195
0.217:0.048
0.83020.308
2.89920.155
0.226.20.088
0.988100 140
EGN (accurate)
2.795=0.144
0.152=0.035
123.559+12.2279
16697=0.116
0.175=0.031
191.091+13,,
CardNN-S (Sec. 2.1)
2.753=10.154
0.13910.0011
7.127&1.241
2.462:00.079
0.097.0.023
6.427
CardNN-GS (Sec. 2,2)
2.420=0.0022
0.023=00009
76.554:4.321
2.283=00000
0.027=0.008
120.689:+22400
CardNN-HGS (Sec. 2.2)
2.416:20.073
0.021+0.009
103.742:44.778
2.275::0.048
0.023++00077
158. 400-:34498
ity, we do not consider the real-world distances between any two stores; instead, we test with both Euclidean distance and Manhattan distance. We set k=30, and the objective values reported are distances x 1000m.
The Twitch dataset for MCP. This social network dataset is collected by Rozemberezki et al. (2021) and the edges represent the mutual friendships between streamers. The streamers are cat- egorized by their streaming language, resulting in 6 social networks for 6 languages. The social networks are DE (9498 nodes), ENGB (7126 nodes), ES (4648 nodes), FR (6549 nodes), PTBR (1912 nodes), and RU (4385 nodes). The objective of the logarithmic number of viewers. We took the logarithm to enforce diversity because those top streamers usually have the dominant number of viewers. We set k=50.
cover more viewers, measured by the sum
E.2 IMPLEMENTATION DETAILS
Our algorithms are implemented by PyTorch and the graph neural network modules are based on Fey & Lenssen (2019). In our paper, we optimize the hyperparameters by greedy search on a small subset of problem instances (~5)) and set the best configuration of hyperparameters for CardNN- S/GS/HGS. The hyperparameters of EGN (Karalias & Loukas, 2020) are tuned in the same way. Here are the hyperparameters used to reproduce our experiment results:
For the Max Covering Problem (MCP), we empirically set the learning rate a 0.1. For the hyperparameters of CardNN, we have 7 = 0.05, = 0.15 for CardNN-GS, 7 = 0.05 for CardNN-S, and r = (0.05, 0.04, 0.03). a = 0.15 for the Homotopy version CardNN- HGS. We set #G 1000 samples for CardNN-GS and CardNN-HGS.
For the Facility Location Problem (FLP), we set the learning rate 0.1. For the hyperparameters of CardNN, we have т = 0.05, a = 0.25 for CardNN-GS, T = 0.05 for CardNN-S, and we set T (0.05, 0.04, 0.03), a 0.25 for the Homotopy version CardNN-HGS. We set #G = 500 samples for CardNN-GS and CardNN-HG: The soft- max temperature for facility location is empirically set as twice of the cardinality constraint:
T == 100 if k = 50, T = 60 if l: = 30.
For the Predictive Portfolio Optimization Problem, we set the learning rate a = 10 For our CardNN-GS module, set r 0.05, 0.1, and set the Gumbel samples as #G = 1000. During inference, among all 1000 portfolio predictions, we return the best portfolio found based on the predicted prices, and we empirically find such strategy beneficial for finding better portfolios on the real test set.
All experiments are done on a workstation with 19.700K33.0GGHH CPU, 16GB memory, and RTX2080Ti GPU.
E.3 DETAILED EXPERIMENT RESULTS
In the main paper, we only plot the experiment results both synthetic datasets and real-world datasets due to limited pages. In Table and 5, we report the digits from the synthetic experiments, which are in line with Fig.
22

---

Published as a conference paper at ICLR 2023
Table 5: Objective score 1, gap 4, and inference time (in seconds) J max covering. Under cardinality constraint k, the problem is to select from m sets to cover a fraction of objects. For the gray entry, the Gurobi solver fails return the optimal solution within 24 hours, thus reported as out-of-time.
5= m=500, 1=0000
k=100, m=1000, n=2000
EGN/CardNN
objectivve
gup 4
(sec)
objectivve
gap
(sec)
greedy
8481228
0.011=0.007
0.024=0.000
88698 9 1217.5
0.008=0.004
0.089:1000011
7.0 (t=100</100s)
6
0.029400.011
86269.9+
1256,
0.035-0.006
120.105-0.498
Gurobi 9.0 (t=100//100s
43917.24:791.5
0.019:0.008
100.171
86862.1
16330.5
0.028 0.011
120.277-0.139
(oplimal)
OOT
EGN (efficient)
37141A41896.0
0.171:10.015
0.24410.107
74633.7
0.165-0.010
0.525-0.229
EGN (accurate)
39025,2:471.9
0.129:0.008
40.542=4.056
14888921088..
0.133-0.006
93.670=8.797
CardNN-S (See. 2.1)
1
0.062:00.088
1.935+1,167
83289.02 O+ 133100
0.068=0.007
5,368=1 0014
CardNN-GS (Sec. 2.2)
44710.344770.9
0.002:10.002
28.104-0.466
89264.8
1232.1
0.001-0.000
60.685--0.045
CardNN-IIGS (Sec. 2.2)
44723.911763.2
0.002
39.575
89340.8. 12216
0.000:10.001
89.7641101228
Some remarks about EGN on real-world dataset. Since the sizes of our real-world problems are relatively small, mainly adopt transfer learning setting: the CO networks are firstly trained on the synthetic data, and then tested on the corresponding real-world datasets. All our CardNN models follow this setting. However, the transfer learning ability of EGN seems less satisfying, and we empirically find the performance of EGN degenerates significantly when transferred to different dataset. Fig. we exploit the advantage of self-supervised learning for EGN: we allow EGN to be trained in self-supervised manner on the real-world dataset. To avoid the scatter plots looking too sparse, we ignore the training time cost when plotting Fig. since does not affect our main conclusion (performance rank: CardNN-HGS CardNN-GS CardNN-S > EGN).
We the detailed experiment results on real-world problems Tables 6-19.
Table 6: FLP-Starbucks London dataset (Euclidean distance)
m=166, k=30
objectivel
time (sec).)
Greedy
0.047
0.6
SCIP 7.0 (t=60s)
0.040
2.8
Gurobi 9.0 (t=60s)
0.040
7.2
Gurobi 9.0 (optimal)
0.040
7.2
EGN (train on synthetic)
0.171
0.2
EGN-accu (train synthetic)
0.171
25.6
EGN (train on test)
0.080
0.1
EGN-accu (train test)
0.078
17.2
CardNN-S
0.054
8.2
CardNN-GS
0.042
19.8
CardNN-HGS
0.042
50.3
Table 7: FLP-Starbuck New York dataset (Euclidean distance)
m=260, k=30
objective
time (sec)..
Greedy
0.033
0.9
SCIP 7.0 (t=60s)
0.028
16.5
Gurobi 9.0 (t=60s)
0.028
60.6
Gurobi 9.0 (optimal)
0.028
126.5
EGN (train on synthetic)
0.174
0.1
EGN-aecu (train on synthetic)
0.174
26.0
EGN (train test)
0,089
0.1
EGN-accu (train on test)
0.057
27.0
CardNN-S
0.174
2.3
CardNN-GS
0.030
20.2
CardNN-HGS
0.029
50.8
23

---

Published as a conference paper at ICLR 2023
Table 8: FLP-Starbucks Shanghai dataset (Euclidean distance)
m=510, k=30
objective
time (sec)
Greedy
0.172
1.9
SCIP 7.0 (t=60s)
10.484
106.
Gurobi 9.0 (t=60s)
0.222
62.3
Gurobi 9.0 (optimal)
0.139
313.1
EGN (train synthetic)
1.561
0.3
EGN-accu (train on synthetic)
1.561
58.5
EGN (train test)
0.360
0.3
EGN-accu (train on test)
0.360
56.5
CardNN-S
0.165
9.0
CardNN-GS
0.162
20.7
CardNN-HGS
0.155
51.3
Table 9: FLP-Starbucks Scoul dataset (Euclidean distance)
m=569, k=30
objective
time (sec).
Greedy
0.245
2.1
SCIP 7.0 (t=60s)
14.530
145.2
Gurobi 9.0 (t=60s)
0.424
62.9
Gurobi 9.0 (optimal)
0.188
540.8
EGN (train on synthetic)
2.680
0.3
EGN-accu (train on synthetic)
2.680
57.9
EGN (train on test)
0.497
0.3
EGN-accu (train test)
0.497
63.7
CardNN-S
0.373
9.0
CardNN-GS
0.284
21.8
CardNN-HGS
0.212
52.7
Table 10: FLP-Sttrrucks London dataset (Manhattan distance)
m=166, k=30
objective..
time (sec).)
Greedy
2.441
0.5
SCIP 7.0 (t=60s)
2.390
2.9
Gurobi 9.0 (t=60s)
2.390
2.2
Gurobi 9.0 (optimal)
2.390
2.2
EGN (train on synthetic)
4.793
0.2
EGN-accu (train on synthetic)
4.793
19.4
EGN (train on test)
3,210
0.1
EGN-accu (train on test)
3.008
18.4
CardNN-S
2.688
4.4
CardNN-GS
2,457
20.6
CardNN-HGS
2.424
51.6
24

---

Published as a conference paper at ICLR 2023
Table 11: FLP-Starbucks New dataset (Manhattan distance)
m=260, k=30
objectivel
time (sec)..
Greedy
2.734
0.9
SCIP 7.0 (t=60s)
2.565
9.6
Gurobi 9.0 (t=60s)
2.565
22.9
Gurobi 9.0 (optimal)
2.565
22.8
EGN (train on synthetic)
4.066
0.2
EGN-accu (train on synthetic)
4.066
30.6
EGN (train test)
3.998
0.1
EGN-accu (train on test)
3,500
27.5
CardNN-S
4.066
2.4
CardNN-GS
2.898
15.2
CardNN-HGS
2.845
30.1
Table 12: FLP-Starbucks Shanghai dataset (Manhattan distance)
m=510, k=30
objectivel
time (sec).
Greedy
9.024
1.8
SCIP 7.0 (t=60s)
59.626
101.8
Gurobi 9.0 (t=60s)
8,931
62.2
Gurobi 9.0 (optimal)
8.439
201.7
EGN (train on synthetic)
21.566
0.3
EGN-accu (train on synthetic)
21.566
55.2
EGN (train on test)
17.951
0.3
EGN-accu (train test)
11.601
53.0
CardNN-S
10.780
5.1
CardNN-GS
8.784
26.0
CardNN-HGS
8.774
58.8
Table 13: FL.-SStaruckk Seoul dataset (Manhattan distance)
m=569, k=30
objective..
time (sec).
Greedy
10.681
2.0
SCIP 7.0 (t=60s)
83.952
95.2
Gurobi 9.0 (t=60s)
14.579
65.7
Gurobi 9.0 (optimal)
9.911
335.7
EGN (train on synthetic)
18,206
0.3
EGN-accu (train on synthetic)
18.206
56.6
EGN (train on test)
15.168
0.3
EGN-accu (train on test)
15,069
64.6
CardNN-S
13.154
5.1
CardNN-GS
10.146
28.6
CardNN-HGS
10.003
63.2
25

---

Published as a conference paper at ICLR 2023
Table 14: MCP-Twitch DE dataset
m=n=9498, k=50
objectivet
time (sec)
Greedy
51452
0.3
SCIP 7.0 (optimal)
51481
1.5
Gurobi 9.0 (optimal)
51481
5,8
EGN (train synthetic)
850
15.5
EGN-accu (train on synthetic)
11732
303.0
EGN (train test)
43036
15.4
EGN-accu (train on test)
43069
303.2
CardNN-S
51478
16.0
CardNN-GS
51481
28.7
CardNN-HGS
51481
56.1
Table 15: MCP-Twitch ENGB dataset
m=n=7126, k=50
objectivet
time (sec)
Greedy
26748
0.1
SCIP 7.0 (optimal)
26757
0.3
Gurobi 9.0 (optimal)
26757
0,8
EGN (train synthetic)
5066
7.6
EGN-accu (train on synthetic)
7749
147.6
EGN (train test)
18725
7.5
EGN-accu (train on test)
19296
147.2
CardNN-S
26745
15.6
CardNN-GS
26757
21.7
CardNN-HGS
26757
42.6
Table 16: MCP-Twitch ES dataset
m=n=4648, k=50
objectivet
time (sec)
Greedy
25492
0.1
SCIP 7.0 (optimal)
25492
0.3
Gurobi 9.0 (optimal)
25492
1.1
EGN (train synthetic)
1183
3.1
EGN-accu (train on synthetic)
1489
57.6
EGN (train on test)
17612
3.1
EGN-accu (train on test)
17872
58.0
CardNN-S
25492
15.7
CardNN-GS
25492
12.6
CardNN-HGS
25492
24.9
Table 17: TCP-hwitch FR dataset
m=n=6549, k=50
objectivet
time (sec)
Greedy
39665
0.2
SCIP 7.0 (optimal)
39694
1.2
Gurobi 9.0 (optimal)
39694
10.7
EGN (train synthetic)
21508
6.2
EGN-accu (train on synthetic)
21701
119.2
EGN (train test)
32439
6.2
EGN-accu (train on test)
32533
119.4
CardNN-S
39687
15.8
CardNN-GS
39693
19.9
CardNN-HGS
39694
39.1
26

---

Published as a conference paper at ICLR 2023
Table 18: MCP-Twitch
PTBR dataset
m=n=1912, k=50
objectivet
time (sec)
Greedy
14141
0.0
SCIP 7.0 (optimal)
14163
0.1
Gurobi 9.0 (optimal)
14163
0.3
EGN (train synthetic)
1402
0.8
EGN-accu (train on synthetie)
7329
14.4
EGN (train test)
10173
0.3
EGN-accu (train on test)
10173
5.3
CardNN-S
14155
15.6
CardNN-GS
14163
10.1
CardNN-HGS
14163
19.7
Table 19: MCP-Twitch RU dataset
m=n=,385, k=50
objectivet
time (sec)
Greedy
25755
0.1
SCIP 7.0 (optimal)
25778
0,2
Gurobi 9.0 (optimal)
25778
0.5
EGN (train on synthetic)
7762
2.7
EGN-accu (train on synthetic) EGN (train on test)
7917
51.5
18148
2.6
EGN-accu (train on test)
18156
48.3
CardNN-S
25776
15.9
CardNN-GS
25778
11.9
CardNN-HGS
25778
23.6
E.4 ABLATION STUDY ON HYPERPARAMETERS
Firstly, we want to add some remarks about the selection of hyperparameters:
#G (number of Gumbel samples): #G affects how many samples are taken during train- ing and inference for CardNN-GS. A larger #G (i.e. more samples) will be more appealing, because CardNN-GS will have a lower variance when estimating the objective score, and it will have higher probability of discovering better solutions. However, #G cannot be arbitrarily large because the GPU has limited memory, also is harmful to the efficiency if # #G is too large. experiments, we set an adequate #G (e.g. #G 1000) and ensure that it can fit into the GPU memory of our workstation (2080Ti, 11G).
t (entropic regularization factor of Sinkhorn): Theoretically, 7 controls the gap of the continuous Sinkhorn solution the discrete solution, and smaller will lead to tight- ened gap. This property is validated by our theoretical findings in Proposition 2.4. Unfortu- nately, 7 cannot be arbitrarily small, because a smaller requires more Sinkhorn iterations to converge. Besides, a smaller v means the algorithm being closer to the discrete ver- sion, and the gradient will be more likely to explode. Therefore, given a fixed number of Sinkhorn iterations (100) ensure the efficiency of our algorithm, we need trial-and-error to discover the suitable for both CardNN-S and CardNN-GS. The grid search results be- low show that our selection of fairly balances the performances of both CardNN-S and CardNN-GS.
a (Gumbel noise factor); As derived Proposition 2.4, a larger a is beneficial for a tight- ened constraint-violatio term. However, it is also worth noting that cannot be arbitrarily large because our theoretical derivation only considers the expectation but not the variance. A larger means larger variance, demanding larger number of samples and bringing computational and memory burdens. In the experiments, we first determine a т. and then find suitable by greedy search small subset (~-5) of problem instances.
27

---

Published as a conference paper at ICLR 2023
We conduct an ablation study about the sensitivity of hyperparameters by performing exten- sive grid search near the configuration used in our max covering experiments (r = 0.05, a = 0.15, #G 1000). We choose the k=50, m=500, n=1000 max covering problem, and we have the following results for CardNN-GS and CardNN-S (higher better):
Table 20: Ablation study result of CardNN-GS with #G = 1000.
0.01
0.05
0.1
0.1
42513.4
44759.2
45039.5
0.15
41456.5
44710.3
44837.2
0.2
41264.3
44638.1
44748.2
Table 21: Ablation study result of CardNN-GS with #G 800.
0.01
0.05
0.1
0.1
42511.6
44754.6
45037.6
0.15
41421.4
44705.8
44841.5
0.2
41235.9
44651.5
44748.6
Table 22: Ablation study result of CardNN-S.
T
0.001
0.005
0.01
0.05
0.1
objective score
35956.6
42013.3
42520.8
42034.9
40721.2
Under the configuration used in our paper, both CardNN-S and CardNN-GS have relatively good results. Our grid search result shows that our CardNN-GS is not very sensitive to a if we have 0.05 or 0.1, and the result of 7 0.01 is inferior because the Sinkhorn algorithm may not converge. The results of #G = 1000 are all better than #G 800, suggesting that a larger #G appealing we have enough GPU memory. It is also discovered that CardNN-S seems to be able to accept a smaller value of 7 compared to CardNN-GS, possibly because adding the Gumbel noise will increase the divergence of elements thus performs sense similar to decreasing T when considering the convergence of Sinkhorn.
F DETAILS OF PREDICTIVE PORTFOLIO OPTIMIZATION
Some details of the portfolio optimization model is omitted due limited pages. Here elabo- rate on the entire process of doing portfolio optimization under the "pred-and-opt" paradigm, with LSTM and our CardNN-GS.
Training steps:
1. Denote the index of "now" t 0. {pelt 0} means the percentage change of prices of each day in history, {prlt 2 0} means the percentage change of prices of each day in future.
An encoder-decoder LSTM module predicts the prices in the future:
{pelt 2 0), h LSTM((p.]t < 0)),
where h denotes the hidden state of LSTM.
Compute risk and return for the future:
J mean (px|1 2 0}), cov(fprl( 2 0}).
In the CardNN-GS module, predict (the probability of selected each asset) from h:
fully-connected(h))
28

---

Published as a conference paper at ICLR 2023
5. Enforce the cardinality constraint by Gumbel-Sinkhorn layer introduced in Sec 3.2, whereby there are #G Gumbel samples:
(T, = 1,2, #G} = Gumbel-Sinkhom(s)
Compute the weights of each asset based on the second row of T2 (ry is risk-free return, set as 3%):
x. = xー -ou-ryy ry). relu(x; @ T,(2,:)), x//sum(x)
Based on the ground -oound-truth prices in the future {pe |t 2 0}. compute the ground truth risk and return:
_ mean ( ((rl 0}), Edh cov
{pt e 2 0}).
8. Estimate the ground-truth truth Sharpe ratio in the future, if we invest based on x;;
J, (e00 r,)]xx x;
Vx Ex'x;
The self-supervised loss is the average over all Gumbel samples:
Loss mean (J,, J2, Ja..., (+c)
Testing steps:
Follow training steps 1-6 predict μr, E, (x:li 2.. #G).
Estimate the predicted Sharpe ratio in the future, we invest based on x;:
J. (μ (u--rp) rx)xxx
X Σx;
Return Xheat X; with the highest J, and enforce hard cardinality constraint on Xbeat by hard
topk.
Evaluate based the ground-truth Sharpe ratio:
J (4et ry) Xbest
V XXinst Ede Xbest
G VISUALIZATION OF MORE PORTFOLIOS
In Fig. 8, we provide more visualizations of the portfolios predicted by our "predict-and prredictaand-optimizz optimizee"" CardNN pipeline (blue), the traditional ppeedictrheen-ppimiize pipeline based LSTM and Gurobi (orange), and the historical-date based "history-opt" (purple). In general, portfolio optimization means trade-off between risks and returns, and we can draw an efficient frontier where the port- folios on this frontier are the Pareto optimal for risks and returns, i.c. for portfolio the efficient frontier, one cannot achieve higher returns unless s/ee could accept higher risks. Being closer to the efficient frontier means portfolio is better. Besides, it is also worth noting that reaching the efficient frontier nearly infeasible in predictive portfolio optimization because our predictions of future asset prices always with errors.
H DETAILS ON USING EXISTING ASSETS
The following open-source resources are used in this paper and we sincerely thank the authors and contributors for their great work.
Implementation of Erdos Goes Neural. Paper: Karalias & Loukas (2020). URL: attps: / httpttttubbb// the GitHub webpage.
ceaeceeeeddds__eeeeeeeeeee neu. No open-source license is found
29

---

Published as a conference paper at ICLR 2023
122
0.50
CardNNN neants
0.50
CardNN noeets
0.25
CaedN purtfolio
CaedNN purtfolio
0.00
histery snasts
portfollo
history iseats
-0.25
ogt assets
0.00
opt
pred then opt porttollo
pred then opt portrotlo
0.5
0.6
0.4
0.5
Risk
(a) 2021-01-27
(b) 2021-02-25
1.25
1.00
0.75
neturn
0.78
0.50
efficient frintive CardNN portfolio
0.50
officwent frintiee
0.25
CardNN portfolio
8.00
history opt assets
history opt assets
-025
histery poctiollo
0.00
assets pred-thangpt portiolin
history portiollo
pred-ban-gg
0.50
0.1
0.2
0.3
04
0.5
0.1
0.2
0.
0.5
Bunk
Back
(c) 2021-04-23
(d) 2021-05-21
0.8
0.5
3oturs
Saturs
0.0
offictent frontler
offictent frontier
CardNNN
CardNN
0.2
-0.5
history upt exeess
hustory upi noets
history opt poctfdli
history opt portfollo prod then opt assets
prod then opt assets
-1.0
0.1
0.2
0.3
0.8
0.5
0.6
6.1
0.2
0.3
0.4
0.5
Risk
Rank
(c) 2021-06-21
(f) 2021-07-06
Figure 8: Visualization of predicted portfolios. The labels denote the starting dates of the portfolios.
SCIP solver. Paper: Gamrath et al. (2020). URL: https://scip.... de/. ZIB
Academic License.
ORLIB. Paper: Beasley (1990).
URL: http://peeple.brunnl.cco
"mastjib/ "mastjjb/jeb/orii http///ttb/o//ppiffaaae html. MIT License.
Starbucks
Locations
Worldwide
(2021
version).
URL:
prttps://wwe kaggle. com/ wtt.//oo/.aaaaeee. /tt///attttt//akrt......
starbucks-locat ions wor deeelldvvee22221eeeeeee License.
CCO: Public Domain
Twitch Social Networks (from MUSAE project). Paper: Rozemberezki et al. (2021).
Project URL: https://gl wtt.hh/w.cmeeeeeeeeeeeeeeeeeeeee razki /MUSAE. Data
30

---

Published as a conference paper at ICLR 2023
URL: http:///aa....saooocco/////dalas
html. GPL-3.0 License.
And we are also using the Gurobi commercial solver under academic license. details about Gurobi's academic license at https: http://wwwwgg.rttt com/ academia a academi e-program-andd-iieee aicenneese...//....
See
31


Reviews:
[{"review_id": "r2rwJU953i9", "reviewer": "Reviewer_m4Wt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The submission studies combinatorial optimization (CO) with cardinality constraints by neural networks. Different from the methods incorporating the constraints as penalties in to the objective function, the submission incorporates the constraints into the network architecture such that these constraints are guaranteed to be satisfied. The performance of the proposed method is demonstrated in several tasks including the facility location problem, max covering problem and portfolio optimization.  ", "summary_of_the_review": "The submission considers a challenging and motivational problem. The proposed solution is novel and thoroughly demonstrated on three different tasks. However, for now, there are too many confusing part for me to evaluate the correctness and contribution of the methodology. ", "strength_and_weaknesses": "Strength\n\n1. The motivation of the submission is clear. CO is a challenging and important problem. It is a motivating question to solve CO while forcing the constraints are satisfied. \n\n2. The empirical performance of the proposed method is thoroughly studied in three different tasks. \n\nWeaknesses \n\n1. The notations of the submission are confusing. Many notations first appear without any definitions. For example the notations in figure 1 appear without definitions. I cannot find the definition of $i$ anywhere in the submission. The definitions of $\\mu^{gt}$ and $\\Sigma^{gt}$ are also missing. Then, there are notions like $[2,:]$ and $sum(softmax(...))$ which are not like math equations but codes. \n\n2. Many concepts in the submission appear without or with very little definition or explanation. For example, the problem encoder is a key component of the method, but first appears in the figure 1, simply described as a model to predict $\\bm{s}$. However, the definition of $\\bm{s}$, how it connects to the CO, and why we need to estimate a probability like this is not provided, making the submission not self-contained   \n\nIt would be great if authors can clarify these confusions. \n\n3. Would it be possible for authors to explain why the CO problem is equivalent to an optimal transport problem on $\\bm{s}$? It seems that this is taken for granted without further explanation. \n\n4. Does the gradient flow to the problem encoder part? If so, in the portfolio optimization task, this means that the the gradient flows to the price prediction part. As a result, the stock prediction may learn a prediction not so good at prediction but just to make the CO objective higher. But in the portfolio optimization, the problem setup is to fix the $\\mu$ and $\\sigma$ to as close as possible to the ground-truth ones. \n\n5. For the portfolio optimization, a yearly return as 40% seems to be overly high in practice. Would it be possible for authors to provide some intuitions behind such a high number. Also, when calculating the efficient frontier, I am wondering what is the return and volatility used. What is  $\\mu^{gt}$ and $\\Sigma^{gt}$? I also find this application not very suitable, since it does not matter whether the cardinality constraint is absolutely satisfied or just \"mostly\" satisfied in portfolio optimization. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "qAOFa5_VDC", "reviewer": "Reviewer_8ecY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper provides an improved way for constructing combinatorial optimization networks for problems that involve cardinality constraints.", "summary_of_the_review": "The paper is concerned with combinatorial optimization networks, a field of growing recent interest. It focuses on a single type of constraints - cardinality constraint - and introduces an improved method for handling it.", "strength_and_weaknesses": "The main strength of the paper is providing an extension to combinatorial optimization network framework that allows for bounding the constraint violation, for the case of cardinality constraints. This is achieved by incorporating SOFT top-k approach (Xie et al., NeurIPS'20) and adding a perturbation with Gumbel distribution. The paper is somewhat limited in its scope by the narrow focus on cardinality constraint - it would be stronger if it offered at least one simple example of how the approach can be extended to another constraint type.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "N9Qmj6iPsF", "reviewer": "Reviewer_oRCe", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers how to build a cardinality constraint into neural network architectures being trained to solve combinatorial optimization tasks. This work builds on the Erdos Goes Neural approach of Karalias & Loukas, which uses a loss penalization term to enforce constrains. While Karalias & Loukas do provide high probability guarantees on constraint satisfaction for the penalization approach, in practice it requires careful selection of the weighting of the penalization loss. \n\nThis paper takes a different approach, and design a differentiable output layer based on solving a Sinkhorn problem with added Gumbel noise. Whilst still only softly enforcing the constraint, the source of the relaxation is very different from Karalias & Loukas since it is not in the loss function itself. Empirical results suggest that in practice the approach doers a pretty good job at enforcing the constraint.", "summary_of_the_review": "Congratulations on a nice paper, I enjoyed reading it. The differentiable k subset selection approach is novel and interesting to me. I am also very much in favor of further exploration of neural combinatorial optimization approaches, and I think this paper plays a role in deepening the literature on this subject. In all I am broadly positive in my recommendation. \n\n\nSome questions and comments:\n\n- While I agree that the naive top-k selection will not work as a training approach, I am not sure it is actually because of non-differentiability. The function in question is a map $f$ from the probability simplex to the family of k-cardinality sets. This function is differentiable almost everywhere, besides the case where the k and k+1 probability are equal. I think the real reason why this $f$ does not suit gradient based training is that it is piecewise constant, and so gradient based training will not see any useful gradient directions with which to update the model. I would like to ask the authors to consider this and either explain to me any misconception I have, or to adjust the motivation given in the paper accordingly. \n- Prop 3.4 is a high probability result. What is the randomness over? The LHS already takes an expectation over the Gumbel variable so I am not sure what other randomness it left. \n\n", "strength_and_weaknesses": "**Strengths**\n\n- A good amount of technical novelty. The OT with Gumbel noise approach is interesting to me and is an attractive wya to recast the top-k selection problem. \n- the paper is well written in my opinion.\n- I am satisfied with the empirical results---a number of problems are considered including facility location, finding max covers, and a portfolio optimization problem. I am not convinced that portfolio optimization really needs cardinality constraints in practice (but definitely a whole bunch of other constraints!), but as a proof of concept I am willing to accept the setup. \n\n**Weaknesses:**\n\n- I am a little concerned at the limited impact of the approach. Cardinality constraints are fairly specific, and I cannot foresee too many people needing to use this method. I am, however, strongly against rejection based on impact. I just believe it important to at least raise the point. \n- The method still only softly enforces the constraint. Perhaps some more discussion explaining why hard enforcement is a difficult problem would help myself and other readers understand why we should feel satisfied with soft enforcement. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster