Re: [Help-glpk] Scheduling problem using MathProg/GLPK

[Andrew Makhorin]

> We are soon going to have a big event, where participants may choose up
> to 6 out of 20 different discussions. There will be 6 different "blocks", so
> that every participant is - theoretically - able to attend every discussion
> he chose. For every discussion there is a minimum and a maximum number of
> participants. A discussion may take place once in every block, but it does
> not have to take place in every block. A discussion is offered once or not
> at all per block. 
> I have to write a program that finds out an optimal distribution, so that
> every participant is as happy as possible. I chose to solve this problem in
> GLPK using MathProg.

> This is how I tried to model the data:

> set participants;
> /* Set of all the names of the participants */

> set discussions;
> /* Set of discussions offered */

> param NumberOfBlocks := 6;
> /* Number of blocks */

> param limitOfParticipantsPerdiscussion{i in 1..card(discussions), 
> {"min","max"}}, >= 0;
> /* The minimum and maximum number of participants per discussion */

> param wishes{participants, 1..6}, integer, >= 0, <= card(discussions), 
> default 0;
> /* The discussions a participant wishes to attend, 0 means no discussion */

> var participation{i in participants, j in 1..NumberOfBlocks, k in 
> 1..card(discussions)}, binary;
> /* participation[i,j,k] = 1 means, that participant i attends discussion k in 
> block j */

> var takesPlace{1..NumberOfBlocks, 1..card(discussions)}, binary;
> /* Denotes if an discussion takes place in a certain block. */


> I am able to write all constraints correctly, but got stuck with the one
> concerning the minimum number of participants per discussion. This is how I
> tried to handle it:

> s.t. fc{j in 1..NumberOfBlocks, k in 1..card(discussions)}: sum{i in
> participants} participation[i,j,k] >= takesPlace[j,k] *
> limitOfParticipantsPerdiscussion[k, "min"];
> /* Lower limit for participants attending an discussion in a certain
> block, if that discussion takes place */


> Now I am wondering how to find out whether a discussion should take
> place. I tried something like this, but it failed:


> s.t. ff{j in 1..NumberOfBlocks, k in 1..card(discussions) : sum{i in
> participants} participation[i,j,k] = 0}: takesPlace[j,k] = 0;
> /* The discussion does NOT take place */

> s.t. fg{j in 1..NumberOfBlocks, k in 1..card(discussions) : sum{i in
> participants} participation[i,j,k] >= 0}: takesPlace[j,k] = 1;
> /* The discussion does take place */

You cannot use 'participation' in indexing expressions, because it is
a variable, and its value is unknown at the translation stage.

The condition you need to express is the following:

    takesPlace[j,k] = participation[1,j,k] or
                      participation[2,j,k] or
                      participation[3,j,k] or ...

where "or" means the logical "or" operator.

In mip this condition can be written, for example, as follows:

s.t. ff{j in 1..NumberOfBlocks, k in 1..card(discussions)}:
     0 <= card(participants) * takesPlace[j,k] -
          sum{i in participants} participation[i,j,k] <=
             card(participants) - 1;

> Has anyone got any idea how to solve this? I am stuck for a while and
> this project is due next Wednesday... I hope you can and will give me a hint
> ;)