pybnb.convergence_checker

Convergence checking implementation.

Copyright by Gabriel A. Hackebeil (gabe.hackebeil@gmail.com).

pybnb.convergence_checker.compute_absolute_gap(sense, bound, objective)

Returns the absolute gap between the bound and the objective, respecting the sign relative to the objective sense of this problem.

pybnb.convergence_checker.compute_relative_gap(sense, bound, objective, scale=<function _default_scale>)

Returns the relative gap between the bound and the objective, respecting the sign relative to the objective sense of this problem.

class pybnb.convergence_checker.ConvergenceChecker(sense, absolute_gap=0, relative_gap=None, scale_function=<function _default_scale>, queue_tolerance=<class 'pybnb.convergence_checker._auto_queue_tolerance'>, branch_tolerance=0, comparison_tolerance=0, objective_stop=None, bound_stop=None)

A class used to check convergence.

Parameters

• sense ({minimize, maximize}) – The objective sense for the problem.

• absolute_gap (float, optional) – The absolute difference between the objective and bound that determines optimality. By default, this option also controls eligibility for the queue. See the “queue_tolerance” setting for more information. (default: 0)

• relative_gap (float, optional) – The relative difference between the objective and bound that determines optimality. (default: None)

• scale_function (function, optional) – A function with signature f(bound, objective) -> float that returns a positive scale factor used to convert the absolute difference between the bound and objective into a relative difference. The relative difference is compared with the relative_gap convergence tolerance to determine if the solver should terminate. The default is equivalent to max{1.0,|objective|}. Other examples one could use are max{|bound|,|objective|}, (|bound|+|objective|)/2, etc.

• queue_tolerance (float, optional) – The absolute tolerance used when deciding if a node is eligible to enter the queue. The difference between the node bound and the incumbent objective must be greater than this value. Leaving this argument at its default value indicates that this tolerance should be set equal to the “absolute_gap” setting. Setting this to zero means that nodes whose bound is equal to the incumbent objective are not eligible to enter the queue. Setting this to larger values can be used to limit the queue size, but it should be kept small enough to allow absolute and relative optimality tolerances to be met. This option can also be set to None to allow nodes with a bound equal to (but not greater than) the incumbent objective to enter the queue.

• branch_tolerance (float, optional) – The absolute tolerance used when deciding if the computed objective and bound for a node are sufficiently different to branch into the node. The default value of zero means that branching will occur if the bound is not exactly equal to the objective. This option can be set to None to enable branching for nodes with a bound and objective that are exactly equal. (default: 0)

• comparison_tolerance (float, optional) – The absolute tolerance used when deciding if two objective or bound values are sufficiently different to be considered improved or worsened. This tolerance controls when the solver considers a new incumbent objective to be found. It also controls when warnings are output about bounds becoming worse on child nodes. Setting this to larger values can be used to avoid the above solver actions due to insignificant numerical differences, but it is better to deal with these numerical issues by rounding numbers to a reliable precision before returning them from the problem methods. (default: 0)

• objective_stop (float, optional) – If provided, the “objective_limit” termination criteria is met when a feasible objective is found that is at least as good as the specified value. If this value is infinite, the termination criteria is met as soon as a finite objective is found. (default: None)

• bound_stop (float, optional) – If provided, the “objective_limit” termination criteria is met when the best bound on the objective is at least as good as the specified value. If this value is infinite, the termination criteria is met as soon as a finite objective is found. (default: None)

check_termination_criteria(global_bound, best_objective)

Checks if any termination criteria are met and returns the corresponding TerminationCondition enum value; otherwise, None is returned.

objective_is_optimal(objective, bound)

Determines if the objective is optimal by checking if the optimality gap is small enough relative to the absolute gap or relative gap settings.

compute_absolute_gap(bound, objective)

Returns the absolute gap between the bound and the objective, respecting the sign relative to the objective sense of this problem.

compute_relative_gap(bound, objective)

Returns the relative gap between the bound and the objective, respecting the sign relative to the objective sense of this problem.

eligible_for_queue(bound, objective)

Returns True when the queue object with the given bound is eligible for the queue relative to the given objective.

eligible_to_branch(bound, objective)

Returns True when the bound and objective are sufficiently far apart to allow branching.

bound_worsened(new, old)

Returns True when the new bound is worse than the old bound by greater than the comparison tolerance.

objective_improved(new, old)

Returns True when the new objective is better than the old objective by greater than the comparison tolerance.

worst_bound(*args, **kwds)

Returns the worst bound, as defined by the objective sense, from a given iterable of bound values. This function passes all keywords and arguments directly to the built-ins min and max.

best_bound(*args, **kwds)

Returns the best bound, as defined by the objective sense, from a given iterable of bound values. This function passes all keywords and arguments directly to the built-ins min and max.

worst_objective(*args, **kwds)

Returns the worst objective, as defined by the objective sense, from a given iterable of objective values. This function passes all keywords and arguments directly to the built-ins min and max.

best_objective(*args, **kwds)

Returns the best objective, as defined by the objective sense, from a given iterable of objective values. This function passes all keywords and arguments directly to the built-ins min and max.