I am trying to develop a MILP constraint where under the condition that two tasks tsk1 and tsk2 are within the same group cluster_1 of tasks, they must be performed adjacently: ie there cannot be a tsk3 in C2 that is executed between them.

I've formulated this as a pair of constraints within IBM OPL

forall(tsk in TaskTuples, tsk2 in TaskTuples: tsk.cluster!= tsk2.cluster, tsk3 in TaskTuples:tsk2.cluster == tsk3.cluster) Tstart[tsk] <= Tstart[tsk2] => Tstart[tsk]<= Tstart[tsk3];

forall(tsk in TaskTuples, tsk2 in TaskTuples: tsk.cluster != tsk2.cluster, tsk3 in TaskTuples:tsk2.cluster == tsk3.cluster) Tstart[tsk] >= Tstart[tsk2] => Tstart[tsk]>= Tstart[tsk3];

But it does not seem to get the solution I expect. It seems to be over-constraining the problem.

asked 11 Jan '18, 08:28

mjbays's gravatar image

mjbays
111
accept rate: 0%


I'm not an OPL user, but it looks like you have two issues: 1. The != should be == in both places. 2. The two logical expressions should be:

not(Tstart[tsk1] <= Tstart[tsk3] and Tstart[tsk3] <= Tstart[tsk2])

and

not(Tstart[tsk2] <= Tstart[tsk3] and Tstart[tsk3] <= Tstart[tsk1])

The first NOT is equivalent to:

Tstart[tsk1] > Tstart[tsk3] or Tstart[tsk3] > Tstart[tsk2]

Which is also equivalent to:

Tstart[tsk1] <= Tstart[tsk3] implies Tstart[tsk3] > Tstart[tsk2]

The second NOT is equivalent to:

Tstart[tsk2] > Tstart[tsk3] or Tstart[tsk3] > Tstart[tsk1]

Which is also equivalent to:

Tstart[tsk2] <= Tstart[tsk3] implies Tstart[tsk3] > Tstart[tsk1]

link

answered 11 Jan '18, 10:31

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26
accept rate: 28%

edited 11 Jan '18, 16:36

Rob: I think I disagree with the first correction. The problem is that the OP starts out with tsk1 and tsk2 being in the same cluster and tsk3 being the interloper to be blocked, but in the OPL code tsk1 and tsk2 become tsk2 and tsk3 and tsk3 becomes tsk.

(11 Jan '18, 14:43) Paul Rubin ♦♦

I see. OK, I edited the logical expressions to use tsk1 as in the description rather than tsk as in the faulty code.

(11 Jan '18, 16:37) Rob Pratt

I'm not sure, but I think you may be misinterpreting (or misreading) the OPL code. In terms of the original three variables, OP's first OPL constraint is saying "if Tstart[tsk3] <= Tstart[tsk1] then Tstart[tsk3] <= Tstart[tsk2]", and the second is also an implication (switching the direction of the inequalities). Frankly, they look correct to me.

(11 Jan '18, 16:42) Paul Rubin ♦♦

Yes, I understood that these were indicator constraints, but I didn't try to map the task names. What you wrote the first constraint to be saying is almost (strict versus not strict inequality) the contrapositive of my second one. So I guess it depends on what the OP wants "between" to mean in cases of ties.

(11 Jan '18, 17:42) Rob Pratt
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:

×27
×21
×16

Asked: 11 Jan '18, 08:28

Seen: 221 times

Last updated: 11 Jan '18, 17:42

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