removing of boolean variable used in channeling constraints during presolve

[gregy4]

Hello,
channeling constraints are often implemented via two constraints and a boolean variable.

model.addEquality(var, value).onlyEnforceIf(boolVar);
model.addDifferent(var, value).onlyEnforceIf(boolVar.not());

model.addEquality(var2, value2).onlyEnforceIf(boolVar);

In case third constraint is removed during presolve for whatever reason or is just missing, boolVar variable is not removed during presolve. It is removed only in case only one of channeling constraint is present. Is it an error or is there another reason why boolean variable is not removed ? I found that unused variables are removed only in case there are present in one constraint only as written in description of VariableIsUniqueAndRemovable method.

Best regards,
Jan

[lperron]

it is. It is just more code :-)

[gregy4]

It is great :-) When is it possible to see a fix on master branch ?

[lperron]

I am not working on that for the next month at least :-(

[gregy4]

Ok, I will try to somehow simulate it to see impact on my scheduling problem.
For artificial example I saw positive effect on both presolve and solving time.

[gregy4]

Added 100 lines in CpPresolver::Presolve method allowed me to see an impact for me.
Althought domains were already filtered by initial propagation of constraint solver, number of variables was reduced from 16 to 13 thousands, number of constraints was reduced from 36 to 30 thousands.
From performance view, speed was not affected to see a change on individual run but cp-sat solver used constrantly around 100-200mb less memory for a size around 1gb. Without prefiltered domains that I use to not model impossible cases, an effect should be highly probably much larger.

Placement of my code in main propagation loop isn't right since it is executed also during solving phase and solver crashes on first solution. I use it only for creation of presolved model that is executed on a solver instance without my change. Can you recommend better place to put my code to skip my workaround ?

Jan
cp_model_presolve.zip

[gregy4]

I have new version, it works for me except validation of a solution in cp_model_checker:SolutionIsFeasible method.

I removed enforcement variable and both constraints during presolve. The constraints should be ignored in original model or enforcement variable (for every solution) should be assigned to be compatible with the model. So far it seems to me that a code is prepared only for unused variable that should be on other side assigned during presolve to be compatible with original model.
Am I right ?

[lperron]

I need to take a look. Thanks for the experiments. Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le ven. 26 mars 2021 à 10:09, gregy4 ***@***.***> a écrit :

…

Added 100 lines in CpPresolver::Presolve method allowed me to see an impact for me. Althought domains were already filtered by initial propagation of constraint solver, number of variables was reduced from 16 to 13 thousands, number of constraints was reduced from 36 to 30 thousands. From performance view, speed was not affected to see a change on individual run but cp-sat solver used constrantly around 100-200mb less memory for a size around 1gb. Without prefiltered domains that I use to not model impossible cases, an effect should be highly probably much larger. Placement of my code in main propagation loop isn't right since it is executed also during solving phase and solver crashes on first solution. I use it only for creation of presolved model that is executed on a solver instance without my change. Can you recommend better place to put my code to skip my workaround ? Jan cp_model_presolve.zip <https://github.com/google/or-tools/files/6210580/cp_model_presolve.zip> — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#2448 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3M7M3YFLM2OBQGGEXLTFRFMFANCNFSM4ZLFAAJA> .

[gregy4]

Hello,
attached is my patch against 8.2 version.

The patch should be improved in following areas:

• detection of potentially removed variables in other constraints, my code checks only enforcement literals.
• a problem with validation of a solution in cp_model_checker:SolutionIsFeasible since it is not always possible to know during presolve phase correct value of removed variable.

I put my code after presolve loop to prevent a situation when enforcement constraints create infeasible situation and my code can make it incorrectly feasible.

Jan

changed_files.zip

[lperron]

Hi, We just pushed the code to remove these enforcement literals. It was a bit tricky to do :-) Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le lun. 31 mai 2021 à 10:58, gregy4 ***@***.***> a écrit :

…

Hello, attached is my patch against 8.2 version. The patch should be improved in following areas: - detection of potentially removed variables in other constraints, my code checks only enforcement literals. - a problem with validation of a solution in cp_model_checker:SolutionIsFeasible since it is not always possible to know during presolve phase correct value of removed variable. I put my code after presolve loop to prevent a situation when enforcement constraints create infeasible situation and my code can make it incorrectly feasible. Jan changed_files.zip <https://github.com/google/or-tools/files/6569012/changed_files.zip> — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#2448 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3MIVAPMU637GX6TG4TTQNFTPANCNFSM4ZLFAAJA> .