Model incorrectly identified as infeasible

[gregy4]

What version of OR-Tools and what language are you using?
Version: main
Language: C++/Java

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)
CP-SAT

What operating system (Linux, Windows, ...) and version?
Linux, Windows

What did you do?
Due to incorrect results I identified strange behaviour when a model was infeasible but when I added some new constraints the model was feasible and optimal solution was found. I verified behaviour on current main branch, problem.proto (with extra constraints) is feasible but original model (problem2.proto) is infeasible. When I skipped presolve phase, problem2.proto was feasible.

The behaviour is probably related to noOverlap constraint and for me it is a blocker for version 9.4.

What did you expect to see
Both models should be feasible.

files.zip

[lperron]

as a workaround, you can set cp_model_probing_level:0. problem2 is optimal with presolve with it.

[lperron]

Can you try reducing the problem on your side ?

[gregy4]

Yes, I can try to reduce it.

To give you some context, I found a solution with simpler model when it was not possible to change a worker for a task between shifts. In more complex model, when it was possible to change a worker and most constraints were replicated for every shift, I tried to fix placement of tasks based on solution of simpler model. This setup lead to infeasible result. When I added constraint to not use a worker not assigned to a task in simpler model optimal solution was found.

So I can try to minimize number of tasks or workers in a model but I’m not sure whether I can simplify complex model.

[lperron]

Anything will help. Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le lun. 1 août 2022 à 22:41, gregy4 ***@***.***> a écrit :

…

Yes, I can try to reduce it. To give you some context, I found a solution with simpler model when it was not possible to change a worker for a task between shifts. In more complex model, when it was possible to change a worker and most constraints were replicated for every shift, I tried to fix placement of tasks based on solution of simpler model. This setup lead to infeasible result. When I added constraint to not use a worker not assigned to a task in simpler model optimal solution was found. So I can try to minimize number of tasks or workers in a model but I’m not sure whether I can simplify complex model. — Reply to this email directly, view it on GitHub <#3407 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3N3ONHBOJLSNXENKDDVXAZABANCNFSM55BZKJIQ> . You are receiving this because you were assigned.Message ID: ***@***.***>

[gregy4]

I am at 7 tasks and 12 workers, the model was minimized to 2000 variables. More progress is about cherry picking of not used variables due to know positions of tasks. Should I continue or is it enough for you ?

minimizedModel.zip

[lperron]

Start by sending the new model. Can you try to reduce it a little bit more ? This is already very helpful. Le mer. 3 août 2022, 02:12, gregy4 ***@***.***> a écrit :

…

I am at 7 tasks and 12 workers, the model was minimized to 2000 variables. More progress is about cherry picking of not used variables due to know positions of tasks. Should I continue or is it enough for you ? minimizedModel.zip <https://github.com/google/or-tools/files/9249810/minimizedModel.zip> — Reply to this email directly, view it on GitHub <#3407 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3NGZR3YHEFNODHROYTVXIZYZANCNFSM55BZKJIQ> . You are receiving this because you were assigned.Message ID: ***@***.***>

[gregy4]

What about only 242 variables ? :-)

minimizedProblem_242vars.zip

[lperron]

Great. Still on it. I am not familiar with this code.
You can set cp_model_probing_level:1 instead of 0. It should be better for performance.

[lperron]

Simplified it again by applying presolve to it, with cp_model_probing_level:1
inf_small.pb.txt
.

[lperron]

The problem is with use_optional_variables:true too, disabling it works fine.

I think our implementation of optional variable is broken in more complex cases :(
Not sure how to fix it so I will disable it by default.

On this problem, we have a corner case like
enforcement => interval present.
enforcement => interval start is fixed. which is encoded at load time by " enforcement => extra_lit <=> start == value."

Because of that we have optional variable with associated literals and It seems we don't handle this too well.

PS: We could also presolve this more, and we don't.

[gregy4]

Is use_optional_variables=false good solution ? I tried to compare performance on 9.4 and on first example with nearly 600 thousand variables and use_optional_variables=false works very badly.
use_optional_variables=true, no presolve and cpmodelprobinglevel=1 variants gave me first solution under 3 minutes and made regular improvement over time. with use_optional_variables=false I received first solution after an hour. 16 search workers were used.

example.zip

[fdidier]

I think that if you try to optimize your model a bit, the difference should go away.

Ideally, you should be able to get rid of constraint/variables that are part of:
enforcement => interval present.
enforcement => interval start is fixed

and just use a fixed start for the interval directly instead of using an intermediate non-fixed variable that is only used in those two constraint. Similarly, when you have a main interval and a bunch of alternatives, the model that just reuse the main interval start/end inside the alternative interval is usually performing better.

Hope that helps.

[lperron]

Can you tell us the structure of the model ? Having potentially optional variables that can be fixed is a strange feature. Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le mer. 24 août 2022 à 16:06, gregy4 ***@***.***> a écrit :

…

Is use_optional_variables=false good solution ? I tried to compare performance on 9.4 and on first example with nearly 600 thousand variables and use_optional_variables=false works very badly. use_optional_variables=true, no presolve and cpmodelprobinglevel=1 variants gave me first solution under 3 minutes and made regular improvement over time. with use_optional_variables=false I received first solution after an hour. 16 search workers were used. example.zip <https://github.com/google/or-tools/files/9416780/example.zip> — Reply to this email directly, view it on GitHub <#3407 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3KWWRBD5VMI2RRNENLV2YT7HANCNFSM55BZKJIQ> . You are receiving this because you modified the open/close state.Message ID: ***@***.***>

[gregy4]

Yes, I tried to verify performance effect of the change on simpler model but with a lot of data ...
I try to schedule around 1800 tasks, each task require one or more workers with a skill. Each worker has only one skill. Optimization function is to minimize number of used workers. Unlike in original problem, placement of tasks is not fixed.

In a model, each task has an interval to which are connected other tasks when order of tasks should be respected. Some tasks require also resources implemented by cumulative constraints. Worker assigned to a task is represented by optional interval, in case a worker is used by a task start variables should be equal with task interval. To guarantee that a worker is not used more than once, noOverlap constraint is used over all optional intervals of a worker.

In the data is a lot of workers (around 600, 100 for every skill), optimal value is under 100. It is not possible to say that a worker will be assigned to a tasks since for every tasks is a lot of alternatives.

fdidier: I already tried to reuse start/end variables from task interval but it's a long time. I can give it a try again.

[gregy4]

I tested behaviour of use_optional_variables=false on attached simple example. Sorry data and supporting classes are not attached since I can't publish them but I can try to somehow anonymize them.
File test.txt contains a model.
File testoptional.txt contains log for variant use_optional_variables=true.
File testoptional-no_optional.txt contains log for variant use_optional_variables=false.
File testoptional-shared.txt contains log variant where start and end variables was shared with start and end variables of task main interval. Results was not affected by use_optional_variables true or false.

It seems that optional intervals with independent variables are strongly affected by use_optional_variables = false, sharing of variables between intervals and optional intervals is not always possible.

test.txt

testoptional-no_optional.txt
testoptional.txt
testoptional-shared.txt

[fdid-git]

It seems that sharing gives the best performance, and also a model with 1/5 of the variables which is probably more manageable. It should be mostly possible to share variables, or at least limit the number of literal => x == y constraints.

Yes, when you have independent variables, setting use_optional_variable=true can make a big difference, but as reported in this bug, the code is currently not always working, and there is no easy path to fix it... Reported solution will be correct, but we might miss the optimal, so maybe you can use both version in parallel, but I would trust more the shared and no optional version.