Constraining linear program with binary variable such that one dimension must be subset of its set

Question

I have a linear program and struggling with a particular constraint requirement. I am hoping there is a way for timely execution via linear construction.

Here is the formula thus far:

Objective function:

max $\sum_{i,j,k=0,0,0}^{m,n,o} x_{i,j,k}*a_{i,j,k}$ where $x_{i,j,k}$ is binary and $a_{i,j,k}$ is a known constant

Thanks in part to help I received here, existing constraints are:

$x_{i,j,k} \leq y_{i,j}$ for all i, j, k

$\sum_{j}y_{i,j} \leq 1$ for all i

$\sum_{i,j}y_{i,j} \leq 13$

Now, I need to constrain $x_{i,j,k}$ such that it can only express a subset of exactly 8 different values of dimension k (which for my purposes is a set of 9) AND that those 8 values are the same for all i (and all i, j since they are constrained to be the same).

I have attempted the following, which is based on the answer to my previous question:

Introduce a new binary $z_k$, which turns each k value on/off, then add constraints:

$x_{i,j,k} \leq z_{k}$

$\sum_{k}^{9}z_{k} = 8$

So, now, for $x_{i,j,k}$ to have a value, that particular k must be activated and, whatever k's are selected, at least and not more than 8 must be activated.

This seems to make sense intuitively, but the run time is extremely long. So I am wondering,

1) if this formulation is correct

2) if it is correct, can it be refactored to reduce the processing time? For instance, I wonder if my solver has to push through all the permutations of 8 out of 9, which are 300k+ ... when I only need to run the combinations, which are 9. Perhaps I could refactor to exclude one value of k rather than include 8.

Appreciate any help.

Answer 1

What you have so far enforces only one direction of the implication: $$\bigvee_{i,j} \left(x_{i,j,k}=1\right) \implies z_k=1$$

To get the converse $$z_k=1 \implies \bigvee_{i,j} \left(x_{i,j,k}=1\right),$$ you need $$z_k \le \sum_{i,j} x_{i,j,k}.$$

If the resulting formulation still takes too long to solve, you might consider solving 9 separate problems independently and taking the best solution. Each problem would contain all but one $k$ value in the indices, and you would not include any of the $z$ variables and associated constraints.