1 Introduction

Graph partitioning problem refers to partitioning the set of nodes of a graph in several disjoint node subsets (or clusters), so that the sum of the weights of the edges whose end-nodes are in different clusters is minimized. A number of variants of the problem have been investigated in the literature depending on constraints imposed on the clusters. We consider here the graph partitioning problem with the knapsack constraints (GPKC) which is defined formally as follows. Given an undirected graph \(G=(V,E)\) with \(n=\vert V\vert \) and \(m=\vert E\vert \). The edges in E are weighted by a vector \(t\in \mathbb {R}^{\vert E\vert }\) and the nodes in V are weighted by a vector \(w\in \mathbb {R}^{\vert V\vert }\). We want to find a partition of V into \(V_1,\ldots ,V_k\) such that:

  1. (i)

    For all \(1\le i\le k,\ \sum _{v\in V_i} w_v \le W\) where W is a given constant,

  2. (ii)

    \(\sum _{i=1}^{k-1} \sum _{j=i+1}^k \sum _{\begin{array}{c} uv\in E\\ u\in V_i\\ v\in V_j \end{array}} t_{uv}\) is minimized.

Note that in the above definition, the number k of clusters is not imposed and is a part of the output of the optimization process. The constraints specified in (i) has the structure of the knapsack constraints as reflected in the acronym GPKC. Variants of this problem have already been considered by several authors before, e.g. Sørensen [24], Labbé et al. [18], Bonami et al. [3], Goldschmidt et al. [16]. Besides GPKC, other variants of graph partitioning problem have been investigated involving additional restrictions. Garey et al. [15], Chopra and Rao [5, 6], Ferreira et al. [12] consider the problem of partitioning a graph into at least (resp: no more than), k clusters with no size restriction on the clusters. The cut polytope which is associated with partitioning into two clusters with no size restriction on the clusters is studied by Barahona and Mahjoub [1] and Deza and Laurent [8, 9].

The stochastic version of GPKC referred to as SGPKC, addressed in the present paper considers the case when the node weights are uncertain. These weights follow a multivariate Gaussian distribution with given mean and covariance matrix. Give a probability level \(\varepsilon \in [0,1]\), the knapsack constraints in (i) can be formulated as chance constraints of the form \(P(\sum _{v\in V_i} w_v \le W)\ge 1-\varepsilon \) for \(i = 1, \ldots , k\). This method was introduced in [4] which is one of the standard methods for handling uncertainty in optimization. In the literature, there are some research on stochastic graph partitioning such as [10] and [2], however the uncertainties in their models impact the edges. The present paper seems to be the first study on the stochastic version of the node weighted graph partitioning problem.

Here we investigate SGPKC under the assumption that w follows a multivariate Gaussian distribution. In the case individual chance constraints and with the probability level \(\varepsilon \) less than 0.5, the chance constraints can then be reformulated as binary second order cone constraints (Binary SOCC) [21]. We discuss an application of the above model relative to partitioning of process networks and we explain why the assumption of a Gaussian distribution of the weights is reasonable in this context.

We present a comparison of several alternative techniques for solving SGPKC: first, we consider the second-order cone formulation for the chance constraint which reduces the SGPKC to a binary second-order cone program (Binary SOCP). The CPLEX solver is used to solve this program. Second, we consider the quadratic formulation for the chance constraint which handle SGPKC as a binary quadratic constrained program. Several linearization techniques are discussed to transform this binary quadratic program into binary linear program. In particular, we consider the classical linearization technique (Fortet [13]) and the linearization using bilinear forms given by Sherali–Smith [23]. Note that contrary to the former, the latter uses much fewer additional variables. Again the CPLEX solver is used for solving the resulting binary linear programs.

The numerical results obtained show that the solution technique using Sherali–Smith linearization provides better efficiency for SGPKC, than the one using binary SOCP; the latter in turn outperforms the classical linearization technique. This shows that although the quadratic formulation of chance constraint is not convex when relaxed (contrary to the second-order formulation), it provides better efficiency as compared with the second-order cone formulation when the variables are binary and a branch-and-bound procedure has to be applied.

2 Problem statement and binary SOCP formulation

2.1 Problem formulation

In this section, we propose a 0–1 formulation for SGPKC in which the variables represent the relations between nodes. We use variables \(x_{ij}\) for all pairs of nodes (i, j) such that \(x_{ij}=1\) if i and j are in the same cluster, and 0 otherwise. We denote \(E_n :=\lbrace (i, j) : i \in V, j \in V, i < j\rbrace \) the set of all ordered pairs of nodes and by \({\mathcal {T}} := \lbrace (i, j, k) : (i, j), (i, k), (j, k) \in E_n\rbrace \) the set of all ordered triples.

In the deterministic case, the version of graph partitioning problem that we study includes all the knapsack constraints that express the fact that the total node weight of the cluster containing u should not exceed W. In this paper, we consider the non-deterministic case where the node weights w are random variables. To handle this problem using chance constrained programming, the knapsack constraints are reformulated as chance constraints \(P(\sum _{\begin{array}{c} v\in V \end{array}}x_{vu} w_v\le W)\ge 1-\varepsilon \) for the cluster containing the node u and with the probability level \(\varepsilon \). Hereafter it will be assumed that the probability distribution of node weights is a multivariate Gaussian law with given means \((\bar{w}_i)_{1\le i\le n}\) and covariance matrix \((\sigma _{ij})_{1\le i,j\le n}\). We therefore reformulate the chance constraints by the Binary SOCCs as follows. For all clusters \(i=1,\ldots ,n\),

$$\begin{aligned} \sum _{u=1}^n x_{ui} \bar{w}_u+\gamma \sqrt{\sum _{u=1}^n\sigma _{uu}x_{ui}^2+2\sum _{u=1}^{n-1} \sum _{v=u+1}^n \sigma _{uv}x_{ui}x_{vi}} \le W \end{aligned}$$
(1)

where \(\gamma ={\mathcal {F}}^{-1}(1-\varepsilon )\), \({\mathcal {F}}\) denoting the cumulative distribution function of \({\mathcal {N}}(0,1)\) (e.g. \(\gamma \simeq 1.685\) for \(\varepsilon = 0.05\)). In the proposed model, the various chance constraints on the various clusters are considered as individual chance constraints.

Then the resulting model for SGPKC is the following Binary SOCP program:

where the triangle constraints guarantee the consistency of the partitions, i.e. if the nodes i, j belong to the same cluster and so do the nodes i, k then j and k belong to the same cluster. The number of constraints of (I) is clearly \(O(n^3)\), and thus polynomial in terms of n. Hence, it represent a compact 0–1 formulation for the SGPKC. However, [14] shows that the large number of triangle constraints may lead to a huge computation time for the formulation (I). The possibility of reducing the number of triangle constraints for a sparse graph where \(\vert E\vert =m\ll \frac{n(n-1)}{2}=\vert K_n\vert \) has been investigated in [22] where it is shown that only part of the triangle inequalities are needed. More precisely, let \({\mathcal {T}}^{'} = \lbrace (i,j,k): i\ne j\ne k \in V\) and at least one of the edges ij, ik and jk \(\in E\rbrace \). Then an equivalent reduced integer program formulation for (I) is:

For a formal proof of the equivalence between (Bi-SOCP) and (I) refer to [22]. It is clear that \(\vert {\mathcal {T}}^{'}\vert \le m(n-2)\) thus the number of triangle constraints in (Bi-SOCP) is O(mn) instead of \(O(n^3)\).

We can see that the continuous relaxation of (Bi-SOCP) is a second-order cone program thus it can be solved using SOCP. SOCP has shown its effectiveness in solving nonlinear convex problem that include linear and (convex) quadratic programs as special cases. Several efficient primal-dual interior-point for SOCP have been developed in the last few years which share many of the features of primal-dual interior-point methods for linear programming (LP). However, the algorithmic efficiency of SOCP solvers when embedded into a tree search branch-and-bound to handle Bi-SOCP problem partly remains an open research problem.

2.2 Problem of partitioning process networks and uncertainty of processing time

As a typical example of application of (SGPKC), we can mention a problem arising in the field of compilation for real-time embedded systems, the task allocation problem in multi-core structures. The goal is to find a feasible placement of all tasks to processors while respecting their computing capacity and minimizing the total volume of inter-processor communication. The nodes and edges are weighted by a positive real number could represent the execution time of the task or the volume of data exchanged between tasks. In a partition of the nodes of G, each cluster contains tasks to place in the same processor and it is subject to the type of knapsack constraints that limits the total duration of the tasks in the cluster by a constant. Known for the one-dimensional and deterministic case as the Node Capacitated Graph Partitioning problem [12], the stochastic version of the problem does not seem to have been investigated so far except from a non-parametric and approximate resolution view point [25].

In this problem, one of the main sources of uncertainties lies in the intrinsic indeterminism of execution times for computing kernels of intermediate granularity. This indeterminacy is due firstly to certain characteristics of processor architectures (presence of memories of arbitrators access caches, etc.) but also, inherently, to the presence of conditional branch structures and dependent loops input data. The distributions of processing times are often complex, sometimes giving use to multimodal distributions (due to the presence of data dependent control). However, in spite of the fact that the Gaussian assumption on the random variables is not verified, the use of multivariate Gaussian approximation is still reasonable, based on the extended central limit theorem. Indeed if we assume that for a given u, the number of \(x_{vu}\) variables equal to 1 (i.e. the cardinality of the cluster containing u) is sufficiently large (typically more than 30–40), the chance constraints

$$\begin{aligned} P\left( \sum _{\begin{array}{c} v\in V \end{array}}x_{vu} w_v\le W\right) \ge 1-\varepsilon \quad \forall u\in V \end{aligned}$$

involve a combination of sufficiently many random variables, which can be approximated as a normal random variable under some conditions that the means and the variances have to satisfy. These conditions were introduced in the Lindeberg–Feller theorem [11, 19] and its corollary, the Liapounov’s theorem [20]. This condition was studied for sums of N independent random variables \((X_i)_{1\le i\le N}\) with means \((m_i)_{1\le i\le N}\) and variances \((a_i^2)_{1\le i\le N}\). Let \(s_n^2=\sum _{i=1}^N a_i^2\) then:

$$\begin{aligned}&\lim _{N\rightarrow \infty } \frac{1}{s_n^2} \sum _{i=1}^N {\mathbb {E}} \left[ (X_i - m_i)^2\mathbbm {1}_{\lbrace \vert X_i - m_i\vert >\epsilon s_n\rbrace }\right] =0,\nonumber \\&\quad \forall \epsilon >0\Longrightarrow \frac{\sum _{i=1}^N \left( X_i-m_i\right) }{s_n}\xrightarrow {\mathbb {P}} {\mathcal {N}}(0,1) \end{aligned}$$
(2)

Lindeberg’s condition is sufficient, but not in general necessary. However if \(\lim _{N\rightarrow \infty } \max _{i=1,\ldots ,N}\frac{a_i^2}{s_n^2}\rightarrow 0\), this condition is both sufficient and necessary. For dependent random variables, the central limit theorem remains valid under conditions investigated in [7]. We have carried out some systematic experiments showing that, for sum of N multimodal random variables (three modes were considered in our experiments), good approximations of the Gaussian cdf are obtained as soon as N exceeds typically 30 to 40.

3 Quadratically constrained 0–1 programming reformulation and linearization techniques

As an alternative to Binary SOCP, we investigate here a quadratic formulation for the (SGPKC). To achieve this, we only need to replace the SOCCs (1) in (Bi-SOCP) with their equivalent quadratic forms:

$$\begin{aligned} \left\{ \begin{aligned}&-2\sum _{u=1}^{n-1} \sum _{v=u+1}^n (\bar{w}_u \bar{w}_v-\gamma ^2 \sigma _{uv})x_{ui}x_{vi}+\sum _{u=1}^n (2W\bar{w}_u+\gamma ^2 \sigma _{uu}-\bar{w}_u^2)x_{ui}\le W^2\\&\sum _{u=1}^n x_{ui}\bar{w}_u\le W \end{aligned} \right. \end{aligned}$$
(3)

Since the quadratic formulation is difficult to handle directly, we will consider reformulations using various linearization techniques. The first technique discussed below is basically the classical linearization technique [13] and the second one is the linearization technique proposed by Sherali and Smith [23].

We first simplify (3) by setting:

$$\begin{aligned} \left\{ \begin{aligned}&q_{uv}=2(\bar{w}_u \bar{w}_v-\gamma ^2 \sigma _{uv})\\&d_u=2W\bar{w}_u+\gamma ^2 \sigma _{uu}-\bar{w}_u^2 \end{aligned} \right. \end{aligned}$$
(4)

then the quadratic constraint in (3) reads:

$$\begin{aligned} \sum _{u=1}^n d_ux_{ui}-\sum _{u=1}^{n-1} \sum _{v=u+1}^n q_{uv}x_{ui}x_{vi}\le W^2 \end{aligned}$$
(5)

3.1 Classical linearization technique

Introducing variable \(y_{uvi}\) to represent each product \(x_{ui} x_{vi}\) then (5) is replaced with:

$$\begin{aligned} \left\{ \begin{aligned}&\sum _{u=1}^n d_ux_{ui}-\sum _{u=1}^{n-1} \sum _{v=u+1}^n q_{uv}y_{uvi}\le W^2\\&\max \left\{ 0,x_{ui}+x_{vi}-1\right\} \le y_{uvi} \le \min \left\{ x_{ui},x_{vi}\right\} \\ \end{aligned} \right. \end{aligned}$$
(6)

Using the classical linearization technique, SGPKC can be reformulated as follows:

It can easily be shown that the constraints \(\max \lbrace 0,x_{ui}+x_{vi}-1\rbrace \le y_{uvi} \) is redundant and can be removed. A drawback of the above formulation (referred to as an “extended formulation” because of the introduction of the extra variables \(y_{uvi}\)) is the large number of variables and constraints it requires. Note that in our graph partitioning problem, for a complete graph with n vertices the quadratic formulations we study already have \(O(n^2 )\) variables and the extended formulation \(O(n^3 )\) variables and also \(O(n^3 )\) added constraints. This can become rapidly unpractical. In the following subsection, we discuss an alternative linearization technique requiring fewer additional variables and additional constraints.

3.2 Sherali–Smith’s linearization technique

This linearization technique has been introduced in [23]. The basic idea underlying this technique is:

  • To transform each quadratic form into a bilinear form using O(n) additional variables: applied to the quadratic constraint (5), it consists in introducing variable \(\lambda _{ui}\) to represent each sum \(\sum _{v=u+1}^n q_{uv}x_{vi}\). If a lower bound \(\lambda _{ui}^{min}\) and an upper bound \(\lambda _{ui}^{max}\) are known for \(\lambda _{ui}\) then the quadratic constraint (5) can be rewritten as:

    $$\begin{aligned} \left\{ \begin{aligned}&\sum _{u=1}^n d_{ui}x_{ui} - \sum _{u=1}^{n-1}x_{ui}\lambda _{ui} \le W^2\\&\sum _{v=u+1}^n q_{uv}x_{vi}=\lambda _{ui},&\quad \forall u=1,\ldots , n-1 \\&\lambda _{ui}^{min}\le \lambda _{ui} \le \lambda _{ui}^{max},&\quad \forall u=1,\ldots , n-1\\&x\in \left\{ 0,1\right\} ^n \end{aligned} \right. \end{aligned}$$

  • Linearizing the various bilinear terms resulting from the above transformation: this is done by introducing a variable \(z_{ui}\) to represent each product \(x_{ui} \lambda _{ui}\):

    $$\begin{aligned} \left\{ \begin{aligned}&\sum _{u=1}^n d_{ui}x_{ui} - \sum _{u=1}^{n-1}z_{ui} \le W^2\\&\sum _{v=u+1}^n q_{uv}x_{vi}=\lambda _{ui},&\quad \forall u=1,\ldots , n-1 \\&\lambda _{ui}^{min} x_{ui}\le z_{ui} \le \lambda _{ui}^{max} x_{ui},&\quad \forall u=1,\ldots , n-1 \\&\lambda _{ui}^{min}\left( 1- x_{ui}\right) \le \lambda _{ui} - z_{ui} \le \lambda _{ui}^{max}\left( 1- x_{ui}\right) ,&\quad \forall u=1,\ldots , n-1 \\&x\in \left\{ 0,1\right\} ^n \end{aligned} \right. \end{aligned}$$

  • We focus our study in the case the node weights are all positives (i.e. \(w_i\ge 0, \forall i\in V\)). This case is suitable for most of the applications of SGPKC including the task allocation problem and to the best of our knowledge, there are no known applications of GPKC with negative node weights. We assume also that the variances are small compared to the means, so that \(q_{uv}=2(\bar{w}_u \bar{w}_v-\gamma ^2 \sigma _{uv})>0, \forall 1\le u< v\le n\). Consequently, we have \(\lambda _{ui}^{min}=0\). Let us introduce new variables \(h_{ui}=\lambda _{ui}-z_{ui}\) to the model. A brief analysis shows that these variables are nonnegative and act as slack variables in the constraints \(\sum _{v=u+1}^n q_{uv}x_{vi}=\lambda _{ui}\) when \(\lambda _{ui}\) is replaced by \(h_{ui}+z_{ui}\). Hence, we can ignore the variables \(h_{ui}\)’s and the constraints \(\lambda _{ui}^{min}\left( 1-x_{ui}\right) \le \lambda _{ui}-z_{ui} \le \lambda _{ui}^{max}\left( 1-x_{ui}\right) \) can be removed. In the general case when the node weights may be negative (i.e. \(w_i\in \mathbb {R},\forall i\in V\)), these constraints should not be removed. However, even in this case, the number of constraints of the problem do not increase asymptotically.

Applying the various transformations above to constraints (5) in the quadratic formulation of SGPKC, we can reformulate it as follows:

The above formulation (SS) requires fewer variables and constraints when compared with the classical linearization (CL). For instance, in our problem for a graph with n vertices, the number of added variables and the number of added constraints are \(O(n^2 )\). However as shown in [23], this is at the expense of weaker relaxation as compared with the classical linearization technique.

The last unknown parameters in this formulation are the bounds \(\lambda _{ui}^{min}\) and \(\lambda _{ui}^{max}\) that can be estimated based on the definition of added variables \((z_{ui})_{1\le i\le n-1}\). Note that we assumed \(q_{uv}\ge 0,\ \forall (u,v)\) therefore \(\lambda _{ui}^{min}=0 \). We will consider two estimates for \(\lambda _{ui}^{max}\) in the following, two variants of the Sherali–Smith reformulation will thus be obtained. In the general case when \(q_{uv}\in \mathbb {R},\ \forall (u,v)\), \(\lambda _{ui}^{min}\) are estimated similarly.

3.2.1 Simple bounds on \(\lambda _{ui}^{max}\)

Note that since \(q_{uv}\ge 0,\ \forall (u,v)\), we can take

$$\begin{aligned} \lambda _{ui}^{max}=\sum _{v=u+1}^n q_{uv} \end{aligned}$$
(7)

It is observed that \(\lambda _{ui}^{max}\) does not depend on i, so at most n values have to be computed. Using these bounds for \(\lambda _{ui}^{max}\) in (SS), we obtain a first formulation based on Sherali–Smith’s technique.

3.2.2 Improved bounds on \(\lambda _{ui}^{max}\)

The application of Sherali–Smith technique can be made more efficient if we can obtain a better estimate of the bounds \(\lambda _{ui}^{max}\). The idea is the fact that we can get stronger bounds of each sum \(\sum _{v=u+1}^n q_{uv}x_{vi}\) by adding valid inequalities in the process of computing them. In our problem, one of the valid inequalities that can be chosen is the stochastic knapsack constraint (1), whereby the bounds can be estimated, for all \(i=1,\ldots ,n\) as:

(8)

Again \(\lambda _{ui}^{max}\) does not depend on i so at most n problems of the form (8) have to be solved. Using the improved bounds \(\lambda _{ui}^{max}\) deduced from (8), we obtain the improved Sherali–Smith formulation (ISS). In addition, we chose the continuous relaxation version of (8) to estimate the bounds \(\lambda _{ui}^{max}\) because our experiments shows that using the integer formulation (8) would not lead to a significant improvement in the quality of the bounds.

4 Computational results

In this section, we present computational results for the SGPKC comparing the formulations that were discussed in the Sect. 4. The formulations are compared in both computation times and gaps.

For a given number of vertices n and number of edges m, we generate five instances by picking edges uniformly at random until the number of edges reaches m. The edge weights t and the means of node weights \(\bar{w}\) are drawn independently and uniformly from the interval [1, 1000], the covariance matrix \(\sigma \) of node weights is generated as diagonally dominant matrix where each point \(\sigma _{ii}\) \(\forall i=1,\ldots , n\) in the diagonal is drawn independently and uniformly from the interval \([1, 20~\%\,\bar{w}_i]\). For each instance, we calibrate the upper bounds of knapsack constraints W in order to ensure that the generated instances will be not “easy” to solved. To achieve this, we used METIS [17] to estimate the solution with the number of clusters \(k=4\) (or 6, 8, 12) that we call the initial partition, we then do 1000 perturbations of this partition. The resulting bounds on W were then chosen so that only 10 % of these partitions are satisfied. Finally the probability level \(\varepsilon \) was chosen to be 0.05 (\({=}5~\%\)), a fairly standard value in practice.

All experiments are run on a machine with Intel Core i7-3630QM 2.40 GHz processors and 16 GiB of RAM. The solver CPLEX 12.6 is used to solve respectively (Bi-SOCP), (CL), (SS) and (ISS) and to ensure that comparisons will not be biased we switch off CPLEX pre-solve. All computation times are in CPU seconds and the computation times are subject to a time limit of 7200 s.

In Table 1 we report the results obtained with (Bi-SOCP), (CL), (SS) and (ISS). In our experiments, each instance belongs to one of four graph types: series-parallel graph (SP), planar grid graph (PG), toroidal grid graph (TG) and random graph (RG). Series-parallel graphs are highly sparse while random graphs are denser graphs with \(m\approx (4{-}8)\times n\). As for each value of n, m, we have five instances, the first column of each technique in this table report the average CPU time to obtain the solution, the second column of each technique report the average gaps at root node. For the (ISS), the CPU time to calculate the bounds is included in the total CPU time to obtain the solution. For a specific technique and for the instances that this technique guarantee a solution, we note the CPU time as “Nopt” and we indicate the residual gap in parenthesis.

As can be seen from Table 1, (ISS) has the highest performance while (CL) is the least efficient technique in term of computation times. We can arrange the order of effectiveness of these techniques as (ISS) \(\succ \) (SS) \(\succ \) (Bi-SOCP) \(\succ \) (CL).

Table 1 Comparison of the various solution techniques
Full size table

The main observations which arise from the results are the following:

  • As discussed above, the (CL) technique does not perform well for large instances due to a large number of added variables and added constraints. We report the solution times for (CL) are worse by a factor of 2 to 4 than those of (Bi-SOCP).

  • For the small instances, (SS) does not outperform (Bi-SOCP). However for the larger instances, (SS) is slightly faster than (Bi-SOCP) in spite of the fact that the number of nodes in the search tree for (Bi-SOCP) is quite reduced. A possible explanation of this is that: (a) the computational effort required for solving each node is significant, and (b) SOCP solvers do not enjoy the same warm-starting capabilities as simplex-based LP solvers.

  • (ISS) clearly dominates the other techniques as we can see in the table, it is faster by a factor of 1.5 to 3 than (SS) in term of solution times.

  • There are also instances for which CPLEX is not even capable to solve (Bi-SOCP) and (CL), but succeeds to find optimal integer solution with (SS) and (ISS). With (ISS) we can solve larger instances, e.g., (\(n=80\)) for series-parallel graphs, (\(n=70\)) for planar grid graphs, (\(n=60\)) for toroidal grid graphs and (\(n=60\)) for random graphs.

  • We also report the average gaps at the root node for each solution technique. Since (CL), (SS) and (ISS) may be considered as relaxations of (Bi-SOCP), the latter provides the best gaps. Another observation is that although improved bounds for \(\lambda ^{max}\) have been used in (ISS), the gaps at root node have not changed. However the number of nodes in the tree search is reduced in most cases, leading to the reduction of CPU times.

Finally, Table 2 shows the impact of computing the improved bounds for \(\lambda _{ui}^{max}\) on total CPU times for (ISS). The computation times of the bounds reported in the third column are very small as compared to the total solution times of (ISS), while the average improvement on the bounds is quite significant.

Table 2 Computation times of the bounds \(\lambda _{ui}^{max}\) by (8)
Full size table

5 Conclusion

In this paper, a stochastic version of the node weighted graph partitioning problem has been investigated. Practical application in the context of partitioning process network problem has been discussed. It has been shown that transforming an initial SOCP based formulation into quadratic constraints and applying some linearization techniques can be more efficient than solving the usual binary SOCP formulation. As a possible direction for future investigations, it would be interesting to check whether the same type of conclusion can be drawn for other combinatorial optimization problems e.g. featuring knapsack constraints with random coefficients.