CP-SAT _ Summing variables under conditions

Question

I have been working lately on scheduling optimization using CP-SAT in OR-TOOLS and now I'm at the point where I need to start considering due dates in my model.

I didn't want to put them as constraints since I was afraid falling in this problem : https://github.com/google/or-tools/issues/973 which would be very bugging for the end users.

So instead I decided to do a multi-objective optimization like : https://github.com/google/or-tools/issues/1344.

I will start by minimizing makespan after which I will try to minimize the sum(end date - due date) for jobs where end dates > due date, and that's where I have a problem.

My question is how do I do a conditionnel sum in OR-Tools ?

Currently my .net code looks like the following for that section :

    var DiffList = new List<LinearExpr>();

    for (int i = 0; i < job_ends.Count(); i++)
    {
        if (DueDateList[i] < horizon)
        {
            var diff = job_ends[i] - DueDateList[i] ;
         
            DiffList.Add(diff);
        }
    }
    var DiffListSum = LinearExpr.Sum(DiffList);


    model.Minimize(DiffListSum);

I have tried several technics already without much success :

• OnlyEnforceIf(job_ends[i] > DueDateList[i]) => Didn't work.

model.Add(diff == (DueDateList[i] - job_ends[i])).OnlyEnforceIf(job_ends[i] > DueDateList[i]);

• if (job_ends[i] > DueDateList[i]) then add to the list => Didn't work.

Please let me know if you have seen an exemple of this or if you have a solution for me.

Answer 1

A few hours after posting my question here I found a concept I was not familiar with called channelling : https://github.com/google/or-tools/blob/stable/ortools/sat/docs/channeling.md

I used it for my needs and it seems to works. I find a bit odd the way I set my variable b, but anyway...

For those it can help, my code now looks like :

    var DiffList = new List<LinearExpr>();

    for (int i = 0; i < job_ends.Count(); i++)
    {
        if (DueDateList[i] < horizon)
        {

            var diff2 = model.NewIntVar(0, horizon, "DueDateList" + i);

            var b = model.NewBoolVar("b"); 

            model.Add(job_ends[i] > DueDateList[i]).OnlyEnforceIf(b);  
            model.Add(job_ends[i] < DueDateList[i]).OnlyEnforceIf(b.Not());
             
            model.Add(diff2 == job_ends[i] - DueDateList[i] ).OnlyEnforceIf(b);
            model.Add(diff2 == 0).OnlyEnforceIf(b.Not());

            DiffList.Add(diff2);
        }
    }
     
    var DiffListSum = LinearExpr.Sum(DiffList);  

    model.Minimize(DiffListSum);