0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ If i understand you correctly, I think i just made an error in the notation which ive corrected $\endgroup$ Commented Jan 30, 2020 at 2:54

1 Answer 1

Reset to default
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ thx. its the right answer but run time is still way too long. I had the 9 separate problems approach lined up already ... wanted to see if there was a way to combine them all. as a lay person in this stuff, its interesting that you could solve a problem 9 times with slight changes pretty rapidly, but try to combine them into one problem and all of a sudden its essentially intractable. $\endgroup$ Commented Jan 31, 2020 at 1:42
  • $\begingroup$ Even solving two completely independent integer programming problems as one would typically take much more than twice as long. Some solvers recognize this structure and exploit it by solving them separately and in parallel. What solver are you using? Are you able to share the full problem and data? $\endgroup$ Commented Jan 31, 2020 at 1:46
  • $\begingroup$ glpk ... no unfortunately is proprietary ... $\endgroup$ Commented Jan 31, 2020 at 2:57

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.