USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization Problems
Year: 2021

Abstract:
Real-world decision-making systems are often subject to uncertainties that have to be resolved through observational data. Therefore, we are frequently confronted with combinatorial optimization problems of which the objective function is unknown and thus has to be debunked using empirical evidence. In contrast to the common practice that relies on a learning-and-optimization strategy, we consider the regression between combinatorial spaces, aiming to infer high-quality optimization solutions from samples of input-solution pairs – without the need to learn the objective function. Our main deliverable is a universal solver that is able to handle abstract undetermined stochastic combinatorial optimization problems. For learning foundations, we present learning-error analysis under the PAC-Bayesian framework using a new margin-based analysis. In empirical studies, we demonstrate our design using proof-of-concept experiments, and compare it with other methods that are potentially applicable. Overall, we obtain highly encouraging experimental results for several classic combinatorial problems on both synthetic and real-world datasets.

heading: 1 Introduction
text: Combinatorial optimization problems are not only of great theoretical interest but also central to enormous applications. Traditional research assumes that the problem settings (i.e., objective function) are completely known [1], but the reality is that the underlying system is often very complicated and only partial knowledge (from historical data) is provided. In a recommendation system, the item-user similarities could be unknown [2], which makes it impossible to compute the optimal recommendation scheme. In the study of wireless communications, the backbone network depends on stochastic node connections [3], incurring extra difficulties in designing management strategies. In the most general sense, we can formalize such scenarios by assuming that the objective function is governed by a configuration space associated with an unknown distribution, where our goal is to maximize the expected objective. For example, the configuration space may specify possible item-user similarities or candidate network structures. We call such problems as undetermined stochastic combinatorial optimization (USCO) problems.
Since the distribution of the configuration space is unknown, one can adopt the learning-andoptimization strategy [4], where the unknown distribution is first learned from data so that the subsequent optimization problem can be solved using existing methods. While such a strategy is natural and proved successful in several applications [5], it may require a large amount of data to learn an excessive number of parameters – for example, the weight between each pair of nodes in a network or the similarity between each pair of user and item in a recommendation system. In the worst case, we may not even have access to such kind of data (due to, for example, privacy issues
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
[6]). Furthermore, a more technical concern is that the learning process is often independent of the optimization process, causing the situation that optimizing the learned objective function does not produce a good approximation to the true objective function, which is theoretically possible [7]. These concerns motivate us to think of the settings that can eschew model learning and can address USCO problems aiming right at the approximation guarantees. To this end, we consider the regression between the input space and solution space, and wish to directly compute the solution for future inputs without learning the hidden objective function.
USCO-Solver. In this paper, we present USCO-Solver, a general-purpose solver to USCO problems. Our framework is designed through two main techniques: randomized function approximation and approximate structured prediction. The key idea is to construct a hypothesis space composed of affine combinations of combinatorial kernels generated using random configurations, from which a large-margin machine is trained using input-solution pairs via approximate inference. The main advantage of USCO-Solver is that it can handle an abstract USCO problem as long as an oracle to solve its deterministic counterpart is given. Another significance of USCO-Solver lies in our use of combinatorial kernels, which suggests a novel and principled way for incorporating an approximation algorithm into a learning process. In doing so, we are able to handle combinatorial objects easily without worrying much about their indifferentiability or the inherited symmetries, which is often not possible for mainstream learning methods [8].
Theoretical analysis. For USCO-Solver, we present a learning-error analysis under the PACBayesian framework, where we introduce the multiplicative margin dedicated to bounding the approximation guarantees. In particular, we prove that the approximation ratio of the predictions is essentially bounded by O(α2), whenever the considered problem admits an α-approximation in the deterministic sense. Such a result is possible due to the fact the hypothesis space of USCO-Solver can approximate the configuration space arbitrarily well. To our knowledge, this is the first result of such kind.
Empirical studies. We conduct experiments with USCO problems concerning three classic combinatorial objects: path, coverage, and matching. On various real-world datasets, we consistently observe that USCO-Solver not only works the way it is supposed to, but also outperforms other competitors by an evident margin in most cases. In many case studies, near-optimal solutions can be computed without consulting the true configuration distribution.
Supplementary material. The proofs, together with more results and discussions on the experiments, can be found in the supplementary material. In addition, we release the experimental materials, including source code, datasets, and pretrain models, as well as their instructions. The experiment materials can be found online1.

heading: 2 Preliminaries

heading: 2.1 Undetermined stochastic combinatorial optimization problems
text: We are concerned with an abstract combinatorial optimization problem associated with three finite combinatorial spaces: the input space X , the output space Y , and a configuration space C; in addition, we are given a bounded non-negative function f(x, y, c) : X ×Y ×C → R+ denoting the objective value to be maximized. Let Φ be the set of all distributions over C. We consider stochastic combinatorial optimization problem in the sense that we seek to maximize f in terms of a distribution φtrue ∈ Φ rather than a fixed configuration in C. This is desired because the system that defines the objective values is often essentially probabilistic, which may stem from random networks or functions with random parameters. Therefore, the objective function is given by
F (x, y, φtrue) = ∫ c∈C φtrue(c) · f(x, y, c) dc. (1)
Given x and φtrue, we are interested in the problem
max y∈Y F (x, y, φtrue). (2)
We may wish to compute either the optimal solution H(x, φtrue) := arg maxy∈Y F (x, y, φtrue) or its α-approximation Hα(x, φtrue) for some α ∈ (0, 1). Such problems are fundamental and also
1https://github.com/cdslabamotong/USCO-Solver
ubiquitous, ranging from the stochastic version of classic combinatorial problems [9] to applications subject to environmental uncertainties, such as commercial recommendation [10], viral marketing [11], and behavioral decision making in autonomous systems [12]. Taking the stochastic longest path problem [13] as an example, the length of each edge could follow a certain distribution, and therefore, each configuration c ∈ C corresponds to a weighted graph; in such a case, x = (u, v) denotes a pair of source and destination, y denotes a path from u to v, and f(x, y, c) amounts to the length of y in c.
While the above formulation is natural, we are always limited by our imperfect understanding of the underlying system, which could be formalized by assuming that the distribution φtrue over the configuration is not known to us. Since the true distribution φtrue is unknown, the objective function F (x, y, φtrue) cannot be directly optimized. Essentially, a learning process is required. In such a sense, we call these problems undetermined stochastic combinatorial optimization (USCO) problems.
Oracle. In general, USCO problems are made difficult by a) the learning challenges in dealing with the unknown distribution φtrue and b) the approximation hardness in solving Equation 2. We focus on the learning challenges and thus assume the approximation hardness (if any) can be resolved by oracles. Notice that the objective function (Equation 1) lies in the positive affine closure of its discretizations, which is
∪∞k=1 { k∑ i=1 wi · f(x, y, ci) : wi ∈ R+, ci ∈ C } . (3)
For some fixed α ∈ (0, 1], we assume the access to a polynomial oracle for computing an αapproximation to maximizing any function in the above class, which implies that Hα(x, φ) is obtainable for each x ∈ X and φ. We can think of α as the best ratio that one can obtain by a polynomial algorithm, with α = 1 denoting the scenario when the optimal solution can be efficiently computed.
For a vector w = (w1, ..., wk) ∈ Rk and a subset C = {c1, ..., ck} ⊆ C of configurations, we denote the induced kernel function as
KC(x, y) := ( f(x, y, c1), ..., f(x, y, ck) ) and the associated affine combination as
F̂w,C(x, y) := k∑ i=1 wi · f(x, y, ci) = wTKC(x, y).
Finally, we denote the α-approximation to maxy∈Y F̂w,C(x, y) as hαw,C(x).

heading: 2.2 Learning settings
text: We consider samples of input-solution pairs: Sm := { (xi, y α i ) }m i=1 ⊆ 2X ×Y where yαi :=Hα(xi, φtrue) is an α-approximation associated with the input xi. Such samples intuitively offer the historical experience in which we successfully obtained good solutions to some inputs. From a learning perspective, we have formulated a regression task between two combinatorial spaces X and Y . Some formal treatments are given as follows. Let us assume that the true distribution φtrue is unknown but fixed, and there is a distribution DX over X . Our goal is to design a learning framework AS : X → Y that can leverage a set S of samples to compute a prediction AS(x) ∈ Y for each future x ∈ X . For a prediction ŷ ∈ Y associated with an input x, let l(x, ŷ) ∈ [0, 1] be a general loss function. Since we aim to examine if ŷ is a good approximation to Equation 2, the loss l is determined jointly by ŷ and x. Consequently, we measure the performance of A by
L(AS ,DX , l) :=Ex∼DX [ l(x,AS(x)) ]

heading: 3 A learning framework
text: In this section, we first present the learning framework and then analyze its generalization bounds. Finally, we discuss training algorithms.

heading: 3.1 USCO-Solver
text: Following the standard idea of structured prediction [14, 15, 16], we wish for a score function F̂ (x, y) such that, for each x ∈ X , the y ∈ Y that can maximize F̂ (x, y) is a good solution to maximizing F (x, y, φtrue). Suppose that we are provided with a set Sm of m ∈ Z samples. USCO-Solver consists of the following steps:
• Step 1. Select a distribution φem ∈ Φ over C and decide a hyperparameter K ∈ Z. • Step 2. Sample K configurations CK = {c1, ..., cK} ⊆ C independently following φem. • Step 3. Compute a seed vector w̃ = (w̃1, ..., w̃K) ∈ RK using the training data. • Step 4. Sample a vector w ∈ RK from Q(w|β · w̃, I), which is an isotropic Gaussian with
identity convariance and a mean of β · w̃, with β being
β := 4
minp |w̃p| · α2
√ 2 ln 2mK
‖w̃‖2 . (4)
• Score function. With CK and w = (w1, ..., wK), we adopt the score function
F̂w,CK (x, y) := K∑ i=1 wi · f(x, y, ci).
• Inference. For each input x ∈ X , the prediction is given by hαw,CK (x), which can be computed by the oracle.
Given that the framework is randomized, the error of interest is L(USCO-SolverSm ,DX , l) :=Ew∼Q,CK∼φem,x∼DX [ l ( x, hαw,CK (x) )] . (5)
So far, we have not seen how to determine the distribution φem, the parameter K, and the seed vector w̃. We will first analyze how they may affect the generalization bound (Sec. 3.2), and then discuss how to make selections towards minimizing the generalization bound (Sec. 3.3).

heading: 3.2 Generalization bound
text: We first study the general loss functions and then consider a particular loss function for measuring the approximation effect in terms of Equation 2.

heading: 3.2.1 General loss
text: The generalization error in general can be decomposed into training error and approximation error [17]; the PAC-Bayesian framework gives a particular bound of such kind [18, 19]. For USCO-Solver, since the decision boundary is probabilistic (as w is sampled from the seed vector w̃), the training error has to be bounded by considering the amount by which hαw,CK (xi) can deviate from h α w̃,CK
(xi) for each training input xi. To this end, we measure the similarity of two outputs y1, y2 ∈ Y through the concept of margin, which is given by
m(w, CK , x, y1, y2) :=α · F̂w,CK (x, y1)− F̂w,CK (x, y2). (6) For an input x, the potentially good solutions are those in
I(x,w, CK) := { y ∈ Y : m(w, CK , x, hαw,CK (x), y) ≤ α
2 · F̂w,CK (x, hαw,CK (x))
} . (7)
Intuitively, these are the solutions that are similar to the suboptimal one hαw,CK (x) in terms of the score function associated with w and CK . For each w, the training error is then taken by the worst-case loss over the possible y within the margin, which is
L(w, CK , Sm) := 1
m m∑ i=1 max y∈I(xi,w,CK) l(xi, y).
Notice that the loss L(w̃, CK , Sm) associated with the seed vector w̃ can be used to bound the training error with respect to w, provided that the predictions are within the margin (with high probability). With such intuitions, we have the first learning bound.
Theorem 1. For each w̃, CK , and δ > 0, with probability at least 1− δ, we have
L(USCO-SolverSm ,DX , l) ≤ L(w̃, CK , Sm) + ‖w̃‖2
m + √√√√ ln 2Km‖w̃‖2 ( 4‖w̃‖minp |w̃p|·α2 )2 + ln mδ 2(m− 1)
The proof is inspired by the PAC-Bayesian framework [20, 21] applying to approximate structured prediction [22, 19], where our contribution lies in the analysis of the multiplicative margin.

heading: 3.2.2 Approximation loss
text: In line with Equation 2, one natural loss function is the approximation ratio of the predictions, which is
lapprox(x, ŷ) := 1−min( F (x, ŷ, φtrue)
F (x,Hα(x, φtrue), φtrue) , 1) ∈ [0, 1]. (8)
Essentially, we seek to generalize the approximation guarantee from the training samples to future inputs, and the guarantees on the training samples are limited by the oracle. With such, we hope to compare the generalization error under lapprox with α. According to Theorem 1, with an unlimited supply of training data (i.e., m→∞), the generalization error is bounded by L(w̃, CK , Sm), and therefore, the learning error of the ERM solution is concentrated on
inf w̃
Ex∼DX [
max y∈I(xi,w̃,CK)
lapprox(xi, y) ] . (9)
Relating the above quantity with α is not possible for the general case because the score function F̂w̃,CK (x, y) defining the margin is independent of the objective function F (x, y, φtrue) inducing the error. However, more concrete results can be obtained for the approximation loss, by leveraging a subtle relationship between our construction of the kernel function and the stochastic combinatorial optimization problem. The next result characterizes the relationship between Equation 9 and α.
Theorem 2. Suppose that f(x, y, c) ∈ [A,B] and C := supc φtrue(c) φem(c) . For each > 0, δ1 > 0, δ2 > 0 and φem, when K is no less than
2 · C2 ·B2
2 · δ22 ·A2 ·max(1 2 , ln |Y |+ ln 1 δ1 ) (10)
with probability at least 1− δ1 over the selection of CK , there exists a w̃ such that
Pr x∼DX
[ max
y∈I(xi,w̃,CK) lapprox(xi, y) ≤ (1 + )− (1− )(α2/2) (1 + )
] ≥ 1− δ2.
The above result shows that the approximation ratio in generalization is essentially bounded by α2/2. It is intuitive that the bound on K depends on the deviation of φem from φtrue (i.e., C), the range of the objective function (i.e.. B/A), and the size of the output space.

heading: 3.3 Training algorithms
text: Theorems 1 and 2 have explained how m, K and φem may affect the generalization performance in theory. Practically, K can be conveniently taken as a hyperparameter, and φem is often the uniform distribution over C (unless prior knowledge about φtrue is given). Now, for the four steps in Sec. 3.1, the only problem left is to compute the seed vector w̃.
Relaxed margin. While Theorem 2 indicates that there exists a desired weight, we are not able to search for such a weight directly because the loss function lapprox is not accessible under our setting. In practice, one can adopt the zero-one loss or other loss function preferred by the considered problem. For example, when the output space is a family of sets, the loss function can be induced by the set similarity [23]. For a general loss function l(xi, y), Theorem 1 suggests computing the weight w̃ by minimizing the upper bound L(w̃, CK , Sm) + ‖w̃‖ 2
m :
min w max y
l(xi, y) · 1(y ∈ I(xi,w, CK)) + ||w||2,
where 1 is the indicator function. Notice that the above problem is not only non-convex but also complicated by the fact that w and hαw,CK (x) are convoluted with each other. For ease of optimization, a relaxed margin will be useful, as seen shortly. Notice that we have F̂w,CK (xi, h α w,CK
(xi)) ≥ α · F̂w,CK (xi, yαi ), and therefore, for each y ∈ Y , y ∈ I(xi,w, CK) implies that
y ∈ I(x,w, CK) := { y ∈ Y : α 2
2 · F̂w,CK (xi, yαi )− F̂w,CK (xi, y) ≤ 0
} ,
where the new margin I is measured with respect to yαi instead of h α w,CK (xi). Immediately, we have I(xi,w, CK) ⊆ I(xi,w, CK), which indicates that the error is further upper bounded by
max y
l(xi, y) · 1(y ∈ I(xi,w, CK)) + ||w||2, (11)
which is less challenging to minimize.
Large-margin training. Seeking a large-margin solution and scaling the margin proportional to the loss function, Equation 11 amounts to solving the following problem:
min 1 2 ‖w‖2 + C 2m m∑ i=1 ξi
s.t. α2
2 wTKCK (xi, yαi )−wTKCK (xi, y) ≥ η · l(xi, y)− ξi, ∀i ∈ [m], ∀y ∈ Y, y 6= yαi
w ≥ 0
where C and η are hyperparameters. Notably, this is the vanilla structured SVM [16, 24]. Viewing KCK as a score function, the constrains enforces that the solution yαi provided by the training data should have a high score. The above formulation appears to be a standard quadratic programming, but it in fact contains | Y | number of constrains, which can be prohibitively large (e.g., exponential in the coding length of the configuration). Since the constraints are equivalent to
max y∈Y
wTKCK (xi, y) + η · l(xi, y) ≤ α2
2 wTKCK (xi, yαi ) + ξi, ∀i ∈ [m],
the number of constraints could be reduced as linear in sample size if we can effectively solve the loss-augmented inference problem:
max y∈Y
wTKCK (xi, y) + η · l(xi, y)
For the zero-one loss, this is exactly to solve maxy∈Y wTKCK (xi, y), which, to our delight, can be solved using the oracle in Sec. 2.1. Once such loss-augmented inference problem can be solved, the entire programming can be readily solved by existing methods, such as the cutting-plane algorithm [25]. This completes the learning framework. Remark 1. While our discussion so far is focused on maximization problems, the theoretical analysis can be adapted to minimization problems easily. In the training part for minimization problems, the major adaption is to reverse wTKCK (xi, yαi ) and wTKCK (xi, y), which also turns the lossaugmented inference into a minimization problem. Remark 2. For the stochastic shortest path problem, φem denotes a distribution over a collection C of weighted graphs, and assuming the weights are nonnegative, we may use Dijkstra algorithm as the oracle, as maxy∈Y F̂w,C(x, y) amounts to computing the shortest path in the combining graph of the sampled weighted graphs.

heading: 4 Empirical studies
text: This section presents experiments across a variety of combinatorial problems, including stochastic shortest path (SSP), stochastic set cover (SSC), and stochastic bipartite matching (SBM). In addition to supporting the theoretical analysis, our empirical studies are of interest also because none of the existing methods is known to be effective for solving any USCO problem.
Evaluation metric. For each training pair (xi, yαi ) and a prediction ŷ, the performance ratio is defined as F (xi,y α i ,φtrue)
F (xi,ŷ,φtrue) for maximization problems and F (xi,ŷ,φtrue)F (xi,yαi ,φtrue) for minimization problems.
Therefore, lower is better in both cases. The performance is measured over five random testings. We here present the main experimental settings and discuss key observations, deferring the complete analysis to Appendix B.

heading: 4.1 Stochastic shortest path (SSP)
text: Problem definition and oracle. In the stochastic version of the shortest path problem, given a source u and a destination v in a graph G = (V,E), we wish to find the path (from u to v) that is the shortest in terms of a distribution over the possible edge weights. In this case, the configuration space C denotes a family of weighted graphs associated with a distribution φtrue, the input x = (u, v) is a pair of nodes, the output y is a path from u and v, and f(x, y, c) denotes the length of y in graph c. We construct instances where the edge weights are non-negative, and thus, each function in Equation 3 can be minimized optimally using the Dijkstra algorithm [26], which is the oracle we use to generate samples and solve the inference problem in USCO-Solver.
Instance construction. To setup a concrete instance, we first fix a graph structure, where two real-world graphs (Col and NY) and one synthetic graph (Kro) are adopted. Col and NY are USA road networks complied from the benchmarks of DIMACS Implementation Challenge [27], and Kro is a Kronecker graph [28]. Following the common practice [29], we assign each edge a Weibull distribution with parameters randomly selected from {1, ..., 10}, which – together with the graph structure – induces the configuration space C and φtrue. For each instance, we generate the pool of all possible input-solution pairs (x, y), where, for an input x = (u, v), y is the optimal solution to miny∈Y F (x, y, φtrue). For each considered method, we randomly select 160 training samples and 6400 testing samples from the pool.
Implementing USCO-Solver. We setup two realizations (φexp and φtrue) of φem that will be used in USCO-Solver. φexp assigns each edge in E an exponential distribution normalized in [1, 1e5], and φtrue is exactly the true underlying distribution that defines the instance. Notice that φtrue is not obtainable under our learning setting, and it is used only to verify our designs. For each distribution, we sample a pool of 10000 configurations (i.e., weighted graphs). The number of configurations (i.e., K) is enumerated from small to large, with different ranges for different datasets. Given the size K, the configurations are randomly selected from the pool in each run of USCO-Solver. We use the zero-one loss, and the training algorithm is implemented based on Pystruct [30].
Implementing other competitors. For a baseline, we implement the Base method which, given an input x = (u, v), outputs the shortest path from u to v in G where the edge weights are randomly sampled from [0, 1]. Conceptually, our problem can be perceived as a supervised learning problem from V ×V to the space of the paths, and thus, off-the-shelf learning methods appear to be applicable, which however turns out to be non-trivial. We managed to implement two methods based respectively on Naive Bayes (NB) [31] and Deep Set Prediction Networks (DSPN) [32], where the idea is to
leverage them to learn the node importance in the shortest path and then build the prediction based on the node importance.
Observations. The main results are presented in Table 1. We highlight two important observations: a) the performance of USCO-Solver smoothly increases when more configurations are provided, and b) when fed with configurations from the true distribution φtrue, USCO-Solver can easily output near-optimal solutions on all the datasets. These observations confirm that USCO-Solver indeed functions the way it is supposed to. In addition, the efficacy of USCO-Solver is significant and robust in terms of the performance ratio. On datasets like Col and NY, it can produce near-optimal solutions using φexp. Meanwhile, other methods are not comparable to USCO-Solver, though DSPN offers non-trivial improvement compared with Base on NY and Kro. It is also worth noting that different instances exhibit different levels of hardness with respect to the number of configurations needed by USCO-Solver. 3200 configurations are sufficient for USCO-Solver to achieve a low ratio on Col, while the ratio is still larger than 4.0 on Kro even though 9600 configurations have been used. See Appendix B.2 for a complete discussion.

heading: 4.2 Stochastic set cover (SSC)
text: In network science, coverage problems often require to compute a set of terminals that can maximally cover the target area [33]; in applications like recommendation system or document summarization [34], one would like to select a certain number of items that can achieve the maximum diversity by covering topics as many as possible. These problems can be universally formulated as a maximal coverage problem [35], where each instance is given by a family U of subsets of a ground set, where our goal is to select a k-subset of U of which the union is maximized. In its stochastic version, we assume that an item will appear in a subset with a certain probability [36]. The oracle we use is the greedy algorithm, which is a (1− 1/e)-approximation [37]. We construct two instances based on two real-world bipartite graphs Cora [38] and Yahoo [39]. Similar to the setup for SSP, we first generate the ground truth distribution φtrue and then generate samples. We implement two learning methods based on Graph neural network (GNN) and DSPN, together with a baseline method Rand that randomly selects the nodes in ŷ. For USCO-Solver, we consider a distribution φuni that generates a configuration by generating subsets uniformly at random. See Appendix B.3 for details.
The results are presented in Table 2. First, the observations here are similar to those in the SSP problem – USCO-Solver works in a manner as we expect, and it can produce high-quality solutions when a sufficient number of configurations are provided. We can see that GNN and DSPN are also effective compared with Rand, which suggests that, compared to SSP, SSC is much easier for being handled by existing learning methods.

heading: 4.3 Stochastic bipartite matching (SBM)
text: Our last problem is bipartite matching, which is regularly seen in applications such as public housing allocation [40], semantic web service [41] and image feature analysis [42]. We consider the minimum weight bipartite matching problem. Given a weighted bipartite graph G = (L,R,E), the input x = (L∗, R∗) consists of two subsets L∗ ⊆ L and R∗ ⊆ R with |L∗| = |R∗|, and the output y is a perfect matching between L∗ and R∗ such that the total cost is minimized. In other words, y is a bijection between L∗ and R∗. In its stochastic version, the weight we for each edge e ∈ E follows a certain distribution, and we aim to compute the matching that can minimize the expected
cost F (x, y, φtrue). Notice that the minimum weight bipartite matching problem can be solved in polynomial time by linear programming [43], which is a natural oracle to use in USCO-Solver. We adopt a synthetic bipartite graph with 128 nodes. The weight we for each edge e ∈ E follows a Gaussian distribution N (µe, σe) with µe sampled uniformly from [1, 10] and σe = 0.3 · µe, which induces the true distribution φtrue. See Appendix B.4 for details.
Results under φuni. For USCO-Solver, we consider φuni that generates the configuration c by giving each edge a weight from [1, 10] uniformly at random. We also test USCO-Solver with features from the true distribution φtrue. The baseline method Rand produces y for a given input x = (L∗, R∗) by randomly generating a permutation of R∗. The result of this part is shown in Table 3. We see that USCO-Solver can again produce a better ratio when more configurations are provided, but different from SSP and SSC, it cannot achieve a ratio that is close to 1 even when 19200 configurations have been used. Plausibly, this is because the output space of SBM is more structured compared with SSP and SSC.
Incorporating prior knowledge into USCO-Solver. For problems like bipartite matching where uniform configurations cannot produce a near-optimal solution, it would be interesting to investigate if USCO-Solver can easily benefit from domain expertise. To this end, given a parameter q ∈ {0.3, 1, 5, 10}, we consider the distribution φq that samples the weight for edge e from [µe − q · µe, µe + q · µe], which accounts for the case that a confidence interval of the weight we is known. The performance ratios produced by such distributions are shown in Table 4. As we can see from the table, the result indeed coincides with the fact that the prior knowledge is strong when p is small. More importantly, with the help of such prior knowledge, the ratio can be reduced to nearly 1 using no more than 160 configurations under φ1, while under the uniform distribution φuni, the ratio was not much better than Rand with the same amount of configurations (as seen in Table 3).

heading: 5 Further discussions
text: Related work. The learning-and-optimization framework has been used widely (e.g., [44, 45, 46, 47, 48]). For example, Du et al. [49] and He et al. [50] study the problem of learning influence function which is used in influence maximization; recently, Wilder et al. [51] proposes a decision-focused learning framework based on continuous relaxation of the discrete problem. In contrast to these works, we consider the input-solution regression without attempting to learn the objective function. A similar setting was adopted in [52] for studying a special application in social network analysis, but our paper targets abstract problems and provides generalization bounds on the approximation ratio. There have been recent efforts to develop learning methods that can handle combinatorial spaces (e.g., [53, 54, 32]), where the key is to preserve the inherited combinatorial structures during the learning process. Our research is different because the problem we consider involves a hidden optimization problem; in other words, we target the optimization effect rather than the prediction accuracy. Our research is also related to the existing works that attempt to solve combinatorial optimization problems using reinforcement learning [55, 56, 57, 58]; however, the objective function is known in their settings, while we study the model-free setting.
Limitations. Our theoretical analysis is based on the assumption that y is an approximation solution in each input-solution (x, y), but in practice, it may be impossible to prove such guarantees for real datasets. Thus, it is left to experimentally examine USCO-Solver using the training pairs (x, y) where
y is produced using heuristic but not approximation algorithms. In another issue, we have shown that USCO-Solver is effective for three classic combinatorial problems, but it remains unknown if USCO-Solver is universally effective, although it is conceptually applicable to an arbitrary USCO problem. In addition, our experiments do not rule out the possibility that off-the-shelf learning methods can be effective for some USCO problems (e.g., SSC), which suggests a future research direction. Finally, we hope to extend our research by studying more practical applications involving highly structured objects, such as Steiner trees, clustering patterns, and network flows. See Appendix C for a more comprehensive discussion.
Acknowledgments and Disclosure of Funding
We thank the reviewers for their time and insightful comments. Funding in direct support of this work: support from the University of Delaware.

Review summaries:
This paper proposes a framework for learning to predict approximate solutions to stochastic combinatorial optimization problems. The class of problems is referred to as "undetermined" stochastic combinatorial optimization. "Undetermined" here refers to the following assumption on the available training data: each data point is a pair (x, y), where x is the input to the stochastic optimization problem (e.g., source-target pairs in an s-t shortest path problem on a fixed graph), and y is an approximate solution; notice how information about the probability distribution over which the true stochastic objective function is defined (e.g., edge weights) is not available in the training set (neither via a set of sample scenarios nor a generator), hence "undetermined".  USCO-Solver does the following in the training phase: it selects an arbitrary distribution over the unknown stochastic parameters of the problems (e.g., edge weights in a graph), samples K configurations, then searches for a weight vector for the K samples such that the true solution (y) is also near-optimal in another optimization problem whose objective function is a linear combination of the K configurations' objectives. This training problem is framed as a structured prediction task which is amenable to structured SVM-style optimization algorithms. Key to the training is the use of an oracle for the deterministic counterpart of the stochastic problem.  Experiments on randomly generated datasets for stochastic shortest path, set cover, and bipartite matching show that USCO-Solver performs significantly better than "direct" ML methods that are trained to simply fit the training set without regard to the combinatorics or stochastic nature of the true optimization problem. 

The paper presents USCO-Solver, a new solver that is able to handle abstract undetermined stochastic combinatorial optimisation problems. The main contribution is a learning framework that allows the solver to infer high quality solutions from samples of input-output pairs without having to learn the objective function. This approach seems to contrast the well known learning-and-optimisation strategy. An empirical evaluation on several classic combinatorial problem domains demonstrate the effectiveness of the proposed approach.

In this paper, the authors propose USCO-Solver, a unified approach to solving stochastic combinatorial optimization by learning the weights of the kernel function. The learning step is similar to SVM. The authors conduct experiments on 3 stochastic problems.