ABNORMAL result from feasible linear model when using dual simplex

[h-rummukainen]

Version: 7.5.7466 using or-tools_VisualStudio2019-64bit_v7.5.7466.zip binaries from
https://github.com/google/or-tools/releases

Language: Java

Solver: GLOP

Operating system: Windows 10 Enterprise, Build 18362

Steps to reproduce the behavior: Please see the attached model proto file. The same model is also attached in LP format. I have included a Java program that attempts to solve the model from the proto file with different linear solver settings, and the output from the Java program.

Although the linear model is feasible, with default settings GLOP returns ABNORMAL status. GLOP successfully solves the model with primal simplex, or when disabling presolve or scaling. The result status is ABNORMAL when using dual simplex with presolve and scaling enabled.

Adjusting primal tolerance and dual tolerance values from their defaults to 1.0 does not help. All objective coefficients in the model are between -1000 and -900, and all other non-zero coefficients and constants are between 1 and 100.

CPLEX can solve the same model from the attached LP file using any of its algorithms: primal and dual simplex, sifting and barrier algorithm all work without any issues.

Is this a bug in GLOP, or some kind of weird numerical issue?

abnormal.zip

[lperron]

Thanks, we will have a look. Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le mer. 5 févr. 2020 à 10:32, h-rummukainen <notifications@github.com> a écrit :

…

Version: 7.5.7466 using or-tools_VisualStudio2019-64bit_v7.5.7466.zip binaries from https://github.com/google/or-tools/releases Language: Java Solver: GLOP Operating system: Windows 10 Enterprise, Build 18362 Steps to reproduce the behavior: Please see the attached model proto file. The same model is also attached in LP format. I have included a Java program that attempts to solve the model from the proto file with different linear solver settings, and the output from the Java program. Although the linear model is feasible, with default settings GLOP returns ABNORMAL status. GLOP successfully solves the model with primal simplex, or when disabling presolve or scaling. The result status is ABNORMAL when using dual simplex with presolve and scaling enabled. Adjusting primal tolerance and dual tolerance values from their defaults to 1.0 does not help. All objective coefficients in the model are between -1000 and -900, and all other non-zero coefficients and constants are between 1 and 100. CPLEX can solve the same model from the attached LP file using any of its algorithms: primal and dual simplex, sifting and barrier algorithm all work without any issues. Is this a bug in GLOP, or some kind of weird numerical issue? abnormal.zip <https://github.com/google/or-tools/files/4158579/abnormal.zip> — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1868?email_source=notifications&email_token=ACUPL3ONGN2QV4JDQQALBBDRBKBT5A5CNFSM4KQHWBNKYY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4ILEVQLA>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3N72IR6EPK5LI3B4H3RBKBT5ANCNFSM4KQHWBNA> .

[fdid-git]

The final solution do not pass our solution checker, if you look at the Glop logs, you see:

Max. rhs perturbation = 2.84217e-14
Max. cost perturbation = 0.00121434
Max. primal infeasibility = 2.84217e-14
Max. dual infeasibility = 0
The needed cost perturbation is too large !!
status: IMPRECISE // Which is later converted to ABNORMAL unfortunately...

And so the cost perturbation is larger than our "solution checker tolerance" which is not the same as the solver inner tolerance. So either bump it up with "solution_feasibility_tolerance:1e-5" works, or you can scale down your objective with coefficient initially in [94431.7, 242283] and with an optimal value of -2.084857149702767e+06 on which is is hard to be super precise.

Hope that helps.

[h-rummukainen]

Thank you, your analysis was extremely helpful! Were those logs generated from Java or another language? Calling MPSolver.enableOutput did not seem to have any effect in my Java test program.

Anyway, it seems that setting solution_feasibility_tolerance should be possible in Java by passing a protobuf-encoded String to MPSolver.SetSolverSpecificParametersAsString.

[lperron]

There are outputted by the C++ code, but you cannot trigger it from java.

If you use the C++ binary solve, you can see it
./bin/solve --input --solver glop -vmodule=lp_solver=1

It outputs

...
Solver : GLOP_LINEAR_PROGRAMMING
Dimension : 61 x 3017
I0205 15:54:26.288928 615 lp_solver.cc:171] Initial problem: 61 rows, 3017 columns, 45833 entries
I0205 15:54:26.288955 615 lp_solver.cc:172] Objective stats: 3017 non-zeros, range [-1.000000e+03, -9.744868e+02]
I0205 15:54:26.296759 615 lp_solver.cc:181] Presolved problem: 58 rows, 3014 columns, 45597 entries
I0205 15:54:26.300410 615 lp_solver.cc:290] Primal objective (before moving primal/dual values) = -2.084857149702767E+06
I0205 15:54:26.300431 615 lp_solver.cc:293] Dual objective (before moving primal/dual values) = -2.084857149702767E+06
I0205 15:54:26.300451 615 lp_solver.cc:483] Max. primal values move = 0
I0205 15:54:26.300477 615 lp_solver.cc:507] Max. dual values move = 0
I0205 15:54:26.300498 615 lp_solver.cc:306] Primal objective (after moving primal/dual values) = -2.084857149702767E+06
I0205 15:54:26.300612 615 lp_solver.cc:754] Max. rhs perturbation = 2.84217e-14
I0205 15:54:26.300627 615 lp_solver.cc:724] Max. cost perturbation = 0.00121434
I0205 15:54:26.300648 615 lp_solver.cc:348] Max. primal infeasibility = 2.84217e-14
I0205 15:54:26.300654 615 lp_solver.cc:350] Max. dual infeasibility = 0
I0205 15:54:26.300665 615 lp_solver.cc:356] Objective error <= 4.99182
I0205 15:54:26.300671 615 lp_solver.cc:375] The needed cost perturbation is too large !!
I0205 15:54:26.300676 615 lp_solver.cc:201] status: IMPRECISE
I0205 15:54:26.300683 615 lp_solver.cc:202] objective: -2.08486e+06
I0205 15:54:26.300691 615 lp_solver.cc:203] iterations: 20
I0205 15:54:26.300699 615 lp_solver.cc:204] time: 0.011911
I0205 15:54:26.300704 615 lp_solver.cc:205] deterministic_time: 0.00201267
Status : MPSOLVER_ABNORMAL
Objective : 0.000000000000000e+00
BestBound : 0.000000000000000e+00
Iterations : 20
Time : 0.01556

[h-rummukainen]

Thanks again. I compiled the C++ "solve" executable on Ubuntu and got the GLOP solver logs working.

In Java I reduced solution_feasibility_tolerance to 1e-3 with the following piece of code:
solver.setSolverSpecificParametersAsString(operations_research.glop.Parameters.GlopParameters.newBuilder().setSolutionFeasibilityTolerance(1e-3).build().toString());

With this setting my test program successfully produces an OPTIMAL status in all cases. A bit tricky, but this was clearly a user error instead of bug.

To make the setting work I had to grab ortools/glob/parameters.proto from the OR-Tools sources, and compile it into Parameters.java with the protobuf compiler protoc. Perhaps it would be useful to include the compiled Parameters class in the released JAR package?

[chengjinqian]

Thanks again. I compiled the C++ "solve" executable on Ubuntu and got the GLOP solver logs working.

In Java I reduced solution_feasibility_tolerance to 1e-3 with the following piece of code:
solver.setSolverSpecificParametersAsString(operations_research.glop.Parameters.GlopParameters.newBuilder().setSolutionFeasibilityTolerance(1e-3).build().toString());

With this setting my test program successfully produces an OPTIMAL status in all cases. A bit tricky, but this was clearly a user error instead of bug.

To make the setting work I had to grab ortools/glob/parameters.proto from the OR-Tools sources, and compile it into Parameters.java with the protobuf compiler protoc. Perhaps it would be useful to include the compiled Parameters class in the released JAR package?

hi buddy, dou you know how to get glop logs in java? solver.enableOutput() seems not work.

[h-rummukainen]

Just to clarify, I did not get logs out of the Java library, but followed the instructions of lperron above with the C++ executable.

[davidrimshnick]

Thanks again. I compiled the C++ "solve" executable on Ubuntu and got the GLOP solver logs working.

In Java I reduced solution_feasibility_tolerance to 1e-3 with the following piece of code:
solver.setSolverSpecificParametersAsString(operations_research.glop.Parameters.GlopParameters.newBuilder().setSolutionFeasibilityTolerance(1e-3).build().toString());

With this setting my test program successfully produces an OPTIMAL status in all cases. A bit tricky, but this was clearly a user error instead of bug.

To make the setting work I had to grab ortools/glob/parameters.proto from the OR-Tools sources, and compile it into Parameters.java with the protobuf compiler protoc. Perhaps it would be useful to include the compiled Parameters class in the released JAR package?

Hi, you say "In Java I reduced solution_feasibility_tolerance to 1e-3 "... What is the default tolerance?