search

google / or-tools

Google's Operations Research tools:
https://developers.google.com/optimization/
Apache License 2.0
11.19k stars 2.12k forks source link

CP SAT python bug: Result random again #1413

Closed Phibedy closed 5 years ago

Phibedy commented 5 years ago

The solver result depends again on the machine it is running (feasible vs infeasible). Like in #1162, where the result was random. It works on two computers but not on the build server (EDIT: most of the time). What I do:

Step 1:

Build docker image with

python:3.7.3-slim
with pip install:
protobuf==3.8.0
ortools==7.2.6977

Step 2:

Step 3:

As I am not able to recreate a minimal example like in the last time I am not sure how this could be solved.

EDIT: I run the program on my machine several times (takes some time). It randomly returns 2,3,4, but most of the time 2. (I am aborting the optimization in after it found the first solution so that should be fine (otherwise the result will take ages))

ResponseInfo:

status: FEASIBLE
objective: 62
best_bound: 0
booleans: 168528
conflicts: 192
branches: 21558
propagations: 7347985
integer_propagations: 1696153
walltime: 30.4988
usertime: 30.4988
deterministic_time: 0

status: INFEASIBLE
objective: NA
best_bound: NA
booleans: 168528
conflicts: 216
branches: 21803
propagations: 7376837
integer_propagations: 1701975
walltime: 28.9972
usertime: 28.9972
deterministic_time: 5.16396
syxolk commented 5 years ago

We are pretty sure now that this bug is closely related to #1162 because we see similar symptoms:

My system:

$ lsb_release -d
Description:    Ubuntu 18.04.2 LTS

$ python3 --version
Python 3.6.8

$ python3 -c "import ortools; print(ortools.__version__)"
7.2.6977

$ python3 -c "from google import protobuf; print(protobuf.__version__)"
3.8.0

If it helps for debugging we are willing to export our protobuf model and send it to one of you.

lperron commented 5 years ago

Can you send me the protobuf of the problem ?

Le dim. 7 juil. 2019 à 22:08, Hans notifications@github.com a écrit :

We are pretty sure now that this bug is closely related to #1162 https://github.com/google/or-tools/issues/1162 because we see similar symptoms:

  • When running with multi-threading enabled I get FEASIBLE, OPTIMAL and INFEASIBLE for a single test-case in different runs. This is rather random, it may take 20 test runs to see a single INFEASIBLE.
  • When running with num_search_workers = 1, linearization_level = 0 and optimize_with_core = True I see OPTIMAL all the time (in at least 40 test runs)

My system:

$ lsb_release -d Description: Ubuntu 18.04.2 LTS

$ python3 --version Python 3.6.8

$ python3 -c "import ortools; print(ortools.version)" 7.2.6977

$ python3 -c "from google import protobuf; print(protobuf.version)" 3.8.0

If it helps for debugging we are willing to export our protobuf model and send it to one of you.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1413?email_source=notifications&email_token=ACUPL3LXAOSTPZ4RNF3IDOTP6JENNA5CNFSM4H6V7KW2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODZLSFOQ#issuecomment-509027002, or mute the thread https://github.com/notifications/unsubscribe-auth/ACUPL3IPJJ5HXJNRFCQL3PDP6JENNANCNFSM4H6V7KWQ .

lperron commented 5 years ago

And can you try with python 3.7 ?

Le dim. 7 juil. 2019 à 22:31, Laurent Perron lperron@google.com a écrit :

Can you send me the protobuf of the problem ?

Le dim. 7 juil. 2019 à 22:08, Hans notifications@github.com a écrit :

We are pretty sure now that this bug is closely related to #1162 https://github.com/google/or-tools/issues/1162 because we see similar symptoms:

  • When running with multi-threading enabled I get FEASIBLE, OPTIMAL and INFEASIBLE for a single test-case in different runs. This is rather random, it may take 20 test runs to see a single INFEASIBLE.
  • When running with num_search_workers = 1, linearization_level = 0 and optimize_with_core = True I see OPTIMAL all the time (in at least 40 test runs)

My system:

$ lsb_release -d Description: Ubuntu 18.04.2 LTS

$ python3 --version Python 3.6.8

$ python3 -c "import ortools; print(ortools.version)" 7.2.6977

$ python3 -c "from google import protobuf; print(protobuf.version)" 3.8.0

If it helps for debugging we are willing to export our protobuf model and send it to one of you.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1413?email_source=notifications&email_token=ACUPL3LXAOSTPZ4RNF3IDOTP6JENNA5CNFSM4H6V7KW2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODZLSFOQ#issuecomment-509027002, or mute the thread https://github.com/notifications/unsubscribe-auth/ACUPL3IPJJ5HXJNRFCQL3PDP6JENNANCNFSM4H6V7KWQ .

Phibedy commented 5 years ago

Can you send me the protobuf of the problem ? Le dim. 7 juil. 2019 à 22:08, Hans notifications@github.com a écrit : … We are pretty sure now that this bug is closely related to #1162 <#1162> because we see similar symptoms: - When running with multi-threading enabled I get FEASIBLE, OPTIMAL and INFEASIBLE for a single test-case in different runs. This is rather random, it may take 20 test runs to see a single INFEASIBLE. - When running with num_search_workers = 1, linearization_level = 0 and optimize_with_core = True I see OPTIMAL all the time (in at least 40 test runs) My system: $ lsb_release -d Description: Ubuntu 18.04.2 LTS $ python3 --version Python 3.6.8 $ python3 -c "import ortools; print(ortools.version)" 7.2.6977 $ python3 -c "from google import protobuf; print(protobuf.version)" 3.8.0 If it helps for debugging we are willing to export our protobuf model and send it to one of you. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1413?email_source=notifications&email_token=ACUPL3LXAOSTPZ4RNF3IDOTP6JENNA5CNFSM4H6V7KW2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODZLSFOQ#issuecomment-509027002>, or mute the thread https://github.com/notifications/unsubscribe-auth/ACUPL3IPJJ5HXJNRFCQL3PDP6JENNANCNFSM4H6V7KWQ .

The docker image uses 3.7.3. syxolk used 3.6.8 on his own machine. I tried 3.6.8 an my machine as well and the docker image with 3.7.3

lperron commented 5 years ago

can you compare the generated protobufs ? Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le dim. 7 juil. 2019 à 17:44, Phibedy notifications@github.com a écrit :

The solver result depends again on the machine it is running (feasible vs infeasible). Like in #1162 https://github.com/google/or-tools/issues/1162. It works on two computers but not on the build server. What I do: Step 1:

Build docker image with

python:3.7.3-slim with pip install: protobuf==3.8.0 ortools==7.2.6977

Step 2:

  • Run it on my machine -> feasible
  • Run it on my friends machine -> feasible
  • Run it on the build server -> infeasible

Step 3:

As I am not able to recreate a minimal example like in the last time I am not sure how this could be solved.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1413?email_source=notifications&email_token=ACUPL3PG3IWXYIC5WMJUSMTP6IFNVA5CNFSM4H6V7KW2YY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4G5W2AEQ, or mute the thread https://github.com/notifications/unsubscribe-auth/ACUPL3JZXDKCQRVVVUGDTNTP6IFNVANCNFSM4H6V7KWQ .

syxolk commented 5 years ago

Yep, I ran the same test case with Python 3.6.8, 3.7.1 and 3.7.3 (all with Protobuf 3.8.0) and exported the models via

import sys
version = f"{sys.version_info.major}.{sys.version_info.minor}.{sys.version_info.micro}"
# build model ...

with open(f"/tmp/model-{version}.pb", "wb") as f:
  f.write(model.Proto().SerializeToString())

with open(f"/tmp/model-{version}.txt", "w") as f:
  f.write(str(model.Proto()))

Then compared the checksums:

$ sha1sum /tmp/model-*.txt
e90616daf10986a8cdbaecfcf62cc0e24863b71b  /tmp/model-3.6.8.txt
e90616daf10986a8cdbaecfcf62cc0e24863b71b  /tmp/model-3.7.1.txt
e90616daf10986a8cdbaecfcf62cc0e24863b71b  /tmp/model-3.7.3.txt

$ sha1sum /tmp/model-*.pb
983507951efaf540aee1d89df7e2eb95ac2064e5  /tmp/model-3.6.8.pb
983507951efaf540aee1d89df7e2eb95ac2064e5  /tmp/model-3.7.1.pb
983507951efaf540aee1d89df7e2eb95ac2064e5  /tmp/model-3.7.3.pb

As you can see, there's no difference.

syxolk commented 5 years ago

@lperron I've send you the model via mail.

syxolk commented 5 years ago

Can you run your program with params log_search_progress:true and send the log when you hit the infeasible ?

Sorry for the delay but here it is:

Parameters: max_time_in_seconds: 10000 log_search_progress: true num_search_workers: 7
Optimization model '':
#Variables: 133678 (192 in objective)
 - 427 in [-1,95]
 - 427 in [-1,96]
 - 132289 in [0,1]
 - 108 in [0,13]
 - 427 in [0,96]
#kBoolAnd: 427 (#enforced: 427) (#literals: 4270)
#kBoolOr: 26257 (#enforced: 26257) (#literals: 29806)
#kLinear1: 1917366 (#enforced: 1888628)
#kLinear2: 99132 (#enforced: 81902)
#kLinear3: 19015
#kLinearN: 8555 (#enforced: 324)
*** starting model expansion at 0.50s
*** starting model presolve at 2.03s
- 62057 affine relations were detected.
- 61494 variable equivalence relations were detected.
- rule 'at_most_one: all false' was applied 1413 times.
- rule 'at_most_one: duplicate literals' was applied 3726 times.
- rule 'at_most_one: removed literals' was applied 3727 times.
- rule 'at_most_one: satisfied' was applied 8729 times.
- rule 'bool_and: always false' was applied 922 times.
- rule 'bool_and: fixed literals' was applied 383 times.
- rule 'bool_and: non-reified.' was applied 46521 times.
- rule 'bool_or: always true' was applied 27371 times.
- rule 'bool_or: fixed literals' was applied 4165 times.
- rule 'bool_or: implications' was applied 35653 times.
- rule 'bool_or: only one literal' was applied 9618 times.
- rule 'bool_or: removed enforcement literal' was applied 101611 times.
- rule 'enforcement literal not used' was applied 61 times.
- rule 'false enforcement literal' was applied 794618 times.
- rule 'linear: always true' was applied 108803 times.
- rule 'linear: empty' was applied 21233 times.
- rule 'linear: extracted enforcement literal from constraint' was applied 5 times.
- rule 'linear: fixed or dup variables' was applied 28811 times.
- rule 'linear: infeasible' was applied 4316 times.
- rule 'linear: negative clause' was applied 6382 times.
- rule 'linear: negative equal one' was applied 2 times.
- rule 'linear: negative reified and' was applied 164136 times.
- rule 'linear: positive at most one' was applied 3748 times.
- rule 'linear: positive clause' was applied 266 times.
- rule 'linear: positive equal one' was applied 19639 times.
- rule 'linear: positive reified and' was applied 30956 times.
- rule 'linear: reduced variable domains' was applied 1980 times.
- rule 'linear: remapped using affine relations' was applied 436 times.
- rule 'linear: simplified rhs' was applied 2317916 times.
- rule 'linear: singleton column' was applied 2500 times.
- rule 'linear: size one' was applied 56544 times.
- rule 'linear: small Boolean expression' was applied 61374 times.
- rule 'true enforcement literal' was applied 1224027 times.
- rule 'variables: canonicalize size two domain' was applied 6 times.
Optimization model '':
#Variables: 52570 (148 in objective)
 - 109 different domains in [-1,96] with a largest complexity of 3.
#kAtMostOne: 17190 (#literals: 53985)
#kBoolAnd: 2248 (#enforced: 2248) (#literals: 15022)
#kBoolOr: 17095 (#literals: 79019)
#kLinear1: 842821 (#enforced: 842821)
#kLinear2: 1252 (#enforced: 1209)
#kLinear3: 330
#kLinearN: 846 (#enforced: 324)
*** starting parallel search at 18.15s with 7 workers: [ auto, lp_br, pseudo_cost, no_lp, max_lp, core, lns_1 ]
#Bound  25.41s best:inf   next:[0,148]    pseudo_cost
#Done   29.51s  max_lp
CpSolverResponse:
status: INFEASIBLE
objective: NA
best_bound: NA
booleans: 168528
conflicts: 210
branches: 21692
propagations: 7367936
integer_propagations: 1699466
walltime: 30.9893
usertime: 30.9893
deterministic_time: 3.00003
lperron commented 5 years ago

I believe we fixed it on the master branch.

Thanks for the report! Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le sam. 13 juil. 2019 à 05:31, Hans notifications@github.com a écrit :

Can you run your program with params log_search_progress:true and send the log when you hit the infeasible ?

Sorry for the delay but here it is:

Parameters: max_time_in_seconds: 10000 log_search_progress: true num_search_workers: 7 Optimization model '':

Variables: 133678 (192 in objective)

  • 427 in [-1,95]
  • 427 in [-1,96]
  • 132289 in [0,1]
  • 108 in [0,13]
  • 427 in [0,96]

    kBoolAnd: 427 (#enforced: 427) (#literals: 4270)

    kBoolOr: 26257 (#enforced: 26257) (#literals: 29806)

    kLinear1: 1917366 (#enforced: 1888628)

    kLinear2: 99132 (#enforced: 81902)

    kLinear3: 19015

    kLinearN: 8555 (#enforced: 324)

    starting model expansion at 0.50s starting model presolve at 2.03s

    • 62057 affine relations were detected.
    • 61494 variable equivalence relations were detected.
    • rule 'at_most_one: all false' was applied 1413 times.
    • rule 'at_most_one: duplicate literals' was applied 3726 times.
    • rule 'at_most_one: removed literals' was applied 3727 times.
    • rule 'at_most_one: satisfied' was applied 8729 times.
    • rule 'bool_and: always false' was applied 922 times.
    • rule 'bool_and: fixed literals' was applied 383 times.
    • rule 'bool_and: non-reified.' was applied 46521 times.
    • rule 'bool_or: always true' was applied 27371 times.
    • rule 'bool_or: fixed literals' was applied 4165 times.
    • rule 'bool_or: implications' was applied 35653 times.
    • rule 'bool_or: only one literal' was applied 9618 times.
    • rule 'bool_or: removed enforcement literal' was applied 101611 times.
    • rule 'enforcement literal not used' was applied 61 times.
    • rule 'false enforcement literal' was applied 794618 times.
    • rule 'linear: always true' was applied 108803 times.
    • rule 'linear: empty' was applied 21233 times.
    • rule 'linear: extracted enforcement literal from constraint' was applied 5 times.
    • rule 'linear: fixed or dup variables' was applied 28811 times.
    • rule 'linear: infeasible' was applied 4316 times.
    • rule 'linear: negative clause' was applied 6382 times.
    • rule 'linear: negative equal one' was applied 2 times.
    • rule 'linear: negative reified and' was applied 164136 times.
    • rule 'linear: positive at most one' was applied 3748 times.
    • rule 'linear: positive clause' was applied 266 times.
    • rule 'linear: positive equal one' was applied 19639 times.
    • rule 'linear: positive reified and' was applied 30956 times.
    • rule 'linear: reduced variable domains' was applied 1980 times.
    • rule 'linear: remapped using affine relations' was applied 436 times.
    • rule 'linear: simplified rhs' was applied 2317916 times.
    • rule 'linear: singleton column' was applied 2500 times.
    • rule 'linear: size one' was applied 56544 times.
    • rule 'linear: small Boolean expression' was applied 61374 times.
    • rule 'true enforcement literal' was applied 1224027 times.
    • rule 'variables: canonicalize size two domain' was applied 6 times. Optimization model '':

      Variables: 52570 (148 in objective)

  • 109 different domains in [-1,96] with a largest complexity of 3.

    kAtMostOne: 17190 (#literals: 53985)

    kBoolAnd: 2248 (#enforced: 2248) (#literals: 15022)

    kBoolOr: 17095 (#literals: 79019)

    kLinear1: 842821 (#enforced: 842821)

    kLinear2: 1252 (#enforced: 1209)

    kLinear3: 330

    kLinearN: 846 (#enforced: 324)

    *** starting parallel search at 18.15s with 7 workers: [ auto, lp_br, pseudo_cost, no_lp, max_lp, core, lns_1 ]

    Bound 25.41s best:inf next:[0,148] pseudo_cost

    Done 29.51s max_lp

    CpSolverResponse: status: INFEASIBLE objective: NA best_bound: NA booleans: 168528 conflicts: 210 branches: 21692 propagations: 7367936 integer_propagations: 1699466 walltime: 30.9893 usertime: 30.9893 deterministic_time: 3.00003

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1413?email_source=notifications&email_token=ACUPL3KQXK23Q7JL65AKA23P7HDJFA5CNFSM4H6V7KW2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODZ3QZMY#issuecomment-511118515, or mute the thread https://github.com/notifications/unsubscribe-auth/ACUPL3NJFTMCFX5G22XTHQ3P7HDJFANCNFSM4H6V7KWQ .

Phibedy commented 5 years ago

Great. We will build it and give it a try, thanks :+1:

syxolk commented 5 years ago

I ran our test case again 100 times with the current master -> all passed. Thanks for the fix!

lperron commented 5 years ago

Great!

Thanks again for the report. Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le lun. 15 juil. 2019 à 15:11, Hans notifications@github.com a écrit :

I ran our test case again 100 times with the current master -> all passed. Thanks for the fix!

— You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1413?email_source=notifications&email_token=ACUPL3N73D7DOGJVWJJVSPDP7TYZ5A5CNFSM4H6V7KW2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODZ7DYNQ#issuecomment-511589430, or mute the thread https://github.com/notifications/unsubscribe-auth/ACUPL3O6BM5AB3PO7MSVAIDP7TYZ5ANCNFSM4H6V7KWQ .