Problem

class bnbpy.cython.problem.Problem

Bases: object

Abstraction for an optimization problem

IMPORTANT: Always remember to implement the methods:

• calc_bound

• is_feasible

• branch

Although not implemented using an abstract base class, due to Cython limitations, these methods are essential for the correct functioning of the branch-and-bound algorithm.

The method warmstart is optional, but it can be used to provide a warmstart solution.

Note that the Cython implementation uses static typing, so the solution attribute class must be a subclass of bnbpy.cython.solution.Solution.

branch()

Generates child nodes (problems) by branching.

Be careful not to modify attributes shared among nodes. It is also recommended to avoid performing expensive copy operations, by only modifying the attributes that differ between nodes.

Returns:

Sequence of child nodes problems generated by branching

Return type:

Sequence[Problem]

calc_bound()

Returns a lower bound of the (sub)problem. By default, the subproblems’ nodes are initialized with the same lower bounds as the parent problems’ nodes.

Returns:

Lower bound of the (sub)problem

Return type:

float

is_feasible()

Returns True if the problem in its complete form has a feasible solution.

It is called after a new node is selected for evaluation from the active queue, if its lower bound is better than the best solution found so far, and before branching.

Returns:

Feasibility check

Return type:

bool

warmstart()

Placeholder for warmstart implementation. If the problem has a warmstart function that returns a feasible problem state, it will be used at the begining of the search tree.

Be careful not to modify the current problem instance, but return a new one.

Returns:

Problem modified in a warmstart form, or None (in case not implemented)

Return type:

Optional[Problem]