Given a course scheduling problem, in which we have to:
Can you think of a good example of a nonlinear constraint for this use case in layman's terms? Would it be an ordinary or an extraordinary constraint? asked 01 Mar '13, 04:34 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. answered 01 Mar '13, 14:54 Paul Rubin ♦ 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 ♦

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