UFL

Module summary

Implements basic functions for UFL – Uncapacitated Facility Location.

Tests coverage: UFLP_test

(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):

add_BDD_to_MIP(D[, model, x, prefix])	Builds a MIP (network flow) from a given BDD.
build_DP_DD(S, f, g)	Builds a BDD for the UFL problem (with x-variables only)
build_MIP(S, f, g)	Builds 'plain-vanilla' MIP instance for UFL.
build_Sf(S)	Returns the list of facility neighborhoods.
create_NF(D)	Generates a network flow instance for diagram D.
create_availability_BDD(S, f)	Encodes consistency of "cover"(z) decisions.
create_covering_BDD(S, c)	Create and return the diagram given the instance.
create_covering_BDD_wg(S, g)	Creates and returns "covering" BDD given an UFL instance.
draw_problem_dia(S, f, g[, filename])	Draws the bipartite graph describing the problem.
generate_dense_instance(n, m[, covering])	Generates a dense test facility location instance.
generate_test_figures()	Generates a simple test instance and creates PDFs.
generate_test_instance(n, m)	Generates a test facility location instance.
make_simple_problem()	Creates a 'toy' UFLP instance (for debugging).
show_BDD_build()	Runs a simple test against a toy problem.
show_BDD_to_MIP()	Tests making a MIP from a single BDD.
show_BDD_to_MIP_wg(S, f, g)	Runs a simple test against a toy problem.
show_build_MIP()	Tests a simple MIP building function.
solve_with_intBDD(S, f, g)	Solves the UFL instance by aligning two BDDs.
test_BDD_and_plain_MIPs([K, TOL, n, m])	Tests that objectives for the two MIPs coincide.
test_DD_creation(S, f, c, name)	Testing unit: BDD generation.
test_MIPs_protocol()	Runs a series of cross-checks.

❖❖❖

Implementation details

❖❖❖

Functions

UFL.add_BDD_to_MIP(D, model=None, x=None, prefix='')

Builds a MIP (network flow) from a given BDD.

Parameters

• D (class BDD) – the diagram object

• model (gurobipy Model) – a model to amend with vars and constraints(default None)

• x (dict) – linking binary variables, if available (default None)

• prefix (str) – a string prefix for variable names

Returns

resulting network flow c (list): list of constraints added v (dict): flow variables added, keyed as (from_id, to_id, arc_type) x (dict): binary variables added (one per layer), keyed by _layer_no_.

Return type

m (gurobipy Model)

UFL.build_DP_DD(S, f, g)

Builds a BDD for the UFL problem (with x-variables only)

Parameters

• S (list) – neighborhood list,

• f (dict) – location costs,

• g (dict) – overlap costs.

Returns

The resulting BDD.

Notes

• employs a DP approach with state being the number of overlaps

  for each customer.

UFL.build_MIP(S, f, g)

Builds ‘plain-vanilla’ MIP instance for UFL.

Encodes arbitrary penalty function g(·).

Parameters

• S (list) – list of customer neighborhoods

• f (dict) – facility costs

• g (dict) – values for overlap penalties, (j, n) for n overlaps at consumer j

Returns

gurobipy model (gp.Model)

UFL.build_Sf(S)

Returns the list of facility neighborhoods.

Parameters

S (list) – of consumer neighborhoods (facility IDs)

UFL.create_NF(D)

Generates a network flow instance for diagram D.

Parameters

D (class BDD) – the underlying diagram.

Returns

resulting model, constraints (list), v(dict): variables.

Return type

model (gurobipy model)

UFL.create_availability_BDD(S, f)

Encodes consistency of “cover”(z) decisions.

Either all “yes”, or all “no” for a specific facility.

Parameters

• S (list) – neighborhood list

• f (dict) – facility costs

UFL.create_covering_BDD(S, c)

Create and return the diagram given the instance.

Parameters

• S (list) – of adjacency lists. len(S) = no. of consumers

• c (dict) – costs of covering, keyed by (facility_id, consumer_id)

Notes

• encodes the fact that all customers need to be covered

  by at least one facility.

• assumes no edge costs, does not allow

  for arbitrary g(·) function.

UFL.create_covering_BDD_wg(S, g)

Creates and returns “covering” BDD given an UFL instance.

Parameters

• S (list) – of adjacency lists

• g (dict) – overlapping costs, g(k,n) is a cost of n overlaps for consumer k)

Returns

covering BDD

Return type

C (class BDD)

UFL.draw_problem_dia(S, f, g, filename='run_logs/problem_dia.gv')

Draws the bipartite graph describing the problem.

UFL.generate_dense_instance(n, m, covering=0.95)

Generates a dense test facility location instance.

In the sense that every customer can be covered by (almost) every facility.

Parameters

• n (int) – number of facilities

• m (int) – number of customers

• covering (float) – share of facilities covering each customer

Returns

A tuple of the following values.

• S (list): neighborhood list

• f (dict): costs of facility location (generated uniformly random int from f_min to f_max)

• g (dict): overlap costs, keys: (customer, overlap)

UFL.generate_test_figures()

Generates a simple test instance and creates PDFs.

UFL.generate_test_instance(n, m)

Generates a test facility location instance.

Parameters

• n (int) – number of facilities

• m (int) – number of customers

Returns

A tuple of the following values.

• S (list): neighborhood list

• f (dict): costs of facility location (generated uniformly random int from f_min to f_max)

• g (dict): overlap costs, keys: (customer, overlap)

UFL.make_simple_problem()

Creates a ‘toy’ UFLP instance (for debugging).

UFL.show_BDD_build()

Runs a simple test against a toy problem.

UFL.show_BDD_to_MIP()

Tests making a MIP from a single BDD.

UFL.show_BDD_to_MIP_wg(S, f, g)

Runs a simple test against a toy problem.

UFL.show_build_MIP()

Tests a simple MIP building function.

UFL.solve_with_intBDD(S, f, g)

Solves the UFL instance by aligning two BDDs.

Parameters

• S (list) – neighborhood list

• f (dict) – facility location costs

• g (dict) – overlap penalty dict.

Returns

Resulting model, constraints, and variables.

UFL.test_BDD_and_plain_MIPs(K=500, TOL=0.001, n=3, m=4)

Tests that objectives for the two MIPs coincide.

Parameters

• K (int) – number of instances to generate (default 500)

• TOL (float) – objective tolerance (for comparison) (default 1e-3)

• n (int) – number of facilities (default 3)

• m (type) – number of customers (default 4)

Returns

Nothing (outputs the success rate to the screen)

UFL.test_DD_creation(S, f, c, name)

Testing unit: BDD generation.

UFL.test_MIPs_protocol()

Runs a series of cross-checks.

Uses generate_test_instance().

Covers functions:

• build_MIP

• create_covering_BDD_wg

• create_availability_BDD

• add_BDD_to_MIP