help-glpk
[Top][All Lists]

## 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.

```