Help understanding solver logs and improving problem formulation
250 views
Skip to first unread message
miguel ramos
Jan 14, 2025, 4:55:08 AM1/14/25
to or-tools-discuss
Hi community,
I want to solve a linear programming problem with GLOP. For that I am using python 3.8.10 and I installed ortools 9.11.4210 using "pip install ortools" command. So far I tried solving this problem with the following settings:
- solve with GLOP finds it abnormal.
- solve with GLOP with the setting "change_status_to_imprecise:false" finds an optimal solution.
- solve with SCIP finds an optimal solution.
The code in python to execute the solve was:
from ortools.linear_solver.python import model_builder
mps_path = "./obfuscated-model.mps"
model = model_builder.ModelBuilder()
model.import_from_mps_file(mps_path)
solver = model_builder.ModelSolver("GLOP") # GLOP --> ABNORMAL, SCIP --> OPTIMAL
parameters = "change_status_to_imprecise:false" # GLOP finds optimal with this parameter!
solver.set_solver_specific_parameters(parameters)
solver.enable_output(True)
solver.solve(model)
I have added the logs of the solves at the end of this message. I will also try to attach the .mps file in a next message as it does not allow me to do it now.
After reading the ortools documentation (which was very helpful) I believe it could be related to very big difference between min and max values in the objective function, the boundaries and the coefficient matrix.
Could you help me understand the logs produced by the solver in every case and provide some advice on how to improve the current setup (so that in every case I get a precise optimal solution)?
Any support is highly appreciated, I am trying to make the most out of ortools.
---------------------------
----Solver Logs----
---------------------------
GLOP logs:
Initial problem: 1326451 rows, 2157136 columns, 3646099 entries with magnitude in [7.097290e-06, 8.307690e+00]
Objective stats: 2156356 non-zeros, range [-1.980000e+03, 1.000000e-09]
Bounds stats: 60084 non-zeros, range [8.460000e-08, 6.300000e+08]
Parameters: log_search_progress: true
Starting presolve...
SingletonPreprocessor : 1066152(-260299) rows, 1969407(-187729) columns, 3198071(-448028) entries. (0.819669s)
ForcingAndImpliedFreeConstraintPreprocessor : 942367(-384084) rows, 1742438(-414698) columns, 2314140(-1331959) entries. (0.437932s)
FreeConstraintPreprocessor : 942338(-384113) rows, 1742438(-414698) columns, 2314000(-1332099) entries. (0.043969s)
ImpliedFreePreprocessor : 942338(-384113) rows, 1742438(-414698) columns, 2314000(-1332099) entries. (0.508209s)
UnconstrainedVariablePreprocessor : 942338(-384113) rows, 970154(-1186982) columns, 2313868(-1332231) entries. (0.345454s)
DoubletonFreeColumnPreprocessor : 481832(-844619) rows, 970154(-1186982) columns, 1834031(-1812068) entries. (1.604930s)
DoubletonEqualityRowPreprocessor : 475925(-850526) rows, 964247(-1192889) columns, 1822217(-1823882) entries. (0.070864s)
FixedVariablePreprocessor : 475925(-850526) rows, 504651(-1652485) columns, 1362621(-2283478) entries. (0.110768s)
SingletonPreprocessor : 51474(-1274977) rows, 270146(-1886990) columns, 703665(-2942434) entries. (0.572581s)
ForcingAndImpliedFreeConstraintPreprocessor : 50119(-1276332) rows, 265902(-1891234) columns, 690708(-2955391) entries. (0.044605s)
FreeConstraintPreprocessor : 49290(-1277161) rows, 265902(-1891234) columns, 676434(-2969665) entries. (0.007589s)
ImpliedFreePreprocessor : 49290(-1277161) rows, 265902(-1891234) columns, 676434(-2969665) entries. (0.081512s)
UnconstrainedVariablePreprocessor : 49290(-1277161) rows, 215858(-1941278) columns, 637140(-3008959) entries. (0.075725s)
DoubletonFreeColumnPreprocessor : 40141(-1286310) rows, 215858(-1941278) columns, 620324(-3025775) entries. (0.094183s)
DoubletonEqualityRowPreprocessor : 39590(-1286861) rows, 215307(-1941829) columns, 619222(-3026877) entries. (0.012929s)
FixedVariablePreprocessor : 39590(-1286861) rows, 75802(-2081334) columns, 438482(-3207617) entries. (0.028319s)
SingletonPreprocessor : 35731(-1290720) rows, 75699(-2081437) columns, 434520(-3211579) entries. (0.020880s)
FreeConstraintPreprocessor : 35370(-1291081) rows, 75699(-2081437) columns, 429117(-3216982) entries. (0.002762s)
UnconstrainedVariablePreprocessor : 35370(-1291081) rows, 75208(-2081928) columns, 429089(-3217010) entries. (0.017392s)
FixedVariablePreprocessor : 35370(-1291081) rows, 75196(-2081940) columns, 429077(-3217022) entries. (0.003011s)
SingletonPreprocessor : 35366(-1291085) rows, 75173(-2081963) columns, 429050(-3217049) entries. (0.009957s)
UnconstrainedVariablePreprocessor : 35366(-1291085) rows, 75066(-2082070) columns, 428943(-3217156) entries. (0.025176s)
Reached fixed point after presolve pass #4
EmptyConstraintPreprocessor : 21932(-1304519) rows, 75066(-2082070) columns, 428943(-3217156) entries. (0.005982s)
ProportionalColumnPreprocessor : 21932(-1304519) rows, 72374(-2084762) columns, 418526(-3227573) entries. (0.037811s)
ProportionalRowPreprocessor : 21594(-1304857) rows, 72374(-2084762) columns, 405516(-3240583) entries. (0.017022s)
SingletonColumnSignPreprocessor : 21594(-1304857) rows, 72374(-2084762) columns, 405516(-3240583) entries. (0.000500s)
ScalingPreprocessor : 21594(-1304857) rows, 72374(-2084762) columns, 405516(-3240583) entries. (0.020699s)
Presolved problem: 21594 rows, 72374 columns, 405516 entries with magnitude in [1.243853e-02, 1.000000e+00]
Objective stats: 72373 non-zeros, range [-6.545526e+02, 1.741245e+02]
Bounds stats: 46997 non-zeros, range [-2.239263e+07, 4.811997e+12]
Starting basis: create from scratch.
Crash is set to 2 but there is no equality rows to remove from initial all slack basis. Starting from there.
The matrix with slacks has 21594 rows, 93968 columns, 427110 entries.
Number of basic infeasible variables: 0
Number of basic slack variables: 21554
Number of basic variables at bound: 20573
Number of basic fixed variables: 0
Number of basic free variables: 0
Number of super-basic variables: 0
Primal feasibility phase, iteration # 0, sum_primal_infeasibilities = 0.000000000000000E+00 [norms]
Current status: PRIMAL_FEASIBLE
Primal infeasibility (bounds) = 0
Primal residual |A.x - b| = 0
Dual infeasibility (reduced costs) = 654.553
Dual residual |c_B - y.B| = 0
Primal optimization phase, iteration # 0, objective = -3.292148271419645E+07
Primal optimization phase, iteration # 1, objective = -3.292378705819643E+07
Primal optimization phase, iteration # 2, objective = -3.295612981319549E+07
Primal optimization phase, iteration # 94, objective = -4.133208497127531E+07
Primal optimization phase, iteration # 479, objective = -7.642151353968197E+07
Primal optimization phase, iteration # 942, objective = -1.416038054966594E+08
...
Primal optimization phase, iteration # 41780, objective = -2.334620442322239E+09
Primal optimization phase, iteration # 41860, objective = -2.334621495601373E+09 [check]
Current status: OPTIMAL
Primal infeasibility (bounds) = 0
Primal residual |A.x - b| = 1.11759e-08
Dual infeasibility (reduced costs) = 9.53493e-09
Dual residual |c_B - y.B| = 5.68434e-14
Final unscaled solution:
Primal objective (before moving primal/dual values) = -2.334621495449477E+09
Dual objective (before moving primal/dual values) = -2.334621495601373E+09
Max. primal values move = 2.91038e-11
Max. dual values move = 0
Primal objective (after moving primal/dual values) = -2.334621495449477E+09
Max. rhs perturbation = 6.98492e-10
Max. cost perturbation = 2.36859e-06
Max. primal infeasibility = 6.98492e-10
Max. dual infeasibility = 2.36859e-06
Objective error <= 2335.63
The needed cost perturbation is too large !!
status: IMPRECISE
objective: -2.33462e+09
iterations: 41860
time: 9.23618
deterministic_time: 0.756315
GLOP with imprecise setting logs:
Initial problem: 1326451 rows, 2157136 columns, 3646099 entries with magnitude in [7.097290e-06, 8.307690e+00]
Objective stats: 2156356 non-zeros, range [-1.980000e+03, 1.000000e-09]
Bounds stats: 60084 non-zeros, range [8.460000e-08, 6.300000e+08]
Parameters: change_status_to_imprecise: false log_search_progress: true
Starting presolve...
SingletonPreprocessor : 1066152(-260299) rows, 1969407(-187729) columns, 3198071(-448028) entries. (0.813902s)
ForcingAndImpliedFreeConstraintPreprocessor : 942367(-384084) rows, 1742438(-414698) columns, 2314140(-1331959) entries. (0.447519s)
FreeConstraintPreprocessor : 942338(-384113) rows, 1742438(-414698) columns, 2314000(-1332099) entries. (0.045619s)
ImpliedFreePreprocessor : 942338(-384113) rows, 1742438(-414698) columns, 2314000(-1332099) entries. (0.536161s)
UnconstrainedVariablePreprocessor : 942338(-384113) rows, 970154(-1186982) columns, 2313868(-1332231) entries. (0.342061s)
DoubletonFreeColumnPreprocessor : 481832(-844619) rows, 970154(-1186982) columns, 1834031(-1812068) entries. (1.547517s)
DoubletonEqualityRowPreprocessor : 475925(-850526) rows, 964247(-1192889) columns, 1822217(-1823882) entries. (0.065593s)
FixedVariablePreprocessor : 475925(-850526) rows, 504651(-1652485) columns, 1362621(-2283478) entries. (0.111533s)
SingletonPreprocessor : 51474(-1274977) rows, 270146(-1886990) columns, 703665(-2942434) entries. (0.553777s)
ForcingAndImpliedFreeConstraintPreprocessor : 50119(-1276332) rows, 265902(-1891234) columns, 690708(-2955391) entries. (0.048194s)
FreeConstraintPreprocessor : 49290(-1277161) rows, 265902(-1891234) columns, 676434(-2969665) entries. (0.009322s)
ImpliedFreePreprocessor : 49290(-1277161) rows, 265902(-1891234) columns, 676434(-2969665) entries. (0.088017s)
UnconstrainedVariablePreprocessor : 49290(-1277161) rows, 215858(-1941278) columns, 637140(-3008959) entries. (0.083936s)
DoubletonFreeColumnPreprocessor : 40141(-1286310) rows, 215858(-1941278) columns, 620324(-3025775) entries. (0.087707s)
DoubletonEqualityRowPreprocessor : 39590(-1286861) rows, 215307(-1941829) columns, 619222(-3026877) entries. (0.014848s)
FixedVariablePreprocessor : 39590(-1286861) rows, 75802(-2081334) columns, 438482(-3207617) entries. (0.030772s)
SingletonPreprocessor : 35731(-1290720) rows, 75699(-2081437) columns, 434520(-3211579) entries. (0.026052s)
FreeConstraintPreprocessor : 35370(-1291081) rows, 75699(-2081437) columns, 429117(-3216982) entries. (0.002772s)
UnconstrainedVariablePreprocessor : 35370(-1291081) rows, 75208(-2081928) columns, 429089(-3217010) entries. (0.017034s)
FixedVariablePreprocessor : 35370(-1291081) rows, 75196(-2081940) columns, 429077(-3217022) entries. (0.003540s)
SingletonPreprocessor : 35366(-1291085) rows, 75173(-2081963) columns, 429050(-3217049) entries. (0.008397s)
UnconstrainedVariablePreprocessor : 35366(-1291085) rows, 75066(-2082070) columns, 428943(-3217156) entries. (0.016903s)
Reached fixed point after presolve pass #4
EmptyConstraintPreprocessor : 21932(-1304519) rows, 75066(-2082070) columns, 428943(-3217156) entries. (0.006839s)
ProportionalColumnPreprocessor : 21932(-1304519) rows, 72374(-2084762) columns, 418526(-3227573) entries. (0.040256s)
ProportionalRowPreprocessor : 21594(-1304857) rows, 72374(-2084762) columns, 405516(-3240583) entries. (0.018844s)
SingletonColumnSignPreprocessor : 21594(-1304857) rows, 72374(-2084762) columns, 405516(-3240583) entries. (0.000577s)
ScalingPreprocessor : 21594(-1304857) rows, 72374(-2084762) columns, 405516(-3240583) entries. (0.019556s)
Presolved problem: 21594 rows, 72374 columns, 405516 entries with magnitude in [1.243853e-02, 1.000000e+00]
Objective stats: 72373 non-zeros, range [-6.545526e+02, 1.741245e+02]
Bounds stats: 46997 non-zeros, range [-2.239263e+07, 4.811997e+12]
Starting basis: create from scratch.
Crash is set to 2 but there is no equality rows to remove from initial all slack basis. Starting from there.
The matrix with slacks has 21594 rows, 93968 columns, 427110 entries.
Number of basic infeasible variables: 0
Number of basic slack variables: 21554
Number of basic variables at bound: 20573
Number of basic fixed variables: 0
Number of basic free variables: 0
Number of super-basic variables: 0
Primal feasibility phase, iteration # 0, sum_primal_infeasibilities = 0.000000000000000E+00 [norms]
Current status: PRIMAL_FEASIBLE
Primal infeasibility (bounds) = 0
Primal residual |A.x - b| = 0
Dual infeasibility (reduced costs) = 654.553
Dual residual |c_B - y.B| = 0
Primal optimization phase, iteration # 0, objective = -3.292148271419645E+07
Primal optimization phase, iteration # 1, objective = -3.292378705819643E+07
Primal optimization phase, iteration # 2, objective = -3.295612981319549E+07
Primal optimization phase, iteration # 94, objective = -4.133208497127531E+07
Primal optimization phase, iteration # 479, objective = -7.642151353968197E+07
...
Primal optimization phase, iteration # 41489, objective = -2.334486409400562E+09
Primal optimization phase, iteration # 41780, objective = -2.334620442322239E+09
Primal optimization phase, iteration # 41860, objective = -2.334621495601373E+09 [check]
Current status: OPTIMAL
Primal infeasibility (bounds) = 0
Primal residual |A.x - b| = 1.11759e-08
Dual infeasibility (reduced costs) = 9.53493e-09
Dual residual |c_B - y.B| = 5.68434e-14
Final unscaled solution:
Primal objective (before moving primal/dual values) = -2.334621495449477E+09
Dual objective (before moving primal/dual values) = -2.334621495601373E+09
Max. primal values move = 2.91038e-11
Max. dual values move = 0
Primal objective (after moving primal/dual values) = -2.334621495449477E+09
Max. rhs perturbation = 6.98492e-10
Max. cost perturbation = 2.36859e-06
Max. primal infeasibility = 6.98492e-10
Max. dual infeasibility = 2.36859e-06
Objective error <= 2335.63
The needed cost perturbation is too large !!
The dual infeasibility of the final solution is too large.
status: OPTIMAL
objective: -2.33462e+09
iterations: 41860
time: 9.06515
deterministic_time: 0.756064
SCIP Logs:
presolving:
(round 1, fast) 2040913 del vars, 1281871 del conss, 0 add conss, 1428039 chg bounds, 3 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 2, fast) 2064033 del vars, 1298753 del conss, 0 add conss, 1451832 chg bounds, 19278 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 3, fast) 2080218 del vars, 1304764 del conss, 0 add conss, 1453228 chg bounds, 21631 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 4, fast) 2083021 del vars, 1306530 del conss, 0 add conss, 1453248 chg bounds, 21636 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 5, fast) 2083140 del vars, 1306564 del conss, 0 add conss, 1453270 chg bounds, 21636 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 6, exhaustive) 2083166 del vars, 1306595 del conss, 0 add conss, 1453446 chg bounds, 21636 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 7, exhaustive) 2090323 del vars, 1306604 del conss, 0 add conss, 1453452 chg bounds, 21642 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 8, fast) 2090581 del vars, 1309346 del conss, 0 add conss, 1453493 chg bounds, 21671 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 9, fast) 2091298 del vars, 1309447 del conss, 0 add conss, 1453497 chg bounds, 21671 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 10, fast) 2091390 del vars, 1309469 del conss, 0 add conss, 1453509 chg bounds, 21674 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 11, exhaustive) 2091503 del vars, 1309475 del conss, 0 add conss, 1453542 chg bounds, 21676 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 12, fast) 2091513 del vars, 1309532 del conss, 0 add conss, 1453544 chg bounds, 21678 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(20.0s) probing cycle finished: starting next cycle
Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).
Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).
presolving (13 rounds: 13 fast, 4 medium, 4 exhaustive):
2157135 deleted vars, 1326451 deleted constraints, 0 added constraints, 1453546 tightened bounds, 0 added holes, 21678 changed sides, 0 changed coefficients
0 implications, 0 cliques
presolved problem has 1 variables (0 bin, 0 int, 1 impl, 0 cont) and 0 constraints
Presolving Time: 18.00
time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl.
t24.0s| 1 | 0 | 0 | - | trivial| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |-2.334622e+09 |-2.334622e+09 | 0.00%| unknown
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 24.00
Solving Nodes : 1
Primal Bound : -2.33462162907611e+09 (1 solutions)
Dual Bound : -2.33462162907611e+09
Gap : 0.00 %
solution violates original bounds of variable <V1368559> [0,1e+20] solution value <-0.0008461>
best solution is not feasible in original problem
Initial problem: 1326451 rows, 2157136 columns, 3646099 entries with magnitude in [7.097290e-06, 8.307690e+00]
Objective stats: 2156356 non-zeros, range [-1.980000e+03, 1.000000e-09]
Bounds stats: 60084 non-zeros, range [8.460000e-08, 6.300000e+08]
Parameters: log_search_progress: true
Starting presolve...
SingletonPreprocessor : 1066152(-260299) rows, 1969407(-187729) columns, 3198071(-448028) entries. (0.819669s)
ForcingAndImpliedFreeConstraintPreprocessor : 942367(-384084) rows, 1742438(-414698) columns, 2314140(-1331959) entries. (0.437932s)
FreeConstraintPreprocessor : 942338(-384113) rows, 1742438(-414698) columns, 2314000(-1332099) entries. (0.043969s)
ImpliedFreePreprocessor : 942338(-384113) rows, 1742438(-414698) columns, 2314000(-1332099) entries. (0.508209s)
UnconstrainedVariablePreprocessor : 942338(-384113) rows, 970154(-1186982) columns, 2313868(-1332231) entries. (0.345454s)
DoubletonFreeColumnPreprocessor : 481832(-844619) rows, 970154(-1186982) columns, 1834031(-1812068) entries. (1.604930s)
DoubletonEqualityRowPreprocessor : 475925(-850526) rows, 964247(-1192889) columns, 1822217(-1823882) entries. (0.070864s)
FixedVariablePreprocessor : 475925(-850526) rows, 504651(-1652485) columns, 1362621(-2283478) entries. (0.110768s)
SingletonPreprocessor : 51474(-1274977) rows, 270146(-1886990) columns, 703665(-2942434) entries. (0.572581s)
ForcingAndImpliedFreeConstraintPreprocessor : 50119(-1276332) rows, 265902(-1891234) columns, 690708(-2955391) entries. (0.044605s)
FreeConstraintPreprocessor : 49290(-1277161) rows, 265902(-1891234) columns, 676434(-2969665) entries. (0.007589s)
ImpliedFreePreprocessor : 49290(-1277161) rows, 265902(-1891234) columns, 676434(-2969665) entries. (0.081512s)
UnconstrainedVariablePreprocessor : 49290(-1277161) rows, 215858(-1941278) columns, 637140(-3008959) entries. (0.075725s)
DoubletonFreeColumnPreprocessor : 40141(-1286310) rows, 215858(-1941278) columns, 620324(-3025775) entries. (0.094183s)
DoubletonEqualityRowPreprocessor : 39590(-1286861) rows, 215307(-1941829) columns, 619222(-3026877) entries. (0.012929s)
FixedVariablePreprocessor : 39590(-1286861) rows, 75802(-2081334) columns, 438482(-3207617) entries. (0.028319s)
SingletonPreprocessor : 35731(-1290720) rows, 75699(-2081437) columns, 434520(-3211579) entries. (0.020880s)
FreeConstraintPreprocessor : 35370(-1291081) rows, 75699(-2081437) columns, 429117(-3216982) entries. (0.002762s)
UnconstrainedVariablePreprocessor : 35370(-1291081) rows, 75208(-2081928) columns, 429089(-3217010) entries. (0.017392s)
FixedVariablePreprocessor : 35370(-1291081) rows, 75196(-2081940) columns, 429077(-3217022) entries. (0.003011s)
SingletonPreprocessor : 35366(-1291085) rows, 75173(-2081963) columns, 429050(-3217049) entries. (0.009957s)
UnconstrainedVariablePreprocessor : 35366(-1291085) rows, 75066(-2082070) columns, 428943(-3217156) entries. (0.025176s)
Reached fixed point after presolve pass #4
EmptyConstraintPreprocessor : 21932(-1304519) rows, 75066(-2082070) columns, 428943(-3217156) entries. (0.005982s)
ProportionalColumnPreprocessor : 21932(-1304519) rows, 72374(-2084762) columns, 418526(-3227573) entries. (0.037811s)
ProportionalRowPreprocessor : 21594(-1304857) rows, 72374(-2084762) columns, 405516(-3240583) entries. (0.017022s)
SingletonColumnSignPreprocessor : 21594(-1304857) rows, 72374(-2084762) columns, 405516(-3240583) entries. (0.000500s)
ScalingPreprocessor : 21594(-1304857) rows, 72374(-2084762) columns, 405516(-3240583) entries. (0.020699s)
Presolved problem: 21594 rows, 72374 columns, 405516 entries with magnitude in [1.243853e-02, 1.000000e+00]
Objective stats: 72373 non-zeros, range [-6.545526e+02, 1.741245e+02]
Bounds stats: 46997 non-zeros, range [-2.239263e+07, 4.811997e+12]
Starting basis: create from scratch.
Crash is set to 2 but there is no equality rows to remove from initial all slack basis. Starting from there.
The matrix with slacks has 21594 rows, 93968 columns, 427110 entries.
Number of basic infeasible variables: 0
Number of basic slack variables: 21554
Number of basic variables at bound: 20573
Number of basic fixed variables: 0
Number of basic free variables: 0
Number of super-basic variables: 0
Primal feasibility phase, iteration # 0, sum_primal_infeasibilities = 0.000000000000000E+00 [norms]
Current status: PRIMAL_FEASIBLE
Primal infeasibility (bounds) = 0
Primal residual |A.x - b| = 0
Dual infeasibility (reduced costs) = 654.553
Dual residual |c_B - y.B| = 0
Primal optimization phase, iteration # 0, objective = -3.292148271419645E+07
Primal optimization phase, iteration # 1, objective = -3.292378705819643E+07
Primal optimization phase, iteration # 2, objective = -3.295612981319549E+07
Primal optimization phase, iteration # 94, objective = -4.133208497127531E+07
Primal optimization phase, iteration # 479, objective = -7.642151353968197E+07
Primal optimization phase, iteration # 942, objective = -1.416038054966594E+08
...
Primal optimization phase, iteration # 41780, objective = -2.334620442322239E+09
Primal optimization phase, iteration # 41860, objective = -2.334621495601373E+09 [check]
Current status: OPTIMAL
Primal infeasibility (bounds) = 0
Primal residual |A.x - b| = 1.11759e-08
Dual infeasibility (reduced costs) = 9.53493e-09
Dual residual |c_B - y.B| = 5.68434e-14
Final unscaled solution:
Primal objective (before moving primal/dual values) = -2.334621495449477E+09
Dual objective (before moving primal/dual values) = -2.334621495601373E+09
Max. primal values move = 2.91038e-11
Max. dual values move = 0
Primal objective (after moving primal/dual values) = -2.334621495449477E+09
Max. rhs perturbation = 6.98492e-10
Max. cost perturbation = 2.36859e-06
Max. primal infeasibility = 6.98492e-10
Max. dual infeasibility = 2.36859e-06
Objective error <= 2335.63
The needed cost perturbation is too large !!
status: IMPRECISE
objective: -2.33462e+09
iterations: 41860
time: 9.23618
deterministic_time: 0.756315
GLOP with imprecise setting logs:
Initial problem: 1326451 rows, 2157136 columns, 3646099 entries with magnitude in [7.097290e-06, 8.307690e+00]
Objective stats: 2156356 non-zeros, range [-1.980000e+03, 1.000000e-09]
Bounds stats: 60084 non-zeros, range [8.460000e-08, 6.300000e+08]
Parameters: change_status_to_imprecise: false log_search_progress: true
Starting presolve...
SingletonPreprocessor : 1066152(-260299) rows, 1969407(-187729) columns, 3198071(-448028) entries. (0.813902s)
ForcingAndImpliedFreeConstraintPreprocessor : 942367(-384084) rows, 1742438(-414698) columns, 2314140(-1331959) entries. (0.447519s)
FreeConstraintPreprocessor : 942338(-384113) rows, 1742438(-414698) columns, 2314000(-1332099) entries. (0.045619s)
ImpliedFreePreprocessor : 942338(-384113) rows, 1742438(-414698) columns, 2314000(-1332099) entries. (0.536161s)
UnconstrainedVariablePreprocessor : 942338(-384113) rows, 970154(-1186982) columns, 2313868(-1332231) entries. (0.342061s)
DoubletonFreeColumnPreprocessor : 481832(-844619) rows, 970154(-1186982) columns, 1834031(-1812068) entries. (1.547517s)
DoubletonEqualityRowPreprocessor : 475925(-850526) rows, 964247(-1192889) columns, 1822217(-1823882) entries. (0.065593s)
FixedVariablePreprocessor : 475925(-850526) rows, 504651(-1652485) columns, 1362621(-2283478) entries. (0.111533s)
SingletonPreprocessor : 51474(-1274977) rows, 270146(-1886990) columns, 703665(-2942434) entries. (0.553777s)
ForcingAndImpliedFreeConstraintPreprocessor : 50119(-1276332) rows, 265902(-1891234) columns, 690708(-2955391) entries. (0.048194s)
FreeConstraintPreprocessor : 49290(-1277161) rows, 265902(-1891234) columns, 676434(-2969665) entries. (0.009322s)
ImpliedFreePreprocessor : 49290(-1277161) rows, 265902(-1891234) columns, 676434(-2969665) entries. (0.088017s)
UnconstrainedVariablePreprocessor : 49290(-1277161) rows, 215858(-1941278) columns, 637140(-3008959) entries. (0.083936s)
DoubletonFreeColumnPreprocessor : 40141(-1286310) rows, 215858(-1941278) columns, 620324(-3025775) entries. (0.087707s)
DoubletonEqualityRowPreprocessor : 39590(-1286861) rows, 215307(-1941829) columns, 619222(-3026877) entries. (0.014848s)
FixedVariablePreprocessor : 39590(-1286861) rows, 75802(-2081334) columns, 438482(-3207617) entries. (0.030772s)
SingletonPreprocessor : 35731(-1290720) rows, 75699(-2081437) columns, 434520(-3211579) entries. (0.026052s)
FreeConstraintPreprocessor : 35370(-1291081) rows, 75699(-2081437) columns, 429117(-3216982) entries. (0.002772s)
UnconstrainedVariablePreprocessor : 35370(-1291081) rows, 75208(-2081928) columns, 429089(-3217010) entries. (0.017034s)
FixedVariablePreprocessor : 35370(-1291081) rows, 75196(-2081940) columns, 429077(-3217022) entries. (0.003540s)
SingletonPreprocessor : 35366(-1291085) rows, 75173(-2081963) columns, 429050(-3217049) entries. (0.008397s)
UnconstrainedVariablePreprocessor : 35366(-1291085) rows, 75066(-2082070) columns, 428943(-3217156) entries. (0.016903s)
Reached fixed point after presolve pass #4
EmptyConstraintPreprocessor : 21932(-1304519) rows, 75066(-2082070) columns, 428943(-3217156) entries. (0.006839s)
ProportionalColumnPreprocessor : 21932(-1304519) rows, 72374(-2084762) columns, 418526(-3227573) entries. (0.040256s)
ProportionalRowPreprocessor : 21594(-1304857) rows, 72374(-2084762) columns, 405516(-3240583) entries. (0.018844s)
SingletonColumnSignPreprocessor : 21594(-1304857) rows, 72374(-2084762) columns, 405516(-3240583) entries. (0.000577s)
ScalingPreprocessor : 21594(-1304857) rows, 72374(-2084762) columns, 405516(-3240583) entries. (0.019556s)
Presolved problem: 21594 rows, 72374 columns, 405516 entries with magnitude in [1.243853e-02, 1.000000e+00]
Objective stats: 72373 non-zeros, range [-6.545526e+02, 1.741245e+02]
Bounds stats: 46997 non-zeros, range [-2.239263e+07, 4.811997e+12]
Starting basis: create from scratch.
Crash is set to 2 but there is no equality rows to remove from initial all slack basis. Starting from there.
The matrix with slacks has 21594 rows, 93968 columns, 427110 entries.
Number of basic infeasible variables: 0
Number of basic slack variables: 21554
Number of basic variables at bound: 20573
Number of basic fixed variables: 0
Number of basic free variables: 0
Number of super-basic variables: 0
Primal feasibility phase, iteration # 0, sum_primal_infeasibilities = 0.000000000000000E+00 [norms]
Current status: PRIMAL_FEASIBLE
Primal infeasibility (bounds) = 0
Primal residual |A.x - b| = 0
Dual infeasibility (reduced costs) = 654.553
Dual residual |c_B - y.B| = 0
Primal optimization phase, iteration # 0, objective = -3.292148271419645E+07
Primal optimization phase, iteration # 1, objective = -3.292378705819643E+07
Primal optimization phase, iteration # 2, objective = -3.295612981319549E+07
Primal optimization phase, iteration # 94, objective = -4.133208497127531E+07
Primal optimization phase, iteration # 479, objective = -7.642151353968197E+07
...
Primal optimization phase, iteration # 41489, objective = -2.334486409400562E+09
Primal optimization phase, iteration # 41780, objective = -2.334620442322239E+09
Primal optimization phase, iteration # 41860, objective = -2.334621495601373E+09 [check]
Current status: OPTIMAL
Primal infeasibility (bounds) = 0
Primal residual |A.x - b| = 1.11759e-08
Dual infeasibility (reduced costs) = 9.53493e-09
Dual residual |c_B - y.B| = 5.68434e-14
Final unscaled solution:
Primal objective (before moving primal/dual values) = -2.334621495449477E+09
Dual objective (before moving primal/dual values) = -2.334621495601373E+09
Max. primal values move = 2.91038e-11
Max. dual values move = 0
Primal objective (after moving primal/dual values) = -2.334621495449477E+09
Max. rhs perturbation = 6.98492e-10
Max. cost perturbation = 2.36859e-06
Max. primal infeasibility = 6.98492e-10
Max. dual infeasibility = 2.36859e-06
Objective error <= 2335.63
The needed cost perturbation is too large !!
The dual infeasibility of the final solution is too large.
status: OPTIMAL
objective: -2.33462e+09
iterations: 41860
time: 9.06515
deterministic_time: 0.756064
SCIP Logs:
presolving:
(round 1, fast) 2040913 del vars, 1281871 del conss, 0 add conss, 1428039 chg bounds, 3 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 2, fast) 2064033 del vars, 1298753 del conss, 0 add conss, 1451832 chg bounds, 19278 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 3, fast) 2080218 del vars, 1304764 del conss, 0 add conss, 1453228 chg bounds, 21631 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 4, fast) 2083021 del vars, 1306530 del conss, 0 add conss, 1453248 chg bounds, 21636 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 5, fast) 2083140 del vars, 1306564 del conss, 0 add conss, 1453270 chg bounds, 21636 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 6, exhaustive) 2083166 del vars, 1306595 del conss, 0 add conss, 1453446 chg bounds, 21636 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 7, exhaustive) 2090323 del vars, 1306604 del conss, 0 add conss, 1453452 chg bounds, 21642 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 8, fast) 2090581 del vars, 1309346 del conss, 0 add conss, 1453493 chg bounds, 21671 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 9, fast) 2091298 del vars, 1309447 del conss, 0 add conss, 1453497 chg bounds, 21671 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 10, fast) 2091390 del vars, 1309469 del conss, 0 add conss, 1453509 chg bounds, 21674 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 11, exhaustive) 2091503 del vars, 1309475 del conss, 0 add conss, 1453542 chg bounds, 21676 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 12, fast) 2091513 del vars, 1309532 del conss, 0 add conss, 1453544 chg bounds, 21678 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(20.0s) probing cycle finished: starting next cycle
Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).
Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).
presolving (13 rounds: 13 fast, 4 medium, 4 exhaustive):
2157135 deleted vars, 1326451 deleted constraints, 0 added constraints, 1453546 tightened bounds, 0 added holes, 21678 changed sides, 0 changed coefficients
0 implications, 0 cliques
presolved problem has 1 variables (0 bin, 0 int, 1 impl, 0 cont) and 0 constraints
Presolving Time: 18.00
time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl.
t24.0s| 1 | 0 | 0 | - | trivial| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |-2.334622e+09 |-2.334622e+09 | 0.00%| unknown
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 24.00
Solving Nodes : 1
Primal Bound : -2.33462162907611e+09 (1 solutions)
Dual Bound : -2.33462162907611e+09
Gap : 0.00 %
solution violates original bounds of variable <V1368559> [0,1e+20] solution value <-0.0008461>
best solution is not feasible in original problem
Laurent Perron
Jan 14, 2025, 4:58:25 AM1/14/25
to or-tools...@googlegroups.com
the logs says it all.
both solvers find a solution that is outside the validity bound.
By default, GLOP tells you it is unprecise, while SCIP ignores it.
--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/324a5dd5-3b81-471c-9aed-c02a451e6b36n%40googlegroups.com.
miguel ramos
Jan 14, 2025, 5:07:45 AM1/14/25
to or-tools-discuss
Hi Laurent,
thank you for your fast response. So would you recommend doing a better scaling of the problem data as explained in the ortools documentation (https://developers.google.com/optimization/lp/lp_advanced)?
Do you have any other suggestions, e.g., any parameters I could set?
Best Regards,
Laurent Perron
Jan 14, 2025, 5:53:28 AM1/14/25
to or-tools...@googlegroups.com
No, imprecise output is the direct consequence of high magnitude variations in coefficients/constants.
So improving the scaling is the way to go.
To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/efc6df0a-6bb6-4da2-824e-e435186ace5cn%40googlegroups.com.
Reply all
Reply to author
Forward
0 new messages