Source code for benderslib.utils

# coding:utf-8
# SPDX-License-Identifier: Apache-2.0
# Copyright (c) 2021-2026 Peng-Hui Guo <[email protected]>

import math




def draw_curve(result: 'BendersResult') -> None:
    """Draw the convergence curve of the Benders algorithm.

    This function plots the lower bound, upper bound, incumbent
    objective value, and gap over iterations. See this
    :doc:`example <../examples/basic/annotated_benders>` for
    a figure generated by this function.

    Parameters
    ----------

    result : BendersResult
        The result object containing the convergence history of the
        Benders algorithm, including lists of lower bounds (``lb_list``),
        upper bounds (``ub_list``), and incumbent objective values (``obj_list``)
        at each iteration.

    Example
    ----------

    .. code-block:: python

        from benderslib.utils import draw_curve

        BD = ClassicalBenders(mp, sp, complicating_vars)
        BD.solve()

        draw_curve(BD.result)
    """

    try:
        import matplotlib.pyplot as plt
    except ImportError:  # pragma: no cover
        raise ImportError("matplotlib is not installed. Please install it with: pip install benderslib[plot]")

    plt.style.use('seaborn-v0_8')

    # Draw convergence curve
    fig, ax1 = plt.subplots(dpi=600)

    ax1.plot(result.lb_list, label='Lower Bound')
    ax1.plot(result.ub_list, label='Upper Bound')
    ax1.plot(result.obj_list, label='Incumbent')
    ax1.set_xlabel('Iteration')
    ax1.set_ylabel('Objective')
    ax1.set_title('Benders Decomposition')
    ax1.grid(True)

    # Draw Gap on the right axis
    ax2 = ax1.twinx()
    gap = [
        (obj - lb) / abs(obj) if abs(obj) > 1e-4 else float('inf')
        for lb, obj in zip(result.lb_list, result.obj_list)
    ]
    ax2.plot(gap, 'k--', label='Gap')
    ax2.set_ylabel('Gap')
    ax2.tick_params(axis='y')
    ax2.set_ylim(0, 1)
    ax2.grid(None)

    # To show the legend for the second axis
    lines, labels = ax1.get_legend_handles_labels()
    lines2, labels2 = ax2.get_legend_handles_labels()
    ax2.legend(lines + lines2, labels + labels2, loc='best')

    plt.tight_layout()
    plt.show()
    plt.close(fig)





def is_all_integer(vals: list[float], tol=1e-5) -> bool:
    """Check if all values in a list are integers within a specified tolerance.

    Sometimes solvers may return values that are very close to integers but
    not exactly integers due to numerical issues. This function checks if
    each value in the list is within a specified tolerance of an integer,
    to determine if the solution can be considered as integer feasible.

    Parameters
    ----------

    vals : list of float
        The list of values to check.
    tol : float, optional
        The tolerance for checking if a value is close enough to an integer.

    Example
    ----------

    .. code-block:: python

        from benderslib.utils import is_all_integer

        vals = [1.0, 2.00001, 3.99999]

        print(is_all_integer(vals))
    """
    for v in vals:
        if abs(v - round(v)) > tol:
            return False
    return True





def normalize_cut(cut: 'Cut', max_norm: float = 1e5) -> 'Cut':
    """
    Normalize a Benders cut if its L2 norm exceeds a threshold.

    This function scales down the cut's coefficients and right-hand side
    if the L2 norm of the coefficient vector is greater than ``max_norm``.
    This can help improve numerical stability in the master problem solver.

    Parameters
    ----------

    cut : Cut
        The Benders cut to normalize.
    max_norm : float, optional
        The maximum allowed L2 norm for the cut's coefficients.

    Example
    ----------

    .. code-block:: python

        from benderslib.utils import normalize_cut

        cut = Cut(
            vars=['x1', 'x2', 'x3'],
            coefs=[2.0e5, 1.0e5, 4.5e6],
            rhs=1e6,
            sense=CST.LE
        )

        norm_cut = normalize_cut(cut, max_norm=1e5)
    """
    # L2 norm
    norm = math.sqrt(sum(c * c for c in cut.coefs))

    if norm > max_norm:
        scale = max_norm / norm

        cut.coefs = [c * scale for c in cut.coefs]
        cut.rhs *= scale

    return cut