$title Assigning students to projects, with constraints

option limrow=0, limcol=0, solprint=off;

$ontext

This problem is a modification of the assignment problem described
earlier.

A teacher wishes to assign 5 projects to 5 different students. Each
student has indicated their preference for each project by assigning it a
score between 0 and 10 (0 indicating strong dislike and 10 indicating
strong preference). The teacher wishes to make the assignment of projects
to students in a way that maximizes their overall satisfaction, as
measured by the sum of the preferences for the given assignments.

The projects are performed on five desks, lined up from left to
right. Because of bad karma between some pairs of students, the teacher
has to ensure that student4 and student5 are not seated at adjacent desks.
Moreover, since project2 and project3 require cooperation, they should be
perfomed on adjacent desks. In addition, student 3 must be seated at desk
5, and project 3 must be performed at desk 3.

$offtext

set projects/proj1*proj5/
    students/student1*student5/
    desks/desk1*desk5/
    ;

table preferences(students,projects)
             proj1     proj2     proj3     proj4    proj5
student1      7          5        5          2       8
student2      2          3        4          8       5
student3      7          0        4          4       7
student4      8          2        3          7       3
student5      6          2        4          6       0
;

* want x to be 1 if that student is assigned to that project at that desk;
* 0 otherwise
binary variable x(students,projects,desks)
		;

* student4AtDesk is 1 if student 4 is seated at that desk, 0 otherwise,
* and so on
variable student4AtDesk(desks), student5AtDesk(desks),
	 project2AtDesk(desks), project3AtDesk(desks);

* variables to indicate if students 4 and 5 are seated in (desks) and
* (desks+1); and so on
variable nextStudents45(desks), nextProjects23(desks);

nextStudents45.lo(desks) = 0; nextStudents45.up(desks) = 1;
nextProjects23.lo(desks) = 0; nextProjects23.up(desks) = 1;

variable satisfaction;

equations
	EQassignProjects(projects)
	EQassignStudents(students)
	EQassignDesks(desks)
	EQstudent4, EQstudent5, EQproject2, EQproject3,
	EQstudent45a, EQstudent45b, EQstudent45c, EQstudent45d,
	EQproject23a, EQproject23b, EQproject23c, EQproject23d,
	EQproject3desk3,
	EQstudent3desk5,
	objective
	;

* ensure that each project is assigned to one of the students at one desk
EQassignProjects(projects)..
	sum((students,desks), x(students,projects,desks)) =e= 1;
	
* ensure that each student is assigned exactly one project at one desk
EQassignStudents(students)..
	sum((projects,desks), x(students,projects,desks)) =e= 1;

* ensure that each desk is occupied by one student
EQassignDesks(desks)..
	sum((students,projects), x(students,projects,desks)) =e= 1;

* define AtDesk variables
EQstudent4(desks)..
	student4AtDesk(desks) =e= sum(projects, x('student4',projects,desks));
EQstudent5(desks)..
	student5AtDesk(desks) =e= sum(projects, x('student5',projects,desks));
EQproject2(desks)..
	project2AtDesk(desks) =e= sum(students, x(students,'proj2',desks));
EQproject3(desks)..
	project3AtDesk(desks) =e= sum(students, x(students,'proj3',desks));

* define nextStudents45(desks)
* >= 1 if indeed at adjacent desks
EQstudent45a(desks)$(ord(desks)<card(desks))..
	nextStudents45(desks) =g=
	  student4AtDesk(desks)  + student4AtDesk(desks+1)
	+ student5AtDesk(desks)  + student5AtDesk(desks+1) - 1;
* <=0 if neither at desk
EQstudent45b(desks)$(ord(desks)<card(desks))..
	nextStudents45(desks) =l=
	  student4AtDesk(desks) + student5AtDesk(desks);
* <=0 if neither at (desk+1)
EQstudent45c(desks)$(ord(desks)<card(desks))..
	nextStudents45(desks) =l=
	  student4AtDesk(desks+1) + student5AtDesk(desks+1);
* we want all of these variables to be zero!
EQstudent45d..
	sum(desks$(ord(desks)<card(desks)), nextStudents45(desks)) =e= 0;

* define nextProject23(desks)
* >= 1 if indeed at adjacent desks
EQproject23a(desks)$(ord(desks)<card(desks))..
	nextProjects23(desks) =g=
	  project2AtDesk(desks)  + project2AtDesk(desks+1)
	+ project3AtDesk(desks)  + project3AtDesk(desks+1) - 1;
* <=0 if neither at desk
EQproject23b(desks)$(ord(desks)<card(desks))..
	nextProjects23(desks) =l=
	  project2AtDesk(desks) + project3AtDesk(desks);
* <=0 if neither at (desk+1)
EQproject23c(desks)$(ord(desks)<card(desks))..
	nextProjects23(desks) =l=
	  project2AtDesk(desks+1) + project3AtDesk(desks+1);
* we want exactly one of these variables to be one!
EQproject23d..
	sum(desks$(ord(desks)<card(desks)), nextProjects23(desks)) =e= 1;


* project 3 performed at desk 3
EQproject3desk3..
	sum(students, x(students,'proj3','desk3')) =e= 1;
* student 3 seated at desk 5
EQstudent3desk5..
	sum(projects, x('student3',projects,'desk5')) =e= 1;

* satisfaction index
objective..
	satisfaction =e= sum((students,projects,desks),
  	  x(students,projects,desks) * preferences(students,projects));

model  happyclass/all/;

solve happyclass using mip maximizing satisfaction;

* define a set to display the solution in a nice way

set matchings(students,projects,desks)
    ;
matchings(students,projects,desks) = yes$(x.l(students,projects,desks) > 0);

* display in list format
option matchings:0:0:1; display matchings;