Given a course scheduling problem, in which we have to:

  • assign lectures to rooms and timeslots
  • assure that no 2 teachers teach the same class as the same time
  • assure that each room has enough seats
  • ...

Can you think of a good example of a non-linear constraint for this use case in layman's terms?

Would it be an ordinary or an extra-ordinary constraint?

asked 01 Mar '13, 04:34

Geoffrey%20De%20Smet's gravatar image

Geoffrey De ... ♦
3.2k232
accept rate: 4%

Anyone got an example of the other case? A common example of nonlinear constraint on course scheduling that cannot be linearized?

(04 Mar '13, 10:42) Geoffrey De ... ♦

Do you need a nonlinear constraint that cannot be linearized? If not, a ratio constraint would have a natural nonlinear initial formulation. For instance, insure that at least a 3/4 of Professor X's classes are in the main building, or before lunch, or upper level.

Similarly, constraints limiting pairings of binary decisions (such as an upper limit on the number of times certain pairs of courses or instructors are scheduled in adjacent rooms) are initially quadratic but easily linearized.

link

answered 01 Mar '13, 14:54

Paul%20Rubin's gravatar image

Paul Rubin ♦
10.5k412
accept rate: 17%

Very interesting distinction. How would one linearize "at least 3/4 of Professor X's classes are in the main building"?

(01 Mar '13, 15:11) Geoffrey De ... ♦
1

Assuming that you have binary variables for assignments (and without trying to impose a specific model formulation on you), something like

(sum of binaries assigning Prof X to any course/room/time in main building) >= 0.75(sum of binaries assigning Prof X to anything).

(01 Mar '13, 16:03) Paul Rubin ♦
1

I was thinking along the same lines. Composition (ratio) times flow constraints are the most common nonlinear constraints that generally cannot be linearized exactly. They appear everywhere, but are damnably nonconvex.

(01 Mar '13, 16:20) Gilead ♦

@Gilead Why not exactly? Paul's linear rewriting of the 75% ratio seems to be exact?

(04 Mar '13, 10:41) Geoffrey De ... ♦

That's right, Paul's reformulation is exact. I meant to say ratio times flow, where both the ratio and flow quantities are variables. But in retrospect, ratio*flow constraints don't appear very often in scheduling problems (more in pipe networks), so please ignore my comment. :-)

(04 Mar '13, 11:10) Gilead ♦
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:

×40

Asked: 01 Mar '13, 04:34

Seen: 528 times

Last updated: 04 Mar '13, 11:10

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