darkcloud

Module summary

Contains the j-UFLP instance generation code (along with some legacy experiments).

Implements the ‘cloud’ algorithm that builds a BDD for a UFLP (using separate MIPs) over a relaxed cavemen graph. Generates the ‘points-cluster’ sturcutred instances.

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

❖❖❖

Implements classes:

DDSolver(S, f, c, caves)

Implements a DD-based solver for the j-UFLP over 'cavemen'-instances.

DDTypedSolver(S, f, c, caves, k, kbar)

ptscloud(e1, e2, S)

Keeps current 'cloud' of points (modeling a 'cave').

Implements functions (outside the classes above):

compare_BDD_vs_MIP(S, f, c, caves)

dump_instance(S[, filename])

Dumps a graph implied by S into a .dot file.

gen_caveman_inst([n, M, L, verbose])

Generates an instance with the related metadata (info on caves).

gen_simple_cavemen_inst0()

Generates a simple instance with metadata.

gen_simple_cavemen_inst1()

Generates (another) simple instance with metadata.

gen_typed_cavemen_inst(n, M, L, K, kb_max)

Generates an instance with types.

main()

Main experiment: runtimes DD vs MIP.

prepare_inst([filename])

prepare_inst_gallery()

save_typed_instance(S, caves, k, kbar[, ...])

Draws a dot for the given instance.

solve_typed_with_MIP(S, f, c, k, kbar)

Creates a MIP model (for gurobi) from an instance specs.

solve_with_MIP(S, f, c)

Creates a MIP model (for gurobi) from an instance specs.

test_BDD_vs_MIP_random(_)

test_BDD_vs_MIP_simple(_)

Tests BDD vs MIP over a single topology (random costs).

test_DD_full(_)

Tests the DD-based approach against a MiP.

test_inst_gen(_)

Tests that instance generator works correctly.

❖❖❖

Implementation details

❖❖❖

DDSolver

class darkcloud.DDSolver(S, f, c, caves)[source]

Implements a DD-based solver for the j-UFLP over ‘cavemen’-instances.

Public Methods:

__init__(S, f, c, caves)

build_cover_DD()

Builds a cover/overlap DD for the instance.

Private Methods:

_add_interim_point(x, current_state, ...[, ...])

Adds variable after the current layer.

_calc_cave(cave, fixed_nodes[, verbose])

Calculates part of the objective due to the given cave.
_add_interim_point(x, current_state, new_state, current_layer, add_costs=None)[source]

Adds variable after the current layer.

_calc_cave(cave, fixed_nodes, verbose=False)[source]

Calculates part of the objective due to the given cave.

build_cover_DD()[source]

Builds a cover/overlap DD for the instance.

❖❖❖

DDTypedSolver

class darkcloud.DDTypedSolver(S, f, c, caves, k, kbar)[source]

Public Methods:

__init__(S, f, c, caves, k, kbar)

build_type_DD()

Builds a BDD encoding location-level constraints.

solve_with_DDs()

Solves the problem using the DD-based approach.

solve_with_DDs_noVS([TtoC])

Solves the problem using the DD-based approach.
Inherited from DDSolver

__init__(S, f, c, caves, k, kbar)

build_cover_DD()

Builds a cover/overlap DD for the instance.

Private Methods:

Inherited from DDSolver

_add_interim_point(x, current_state, ...[, ...])

Adds variable after the current layer.

_calc_cave(cave, fixed_nodes[, verbose])

Calculates part of the objective due to the given cave.
build_type_DD()[source]

Builds a BDD encoding location-level constraints.

Deals with no. locations per type and location costs.

Parameters

  • f (dict) – location costs,

  • types (dict) – type codes per facility

  • k_bar (np.array) – max. number of locations per type.

  • preferred_order (list) – order of nodes to align to, as possible (e.g., of the already built cover DD)

Returns

resulting diagram. nl (dict): string node labels (“states”), id -> label (string).

Implementation based on tUFLP.build_type_DD().

FIXME: revise this doc

Return type

D (class BDD)

solve_with_DDs()[source]

Solves the problem using the DD-based approach.

solve_with_DDs_noVS(TtoC=True)[source]

Solves the problem using the DD-based approach.

❖❖❖

ptscloud

class darkcloud.ptscloud(e1: tuple[int], e2: tuple[int], S: list[int])[source]

Keeps current ‘cloud’ of points (modeling a ‘cave’).

e1, e2

the 4 endpoints of the 2 edges emanating from the cave,

Type

tuple

S

a list of points within the cave.

Type

list[int]

Public Methods:

__init__(e1, e2, S)

__repr__()

Return repr(self).

__eq__(other)

Return self==value.
S: list[int]
e1: tuple[int]
e2: tuple[int]

❖❖❖

Functions

darkcloud.compare_BDD_vs_MIP(S, f, c, caves)[source]
darkcloud.dump_instance(S, filename='tmp/S.dot')[source]

Dumps a graph implied by S into a .dot file.

darkcloud.gen_caveman_inst(n=10, M=5, L=0.5, verbose=False)[source]

Generates an instance with the related metadata (info on caves).

Parameters

  • n (int) – number of caves,

  • M (int) – number of points in a cave,

  • L (float) – edge sparsity parameter (share of missing edges)

  • verbose (Bool) – print debug info

Returns

instance (S,f,c) and caves description.

Return type

S, f, c, caves

Note

The parameter L is assumed to be:

\[L = 1 - 2\frac{\textrm{Number of existing arcs}}{N(N-1)}\]

(See, e.g., Sefair and Smith 2016 on DSPI for a similar approach.)

darkcloud.gen_simple_cavemen_inst0()[source]

Generates a simple instance with metadata.

Returns

S, f, c, caves

darkcloud.gen_simple_cavemen_inst1()[source]

Generates (another) simple instance with metadata.

Returns

S, f, c, caves

darkcloud.gen_typed_cavemen_inst(n, M, L, K, kb_max)[source]

Generates an instance with types.

First parameters are that of gen_caveman_inst(). The other ones are K, number of types, and kb_max – max type budget.

Relies on darkcloud.gen_caveman_inst() for graph generation.

Returns

S (adjacencies), f (overlap costs), c (location costs), caves (list of ptscloud), k (point types), kbar (type budgets)

darkcloud.main()[source]

Main experiment: runtimes DD vs MIP.

darkcloud.prepare_inst(filename='tmp/instance.gv')[source]
darkcloud.save_typed_instance(S, caves, k, kbar, more_info='', filename='tmp/inst.dot')[source]

Draws a dot for the given instance.

darkcloud.solve_typed_with_MIP(S, f, c, k, kbar)[source]

Creates a MIP model (for gurobi) from an instance specs.

(Typed version.)

Parameters

  • S (list) – list of adjacency lists,

  • f (list) – overlap cost function, f[j][a],

  • c (list) – location costs per point.

  • k (dict) – point types,

  • kbar (list) – budget types.

Returns

model, objective value, x, and y

darkcloud.solve_with_MIP(S, f, c)[source]

Creates a MIP model (for gurobi) from an instance specs.

Parameters

  • S (list) – list of adjacency lists,

  • f (list) – overlap cost function, f[j][a],

  • c (list) – location costs per point.

Returns

model, objective, x, y

darkcloud.test_BDD_vs_MIP_random(_)[source]
darkcloud.test_BDD_vs_MIP_simple(_)[source]

Tests BDD vs MIP over a single topology (random costs).

darkcloud.test_DD_full(_)[source]

Tests the DD-based approach against a MiP.

darkcloud.test_inst_gen(_)[source]

Tests that instance generator works correctly.