I know how to linearize non-overlapping constraint for two intervals. For example, [l1,u1] and [l2,u2]. Non-overlapping means that they do not have intersection, so I can use the following logical constraint:

u1<l2 or u2<l1.

Then I introduce a binary variable s and a big M to linearize it to:

l2-u1-M*s<0; 
l1-u2+M*s>0; 
l2-u1+M*(1-s)>0; 
l1-u2-M*(1-s)<0.

However, if there are more than two intervals, for example, 3 intervals. Then there will be 6 possibilities:

u1<l2,u2<l3 
or u1<l3,u3<l2 
or u2<l1,u1<l3 
or u2<l3,u3<l1 
or u3<l2,u2<l1 
or u3<l1,u1<l2.

I don't how many binary variables I need to introduce in order to linearize these constraints. More generally, for n intervals, there will be n! possibilities. Is there a way to linearize the non-overlapping constraint for all n intervals other than list out all possibilities? Furthermore, it will be even more difficult if I allow some intervals to overlap with each other. It is quite commonly encountered in scheduling problems: there are n operations to be performed, at most m(m<n) of them are allowed to be performed simultaneously. How do I linearize such a constraint?

asked 09 Oct '16, 04:28

Sulivan%20Cheung's gravatar image

Sulivan Cheung
113
accept rate: 0%

edited 09 Oct '16, 04:47


You need only the second and third constraints out of four in your big-M formulation for two intervals.

For \(n\) intervals, you need only \(n \choose 2\) binary variables and twice that many constraints, with one variable and two constraints per pair of intervals. You can omit these for the pairs that you allow to overlap.

To allow at most \(m\) jobs (intervals) to overlap at a time, you can introduce additional binary variables and constraints to assign the jobs to \(m\) machines and impose the nonoverlapping constraints on the jobs assigned to each machine.

link

answered 09 Oct '16, 11:16

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26
accept rate: 28%

Dear Rob, Thank you very much for you answer. I've figured out your answers to my first two questions. However, I'm still not quite clear on the last question. Consider such a case: You have n jobs, n machines (rather than m), each job assigned to a machine. However, only m jobs can be performed simultaneously.

(10 Oct '16, 00:51) Sulivan Cheung

If you already have \(n\) real machines and want to enforce that at most \(m < n\) are active simultaneously, you can introduce \(m\) virtual machines just for that purpose.

Alternatively, if the set of possible start times is finite, you can introduce a binary variable \(x_{i,t}\) for each job \(i\) and start time \(t\) and then impose a cardinality constraint \(\sum_i \sum_{t':t' \le t < t'+d_i} x_{i,t'} \le m\) for each \(t\), where \(d_i\) is the duration of job \(i\).

(10 Oct '16, 10:52) Rob Pratt

I see that your question is tagged "constraint-programming", and indeed constraint programming (CP) makes sense if you are solving this type of scheduling problem. In CP you do not need to linearize your non-overlapping constraints as there exist predefined constraints for that. For example in CP Optimizer (available inside CPLEX Optimization Studio), you would just add a constraint noOverlap([x1,...,xn]) where xi are interval variables.

link

answered 13 Dec '16, 11:31

Philippe%20Laborie's gravatar image

Philippe Lab...
623
accept rate: 9%

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:

×65
×37
×29

Asked: 09 Oct '16, 04:28

Seen: 1,248 times

Last updated: 13 Dec '16, 11:31

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