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 https://github.com/google/or-tools/issues/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?

[DUSTI919]

Hi,

I do have the same issues. Does anyone know how to set the "solution_feasibility_tolerance" in C#? I tried the following with no success:

solver.SetSolverSpecificParametersAsString("solution_feasibility_tolerance:1e-2");

Regards, Dustin

[davidrimshnick]

Hey, you have to create a parameters object and pass to Solve(), like this

https://stackoverflow.com/a/66077241

On Fri, Feb 18, 2022 at 11:13 AM DUSTI919 @.***> wrote:

Hi,

I do have the same issues. Does anyone know how to set the "solution_feasibility_tolerance" in C#? I tried the following with no success:

solver.SetSolverSpecificParametersAsString("solution_feasibility_tolerance:1e-2");

Regards, Dustin

— Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1868#issuecomment-1044772196, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABBNXXZCQ25UFCBGDVFFCVLU3ZV3TANCNFSM4KQHWBNA . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

You are receiving this because you commented.Message ID: @.***>

[DUSTI919]

Thanks, but how should that work. "SetSolverSpecificParametersAsString" is not part of "Google.OrTools.LinearSolver.MPSolverParameters" ?

Or am I not getting it?

[lperron]

it is on the MPSolver class. Laurent Perron | Operations Research | @.*** | (33) 1 42 68 53 00

Le ven. 18 févr. 2022 à 18:03, DUSTI919 @.***> a écrit :

Thanks, but how should that work. "SetSolverSpecificParametersAsString" is not part of "Google.OrTools.LinearSolver.MPSolverParameters" ?

Or am I not getting it?

— Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1868#issuecomment-1044848681, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3L3UHPRS3AJLKM7VDDU3Z3XBANCNFSM4KQHWBNA . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

You are receiving this because you commented.Message ID: @.***>

[DUSTI919]

Sorry, I don't get it.....

[DUSTI919]

this should work? right?` var Params = new Google.OrTools.LinearSolver.MPSolverParameters(); Params.SetIntegerParam(MPSolverParameters.IntegerParam.LP_ALGORITHM, 10); solver.SetSolverSpecificParametersAsString("solution_feasibility_tolerance:100");
Solver.ResultStatus resultStatus = solver.Solve(Params);

and with Solver solver = Solver.CreateSolver("GLOP");

[DUSTI919]

It seems that it has no effect whatever Value is set to "solution_feasibility_tolerance". I am always getting "No optimal solution".

Number of variables = 2236 Number of constraints = 307

Initial problem: 307 rows, 2236 columns, 497806 entries with magnitude in [1.200000e-05, 6.144637e+06] Objective stats: 2236 non-zeros, range [1.000000e+00, 1.000000e+00] Bounds stats: 308 non-zeros, range [-1.224178e+09, 1.226629e+09]

Starting presolve... SingletonPreprocessor : 299(-8) rows, 2236(0) columns, 497798(-8) entries. (0.007311s) Reached fixed point after presolve pass #1 ProportionalRowPreprocessor : 149(-158) rows, 2236(0) columns, 247781(-250025) entries. (0.005584s) ScalingPreprocessor : 149(-158) rows, 2236(0) columns, 247781(-250025) entries. (0.009764s)

Presolved problem: 149 rows, 2236 columns, 247781 entries with magnitude in [2.393271e-06, 1.000000e+00] Objective stats: 2236 non-zeros, range [7.788491e-03, 2.021877e+01] Bounds stats: 300 non-zeros, range [-3.746315e+02, 2.412212e+02]

Starting basis: create from scratch. Trying to remove 1 fixed variables from the initial basis. The matrix with slacks has 149 rows, 2385 columns, 247930 entries. Number of basic infeasible variables: 149 Number of basic slack variables: 149 Number of basic variables at bound: 0 Number of basic fixed variables: 1 Number of basic free variables: 0 Number of super-basic variables: 0

Dual feasibility phase, iteration # 0, sum_dual_infeasibilities = 4.852371069833371E+03 Dual feasibility phase, iteration # 19, sum_dual_infeasibilities = 0.000000000000000E+00 Current status: DUAL_FEASIBLE Primal infeasibility (bounds) = 482.992 Primal residual |A.x - b| = 5.68434e-14 Dual infeasibility (reduced costs) = 0 Dual residual |c_B - y.B| = 8.88178e-16

Dual optimization phase, iteration # 0, objective = 5.893055764843972E+04 Dual optimization phase, iteration # 65, objective = 3.084411360999999E+03 Dual optimization phase, iteration # 130, objective = 3.084411360999945E+03 Dual optimization phase, iteration # 195, objective = 3.084411361000050E+03 Dual optimization phase, iteration # 260, objective = 3.084411360983797E+03 Dual optimization phase, iteration # 325, objective = 3.084411361013150E+03 Dual optimization phase, iteration # 390, objective = 3.084411360992752E+03 Dual optimization phase, iteration # 455, objective = 3.084411360981925E+03 Dual optimization phase, iteration # 503, objective = 3.084411406389278E+03 Current status: DUAL_UNBOUNDED Primal infeasibility (bounds) = 7.45407e+08 Primal residual |A.x - b| = 2.68919e-06 Dual infeasibility (reduced costs) = 0 Dual residual |c_B - y.B| = 9.28146e-14

Final unscaled solution: Primal objective (before moving primal/dual values) = 3.084411406463711E+03 Dual objective (before moving primal/dual values) = 3.084411246033969E+03 Primal objective (after moving primal/dual values) = 3.084411406463711E+03 Max. rhs perturbation = 8.23591e+09 Max. cost perturbation = 1.35802e-12 Max. primal infeasibility = 8.23591e+09 Max. dual infeasibility = 1.35802e-12 Objective error <= 1.14225e+09 status: DUAL_UNBOUNDED objective: 3084.41 iterations: 522 time: 0.226179 deterministic_time: 0.294754

The problem does not have an optimal solution!