[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Re: How to make consecutive variables take a certain val
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] Re: How to make consecutive variables take a certain value? |
Date: |
Thu, 13 Dec 2007 21:45:03 +0300 |
> I did not implement the problem and data yet but i think i found
> (probably) a possible solution to the problem.
> There are sessions of courses of 3 and 2 hours length (courses which have
> durations of 4 hours can be treated as 2 seperate course which have
> session length of 2 hours;
> because there is a constraint in the model says so: i.e. the 2 part of
> those sessions with 4 hours of duration should not be in the same day)
> and the question is if binary decision variable with 'course
> title','classroom','day' and 'hour' indices become 1,
> then the following two hours for sessions of 3 hours duration and
> following one hour for sessions of 2 hours duration should also equalt to 1.
> If this constraint did not hold say (for a 2 hours length session) then x_t -
> x_(t-1) ;
> x_t ... 0 0 0 0 1 0 0
> 0 1 0 0 ...
> | | | | | | | | | |
> x_(t-1) ... 0 0 0 1 -1 0 0 1
> -1 0 ...
> So if it did hold:
> x_t ... 0 0 0 0 1 1 0
> 0 0 0 0 ...
> | | | | | | | | | |
> x_(t-1) ... 0 0 0 1 0 -1 0 0
> 0 0 ...
> To be short; i suggest a constraint that checks the sum of absolute value
> of the difference x_h - x_(h-1).
> For both 2 and 3 hours length sessions this sum should be exactly 2.
> Do you think that this should work for me?
I did not understand your idea. It seems to me you can use simple
logical conditions (as it was noticed by some one on the list). Let
x[course,classroom,day,hour] be a decision binary variable. Then you
can model a course that requires 2 hours as follows:
sum{h in 1..PERIOD} x[h] = 2;
/* exactly two hours must be assigned to the course */
Besides, there must be a condition that only adjacent variables can
be 1, i.e. x[h] can be 1 iff x[h-1] is 1 or x[h+1] is 1. This condition
can be modeled as a set of the following linear constraints:
x[h] <= x[h-1] + x[h+1] for all h = 2,...,PERIOD-1
Thus, if x[h-1] = x[h+1] = 0, x[h] cannot be 1.
Courses of 3 hours long can be modeled in a similar way.