1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ How big is $n$? What do the linear constraints look like? $\endgroup$
    – RobPratt
    Nov 29, 2023 at 4:48
  • $\begingroup$ @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$. $\endgroup$
    – Jacob
    Nov 29, 2023 at 5:18
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    Nov 29, 2023 at 5:40
  • $\begingroup$ @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. $\endgroup$
    – Jacob
    Nov 29, 2023 at 5:48
  • $\begingroup$ 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? $\endgroup$
    – RobPratt
    Nov 29, 2023 at 14:25

1 Answer 1

0
$\begingroup$

One possible way to do what you want is through the use of chance constraints, which are used to constrain probabilities to be greater than or less than some value. I'm not familiar with a Skellam random variable, but my hunch is that using chance constraints on this distribution will result in a non-convex optimization problem, which a solver such as Gurobi could solve using spatial branching. Below is a simple re-formulation that could use chance constraints:

$\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.

Hope that helps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.