violation: right hand side is violated by 1049.999

[quant2008]

Hello， I use or-tools with scip to solve my case. In one case, I get the message "violation: right hand side is violated by 1049.999",
it seems this is a numerical problem. I wonder how to resolve this problem.

[2023-05-30 19:57:41,156] [DEBUG] autorosterplant_model.py [line:545] [autorosterplant_model] - begin solve level 1
  [linear] <auto_c_000000152>:  +10<underSkillLevel_891_3_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_6189_2_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61812_4_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61814_3_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_891_4_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61811_3_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_999_3_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_891_1_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61814_2_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_6189_3_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) 
+10<underSkillLevel_6186_1_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61811_4_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_999_4_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61815_3_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61810_3_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61815_1_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61815_2_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61810_1_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61814_4_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_6186_4_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_6189_4_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_6186_3_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61810_4_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61812_3_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_6186_2_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_891_2_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_999_2_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61812_2_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61812_1_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_999_1_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_6189_1_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61810_2_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61811_1_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61811_2_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) +10<underSkillLevel_61815_4_3a0682b5-f814-46c3-8614-922161a72876_569>[I] (+3) <= 0.001;
;
violation: right hand side is violated by 1049.999
1/3 feasible solution given by solution candidate storage, new primal bound 4.800000e+04

presolving:
(round 1, fast)       92 del vars, 143 del conss, 0 add conss, 89 chg bounds, 32 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
   (0.0s) probing cycle finished: starting next cycle
   Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).
presolving (2 rounds: 2 fast, 1 medium, 1 exhaustive):
 92 deleted vars, 157 deleted constraints, 0 added constraints, 89 tightened bounds, 0 added holes, 32 changed sides, 0 changed coefficients
 0 implications, 0 cliques
presolved problem has 17 variables (17 bin, 0 int, 0 impl, 0 cont) and 0 constraints
transformed objective value is always integral (scale: 1000)
Presolving Time: 0.00
transformed 1/1 original solutions to the transformed problem space

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl.
t 0.0s|     1 |     0 |     0 |     - | trivial|   0 |  17 |   0 |   0 |   0 |  0 |   0 |   0 | 3.100000e+04 | 3.100000e+04 |   0.00%| unknown

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.00
Solving Nodes      : 1
Primal Bound       : +3.10000000000000e+04 (2 solutions)
Dual Bound         : +3.10000000000000e+04
Gap                : 0.00 %

[svigerske]

If it's a numerical issue, then it sometimes helps to set parameter presolving/donotmultaggr = TRUE.
But since the violation is rather large, it could also be a bug, e.g., a wrong presolve reduction.

[sschnug]

I observed more or less the same issue when solving big multi-commodity flow like (enriched) models using or-tools with scip.
Neither the setting mentioned by Stefan above nor other expected-to-help param-tunings did get rid of the issue.

It may sound harsh, as i never analyzed / debugged it nor did i create upstream issues, but i would warn a bit about this combination (for now).

(The only worklog of mine i can find is my git-msg: "switch away from scip/glop (or-tools) to scip/soplex -> no numerical-trouble issues anymore")

Now the issue here is: where does this come from and "who is to blame" (excuse the wording).

It's not easy to track all relevant actors here. Just a remark from what i understood:

• or-tools with SCIP is using or-tools GLOP and not SOPLEX
  • probably the most important aspect here
    • this implies, that SCIP will use scip/src/lpi/lpi_glop.cpp instead of scip/src/lpi/lpi_spx2.cpp
  • this was my core motivation of using or-tools with SCIP as SOPLEX seems kind of outdated nowadays compared to GLOP/Highs and co.

There are other factors, probably irrelevant, like your binaries missing symmetry-reduction although always active in bazel-based builds (and maybe in cmake-based builds).

Seeing the amount of violation compared to the "smallness" of your problem, it really looks like something rather buggy than a num-tolerance thing (imho). In my case, instances were much much bigger.

I think, i would start with turning off presolve completely and retrying. If still broken, i would claim scip/src/lpi/lpi_glop.cpp is broken.

Maybe you are more helpful than i were and can offer a reproducable test-case for people wanting to analyze it :-). There are probably many paths to achieve that (python code with data; but also protobuf-based serialization which might be accessible through python-wrappers too) howewer.

[matbesancon]

I think, i would start with turning off presolve completely and retrying. If still broken, i would claim scip/src/lpi/lpi_glop.cpp is broken.

that claim would very much be an over-generalization ;)
you have to realize MIP solving is a complex process involving a lot of components, handling numerical inaccuracies that propagate in all components, this is not a simple data processing pipeline. In particular, all solvers have instances on which they return an infeasible solution / detect infeasibility.

There are probably many paths to achieve that (python code with data; but also protobuf-based serialization which might be accessible through python-wrappers too) however.

Overall, the best thing to do is a simple model in MPS / LP format, no need to reinvent the wheel, these are good standards in the MIP community.

[matbesancon]

@quant2008 one thing that can lead to such issues is ill-conditioned problems, typically having very large or very small coefficients. If you can, check if some constraints have these bad numerics.

Do you know if the final obtained solution is indeed valid for your problem or not, checking it with an external program? Or at least checking the optimal value?

[quant2008]

yes, the final obtained solution is indeed valid. So can I just ignore the violation message?matbesancon

[svigerske]

The messages

violation: right hand side is violated by 1049.999
1/3 feasible solution given by solution candidate storage, new primal bound 4.800000e+04

refer to solutions given to SCIP by the caller. They just say that 2 of these solutions are not feasible.
This is actually no numerical issue. The LP solver is not involved either.