Find a starting date of the project using an alternative linear expression than min function

Support
1

Hi,

I am working on an allocation and scheduling model.
I would like to identify the optimal starting D[j] and finishing F[j] dates of each project j.
These dates depend on the resource demand for each project as well as resources availabilities.

Binary variable Act[j,t] is used to know if the project is being executed during the period t from T or not and to be able to express the number of human resource being consumed by each project j at period t.
Thus :

subject to DurationConstraint {j in P}:
   sum{t in T} Act[j,t] = Duration[j];

Breaks are allowed means if there is not enough resources to execute all projects together, some projects could be interrupted for a certain time while respecting the deadline LF[j].

I would like to express the starting and finishing dates while using linear constraints, as I have only access to Cplex. I could not use other solver that accept the min and max constraints or other non-convex constraints.

The finishing date is solved as follows :

subject to Max_Constraint{j in P, t in T}: 
   t * Act[j,t] <= FinMax[j];  
subject to Define_Fin{j in P}: 
   F[j] = FinMax[j];

However, I could not find the right expression to define the starting date D[j] such as D[j] = the first period t in which Act[j,t] = 1.

Thank you!

Best regards,

2

The current version of CPLEX for AMPL is based on the new MP interface, which accepts many functions, operators, and expressions — including min and max — that are nonlinear or logical, and that can be used to write nonconvex objectives and constraints.

Your Max_Constraint should insure that FinMax[j] >= the finishing date. If some other objective or constraint of your model forces FinMax[j] to be as small as possible (while still satisfying Max_Constraint) then this will be enough. Otherwise, you might get some solutions with FinMax[j] > the finishing date; in that case, to ensure that FinMax[j] equals the finishing date, you will need to add a constraint that also forces FinMax[j] <= the finishing date. (Your constraint Define_Fin only forces F[j] and FinMax[j] to be equal, so it’s not enough by itself to force FinMax[j] to equal the finishing date.)

You can force FinMin[j] <= the starting date with a constraint like this,

StaMin[j] <= t * Act[j,t] + U * (1-Act[j,t])

where U is an upper bound on StaMin[j] for all j. But the complications described above also apply for this.

You might want to search Operations Research Stack Exchange, or post your own question there, as there is a lot of discussion of scheduling and of linearizations on that site.

1 Like
3

Thank you so much for this detailed answer.
I tried to add the following constraints :
LU is the upper bound and Dmin[j] = Stamin [j]
subject to MinConstraint {j in P, t in T}:
Dmin [j] <= tAct[j, t]+ LU (1-Act[j, t]);

subject to DebutConstraint {j in P}:
Debut[j] <= Dmin[j];

subject to Debut2Constraint {j in P}:
Debut[j] >= Dmin[j];

However, the results, in this case, indicate that the starting date is always t=1 for all project which is not true. In fact, in resource allocation table some projects start at t=2 other t= 4 not really t=1 for all projects …

4

As I mentioned, you can force a variable like DMin[j] to be less than or equal to the starting date by use of constraints like this,

DMin[j] <= t * Act[j,t] + LU * (1-Act[j,t])

(where LU is an upper bound on DMin[j] for all j). But as you are seeing, this constraint also allows DMin[j] to be less than the starting date, unless some other constraints prevent that.

There a general description of how to linearize any relationship like y = \min \{x_1, x_2, \ldots, x_n\} on FICO’s Minimum Values formulation page. For your example, y is DMin[j] and x_j is t * Act[j,t] + LU * (1-Act[j,t]).

1 Like