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

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.

• If i understand you correctly, I think i just made an error in the notation which ive corrected Jan 30 '20 at 2:54

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.