Implementation of an overlap constraint in linear programming problem

2 次查看（过去 30 天）
Maurizio Pellecchia
评论： Maurizio Pellecchia 2023-3-4
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?

请先登录，再回答此问题。

采纳的回答

Matt J
Matt J 2023-3-4
编辑：Matt J 2023-3-4
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.

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Linear Programming and Mixed-Integer Linear Programming 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by