search

google / or-tools

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

SCIP is not the optimal solution in the case of a few variables #2359

Closed EnjoyRenWei closed 3 years ago

EnjoyRenWei commented 3 years ago

What version of OR-tools and what language are you using?

Version: v8.0.8.
Language: Java

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

SCIP

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

Linux、Windows、Mac

What did you do? 1.when there are few variables SCIP cannot get the optimal value, The model is as follows:

Maximize
 Obj: +1500 x0 +1500 x1 +1500 x2 +1200 x3 +1700 x4 +1800 x5 +1300 x6 +1700 x7 +1300 x8 +1300 x9 +1600 x10 +1700 x11 +1200 x12 +1600 x13 +1200 x14 +1200 x15 +1900 x16 +1400 x17 +1500 x18 +1400 x19 
Subject to
 _1001_rhs: +1 x0 +1 x1 +1 x2 +1 x3 +1 x4 +1 x5 +1 x6 +1 x7 +1 x8 +1 x9  <= 5
 _1001_lhs: +1 x0 +1 x1 +1 x2 +1 x3 +1 x4 +1 x5 +1 x6 +1 x7 +1 x8 +1 x9  >= 0
 _1002_rhs: +1 x0 +1 x1 +1 x2 +1 x3 +1 x10 +1 x11 +1 x12 +1 x13 +1 x14 +1 x15  <= 4
 _1002_lhs: +1 x0 +1 x1 +1 x2 +1 x3 +1 x10 +1 x11 +1 x12 +1 x13 +1 x14 +1 x15  >= 0
 _1003_rhs: +1 x0 +1 x4 +1 x5 +1 x6 +1 x10 +1 x11 +1 x12 +1 x16 +1 x17 +1 x18  <= 2
 _1003_lhs: +1 x0 +1 x4 +1 x5 +1 x6 +1 x10 +1 x11 +1 x12 +1 x16 +1 x17 +1 x18  >= 0
 _1005_rhs: +1 x1 +1 x4 +1 x7 +1 x8 +1 x10 +1 x13 +1 x14 +1 x16 +1 x17 +1 x19  <= 2
 _1005_lhs: +1 x1 +1 x4 +1 x7 +1 x8 +1 x10 +1 x13 +1 x14 +1 x16 +1 x17 +1 x19  >= 0
 _1006_rhs: +1 x3 +1 x6 +1 x8 +1 x9 +1 x12 +1 x14 +1 x15 +1 x17 +1 x18 +1 x19  <= 1
 _1006_lhs: +1 x3 +1 x6 +1 x8 +1 x9 +1 x12 +1 x14 +1 x15 +1 x17 +1 x18 +1 x19  >= 0
 _1007_rhs: +1 x2 +1 x5 +1 x7 +1 x9 +1 x11 +1 x13 +1 x15 +1 x16 +1 x18 +1 x19  <= 1
 _1007_lhs: +1 x2 +1 x5 +1 x7 +1 x9 +1 x11 +1 x13 +1 x15 +1 x16 +1 x18 +1 x19  >= 0
Bounds
 0 <= x0 <= 2
 0 <= x1 <= 2
 0 <= x2 <= 1
 0 <= x3 <= 1
 0 <= x4 <= 2
 0 <= x5 <= 1
 0 <= x6 <= 1
 0 <= x7 <= 1
 0 <= x8 <= 1
 0 <= x9 <= 1
 0 <= x10 <= 2
 0 <= x11 <= 1
 0 <= x12 <= 1
 0 <= x13 <= 1
 0 <= x14 <= 1
 0 <= x15 <= 1
 0 <= x16 <= 1
 0 <= x17 <= 1
 0 <= x18 <= 1
 0 <= x19 <= 1
Binaries
 x2
 x3
 x5
 x6
 x7
 x8
 x9
 x11
 x12
 x13
 x14
 x15
 x16
 x17
 x18
 x19
Generals
 x0
 x1
 x4
 x10
End

2.SCIP returns 7400 and it is OPTIMAL

SCIP
result：7400.0 
MPSolver.ResultStatus：OPTIMAL

3.But the optimal solution should be 7500 (for example, you can get this optimal solution using CBC)

CBC
result：7500.0 
MPSolver.ResultStatus：OPTIMAL

What did you expect to see

solution value is 7500

What did you see instead?

Make sure you include information that can help us debug (full error message, model Proto).

Anything else we should know about your project / environment

lperron commented 3 years ago

Please try CP-SAT, I do not trust CBC.

Le mar. 26 janv. 2021 à 02:55, renwei notifications@github.com a écrit :

What version of OR-tools and what language are you using?

Version: v8.0.8.

Language: Java

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

SCIP

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

Linux、Windows、Mac

What did you do? 1.when there are few variables SCIP cannot get the optimal value, The model is as follows:

Maximize

Obj: +1500 x0 +1500 x1 +1500 x2 +1200 x3 +1700 x4 +1800 x5 +1300 x6 +1700 x7 +1300 x8 +1300 x9 +1600 x10 +1700 x11 +1200 x12 +1600 x13 +1200 x14 +1200 x15 +1900 x16 +1400 x17 +1500 x18 +1400 x19

Subject to

_1001_rhs: +1 x0 +1 x1 +1 x2 +1 x3 +1 x4 +1 x5 +1 x6 +1 x7 +1 x8 +1 x9 <= 5

_1001_lhs: +1 x0 +1 x1 +1 x2 +1 x3 +1 x4 +1 x5 +1 x6 +1 x7 +1 x8 +1 x9 >= 0

_1002_rhs: +1 x0 +1 x1 +1 x2 +1 x3 +1 x10 +1 x11 +1 x12 +1 x13 +1 x14 +1 x15 <= 4

_1002_lhs: +1 x0 +1 x1 +1 x2 +1 x3 +1 x10 +1 x11 +1 x12 +1 x13 +1 x14 +1 x15 >= 0

_1003_rhs: +1 x0 +1 x4 +1 x5 +1 x6 +1 x10 +1 x11 +1 x12 +1 x16 +1 x17 +1 x18 <= 2

_1003_lhs: +1 x0 +1 x4 +1 x5 +1 x6 +1 x10 +1 x11 +1 x12 +1 x16 +1 x17 +1 x18 >= 0

_1005_rhs: +1 x1 +1 x4 +1 x7 +1 x8 +1 x10 +1 x13 +1 x14 +1 x16 +1 x17 +1 x19 <= 2

_1005_lhs: +1 x1 +1 x4 +1 x7 +1 x8 +1 x10 +1 x13 +1 x14 +1 x16 +1 x17 +1 x19 >= 0

_1006_rhs: +1 x3 +1 x6 +1 x8 +1 x9 +1 x12 +1 x14 +1 x15 +1 x17 +1 x18 +1 x19 <= 1

_1006_lhs: +1 x3 +1 x6 +1 x8 +1 x9 +1 x12 +1 x14 +1 x15 +1 x17 +1 x18 +1 x19 >= 0

_1007_rhs: +1 x2 +1 x5 +1 x7 +1 x9 +1 x11 +1 x13 +1 x15 +1 x16 +1 x18 +1 x19 <= 1

_1007_lhs: +1 x2 +1 x5 +1 x7 +1 x9 +1 x11 +1 x13 +1 x15 +1 x16 +1 x18 +1 x19 >= 0

Bounds

0 <= x0 <= 2

0 <= x1 <= 2

0 <= x2 <= 1

0 <= x3 <= 1

0 <= x4 <= 2

0 <= x5 <= 1

0 <= x6 <= 1

0 <= x7 <= 1

0 <= x8 <= 1

0 <= x9 <= 1

0 <= x10 <= 2

0 <= x11 <= 1

0 <= x12 <= 1

0 <= x13 <= 1

0 <= x14 <= 1

0 <= x15 <= 1

0 <= x16 <= 1

0 <= x17 <= 1

0 <= x18 <= 1

0 <= x19 <= 1

Binaries

x2

x3

x5

x6

x7

x8

x9

x11

x12

x13

x14

x15

x16

x17

x18

x19

Generals

x0

x1

x4

x10

End

2.SCIP returns 7400 and it is OPTIMAL

SCIP

result：7400.0

MPSolver.ResultStatus：OPTIMAL

3.But the optimal solution should be 7500 (for example, you can get this optimal solution using CBC)

CBC

result：7500.0

MPSolver.ResultStatus：OPTIMAL

What did you expect to see

solution value is 7500

What did you see instead?

Make sure you include information that can help us debug (full error message, model Proto).

Anything else we should know about your project / environment

— 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/2359, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3M2HKFGPAYGDTYRVB3S3YOIFANCNFSM4WSVQZJQ .

EnjoyRenWei commented 3 years ago

Please try CP-SAT, I do not trust CBC. Le mar. 26 janv. 2021 à 02:55, renwei notifications@github.com a écrit : … What version of OR-tools and what language are you using? Version: v8.0.8. Language: Java Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi) SCIP What operating system (Linux, Windows, ...) and version? Linux、Windows、Mac What did you do? 1.when there are few variables SCIP cannot get the optimal value, The model is as follows: Maximize Obj: +1500 x0 +1500 x1 +1500 x2 +1200 x3 +1700 x4 +1800 x5 +1300 x6 +1700 x7 +1300 x8 +1300 x9 +1600 x10 +1700 x11 +1200 x12 +1600 x13 +1200 x14 +1200 x15 +1900 x16 +1400 x17 +1500 x18 +1400 x19 Subject to _1001_rhs: +1 x0 +1 x1 +1 x2 +1 x3 +1 x4 +1 x5 +1 x6 +1 x7 +1 x8 +1 x9 <= 5 _1001_lhs: +1 x0 +1 x1 +1 x2 +1 x3 +1 x4 +1 x5 +1 x6 +1 x7 +1 x8 +1 x9 >= 0 _1002_rhs: +1 x0 +1 x1 +1 x2 +1 x3 +1 x10 +1 x11 +1 x12 +1 x13 +1 x14 +1 x15 <= 4 _1002_lhs: +1 x0 +1 x1 +1 x2 +1 x3 +1 x10 +1 x11 +1 x12 +1 x13 +1 x14 +1 x15 >= 0 _1003_rhs: +1 x0 +1 x4 +1 x5 +1 x6 +1 x10 +1 x11 +1 x12 +1 x16 +1 x17 +1 x18 <= 2 _1003_lhs: +1 x0 +1 x4 +1 x5 +1 x6 +1 x10 +1 x11 +1 x12 +1 x16 +1 x17 +1 x18 >= 0 _1005_rhs: +1 x1 +1 x4 +1 x7 +1 x8 +1 x10 +1 x13 +1 x14 +1 x16 +1 x17 +1 x19 <= 2 _1005_lhs: +1 x1 +1 x4 +1 x7 +1 x8 +1 x10 +1 x13 +1 x14 +1 x16 +1 x17 +1 x19 >= 0 _1006_rhs: +1 x3 +1 x6 +1 x8 +1 x9 +1 x12 +1 x14 +1 x15 +1 x17 +1 x18 +1 x19 <= 1 _1006_lhs: +1 x3 +1 x6 +1 x8 +1 x9 +1 x12 +1 x14 +1 x15 +1 x17 +1 x18 +1 x19 >= 0 _1007_rhs: +1 x2 +1 x5 +1 x7 +1 x9 +1 x11 +1 x13 +1 x15 +1 x16 +1 x18 +1 x19 <= 1 _1007_lhs: +1 x2 +1 x5 +1 x7 +1 x9 +1 x11 +1 x13 +1 x15 +1 x16 +1 x18 +1 x19 >= 0 Bounds 0 <= x0 <= 2 0 <= x1 <= 2 0 <= x2 <= 1 0 <= x3 <= 1 0 <= x4 <= 2 0 <= x5 <= 1 0 <= x6 <= 1 0 <= x7 <= 1 0 <= x8 <= 1 0 <= x9 <= 1 0 <= x10 <= 2 0 <= x11 <= 1 0 <= x12 <= 1 0 <= x13 <= 1 0 <= x14 <= 1 0 <= x15 <= 1 0 <= x16 <= 1 0 <= x17 <= 1 0 <= x18 <= 1 0 <= x19 <= 1 Binaries x2 x3 x5 x6 x7 x8 x9 x11 x12 x13 x14 x15 x16 x17 x18 x19 Generals x0 x1 x4 x10 End 2.SCIP returns 7400 and it is OPTIMAL SCIP result：7400.0 MPSolver.ResultStatus：OPTIMAL 3.But the optimal solution should be 7500 (for example, you can get this optimal solution using CBC) CBC result：7500.0 MPSolver.ResultStatus：OPTIMAL What did you expect to see solution value is 7500 What did you see instead? Make sure you include information that can help us debug (full error message, model Proto). Anything else we should know about your project / environment — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#2359>, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3M2HKFGPAYGDTYRVB3S3YOIFANCNFSM4WSVQZJQ .

I tried four kinds of solvers: CBC, SAT, BOP and SCIP. CBC, SAT and BOP all returned 7500, only SCIP returned 7400

ghost commented 3 years ago

May be related to https://github.com/google/or-tools/discussions/2295

EnjoyRenWei commented 3 years ago

May be related to #2295

works well for me.

感谢

EnjoyRenWei commented 3 years ago

May be related to #2295

The above problem is solved, but even if I set it to 0.000001, there are still problems in other scenes