4
4

Given N binary variables \(x_{i},x_{i+1},..,x_{i+N}\) exactly \(min \le \alpha \le max\) variables can be equal to 1 and they have to be consecutives. For example \(\{x_{i} = x_{i+1} = x_{i+2} = 1\}\) is a valid solution while \(\{x_{i} = x_{i+1} = x_{i+3} = 1\}\) is not.

Any possible way to model this constraint?

asked 25 Jan '13, 03:26

memecs's gravatar image

memecs
6317
accept rate: 0%

edited 25 Jan '13, 04:54

fbahr's gravatar image

fbahr ♦
4.6k716


To select \( \alpha \) contiguous variables, you can use an additional binary variable \( s_i \) (start) which is 1 if \( i \) is the initial variable. Then the following constraints should suffice:

  1. only one start: $$\sum_{i=0}^{N-1} s_i = 1 $$

  2. \( \alpha \) (which, of course, can be removed from the formulation) is between a maximum and a minimum: $$\min \leq \sum_{i=0}^{N-1} x_i = \alpha \leq \max$$

  3. adjacency is obtained this way: $$x_i \leq s_i + x_{i-1} \forall i = 1, \ldots, N-1 $$

  4. constrain also the initial \( x_0 \) to sync with \(s_0\) (thanks to @Xiaodong):

\[x_0 = s_0\]

Note that the last constraint is necessary otherwise it is possible to obtain undesired assignments, e.g., suppose \(\alpha = 2\) and \( N = 3 \), then \(x=1010\), \(s=0010\) is a feasible non-contiguous solution.

I assumed your variables are indexed with \( i \) from 0 to \( N-1 \), you might want to tune these indices.

BTW, this reminds me of time-indexed scheduling formulations, I am curious: what are you modelling?

link

answered 25 Jan '13, 04:32

kr1zz's gravatar image

kr1zz
197310
accept rate: 25%

edited 06 Oct '13, 11:16

fbahr's gravatar image

fbahr ♦
4.6k716

2

Thanks! (I will up-vote you as soon as I have enough reputation). I am not modeling anything in particular, I am just making up possible scenarios as I want to get deeper into ILP.

Did you know the answer by heart or is there any particular way to approach the modeling of particular constraints as this one.

Latex Issue: my browser is not formatting $..$ as Latex. Not sure why, it works in similar websites.

(25 Jan '13, 04:51) memecs

I used a similar formulation for a scheduling problem, I don't remember exactly how I came up with that but I suspect I obtained it after a few reasoning. However yours is an interesting question: how do we model certain constraints? How do we learn to do it? I think this site has many questions and answers about it...

(25 Jan '13, 05:16) kr1zz
2

I am going to look for them then. By the way setting \(\sum_{i=0}^{N-1}s_i = \lambda\) might lead to \(\lambda\) non adjacent blocks of consecutive \(x\)'s. Something like {0,0,1,1,1,0,0,1,1}. That's also pretty interesting.

(25 Jan '13, 08:06) memecs
1

The LaTeX delimiters here are backslash( or backslash[ (and the corresponding closing delimiter). Also, all backslashes must be escaped (write two consecutive backslashes for each one you need).

(25 Jan '13, 16:03) Paul Rubin ♦♦
2

Although it is obvious, I need to add x_0=s_0 for it to work.

(27 Jan '13, 21:52) Xiaodong Zhang

@Xiaodong: you are wrong, it is not obvious! I am kidding, you are right, since constraint 3 does not apply to i=0 odd things can happen. I'll edit the post, thank you.

(28 Jan '13, 03:58) kr1zz

After discussing with a colleague, I've got a question for you: do you think it would be useful (because it would lead to a tighter linear relaxation) to replace the second constraint with this? $$ \min \sum_{i=0}^{N-1}s_i \leq \sum_{i=0}^{N-1} x_i = \alpha \leq \max \sum_{i=0}^{N-1}s_i $$ (note: min and max are constants, not the minimization or maximization operators)

(27 May '13, 10:15) kr1zz

I suspect a presolver would convert this back to the original form. If not, it would make the matrix a bit denser. I don't see why the formulation would be tighter.

(27 May '13, 17:06) Paul Rubin ♦♦
showing 5 of 8 show 3 more comments

The third constraint can be obtained somewhat automatically by rewriting in "conjunctive normal form" as follows:

if x[i-1] = 0 and x[i] = 1 then s[i] = 1
<=>  not(x[i-1] = 0 and x[i] = 1) or s[i] = 1
<=>  not(x[i-1] = 0) or not(x[i] = 1) or s[i] = 1
<=>  x[i-1] = 1 or x[i] = 0 or s[i] = 1
<=>  x[i-1] + (1 - x[i]) + s[i]   >= 1
<=>  x[i-1]      - x[i]  + s[i]   >= 0
<=>                x[i]  - x[i-1] <= s[i]

A useful reference for this is:

Raman, R. and I.E. Grossmann, Relation Between MILP Modelling and Logical Inference for Chemical Process Synthesis, Computers Chem. Engng. 15 (1991).

link

answered 25 Jan '13, 13:27

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26
accept rate: 28%

edited 07 May '15, 18:47

Thanks @Rob, I am going to reuse soon this way of reasoning :-)

(28 Jan '13, 03:42) kr1zz
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×127
×101

Asked: 25 Jan '13, 03:26

Seen: 4,751 times

Last updated: 07 May '15, 18:47

OR-Exchange! Your site for questions, answers, and announcements about operations research.