# Maximizing sum of probabilities with variable distributions

Suppose $$\\{X_i\\}$$ are binary decision variables and $$\\{A_j\\}$$ are Skellam random variables with $$(\mu_1, \mu_2) = (\sum_i b_{i} X_i, c_j)$$. Here, $$b_i, c_j \in \mathbb{R}^{\geq 0}$$ are constants. The goal is to maximize the function $$f(X_1, X_2, \dots, X_n) = \sum_j P(A_j > 0)$$ subject to certain linear constraints in the $$X_i$$. What are some known computational methods for solving this problem?

One possible approach is as follows: let $$F_j(x)$$ be the CDF of a Skellam variable with $$(\mu_1, \mu_2) = (x, c_j)$$. For each $$j$$, we can approximate $$F_j$$ by a piecewise linear function. Then the original problem can be formulated as an integer linear programming problem. However, this approach doesn't seem especially robust to me; for instance, I'm not sure how to determine the number of sample points to use for the linear approximation (given an error tolerance) nor how to space the sample points.

• How big is $n$? What do the linear constraints look like? Nov 29, 2023 at 4:48
• @RobPratt $n$ is small, usually about $10$. All of the constraints are of the form $\sum_{i \in I} X_i \leq C_I$ for some index set $I$. Nov 29, 2023 at 5:18
• OK, $n=10$ is small enough for complete enumeration. An alternative exact approach is combinatorial Benders decomposition, with dynamically generated optimality cuts to enforce the correct objective value. Nov 29, 2023 at 5:40
• @RobPratt sorry, I made a mistake transcribing the problem. $n$ is between 40 and 60, so complete enumeration is not possible. I will look into Benders decomposition. Nov 29, 2023 at 5:48
• To get an upper bound better than just the trivial $\sum_j 1$, you can first maximize $\sum_i b_i X_i$ subject to the linear constraints and then compute $f$ for the resulting $X^*$. Are you able to share the data? Nov 29, 2023 at 14:25

$$\underset{x, t}{\text{max}} \hspace{0.1in} t \\ \text{subject to} \\ t \leq \sum_{i} P(A_{i} > 0)$$
We want to make the new variable $$t$$ as large as possible, but $$t$$ must be smaller than the joint probability that you are interested in, which is obviously bounded above by 1. With chance constraints, you can reformulate the RHS of the constraint.