Need ILiteral instead of BoundedLinearExpression for OnlyEnforceIf

[Tyler Wallace]

Hey everyone!

I've been using OR-Tools for the last several months, but I am working on a new problem and I'm having issues implementing one constraint. I've tried to simplify the problem as much as possible for this post to focus on where I'm having issues. I'm going to give a brief background that I hope will help when looking at my code. 

I have a job schedule that requires the setup shown below (I hope that renders in a readable way)

 __________________________________________

|           | slot 1 | slot 2 | slot 3 |

|-----------|--------|--------|--------|

| machine 1 | job 1  | job 2  | job 3  |

|-----------|--------|--------|--------|

| machine 2 | job 3  | job 4  | job 5  |

|-----------|--------|--------|--------|

| machine 3 | job 6  | job 7  | job 8  |

 -------------------------------------- 

The rules (there are more but I don't think they matter for this example) 

1. Each job has to stay in its current slot. For example: jobs 1, 3, 6 all need to remain in slot 1; jobs 2, 4, 7 all need to remain in slot 2, etc;
2. A job can go on any machine in its assigned slot. For example: job 1 can go on machine 1, 2, or 3
3. There can only be one job per machine/slot. For example: Machine 1/Slot 1 can only have 1 job.
4. The slots have to be completed sequentially on a machine. For example: The job on Machine 1/Slot 1 must complete before the job on Machine 1/Slot 2 can start. <== This is what I am having trouble with

using System.Collections.Generic;

using System.Linq;

using Google.OrTools.Sat;

public class JobOption

{

   public IntVar OnVar { get; set; } // lb: 0, up: horizon

   public IntVar OffVar { get; set; } // lb: 0, up: horizon

   public IntVar Machine { get; set; } // lb: 1, up: 4

   public int Slot { get; set; }

}

public class Job

{

   public int Id { get; set; }

   public int Slot { get; set; }

   public int Duration { get; set; }

}

public class ForumSolver

{

   public void Solve()

   {

       int numberOfSlots = 3;

       IEnumerable<int> slots = Enumerable.Range(1, numberOfSlots);

       int numberOfMachines = 4;

       IEnumerable<int> machines = Enumerable.Range(1, numberOfMachines);

       var jobs = new List<Job>();

       var jobOptions = new List<JobOption>();

       var model = new CpModel();

       var horizon = 1440;

       /*....left out work here to populate jobOptions....*/

   

       foreach (int slot in slots)

       {

           IEnumerable<JobOption> slotJobs = jobOptions

               .Where(o => o.Slot == slot);

            var machineVars = slotJobs.Select(o => o.Machine);

            // all options have to be in different machines in the same slot

           model.AddAllDifferent(machineVars);

            // skip last slot because it will throw an error if we do the rest for the last slot

           if (slot == slots.Last())

               continue;

            // slot[i] job.end must come before slot[i + 1] job.start if same machine

           IEnumerable<JobOption> nextSlotJobs = jobOptions

               .Where(o => o.Slot == slot + 1);

            foreach (JobOption job in slotJobs)

           {

               foreach (JobOption next in nextSlotJobs)

               {

                   // I need to know if job in this slot and job in next slot are using the same machine so I can add this constraint if they are

                   // HOW DO I DO THIS? I don't understand how I can set that up as a ILiteral or somehow use NewBoolVar?    

                   model.Add(job.OffVar <= next.OnVar).OnlyEnforceIf(job.Machine == next.Machine);                                    

               }

           }

       }

   }

}

I think there is something simple I'm missing with how I can model the machine assignment for each job. Right now, I have them as an IntVar. Should I be utilizing BoolVars in some way?

Let me know if a more complete code example would be helpful! I'm happy to provide more. I just didn't want to overwhelm.

Thanks in advance for any help! This tool is awesome and I feel like I've hardly scratched the surface on its capabilities.

[Xiang Chen]

See: https://github.com/google/or-tools/blob/stable/ortools/sat/doc/channeling.md#c-code-1

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

model.Add(job.Machine == next.Machine).OnlyEnforceIf(b);
model.Add(job.Machine != next.Machine).OnlyEnforceIf(b.Not());

 model.Add(job.OffVar <= next.OnVar).OnlyEnforceIf(b);

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/5831a9f1-222b-453e-bcbb-e9e94fe501bd%40googlegroups.com.

[Christopher Hamkins]

Hello, I was having basically the same problem and use the method Xiang Chen describes in his answer.

This was my post https://groups.google.com/forum/#!topic/or-tools-discuss/8wGnC4V7HdE  about the topic.

Since I need to build up a lot of generic Boolean expressions I finally wound up creating my own delegate classes which internally have a reference to an IntVar (which could be a Boolean version of an IntVar).

I overrode the == and != operators for the class, here's the relevant code snippet for IntVar == long

{

       protected CSolverModel myModel;

        public CSolverIntVar(CSolverModel myModel_, IntVar intvar_)

       {

           this.myModel = myModel_;

           this.intvar = intvar_;

       }

        public IntVar intvar { get; private set; }

        /// <summary>

       /// Creates a new IntVar whose value is equivalent to the result of a == b

       /// and returns it encapsulated as a MyIntVar

       /// </summary>

       /// <param name="a">The MyIntVar whose equality is being checked</param>

       /// <param name="b">The long against which to check the value.</param>

       /// <returns>A new MyIntVar whose value is equivalent to the expression a == b</returns>

       public static CSolverIntVar operator == (CSolverIntVar a, long b)

       {

           // Check for null operand

           if (object.ReferenceEquals(a, null))

           {

               throw new ArgumentException("Attempt to equate a null MyIntVar with a long.");

           }

           string resultName = string.Format("{0}=={1}", a.intvar.Name(), b);

           IntVar iv = a.myModel.NewBoolVar(resultName);

           a.myModel.Add(a.intvar == b).OnlyEnforceIf(iv);

           a.myModel.Add(a.intvar != b).OnlyEnforceIf(iv.Not());

           return new CSolverIntVar(a.myModel,iv);

       }

        /// <summary>

       /// Creates a new IntVar whose value is equivalent to the result of a != b

       /// and returns it encapsulated as a MyIntVar

       /// </summary>

       /// <param name="a">The MyIntVar whose inequality is being checked</param>

       /// <param name="b">The long against which to check the value.</param>

       /// <returns>A new MyIntVar whose value is equivalent to the expression a != b</returns>

       public static CSolverIntVar operator !=(CSolverIntVar a, long b)

       {

           // Check for null operand

           if (object.ReferenceEquals(a, null))

           {

               throw new ArgumentException("Attempt to compare a null MyIntVar with a long.");

           }

           string resultName = string.Format("{0}!={1}", a.intvar.Name(), b);

           IntVar iv = a.myModel.NewBoolVar(resultName);

           a.myModel.Add(a.intvar != b).OnlyEnforceIf(iv);

           a.myModel.Add(a.intvar == b).OnlyEnforceIf(iv.Not());

           return new CSolverIntVar(a.myModel, iv);

       }

I also made versions for IntVar == IntVar etc. and a Boolean version of them which overloads the logical operators. 

Then I can can do this:

CSolverIntVar csivJobMachine = CSolverIntVar (model, job.Machine);

CSolverIntVar csivNextMachine = CSolverIntVar (model, next.Machine);

 model.Add(job.OffVar <= next.OnVar).OnlyEnforceIf((csivJobMachine  == csivNextMachine).intvar);

[Tyler Wallace]

Thanks Xiang Chen! That's just what I needed and it makes sense now that I see it. I figured there was a simple concept that I was missing that would allow me to do what I needed.

Christopher, that is an interesting approach. I may do something similar!

I believe I'll have another question in the coming days about how to build the objective for this problem because it isn't as simple as minimizing a value, but I'll post a new topic if needed because you both have answered my original question here.

Thanks!

[Tyler Wallace]

Hey guys,

I actually have another question that is an extension of this question, so I'm adding it here instead of creating a new post. 

The schedule is a little more complex for this question. There are multiple groups of machines like the one group shown in my original post. The job intervals within a group can't overlap, but it doesn't matter if jobs in different groups overlap. I'm having issues restricting the no overlap rule because jobs can be assigned to any machine in any group, and I need to know the value of the Job.Machine IntVar to know what group the job was placed in.

I've written some code that lets me determine if a job is on a machine in the group in reference. But I'm not sure how to leverage that info to create a list of IntervalVar that I can use in the NoOverlap constraint. 

Here's what I have so far:

    foreach (var group in groups)

   {

       var groupNoOverlap = new List<IntervalVar>();

       foreach (var option in jobOptions)

       {

           var isInGroup = new List<IntVar>();

           foreach (var machine in group.Machines)

           {

               var isOnMachine = model.NewBoolVar($"isInMachine_g{group.Id}_j{option.Id}_m{machine}");

               model.Add(option.Machine == machine).OnlyEnforceIf(isOnMachine);

               model.Add(option.Machine != machine).OnlyEnforceIf(isOnMachine.Not());

               isInGroup.Add(isOnMachine);

           }

            // if any value in isInGroup is true, then the option is in this group

           // Is there a way to check if any of the values in the isInGroup list are true?

           // Is there a way to create a boolvar for isInGroup that I could work off of?

            if (isInGroup.Any(x => x == true))

           {

               groupNoOverlap.Add(option.IntervalVar);

           }

       }

       model.AddNoOverlap(groupNoOverlap);

   }

[Xiang Chen]

Maybe you should use OptionalIntervalvars instead

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/f5571025-0de4-43c5-a096-1366b012680b%40googlegroups.com.

[Tyler Wallace]

Thanks Xiang, that does look like a potential solution.

I've taken a look at the OptionalIntervals docs: https://github.com/google/or-tools/blob/stable/ortools/sat/doc/scheduling.md#c-code-3

and at a couple of examples in the or-tools docs. The thing that I'm most unsure of is how I control when an OptionalInterval is used if there are more than 2 optional intervals.

In my situation, I think I would have to create an optional interval for each machine that a job interval could be on. I would then need to restrict those optional intervals so that exactly one is used for each job. Do you know of any examples on how I could do that?

[Xiang Chen]

Example in Python:

https://github.com/google/or-tools/blob/4a0e9b1860276a021335aacb8b69e10a0d08942c/examples/python/flexible_job_shop_sat.py

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/f5571025-0de4-43c5-a096-1366b012680b%40googlegroups.com.

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/48ba1422-34ea-4334-bf5d-6a1a3b914a63%40googlegroups.com.

[Tyler Wallace]

Thanks Xiang!!