[Help-glpk] Scheduling problem using MathProg/GLPK

[hans . fischer23]

Hello,

First of all I want to apologize for my bad english. I'm not a native speaker, 
because I'm Austrian.

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 */


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 ;)


Thanks in advance,

Hans Fischer