Implementation of an overlap constraint in linear programming problem

Hi everyone, I have a problem that can mathematically be described as a ILP.

I have a set of N tasks, each one each characterized by a StartTime and an EndTime. I have to find the combination that maximizes the number of performed tasks.

I think the problem can be solved with the intlinprog function, defining a binary output vector "x" which associates the value 1 to each task if it is selected and 0 if it is discarded, and a vector "f" made only of "-1". Of course, I can't execute two tasks if they overlap, so an overlapping constraint has to be considered. I thought about considering each task one by one and verify its overlapping with all the others, generating a symmetric square matrix A of size N*N, and a vector "b" of all ones

So, assuming a case with N=6, with task-1 overlapping task-4 and task-5 (but with task-4 and task-5 NOT overlapping), matrix A and vector b assume the following forms:

In this case, the intlinprog function, which maximizes the number of executed tasks, should return the vector: x= [0;1;1;1;1;1] avoiding selecting the first taks, which overlaps the fourth and fifth. However, this vector violates the constraint A*x≤b, since:

with the first element of the vector A*x which turns out to be greater than b(1)=1, not respecting the constraint A*x≤b.

Therefore, I think that this solution for implementing the constraint is wrong, but I can't think of another solution. Do you have any idea?

Answer 1

[Matt J]

Instead of a distance matrix, the columns of A should be a TxN matrix where T is some number of discrete time points over which your projects occur and A(:,i) =1 at times when task i is active. Then the costraint A*x<=1 will do what you want. The time discretization merely needs to be fine enough to capture the overlaps.

[Maurizio Pellecchia]

It works perfectly. Thank you very much