Optimizing AddElement constraits

[Florent Deroche]

Hello everyone,

I am currently working on a problem that requires me to add numerous AddElement constraints with a very big table (length of roughly 14 000) as a parameter. Because of this, finding a solution, while still possible, takes a considerable amount of time. Is there a way to make the model more efficient ?

For example, is spliting the table in 14 smaller tables (each with a length of ~1000) a good idea ? I would calculate which table the required information is in along with its index. I would then add 14 AddElements constraints to find the value with said index in each table, and only take the one that comes from correct table (there is no way to use the OnlyEnforceIf method alongside AddElement to my knowledge). The index would have a much smaller domain, but is it even worth it ?

This brings me to my next question: can I get around the fact that I cannot use OnlyEnforceIf on AddElement constraints by manually creating the variables and constraints that AddElement implicitly creates and using OnlyEnforceIf on these constraints ? Is it worth the hassle ?

[Laurent Perron]

an element constraint is expanded to:

for all i:

  b <=> index == i

  b => target == array[i]

it is easy to add an enforced literal c

for all i:

  b <=> index == i

  b and c => target == array[i]

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 visit https://groups.google.com/d/msgid/or-tools-discuss/994ed21d-43e8-43ba-9170-4d0080fd41b4n%40googlegroups.com.

[Florent Deroche]

Thank you or your reply. Would this be sufficient or is there a better alternative ? 

def add_element_only_enforce_if(

        model: cp_model.CpModel,

        index: cp_model.IntVar,

        array: list[int],

        target: cp_model.IntVar,

        condition: cp_model.BoolVarT

) -> None:

    for i in range(len(array)):

        is_correct_index = model.new_bool_var("is_correct_index")

        model.add(index == i).only_enforce_if(is_correct_index, condition)

        model.add(index != i).only_enforce_if(is_correct_index.Not(), condition)

        model.add(target == array[i]).only_enforce_if(is_correct_index, condition)

[Laurent Perron]

no need for the condition on the index. You can always maintain the mapping.

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

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/a8a42bfb-3f9d-4407-9672-92e49df9cf93n%40googlegroups.com.

[Laurent Perron]

make sure the range of the index is 0..size(array)-1

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