Implementation of an overlap constraint in linear programming problem

2 views (last 30 days)
Maurizio Pellecchia
Maurizio Pellecchia on 4 Mar 2023
Commented: Maurizio Pellecchia on 4 Mar 2023
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?

Sign in to answer this question.

Accepted Answer

Matt J
Matt J on 4 Mar 2023
Edited: Matt J on 4 Mar 2023
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.

More Answers (0)

Categories

Find more on Linear Programming and Mixed-Integer Linear Programming in Help Center and File Exchange

Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!