experiments.softcover
Module summary
Generates and solves UFLP with ‘soft cover’ constraints.
Implements the UFLP model when all solutions are feasible, but there are overlap costs (which can be thought of as “soft” covering constraints).
(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):
|
Check that the instance is technically correct. |
|
Builds a BDD for the soft-UFL problem with overlaps. |
|
Prints random diagram sizes for different instance size. |
|
Dumps a graph implied by S into a .dot file. |
|
Generates adjacency lists S. |
Generates overlaps values (costs) f given adjacencies S. |
|
|
Creates a MIP model (for gurobi) from an instance specs. |
|
Generates a special type instance ('cavemen'). |
|
Generates an instance of n points and connectivity p. |
|
Helper: formats a node label out of the state. |
|
Generates a special-type instance ('organic molecule'). |
|
Generates a special-type instance ('string'). |
|
Makes a node key. |
Tries a specific, simple instance. |
|
|
Asserts naive MIP ~ BDD MIP. |
Tests the softcover DD construction procedure. |
|
Tests the softcover DD construction procedure. |
|
Tries a trivial instance. |
|
|
Solves a softcover inst with naive MIP and BDD MIP (both w/Gurobi). |
❖❖❖
Implementation details
❖❖❖
Functions
- experiments.softcover.assert_instance(S, f, c)[source]
Check that the instance is technically correct.
- experiments.softcover.build_soft_cover_DD(S, f, c, next_node_type='min')[source]
Builds a BDD for the soft-UFL problem with overlaps.
- Parameters
S (list) – neighborhood list,
f (list) – overlap costs, f[j][a], a=0,..,|S_j|
c (list) – location costs. next_node_type (str): min, max, or rnd – see DegreeKeeper docstring for details.
- Returns
The resulting BDD.
Notes
employs a DP approach with state being the Boolean covering at each customer.
- experiments.softcover.dia_sizes(n1=5, n2=10, K=5, igen=<function make_instance>)[source]
Prints random diagram sizes for different instance size.
- experiments.softcover.dump_instance(S, filename='tmp/S.dot')[source]
Dumps a graph implied by S into a .dot file.
- experiments.softcover.generate_S(n, p=0.25)[source]
Generates adjacency lists S.
- Parameters
n (int) – number of points,
p (float) – probability of an edge.
- Returns
list of lists.
- Return type
S
- experiments.softcover.generate_overlaps(S)[source]
Generates overlaps values (costs) f given adjacencies S.
- Parameters
S (list) – list of lists (adjacencies)
- Returns
list of lists, f[j][a], a=0,..,|S_j|
- Return type
f (list)
- experiments.softcover.make_MIP(S, c, f)[source]
Creates a MIP model (for gurobi) from an instance specs.
- Parameters
S (list) – list of adjacency lists,
c (list) – location costs per point,
f (list) – overlap cost function, f[j][a]
- Returns
gurobi model and vars
- Return type
(m, x, y)
- experiments.softcover.make_caveman_inst(n=10, M=5, pcave=0.8, verbose=True)[source]
Generates a special type instance (‘cavemen’).
- experiments.softcover.make_instance(n, p=0.25, verbose=True)[source]
Generates an instance of n points and connectivity p.
- experiments.softcover.make_label(state, pts)[source]
Helper: formats a node label out of the state.
- experiments.softcover.make_organic_inst(n, verbose=True)[source]
Generates a special-type instance (‘organic molecule’).
Note: n here is length of the “main” line.
- experiments.softcover.make_string_inst(n, verbose=True)[source]
Generates a special-type instance (‘string’).
- experiments.softcover.mknode(state, freedoms)[source]
Makes a node key.
- Parameters
state (list) – no. of overlaps per point,
freedoms (DegreeKeeper) – no. of point (residual) degrees.
- Returns
String label.
- experiments.softcover.test_build_soft_cover_DD_simple1()[source]
Tests the softcover DD construction procedure.