Column Generation

class bnbpy.colgen.PriceSol(red_cost, new_col)[source]

Bases: object

Returns the solutions of the pricing problem (which includes a new column). Is is NOT recommended to modify these instance after creation due to safe hashing.

Parameters:

red_cost (float)
new_col (Any)

red_cost: float

new_col: Any

class bnbpy.colgen.MasterSol(cost, duals)[source]

Bases: object

Returns the solutions of the master problem (which includes dual information). Is is NOT recommended to modify these instance after creation due to safe hashing.

Parameters:

cost (float)
duals (Any)

cost: float

duals: Any

class bnbpy.colgen.Pricing(price_tol=0.01)[source]

Bases: ABC

Abstraction for pricing problem

Parameters:: price_tol (float)

price_tol: float: Tolerance for including new columns into master problem

solutions: Set[PriceSol]: Solutions to price problems already returned

abstractmethod set_weights(c)[source]

Modifies problem by incorporating new weights

Parameters:: c (Any) – New weights (depend on problem structure)
Return type:: None

abstractmethod solve()[source]

Solves pricing problem and returns PriceSol instance

Returns:: Instance with reduced cost and new column
Return type:: PriceSol

evaluate()[source]

Solves pricing problem and evaluates quality of solution by reduced cost and repeated solutions. Only returns columns not yet generated.

Return type:: PriceSol | None

copy(deep=False)[source]

Parameters:: deep (bool)
Return type:: Pricing

class bnbpy.colgen.Master[source]

Bases: ABC

Abstraction of master problem Must overwrite methods add_col and solve

abstractmethod add_col(c)[source]

Includes new column into master problem and returns True if it is valid to continue pricing

Parameters:: c (Any) – New column
Returns:: Either or not to proceed
Return type:: bool

abstractmethod solve()[source]

Solves master problem and returns an instance of MasterSol

Returns:: Solution with cost and duals
Return type:: MasterSol

copy(deep=False)[source]

Parameters:: deep (bool)
Return type:: Master

class bnbpy.colgen.ColumnGenProblem(master, pricing, max_iter_price=None)[source]

Bases: Problem

Abstraction of optimization problem solved using column generation

Parameters:

master (Master)
pricing (Pricing)
max_iter_price (int | None)

master: Master

pricing: Pricing

cleanup()[source]

Return type:: None

calc_bound()[source]

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

copy(deep=False)[source]

Parameters:: deep (bool)
Return type:: ColumnGenProblem