I am generating a schedule of activities but some of them have constraint that they must be scheduled on the "same day".

My problem formulation has the following 'matrix' structure:

   S1  S2 | S3 S4
A1 x        x   x
A2     x    x   x
A3 x   x    x

Where Ai is the 'i'th activity and Sj is 'j'th slot. S1 and S2 are on the same day and so are S3 and S4 (after the '|'). The 'x' are the slots in which activity 'i' can be scheduled.

I've coded this is a matching problem but wish to enforce a constraint like:

A1 and A3 must be scheduled on the same day

That is, either day 1 {S1,S2} or day 2 {S3, S4}

Given that all 'x' are binary variables I'm unable to come up with an effective way to linearize this constraint?

I was thinking of something along these lines but the results were in correct (i.e., A1 on S1 and A3 on S3)

A1S1 + A3S2 <= 2

A1S4 + A3S3 <= 2

Along with a constraint that the total sum of the above is also less than 2. The above is true if A1S1 is 1 and A3S3 is 1 making the formulation incorrect.

How to encode this logical constraint?

asked 27 Sep '14, 23:11

PhD's gravatar image

PhD
6317
accept rate: 0%

1

Hint: "A1 and A3 must be scheduled on the same day" is the same as "A1 and A3 must not be scheduled on different days."

(27 Sep '14, 23:45) Austin Buchanan

A hint in a different direction (that does not depend on the variables being binary): what does it mean, in terms of the corresponding sets of decision variables, for two "things" to behave the same way as each other in every feasible solution?

(28 Sep '14, 16:34) Rob Pratt

@Austin: Isn't that a lot of constraints? Seems to me like a permutation of all possible "invalid" combinations of schedules. Am I missing something? Can you may be give me an example?

(28 Sep '14, 20:15) PhD

@RobPratt: Not sure I understand what you mean. Can you please clarify?

(28 Sep '14, 20:16) PhD

You want the solution to come out "the same" for two things. How can you enforce that mathematically, given the decision variables associated with those two things?

(28 Sep '14, 22:54) Rob Pratt

Change the right-hand-side of your constraints to 1 (instead of 2).

(29 Sep '14, 13:06) Austin Buchanan
showing 5 of 6 show 1 more comments

A general remark: if the variables you have in your model (here: binary assignment variables activity->slot) are not sufficient to express the constraints you whish to formulate, introduce new variables! Here: introduce binary variables with meaning activity->day. You can then easily formulate that certain activities must take place on the same day. It only remains to "link" your existing to the new variables, which should be easy. Can you do that?

link

answered 01 Oct '14, 04:35

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
3.4k1615
accept rate: 16%

The constraints that you want are of the form: a or b == c or d

where a,b,c,d are boolean (0/1) variables. The inequalities that describe this are those (besides the trivial bound inequalities) that describe the convex hull of all the solutions. They are

a + b >= c, a + b >= d, c + d >= a, c + d >= b

You can either work these out (as I do, when faced with complicated boolean constraints) by enumerating all possible 0/1 vectors satisfying them, and then giving them to a program like cdd ( http://www.inf.ethz.ch/personal/fukudak/cdd_home/ ), or, in this case using boolean algebra:

(a or b) = (c or d) is the same as

(a or b) ==> (c or d) and vice versa

This is the same as

not (a or b) or (c or d) which becomes two constraints in CNF:

(not a) or c or d, and, (not b) or c or d

Each constraint in CNF (conjunctive normal form) becomes one inequality (no-good). For really complicated boolean constraints this may not give you a minimal set (facet definining) inequalities, but in this case it does.

However, in your case, you've forbidden some slots so that reduces the number of inequalities

In summary, you'll need 6 additional inequalities (3 for day 1, and 3 for day 2).

link

answered 06 Oct '14, 15:58

VictorSMiller's gravatar image

VictorSMiller
343215
accept rate: 0%

edited 06 Oct '14, 16:05

I would introduce a new set of binary variables yad for each pair of activity a and day d.

for each activity a, yad is the sum of the x for activity a and day d

for two activities a and b that must be scheduled the same day you state that yad = ybd for all d

There is no need to linearize any or constraint this way.

link

answered 07 Oct '14, 07:08

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

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
×65
×37

Asked: 27 Sep '14, 23:11

Seen: 1,818 times

Last updated: 07 Oct '14, 07:08

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