1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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/doc/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);
$\endgroup$
1
  • $\begingroup$ this is the recommended way. $\endgroup$ – Laurent Perron Jan 13 at 6:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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