UFLP_fullDD

Module summary

Solves UFLP using a DD-based approach.

The core function, create_cover_DD(), implements the BDD-building procedure to encode a j-UFLP sub-instance (i.e., a UFLP problem with overlap costs).

Related: a good order of variables is found with UFLPOrder module.

(In the implementation details below, click on class/function names for additional documentation and links to the source code.)

❖❖❖

Implements functions (outside the classes above):

`calc_cost`(pts_list, state, prev_state, ...)	Helper: calculates the added cost during the BDD creation.
`create_cover_DD`(S, f, c, node_order)	Generates a BDD for an UFLP with cavemen structure.
`make_label`(state)	Helper: formats a node label according to the `state`.
`run_fullDD_simple`()	Creates a diagram for a simple UFLP instance.
`test_cost_calc`()	Tests `UFLP_fullDD.calc_cost()` function.
`test_full_DD`(inst)	Tests the full-DD-based approach against a MiP.

❖❖❖

Implementation details

❖❖❖

Functions

UFLP_fullDD.calc_cost(pts_list, state, prev_state, last_decision, S, f, c)[source]

Helper: calculates the added cost during the BDD creation.

Parameters

S – UFLP instance parameters,
f – UFLP instance parameters,
c – UFLP instance parameters,
pts_list (list) – points to generate cost for,
state – the new state
last_decision (tuple) – a var (int) - value(int) pair.

Returns

Added cost according to the state.

UFLP_fullDD.create_cover_DD(S, f, c, node_order)[source]

Generates a BDD for an UFLP with cavemen structure.

Parameters

S – instance params (see darkcloud.gen_caveman_inst()),
f – instance params (see darkcloud.gen_caveman_inst()),
c – instance params (see darkcloud.gen_caveman_inst()),
node_order (list[int]) – order of nodes to add.

Returns

resulting diagram

Return type

B (class BDD)

Note

Implements ‘forgetting’ nodes along the way.

UFLP_fullDD.make_label(state)[source]: Helper: formats a node label according to the state.

UFLP_fullDD.run_fullDD_simple()[source]: Creates a diagram for a simple UFLP instance.

UFLP_fullDD.test_cost_calc()[source]: Tests UFLP_fullDD.calc_cost() function.

UFLP_fullDD.test_full_DD(inst)[source]: Tests the full-DD-based approach against a MiP.