2
$\begingroup$

I would like to know how to express the continuity constraint without using a decision variable in the conditional form. My challenge is to stay with a linear formulation. I will start to explain my model : We would like to determine the optimal starting and finishing date of the project while respecting the human resource capacity available to execute the project.

One of the assumptions is that the project could not be interrupted during its executing period, means once it starts it should be executed continually. Thus, we would like to express this constraint using a linear formulation :

subject to continuityConstraint {j in P, t in T: t >= 2}: t <= Fin[j] ==> Act[j,t] >= Act[j,t-1];

We are not with a linear model anymore

Sets :

set P:= {1..n}; #set of projects

set RType:={"Project manager", "Technical Expert", "Financial Analyst", "Estimator", "Contractual manager"}; #set of human resources

set T:= {1..l}; #set of terms

set S:= {"SP", "MP", "LP", "XLP"};#set of project sizes : small, medium, large and major

set PS within {P,S}; # Set of project-size combinations

Parameters :

param ES{j in P}; # Earliest starting of the project

param LF{j in P}; # Latest finishing of the project

param Duration{j in P};# duration of project j

param RDemand{s in S, r in RType}; # total number of required resource type r to be allocated to project j on any term within its duration

param Av{r in RType, t in T}>=0; #avaialibility of each human resource type r at the period t

Deicision variables :

var Act{j in P, t in T} binary; #=1 if the project j is executing durint period t and 0 otherwise

var FinMax {j in P} integer;

var Debut{j in P} integer; # starting date of the project j

var Fin{j in P} integer; # Finishing date of the project j

var Y{j in P, r in RType, t in T} integer;# number of human resource type r allocated to project j at period t

Constraints :

subject to DurationConstraint {j in P}:

sum{t in T} Act[j, t] = Duration[j];

subject to AffectConstraint {r in RType, t in T}:

sum {j in P, (j,s) in PS} RDemand[s,r]*Act[j,t]<= Av[r,t];

subject to DemandConstraint {j in P, (j,s) in PS, (j, m) in PM, r in RType,t in T}:

Y[j, r, t] =RDemand[s,m,r]*Act[j,t];

subject to Max_Constraint{j in P, t in T}:

t * Act[j, t] <= FinMax[j];

subject to Define_Fin{j in P}:

Fin[j] = FinMax[j];

subject to ActConstraint {j in P}:

(Fin[j]-Debut[j]) =(sum{t in T} Act[j,t])-1;

subject to FinishConstraint {j in P, t in T: t > LF[j]}:

Act[j,t]=0;

subject to SConstraint {j in P, t in T: t < ES[j]}:

Act[j,t]=0;

subject to continuityConstraint {j in P, t in T: t >= 2}: t <= Fin[j] ==> Act[j,t] >= Act[j,t-1];

$\endgroup$

1 Answer 1

5
$\begingroup$

You want to enforce the logical implication $$t \le \text{Fin}[j] \implies \text{Act}[j,t] \ge \text{Act}[j,t-1]$$ Equivalently, the contrapositive is $$\text{Act}[j,t] < \text{Act}[j,t-1] \implies t > \text{Fin}[j]$$ Because Act is binary and Fin is integer, we can rewrite as $$(\text{Act}[j,t] = 0 \land \text{Act}[j,t-1] = 1) \implies \text{Fin}[j] \le t-1$$ You can enforce this via a linear big-M constraint: $$\text{Fin}[j] - (t-1) \le M_{j,t}(1 + \text{Act}[j,t] - \text{Act}[j,t-1])$$

$\endgroup$
3
  • $\begingroup$ Dear @RobPratt, what is actually the third line meaning? How is $\lt$ changed into $\land$? (It seems it is possible to use $\lt$ instead of $\leq$ when it comes to the logic form). $\endgroup$
    – A.Omidi
    Jan 29 at 12:49
  • 1
    $\begingroup$ @A.Omidi For binary variables $x$ and $y$, the constraint $x<y$ has exactly one solution $x=0 \land y=1$. $\endgroup$
    – RobPratt
    Jan 29 at 14:27
  • $\begingroup$ Dear @RobPratt, thanks. The logic is exactly what you mentioned. The interesting thing was of changing $\leq$ to $\lt$ and then using the logic form that is new to mine. 🙏 $\endgroup$
    – A.Omidi
    Jan 29 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.