About New Constraint

Problems with modeling
Post Reply
Emine
User
User
Posts: 5
Joined: 6 years ago

About New Constraint

Post by Emine »

Hello guys,
I need your help.

My project is on booklet optimization for exams, it is a timetabling problem.
Here my sets, variables, equ. and obj. :

SETS

o sessions /1*4/
k booklets /1*k/
i courses / course1 * coursen/
s students/student1*studentm/;

VARIABLES
x(i,k) if course i assing to booklet k,
z(i,o) if course i assing to session o,
y(k,o) if booklet k assing to session o,
q(k) if booklet k created,
a obj;

BINARY VARIABLES
x(i,k)
z(i,o)
y(k,o)
q(k);

PARAMETER NCs(s) -it is a parameter that gives number of courses for every student
TABLE P(s,i) student- course matrix(0-1 matrix)

EQUATIONS
obj obj. function
cons2 a booklet can include max. 6 courses
cons21 a booklet can include at least 4 courses
cons3 a course must be assigned to only one session
cons4 a booklet must be assigned to only one session
cons5 all courses must be assigned and they can be assigned to more than one booklets as long as being one session
cons6 a student must be assigned max 5 lessons in one session
cons9 correlation cons. with y(ko) and q(k)
cons91 correlation cons. with y(ko) and q(k)
cons12 correlation cons. with x(ik) and q(k)
cons13 correlation cons. with x(ik) and q(k)
cons15 equality that counts the courses of students for every student and session
cons16 correlation cons. x(ik), z(io), y(ko)
cons17 correlation cons. x(ik), z(io), y(ko);

obj.. a =e= sum(k,q(k));
cons2(k).. sum(i, x(i,k)) =l=6;
cons21(k).. sum(i, x(i,k)) =g=4;
cons3(i).. sum(o, z(i,o)) =e= 1;
cons4(k).. sum(o, y(k,o)) =e= 1;
cons5(i).. sum(k, x(i,k)) =g= 1;
cons6(s,o)..sum(i, P(s,i)*z(i,o))=l= 5;
cons9(k)..sum(o, y(k,o)) =l= M* q(k);
cons91(k)..sum(o, y(k,o)) =g= q(k);
cons12(k)..sum((i), x(i,k)) =g= q(k) ;
cons13(k)..sum((i), x(i,k)) =l= M* q(k);
cons15(s)..NCs(s) =e= sum ((i,o),P(s,i)* z(i,o)) ;
cons16(i,o,k)..(z(i,o)-y(k,o))=l= 1-(x(i,k));
cons17(i,o,k)..z(i,o)-y(k,o)=g= -(1-(x(i,k)));
MODEL oturum /all/;
SOLVE oturum using mip minimizing a;

solver is cplex.

Actually it works, but i realized that a student can get more than one books per session in this situation.
But this is a hard cons., a student can have only one booklet for each session.

I added a new variable w(s,o,k) : if student s, assigned to booklet k, in session o.
And i added 3 constraint. But i can't find a solution,

*Kisit19(s,o)..sum((k), w(s,o,k))=l=1 :
*Kisit25(s,i,o,k)..(w(s,o,k)-y(k,o))=l= 1-x(i,k);
*Kisit26(s,i,o,k)..(w(s,o,k)-y(k,o))=g= -(1-x(i,k));


Please can you give me a suggestions about constraints or my new variable.
I tried lot of things, but didn't work, i will be really appriciated, if you help.
Thank you!

Emine.
cladelpino
User
User
Posts: 108
Joined: 7 years ago

Re: About New Constraint

Post by cladelpino »

Hi Emine, perhaps you should keep this post in your original thread ? (viewtopic.php?f=9&t=10293).

A general answer: If the problem is infeasible when you run it, you can generate a feasible solution by hand, fix the variables at this levels, and then find out which equations are infeasible in this "should be feasible" point, by inspecting the "Equation listing" part of the .lst file.

A specific answer given your problem type and solver choice: pay attention to the CPLEX output, it tells you about which variable or equation is ultimately infeasible. Finally, inspect the manual because CPLEX is able to generate an "irreducible infeasible set" which is usually very informative to resolve infeasibilities.

Good luck
Claudio
Post Reply