Numerical Issues¶
When working with optimization solvers, it’s common to encounter numerical precision issues. These can affect both the coefficients of generated cuts and the comparison of floating-point values like objective functions. BendersLib handles these challenges as follows.
Comparing Objective Function Values¶
A core step in the stochastic Benders decomposition algorithm is to check if an optimality cut needs to be added.
This is done by comparing the objective value of the subproblem (sub_obj) with the current value of
the master problem’s estimator variable (theta). A cut is added if sub_obj is greater than theta.
However, due to floating-point inaccuracies, a direct comparison like sub_obj > theta can be unreliable.
The subproblem’s objective might be trivially larger than the estimator due to numerical noise,
leading to the addition of unnecessary cuts.
To perform a robust comparison, BendersLib involves a parameter tol_obj_diff that defines
a tolerance level for the difference between sub_obj and theta.
This ensures that a cut is only added when the violation is significant, i.e., when the difference exceeds this tolerance
(sub_obj - theta > tol_obj_diff).
This approach is used within BendersLib’s own cut generators for Benders methods with multiple subproblems,
such as in LShapedOCGen, IntegerLShapedOCGen, and GeneLShapedOCGen,
to ensure that only meaningful optimality cuts are added to the master problem.
Determining Whether Two Cuts are Identical¶
Another numerical challenge is identifying duplicate cuts. During the Benders decomposition process, the same cut may be generated in different iterations. Adding duplicate cuts to the master problem is inefficient and can slow down the solver.
Due to floating-point arithmetic, the coefficients and right-hand side (RHS) values of two cuts that are mathematically identical might have small numerical differences. A simple direct comparison would fail to identify them as duplicates.
To address this, BendersLib uses the tol_cut_diff parameter.
When checking if a new cut is a duplicate of an existing one, the algorithm compares their coefficients
and RHS values within this tolerance. If all corresponding values are closer than tol_cut_diff,
the cuts are considered identical, and the new cut is discarded.
This logic is implemented in the __eq__ method of the Cut class.
To ensure consistency, the __hash__ method is also adapted. It discretizes the floating-point numbers
(coefficients and RHS) based on the tolerance before hashing. This guarantees that cuts considered equal
under the specified tolerance will also have the same hash value, allowing them to be managed correctly.
Handling Large Cutting Coefficients¶
In Benders decomposition, cut coefficients can sometimes become excessively large, leading to numerical instability. Mathematically equivalent cuts can lead to different convergence performances due to the limitations of finite-precision floating-point arithmetic. Cuts with large coefficients can make the master problem’s constraint matrix ill-conditioned, leading to slower convergence, inaccurate solutions, or even solver failure. For instance, consider two mathematically equivalent cuts
Solvers use tolerances to determine whether a solution satisfies a constraint. A constraint \(a^T x \ge b\) is considered satisfied if \(a^T x - b \ge -\epsilon\), where \(\epsilon\) is a small positive number (e.g., \(10^{-6}\)). For the normalized constraint \(x + y \ge 1\), if a solution results in \(x+y = 1 - 10^{-7}\), its violation is only \(10^{-7}\). This solution is very close to the feasible boundary and would be accepted by the solver’s tolerance. However, for the constraint with large coefficients, \(10^9 x + 10^9 y \ge 10^9\), the same solution yields \(10^9(x+y) = 10^9(1 - 10^{-7}) = 10^9 - 100\). The constraint violation is a massive \(100\). This far exceeds a solver’s standard tolerance, and the solution would be flagged as infeasible. This makes the solver struggle to find a feasible solution, leading to slow convergence or failure.
Normalizing the cut, even though it doesn’t change the feasible region, creates a better-conditioned problem that is more numerically stable for the solver to handle, often resulting in faster and more reliable convergence. Readers can refer to Cut Normalization for an example of how to normalize cuts using callbacks in BendersLib.