How to model a contiguity constraint?

Answered

rs

• February 05, 2023 23:46
• Edited

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?

 

1

• 

  Riley Clement

  Gurobi Staff

  • February 05, 2023 23:44

  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
• 

  rs

  • February 05, 2023 23:46

  

  

  

  Yes! k contiguous variables *have* to be 1! Let me edit the question to reflect this.

  0
• 

  Bruno Colonetti

  • February 06, 2023 00:39

  

  

  

  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 variable

  1
• 

  Riley Clement

  Gurobi Staff

  • February 06, 2023 06:02
  • Edited

  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
• 

  rs

  • February 06, 2023 12:14

  

  

  

  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
• 

  Riley Clement

  Gurobi Staff

  • February 06, 2023 13:29
  • Edited

  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

Please sign in to leave a comment.