How to model a contiguity constraint?
回答済みI am modeling what I call a "contiguity constraint". I have an array of binary variables in Gurobi and I want to constrain that only a contiguous set of variables can be 1. For example, among [<var1>, <var2>, <var3>, <var4> .. ], only k contiguous variables *have* be 1. So, for k=2, if var1 and var 2 are 1, var3 and var4 have to be 0. Or, var2, var3 are 1 but var1 and var4 have to be 0. How can I model this constraint?
-
正式なコメント
-
Gurobi Staff
This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
Hi,
You may need to clarify the following in order for someone to accurately answer your question:Only k contiguous variables can be 1. But do k contiguous variables have to be 1? I.e. is a solution where all variables zero valid?
- Riley
1 -
-
Yes! k contiguous variables *have* to be 1! Let me edit the question to reflect this.
0 -
-
I suppose you could do something like this:
for 4 variables x_1, x_2, x_3, x_4 and k = 2, create three binary auxiliary variables a_1, a_2, and a_3. a_1 is 1 if x_1 and x_2 are 1, a_2 is 1 x_2 and x_3 are 1, and a_3 is 1 if x_3 and x_4 are 1.
if you have to enforce that exactly one pair of contiguous variables is chosen, then add constraints
a_1 + a_2 + a_3 = 1 (1)
x_1 + x_2 + x_3 + x_4 = 2 (2)
now, to make sure that having a_1 = 1 triggers x_1 = 1 and x_2 = 1 and all the rest is 0, add the following constraints
x_1 + x_2 >= 2*a_1, (3)
x_2 + x_3 >= 2*a_2, (4)
x_3 + x_4 >= 2*a_3, (5)
you need greater-than-or-equal-to constraints in (3)-(5) because some variables appear in more than one pair. Also, note that while (3)-(5) alone would allow for all variables to be 1 indiscriminately, (2) makes sure that exactly 2 of them are chosen. Constraints (3) - (5) guarantee that the variables chosen are adjacent.
I haven't tested it, but I suppose it would work
P.S: if x_1 and x_4 are considered a valid pair, create another auxiliary variable1 -
-
-
Hi,
Bruno Colonetti has done a good job and the formulation looks correct. I'd like to pose some strengthenings, using Bruno's notation.
Note that
\[a_{i-t} \leq x_i\]
is a valid constraint for t = 0,...,k-1 for each i
Since the sum of "a" variables is 1 we can lift these constraints for each i:
\[ \sum_{j=i-k+1}^{i} a_j \leq x_i, \,\,\,\, (6)\]
If you were to sum these constraints for i and i+1 you get a constraint
\[a_{i-k+1} + 2\sum_{j=i-k+2}^{i} a_j + a_{i+1} \leq x_i + x_{i+1}\]
which dominates (3) - (5), and so (6) is strictly tighter. (eg, for k=2 and i=2 the corresponding constraint would be \[a_1 + 2a_2 + a_3 \leq x_2 + x_3\])
Along with (1) and (2) introduced by Bruno, the (6) constraints are enough for correctness of formulation.2 -
-
Thank you Bruno Colonetti and Riley Clement. This is very helpful. Something I should have mentioned is that k (number of contiguous variables set) is a Gurobi variable in my formulation. I get the gist of your idea of using indicator variables to choose every k contiguous variables but I am not sure if I can extend that for the case when k is also a variable of the formulation.
2 -
-
-
Ok, in that case introduce binary variables \(k_n\) which indicate whether \(k = i\), eg \(k_3 = 1\) means we require \(k = 3\).
Add the constraint \[\sum_n k_n = 1\]Note that the inequality \( a_{i-t} \leq x_i \) holds if and only if \(t \leq k-1\), and so doesn't hold if and only if \(k \leq t\)
So we can form the following valid constraint for each \(i\), and \(t \in \{0, ... , i-1\}\)
\[ a_{i-t} \leq x_i + \sum_{n=1}^t k_n \]
We can again strengthen by lifting in \(a\) variables, so for each \(i\), and \(t \in \{0, ... , i-1\}\):
\[ \sum_{j=i-t}^i a_j \leq x_i + \sum_{n=1}^t k_n \]
I think this should work, but it is untested.
1 -
投稿コメントは受け付けていません。
コメント
7件のコメント