Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Python CPSAT model is now (7.5) infeasible was not infeasible in 7.3 #1908

Closed
Phibedy opened this issue Mar 4, 2020 · 12 comments
Closed

Python CPSAT model is now (7.5) infeasible was not infeasible in 7.3 #1908

Phibedy opened this issue Mar 4, 2020 · 12 comments
Assignees
@lperron
Labels
Bug Lang: Python Python wrapper issue Solver: CP-SAT Solver Relates to the CP-SAT solver
Milestone
v7.6

Comments

@Phibedy
Copy link

Phibedy commented Mar 4, 2020 •
edited
Loading

Version 7.5.7466 vs 7.3.7083
Language:
Python CP-SAT
Ubuntu 18.04.3 LTS

What I do:

  • solve model multiple times with different cost functions
  • fix some variables using model.Add(variable == solver.Value(variable))
  • set hints for all variables
  • solve again (with different cost function)
  • works on 7.3 and 7.4, fails on 7.5

I am quite sure that the code I use is fine as I am just executing

* sudo pip3 install ortools==7.3.7083 --upgrade
* pytest ...
* -> works

* sudo pip3 install ortools==7.5.7466 --upgrade
* pytest ...
* -> fails

Is this a known bug or should I send you the proto via email (did not find it anywhere)?
If so do you want both models or just the 7.5 one or each model from each optimization step?

In addition in 7.5 it takes quite longer (in this case I have 3 optimization steps):

The number is the nth found solution, the time is in seconds
Step 1 (7.5):

[json]{"number": 24, "time": 76.26023958501173, "value": 23.0}
solved in 78.34767117101 seconds for state: 4

Step 2 (7.5):

[json]{"number": 10, "time": 70.49741753899434, "value": 56.0}
in 72.49534865799069 for state 4

Step 3 (7.5):

in 16.87480183399748 for state 3

Step 1 (7.3):

[json]{"number": 15, "time": 27.856430420011748, "value": 23.0}
solved in 29.05248812600621 seconds for state: 4

Step 2 (7.3):

[json]{"number": 11, "time": 41.622797275995254, "value": 56.0}
in 45.057837113999994 for state 4

Step 3 (7.3):

[json]{"number": 0, "time": 21.66252404000261, "value": 50.0}
in 22.549597756005824 for state 4

Edit for 7.4

[json]{"number": 26, "time": 43.58731715500471, "value": 23.0}
in 44.897974798994255 seconds for state: 4

[json]{"number": 8, "time": 46.87737082700187, "value": 56.0}
in 49.81951963399479 for state 4

[json]{"number": 0, "time": 27.110546865995275, "value": 52.0}
in 27.89457695899182 for state 4

Thank you for your support :)
@lperron
Copy link
Collaborator

lperron commented Mar 4, 2020 via email

@Phibedy
Copy link
Author

Phibedy commented Mar 4, 2020

@lperron Thank you for the fast response. Of course, just need some time to compile :)

Just tried 7.4 and it worked (added times in issues)

@Phibedy
Copy link
Author

Phibedy commented Mar 5, 2020

@lperron I have just sent you an email with the models and the log. I tried the current master branch and it fails to find a solution, too.
Used docker image
The tests of the current master branch was done on a different machine, therefore the measured time can't be compared, but I add them anyways:

Step 1 (current master)

[json]{"number": 8, "time": 22.41800951398909, "value": 23.0}
solved in 23.586646577343345 seconds for state: 4

Step 2 (current master)

[json]{"number": 6, "time": 25.17622970044613, "value": 56.0}
in 26.66402460820973 for state 4

Step 3 (current master)
in 11.983792051672935 for state 3

@lperron
Copy link
Collaborator

lperron commented Mar 5, 2020 via email

@Phibedy
Copy link
Author

Phibedy commented Mar 5, 2020

Our ci server says:

  • Ortools version says 7.6.9999
  • The used image is: syxolk/python-ortools:python3.7-ortools7.5-69c729
    which downloads ortools via:
    RUN wget -q https://github.com/google/or-tools/archive/69c7295289c8bcef185415e2ef3d76ffff18a849.zip -O or-tools.zip so it should be fine.

How did you load the proto and run it?

@lperron
Copy link
Collaborator

lperron commented Mar 5, 2020 via email

@Phibedy
Copy link
Author

Phibedy commented Mar 5, 2020

Thank you, I will have a look at it :). The log you send me via email seems to be quite useful, how can I enable it?

@lperron
Copy link
Collaborator

lperron commented Mar 5, 2020 via email

@Mizux Mizux added this to the v7.6 milestone Mar 5, 2020
@Mizux Mizux added Help Needed Modeling/Usage problem Lang: Python Python wrapper issue Solver: CP-SAT Solver Relates to the CP-SAT solver labels Mar 5, 2020
@Phibedy
Copy link
Author

Phibedy commented Mar 5, 2020 •
edited
Loading

My mistake. Model 7.5/model-3 is indeed infeasible with presolve, and feasible without it. Just a small comment, you create table constraints with duplicate variables: table { vars: 9843 vars: 9844 vars: 2336 vars: 2336 vars: 2336 vars: 2336 vars: 2336 vars: 2336 vars: 2336 vars: 2336 vars: 2336 vars: 2336 vars: 2336 vars: 2336 vars: 2336 vars: 2336 values: 1 values: 1 values: 1 values: 1 values: 1 values: 1 values: 1 values: 1 values: 1 values: 1 values: 1 values: 1 values: 1 values: 1 values: 1 values: 1 } This is really costly :-) Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le jeu. 5 mars 2020 à 13:40, Phibedy notifications@github.com a écrit :
…
Our ci server says: - Ortools version says 7.6.9999 - The used image is: syxolk/python-ortools:python3.7-ortools7.5-69c729 which downloads ortools via: RUN wget -q https://github.com/google/or-tools/archive/69c7295289c8bcef185415e2ef3d76ffff18a849.zip -O or-tools.zip so it should be fine. How did you load the proto and run it? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#1908?email_source=notifications&email_token=ACUPL3K7BNTDNZMKD7QIOG3RF6MTHA5CNFSM4LBJNFQ2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEN5CS3A#issuecomment-595208556>, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3JETS4YVPUJYP6MRRDRF6MTHANCNFSM4LBJNFQQ .

I am using AddAllowedAssignments, but I am quite sure that there are not the same variables inside the AddAllowedAssignments. If I call v.Index() on all variables there are no duplicates in one AddAllowedAssignments call. If I remove the AddAllowedAssignments calls the model is solvable (even with version 7.5).
The one I find is

9843
9844
16836
16837
26621
26622
37123
37124
43756
43757
49397
49398
58583
58584
64921
64922

and forcing them all to 1 is not the case either. The model creates tables like

1
1
0
0
...

0
0
1
1
...

So as you can see there are always two following variables 1, rest 0.
There is no variable with index 2336 in my case, the only one who starts with 9843 is the one above.
How did you check if there are duplicated table constraints (get the table{...} output?

@lperron
Copy link
Collaborator

lperron commented Mar 5, 2020 via email

@lperron lperron closed this as completed in b74478d Mar 5, 2020
@Phibedy
Copy link
Author

Phibedy commented Mar 5, 2020

Great I will give it a try 👍

@lperron
Copy link
Collaborator

lperron commented Mar 5, 2020 via email

@Mizux Mizux added Bug and removed Help Needed Modeling/Usage problem labels Mar 5, 2020
lnikkila pushed a commit to Boulevard/or-tools that referenced this issue Mar 6, 2020
@lperron @lnikkila
fix google#1908
4c57ca7
lnikkila pushed a commit to Boulevard/or-tools that referenced this issue Mar 20, 2020
@lperron @lnikkila
fix google#1908
5ee559e
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@lperron lperron

Labels
Bug Lang: Python Python wrapper issue Solver: CP-SAT Solver Relates to the CP-SAT solver
Projects
None yet
Milestone
v7.6
Development

No branches or pull requests
3 participants
@Phibedy @Mizux @lperron