jUFLP_cavemen

Module summary

Proof-of-concept experiment: joint UFLP over special class of instances.

Implements DD-based solution procedures for j-UFLP instances, along with the instance generation. Note that the up-to-date experiment corresponding to Section 4.2 of the paper is presented in UFLP_2_cav, but it calls solution procedures implemented in this module.

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

❖❖❖

Implements classes:

jUFLPEncoder(*[, skipkeys, ensure_ascii, ...])

A technical implementation needed to save an instance as .json

Implements functions (outside the classes above):

compare_runtimes()

Performs a quick runtimes comparison (toA vs VS).

dump_instance(S, caves[, filename])

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

gen_cavemen_jUFLP_inst([n, M, L, verbose, ...])

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

load_inst(filename)

Loads a jUFLP instance from .json file.

main()

save_inst(i1, i2, join_map, filename)

Saves the jUFLP instance to .json file.

show_inst(inst1, inst2, join_map[, filename])

Shows the supplied j-UFLP instance / saves it to a .dot file.

solve_cm_jUFLP_CPPMIP(i1, i2, jmap)

Solves a jUFLP on cavemen with CPPMIP.

solve_cm_jUFLP_CPPMIP_fullDDs(i1, i2, jmap)

Solves a jUFLP on cavemen (full-DDs) with CPPMIP.

solve_cm_jUFLP_DDs(i1, i2, jmap[, intmode, ...])

Solves the jUFLP cavemen instance with DDs.

solve_cm_jUFLP_MIP(i1, i2, jmap)

Solves the special jUFLP instance with MIP.

solve_cm_jUFLP_fullDDs(i1, i2, jmap, intmode)

Solves the jUFLP cavemen instance with DDs.

solve_with_DDs(S, S2, f, f2, c, caves[, intmode])

Solves the jUFLP cavemen instance with DDs.

solve_with_MIP(S, S2, f, f2, c, caves)

Generates and solves a MIP for the supplied jUFL cavemen instance.

test_cm_jUFL_DDvsMIP(test_inst)

test_jUFL_DDs(test_inst)

test_load_save(test_inst)

❖❖❖

Implementation details

❖❖❖

jUFLPEncoder

class jUFLP_cavemen.jUFLPEncoder(*, skipkeys=False, ensure_ascii=True, check_circular=True, allow_nan=True, sort_keys=False, indent=None, separators=None, default=None)[source]

A technical implementation needed to save an instance as .json

Public Data Attributes:

Inherited from JSONEncoder

item_separator

key_separator

Public Methods:

default(obj)

Implement this method in a subclass such that it returns a serializable object for o, or calls the base implementation (to raise a TypeError).
Inherited from JSONEncoder

__init__(*[, skipkeys, ensure_ascii, ...])

Constructor for JSONEncoder, with sensible defaults.

default(obj)

Implement this method in a subclass such that it returns a serializable object for o, or calls the base implementation (to raise a TypeError).

encode(o)

Return a JSON string representation of a Python data structure.

iterencode(o[, _one_shot])

Encode the given object and yield each string representation as available.
default(obj)[source]

Implement this method in a subclass such that it returns a serializable object for o, or calls the base implementation (to raise a TypeError).

For example, to support arbitrary iterators, you could implement default like this:

def default(self, o):
    try:
        iterable = iter(o)
    except TypeError:
        pass
    else:
        return list(iterable)
    # Let the base class default method raise the TypeError
    return JSONEncoder.default(self, o)

❖❖❖

Functions

jUFLP_cavemen.compare_runtimes()[source]

Performs a quick runtimes comparison (toA vs VS).

jUFLP_cavemen.dump_instance(S, caves, filename='tmp/S.dot')[source]

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

jUFLP_cavemen.gen_cavemen_jUFLP_inst(n=10, M=7, L=0.25, verbose=False, linking='default')[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

  • linking (str) – linking constraints type

Returns

sub-instances and caves description.

Return type

inst1, inst2, join_map

Note

Each sub-instance is parameterized by [S,f,c,caves]. (See darkcloud.gen_caveman_inst() for details.)

jUFLP_cavemen.load_inst(filename)[source]

Loads a jUFLP instance from .json file.

Returns

[[S,f,c,ptsclouds], [S2,f2,c2,pltsclouds2], jmap]

jUFLP_cavemen.main()[source]
jUFLP_cavemen.save_inst(i1, i2, join_map, filename)[source]

Saves the jUFLP instance to .json file. (old instance format).

jUFLP_cavemen.show_inst(inst1, inst2, join_map, filename='./tmp/jUFLP.dot')[source]

Shows the supplied j-UFLP instance / saves it to a .dot file.

Parameters

  • inst1 (list) – instances description, [S,f,c,caves]

  • inst2 (list) – instances description, [S,f,c,caves]

  • filename (str) – filename to save to (default “./tmp/jUFLP.dot”)

jUFLP_cavemen.solve_cm_jUFLP_CPPMIP(i1, i2, jmap)[source]

Solves a jUFLP on cavemen with CPPMIP.

Parameters

  • i1 (list) – instances

  • i2 (list) – instances

  • jmap (dict) – joining dict.

Notes

Instance is parameterized as per darkcloud.gen_caveman_inst(), The diagrams are built with darkcloud.DDSolver.

Returns

objective (float)

jUFLP_cavemen.solve_cm_jUFLP_CPPMIP_fullDDs(i1, i2, jmap)[source]

Solves a jUFLP on cavemen (full-DDs) with CPPMIP.

Parameters

  • i1 (list) – instances

  • i2 (list) – instances

  • jmap (dict) – joining dict.

Notes

Instance is parameterized as per darkcloud.gen_caveman_inst(), The diagrams are built with UFLP_fullDD.create_cover_DD().

Returns

objective (float)

jUFLP_cavemen.solve_cm_jUFLP_DDs(i1, i2, jmap, intmode='toA', ret_int=False)[source]

Solves the jUFLP cavemen instance with DDs.

Parameters

  • i1 (list) – instances

  • i2 (list) – instances

  • intmode (str) – alignment mode, ‘toA’, ‘toB’, or ‘VS’

Notes

Instance is parameterized as per darkcloud.gen_caveman_inst(), The diagrams are built with darkcloud.DDSolver.

jUFLP_cavemen.solve_cm_jUFLP_MIP(i1, i2, jmap)[source]

Solves the special jUFLP instance with MIP.

jUFLP_cavemen.solve_cm_jUFLP_fullDDs(i1, i2, jmap, intmode, ret_int=False)[source]

Solves the jUFLP cavemen instance with DDs.

Parameters

  • i1 (list) – instances

  • i2 (list) – instances

Notes

Instance is parameterized as per darkcloud.gen_caveman_inst().

jUFLP_cavemen.solve_with_DDs(S, S2, f, f2, c, caves, intmode='toA')[source]

Solves the jUFLP cavemen instance with DDs.

Parameters

intmode (str) – intersection mode, ‘toA’ or ‘VS’

Notes

Instance is parameterized as per darkcloud.gen_caveman_inst(), The diagrams are built with darkcloud.DDSolver.

jUFLP_cavemen.solve_with_MIP(S, S2, f, f2, c, caves)[source]

Generates and solves a MIP for the supplied jUFL cavemen instance.

Note

The instance is parameterized as per darkcloud.gen_caveman_inst(). Most of the code is adapted form darkcloud.solve_with_MIP().

jUFLP_cavemen.test_cm_jUFL_DDvsMIP(test_inst)[source]
jUFLP_cavemen.test_jUFL_DDs(test_inst)[source]
jUFLP_cavemen.test_load_save(test_inst)[source]