Question on relaxing feasibility tolerances in GLOP (C# API)

[Alfred Manoj]

Hello OR-Tools / GLOP team,

I’m reaching out for guidance regarding feasibility tolerances in the GLOP solver and how to correctly relax them.

We have a linear feasibility model for which GLOP is able to find a solution reliably using the default parameters. With the defaults (notably primal_feasibility_tolerance = 1e-8), the solver converges in ~ 740-750 iterations and returns a valid solution.

For our use case, we would like to be more lenient on feasibility - specifically allowing slightly larger bound or constraint violations. To do this, we attempted to relax the tolerance by setting:

• primal_feasibility_tolerance = 1e-7

(using the C# API via SetSolverSpecificParametersAsString).

Unexpectedly with this change, the solver no longer converges as expected. While the default settings consistently find a solution, the run with the relaxed tolerance does not.

To rule out mismatched feasibility criteria, we also tried explicitly setting:

• dual_feasibility_tolerance = 1e-7

However, this did not change the behavior.

Given that numerically 1e-7 is a looser tolerance than the default 1e-8, we were expecting feasibility to be easier to satisfy, not harder.

Our questions are:

1. Is relaxing feasibility tolerances in GLOP (e.g., to 1e-7 or 1e-6) a supported and recommended use case?

2. Are there additional parameters that should be adjusted in conjunction with primal_feasibility_tolerance when relaxing feasibility requirements?

3. Is there known solver behavior where loosening feasibility tolerances can lead to non-convergence or solver stalling due to changes in pivot selection or numerical stability?

4. Are there best-practice guidelines for using GLOP when a looser feasibility acceptance is desired, particularly when using the C# API?

For context:

• We are using the C# API of OR-Tools.

• The model is continuous (no integer variables).

• The objective is zero; this is effectively a feasibility problem.

• Default parameter settings solve the model reliably.

Any guidance on the correct parameter combinations or recommended approach would be greatly appreciated.

Thank you for your time and for maintaining OR-Tools.

Regards,

Alfred

[Frederic Didier]

Hi,

It is hard to tell without looking at the logs.

Can you send us the problem so we can run it ourselves ? That would be the easiest for us to have a look at what is going on.

Usually, when changing tolerances has a big impact, it means your problem might not be numerically stable, scaling it to have a lower range of coefficients/bounds might help.

--
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/ef493490-3696-4891-90de-2e764ac592bfn%40googlegroups.com.

[Alfred Manoj]

Hi Team,

Thank you for the response, and apologies for the delay in getting back.

As suggested, I am attaching the solver logs for two runs of the same model so you can compare the behavior:

1. Run with default parameters

   • Default primal_feasibility_tolerance = 1e-8

   • Solver converges successfully in ~730 iterations and returns a feasible solution.

2. Run with relaxed feasibility tolerance

   • primal_feasibility_tolerance = 1e-7

   • (We also tried setting dual_feasibility_tolerance = 1e-7, with no observable change.)

   • In this case, the solver does not converge; it continues iterating indefinitely.

   • We terminated the run manually after ~18,983 iterations.

Both runs use the same model, solver backend (GLOP), and C# API, with the only difference being the feasibility tolerance settings.

Please let me know if reviewing these logs gives you an indication of where we should focus next and if you need any further info.

Thanks again for your time and help.

Regards,

Alfred

[Frederic Didier]

From the log, I see that your range of input coefficients is not ideal: [1.220000e-22, 7.388677e-01]

Usually, you don't want such a high range of magnitude, that can lead to issues.

Even commercial solvers like Gurobi recommend a smaller range: "We recommend that you scale the matrix coefficients so that their range is contained in six orders of magnitude or less, and hopefully within
[1e-3, 1e6]. Depending on how the solver uses tolerances, basically everything under 1e-12 can just be dropped (we don't do that with glop by default, which could explain the weird behavior you see).

You can try with drop_magnitude:1e-12 which will drop everything smaller than this and see if it works better. Note that if the final solution magnitude is reasonable (like <1e4), then dropping such small numbers will still satisfy the tolerance of every constraint up to the primal tolerance.

Another thing to try, is use_dual_simplex:true, sometimes the dual simplex is a lot more stable numerically than the primal, so this could help with your problem.

Hope that helps.

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/a244514d-6ad8-4615-9c9d-2adae93d3b41n%40googlegroups.com.

[Alfred Manoj]

Hi Frederic,

Thank you for the detailed explanation - that helps a lot. I tried the suggestions you mentioned and wanted to share the updated results (logs attached for all runs).

Summary of what I tested

1. Baseline (default parameters)

• primal_feasibility_tolerance: 1e-08 (defaults)
• Solves successfully (previously ~749 iterations)

2. With dropping tiny coefficients

• drop_magnitude: 1e-13
• With default tolerances, this now converges successfully and a bit faster (~730 iterations instead of ~749).

3. Drop tiny coefficients + relaxed primal tolerance

• drop_tolerance: 1e-13
• primal_feasibility_tolerance: 1e-7
• (also tried dual_feasibility_tolerance: 1e-7)
• This still fails to converge (I terminated after ~290,573 iterations).

In this stalled run, the solver appears to enter a loop where sum_primal_infeasibilities oscillates between nearly identical values repeatedly. For example:

Primal feasibility phase, iteration # 289533, sum_primal_infeasibilities = 1.076508386077535E-05

Primal feasibility phase, iteration # 289598, sum_primal_infeasibilities = 1.204802026277818E-05

Primal feasibility phase, iteration # 289663, sum_primal_infeasibilities = 1.076508409481036E-05

Primal feasibility phase, iteration # 289728, sum_primal_infeasibilities = 1.204802049148412E-05

… (continues alternating similarly)

This looks like a limit-cycle / degeneracy behavior rather than gradual convergence.

4. Dual simplex

• use_dual_simplex: true
• In our case, this configuration does not find a solution even with default tolerances, and instead returns DUAL_UNBOUNDED (log attached).

Given that drop_tolerance: 1e-13 improves the default run but does not help once primal_feasibility_tolerance is relaxed, do you have any suggestions on what solver parameters typically help break the kind of oscillation shown above?
Also, Is there a known reason why loosening primal_feasibility_tolerance (from 1e-8 to 1e-7) could cause the solver to follow a pivot path that cycles even after very small coefficients have been dropped?

Thank you again for your time and support. I look forward to your suggestions.

Regards,

Alfred

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/CABqCn%3DdV4u0XP0Sc4vyV81A5domUi27mmfU-8KWnjw5s2by3Sw%40mail.gmail.com.