AddForbiddenAssignments + OnlyEnforceIf

[Franco Peschiera]

Hello everyone,

(for some reason I haven’t seen my question posted some days ago so I guess it means the post failed. I apologize in advance if this message is sent multiple times.)

I’m using ortools 8.1.8487 python under Ubuntu 20.04. I’m kind of new to CP and ortools, coming from the LP/ MIP solvers and modelers.

I’m trying to add a binary slack variable to a “forbidden assignments constraint”, as part of an university exam scheduling model.

I’ll put the main parts here and a complete reproducible example at the end.

The constraint to which I want to add a slack variable is the following:

for student, content in student_types.items():
    # for each student group, we know which subjects (student['subject']) they take
    # and the id of the student group (student['id'])
    for exam, subjects in exam_subs.items():
        # for each exam, we get all the subjects that intersect
        subjects_for_exam = list(subjects & set(content["subject"]))
        for pos, s1 in enumerate(subjects_for_exam):
            for s2 in subjects_for_exam[pos + 1 :]:
                # for each pair of subjects, we add the forbidden options
                # in both senses
                # exam_close_tsInts[exam] is a list of forbidden timeslots pairs (because they are too close in time)
                # assign[s1, exam] is a variable that returns a timeslot for a subject and exam
                model.AddForbiddenAssignments(
                    [assign[s1, exam], assign[s2, exam]],
                    exam_close_tsInts[exam],
                )

I then defined a overload binary variable to store violations and tried adding a OnlyEnforceIf at the end:

# this does not raise an exception:
model.AddForbiddenAssignments(
    [assign[s1, exam], assign[s2, exam]],
    exam_close_tsInts[exam],
).OnlyEnforceIf(overload[content["id"], exam, s1, s2].Not())

But then model.Validate() returns:

Enforcement literal not supported in constraint: enforcement_literal: -28 table { vars: 11 vars: 13 values: 118 values: 120 values: 118 values: 119 values: 118 values: 123 values: 118 values: 122 values: 118 values: 121 values: 116 values: 120 values: 116 values: 118 values: 116 values: 119 values: 116 values: 123 values: 116 values: 122 values: 116 values: 121 values: 116 values: 117 values: 119 values: 120 values: 119 values: 123 values: 119 ...

I then tried other various modeling tricks. At the end I got something that works but is not pretty at all which is to create a flag boolean variable for each potentially forbidden value:

def get_add_flag(model, assign_var, value, cache):
    name = "b_{}_{}".format(assign_var, value)
    bool_var = cache.get(name)
    if bool_var is None:
        bool_var = cache[name] = model.NewBoolVar(name)
    model.Add(assign_var == value).OnlyEnforceIf(bool_var)
    model.Add(assign_var != value).OnlyEnforceIf(bool_var.Not())
    return bool_var

cache = {}
for student, content in student_types.items():
    print(student)
    # for each student group, we know which subjects they take
    # and the id of the student_type
    for exam, subs in exam_subs.items():
        # for each exam, we get all the subjects that need to be separated
        subjects_for_exam = list(subs & set(content["subject"]))
        for pos, s1 in enumerate(subjects_for_exam):
            for s2 in subjects_for_exam[pos + 1 :]:
                # for each pair, we add the forbidden options
                # in both senses
                for assign1, assign2 in exam_close_tsInts[exam]:
                    s1_is_assign1 = get_add_flag(
                        model, assign[s1, exam], assign1, cache
                    )
                    s2_is_assign2 = get_add_flag(
                        model, assign[s2, exam], assign2, cache
                    )
                    model.Add(s2_is_assign2 + s1_is_assign1 < 2).OnlyEnforceIf(
                        overload[content["id"], exam, s1, s2].Not()
                    )

what I want to accomplish is: not(assign[s1, exam] and assign[s2, exam]) or overload[content["id"], exam, s1, s2]. Is there a better way ?

(Reproducible example in attached python file).

Thanks!

Franco

​

[Laurent Perron]

a forbidden assignment is just a list of clauses.

if (x, y, z) are the variables, and (3, 1, 2) is a tuple, then the encoding is just

bool_or([(x!= 3), (y != 1), (z != 2)]). using the correct channeling literals.

In that case, [l1, l2] => bool_or([(x!= 3), (y != 1), (z != 2)]) is just bool_or([(x!= 3), (y != 1), (z != 2), l1.Not(), l2.Not()])

So you can do the decomposition yourself.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
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/0fdff01f-fde1-4094-b31e-4db59b02dea4n%40googlegroups.com.

[Franco Peschiera]

Thanks Laurent,

I think I’m missing the correct syntax.

From what I understood in your response I’d have to do something like this:

from ortools.sat.python import cp_model
model = cp_model.CpModel()

# two arrays of integer variables
a_arr = [model.NewIntVar(0, 100, "a_{}".format(p)) for p in range(100)]
b_arr = [model.NewIntVar(0, 100, "b_{}".format(p)) for p in range(100)]

# forbidden pairs for a_arr and b_arr:
forbidden_pairs = [(1, 2), (4, 3), (100, 99)]

# for each pair of variables: do they violate the forbidden pairs constraint? 
slack = {
    (a.Name(), b.Name()): model.NewBoolVar("bool_{}_{}".format(a.Name(), b.Name()))
    for a in a_arr for b in b_arr
}

# we minimize the slack (violations)
model.Minimize(sum(slack.values()))

for a in a_arr:
    for b in b_arr:
        # for each pair of variables a and b
        for value1, value2 in forbidden_pairs:
            # for each forbidden pair:
            # at least one of the variables does not have the value.
            # or the slack for those variables is true.
            model.AddBoolOr([(a!=value1), (b!=value2), slack[a.Name(), b.Name()]])

But this raises an error. From what I understand I need to give the AddBoolOr method a list of boolean variables (instead of var != value) and so I need to create boolean variables for each orbidden assignment? I’m not sure if this is true though. Or maybe I’m just using the wrong syntaxis (which is likely).

thanks again,

Franco

You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/6l4_hzrjWt8/unsubscribe.
To unsubscribe from this group and all its topics, 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/CABcmEeYVibJ3b4FpSn_d-7oyvTTF99boXWz2DwcECqLyM%2BR7tw%40mail.gmail.com.

[Laurent Perron]

Please read https://github.com/google/or-tools/blob/stable/ortools/sat/doc/channeling.md

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAPEBFCZQzAxemKW2KK%2BMB%3DsBRpjEjhqSoo4DugSOh8%2BDFzxncA%40mail.gmail.com.

[Franco Peschiera]

Hello Laurent,

Thanks for link. Indeed, it was because I’d read that link before that I suspected I needed to translate / link the IntVar into BoolVar. This, I guess, confirms the initial implementation I presented / had in mind.

Below the last example including the boolean linkage:

from ortools.sat.python import cp_model
model = cp_model.CpModel()

# two arrays of integer variables
a_arr = [model.NewIntVar(0, 100, "a_{}".format(p)) for p in range(100)]
b_arr = [model.NewIntVar(0, 100, "b_{}".format(p)) for p in range(100)]

# forbidden pairs for a_arr and b_arr:

forbidden_pairs = [(1, 2), (1, 5), (5, 2),  (4, 3), (100, 99)]

# for each pair of variables: do they violate the forbidden pairs constraint?
slack = {
    (a.Name(), b.Name()): model.NewBoolVar("bool_{}_{}".format(a.Name(), b.Name()))
    for a in a_arr for b in b_arr
}

# we store in cache the boolean variables in case we use them more than once
cache = {}

# this function returns a boolean variable for the assginment of value *value* to variable *some_var*
def get_bool_var(some_var, value):
    name = "b_{}_{}".format(some_var.Name(), value)
    bool_var = cache.get(name)
    if bool_var is None:
        bool_var = cache[name] = model.NewBoolVar(name)
    model.Add(some_var == value).OnlyEnforceIf(bool_var)
    model.Add(some_var != value).OnlyEnforceIf(bool_var.Not())
    return bool_var

# we minimize the slack (violations)
model.Minimize(sum(slack.values()))

for a in a_arr:
    for b in b_arr:
        # for each pair of variables a and b
        for value1, value2 in forbidden_pairs:
            # for each forbidden pair:

            # at least one of the pair does not have the value.

            # or the slack for those variables is true.

            a_has_value1 = get_bool_var(a, value1)
            b_has_value2 = get_bool_var(b, value2)
            model.AddBoolOr([a_has_value1.Not(), b_has_value2.Not(), slack[a.Name(), b.Name()]])

Does this make sense? I’ve noticed that doing this (i.e., building the model this way) takes some seconds (of building time) and several seconds (in the building of the model in the test instance). This was one of the reasons that made me think it was possibly not the best approach.

regards,

Franco Peschiera

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeb2fDS9oPzsPOZPvxz%2BJYMhdeHU03RQbP0ArwcGZjjyuA%40mail.gmail.com.

[Laurent Perron]

You can profile the python code.

The cache can be expensive. In general, python modeling is extremely slow.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAPEBFCbuRDf-okNhDUfqDSHx7BgCThO9B3eu9mqma%2BE6aWKKbg%40mail.gmail.com.

[Laurent Perron]

you are recreating the enforced quality each time you call get_bool_var().

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

[Franco Peschiera]

Ah! You're right! My mistake. That definitely helps with efficiency, of course.

Glad to know that at least the idea (if not the implementation) was correct.

Thanks again!

Franco

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeZ68m8z%3DuzZYv9vCWSFwZb_Uh%2BqJdwJYe7ufO50fxTkTg%40mail.gmail.com.