MATLAB: Creating an OR constraint with intlinprog

intlinprogOptimization Toolboxor

Hey there,
I am working on assigning teachers to teach a class using intlinprog. The class may start any day of the week, Monday through Friday and there are 2 teachers. My 10 decision variables are Monday_teacher1, Monday_teacher2, Tuesday_teacher1, Tuesday_teacher2, … Friday_teacher2 The course needs to be taught twice and it requires 2 teachers. There may be some logic error here, but I am having trouble figuring it out. I would like to assign either 2 teachers on the same day OR zero teachers for that day. I present sample code which will not provide a feasible solution. I believe I may be able to create a function for this, but do not know how to go about it after reading: https://www.mathworks.com/help/optim/ug/or-instead-of-and-constraints.html
f = repelem(1:5,1,2); %Monday preferred over later in the week 
intcon = 1:length(f);
A = [-1 -1 0 0 0 0 0 0 0 0;
     0 0 -1 -1 0 0 0 0 0 0;
     0 0 0 0 -1 -1 0 0 0 0;
     0 0 0 0 0 0 -1 -1 0 0;
     0 0 0 0 0 0 0 0 -1 -1];
b = [-2;-2;-2;-2;-2];
Aeq = [1 1 1 1 1 1 1 1 1 1];
beq = 4;
lb = zeros(1,length(f));
ub = ones(1,length(f));
[x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub);
Thank you for any help you can provide.

Best Answer

Don't think of it as if you are trying to assign some number of teachers on each day. This is NOT an integer program on the number of teachers to assign. There is no "or" constraint needed.
You have 5 days. Exactly 2 classes to teach. The classes cannot be taught on the same day. If a class is taught on any given day, then it uses 2 teachers, but that is irrelevant. The class is taught, or it is not taught, and there must be two classes taught, n different days.
So your unknown vector (x) will be a boolean vector (0 or 1) of length 5.
The goal that you seem to have written, that classes are best taught early in the week corresponds to a vector
f = 1:n;
so the goal is to minimize f*x.
The constraints are simple.
intcon = [1 2];
lb = [0 0 0 0 0];
ub = [1 1 1 1 1];
% total classes are exactly 2.
Aeq = ones(1,5);
beq = 2;
% no more than one class per day.
A = eye(5);
b = ones(1,5);
Of course, it seems pretty clear in advance the solution will be to hold classes on Monday and Tuesday.
X = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
LP:                Optimal objective value is 3.000000.                                             
Optimal solution found.
Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The
intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).
X =
     1
     1
     0
     0
     0
As intuition suggested, Monday and Tuesday. On each of those two days, two teachers will be used.
Related Question