kep_solver.model module

class Sense(value)

Bases: Enum

An enumeration of the sense of an objective.

MAX = 1
MIN = 2
EXACT = 3
toConstraint()

Converts a Sense into a constraint type suitable for use with PuLP

Returns:

constraint sense

toObjective()

Converts a Sense into an objective type suitable for use with PuLP

Returns:

objective sense

class Objective

Bases: object

A base class for an objective.

need_alt_embed: bool = False

Does this particular objective need alternate and embedded cycles built.

is_integral: bool = True

Does this objective always return an integer value.

__init__()
edgeValue(graph, edge, position=None)

What value should the given transplant in the given graph be given, if it is at the given position (i.e., position = 1 means this is the first edge in a chain)?

Parameters:

  • graph (CompatibilityGraph) – The graph containing the exchange

  • edge (Edge) – The edge, representing a transplant

  • position (Optional[int]) – The position of this edge in an exchange

Return type:

float

Returns:

The value of this edge in this position

value(graph, exchange)

What value should the given exchange in the given graph be given?

Parameters:
Return type:

float

describe()

Describes what this objective optimises.

Return type:

str

Returns:

the description

property sense: Sense

The sense of the objective.

class TransplantCount

Bases: Objective

An objective to maximise the number of transplants. Note that for a chain, the donation to the non-directed donor (which often would go to a deceased-donor waiting list) is counted as a transplant.

__init__()
edgeValue(graph, edge, position=None)

What value should the given transplant in the given graph be given, if it is at the given position (i.e., position = 1 means this is the first edge in a chain)?

Parameters:

  • graph (CompatibilityGraph) – The graph containing the exchange

  • edge (Edge) – The edge, representing a transplant

  • position (Optional[int]) – The position of this edge in an exchange

Return type:

float

Returns:

The value of this edge in this position

value(graph, exchange)

How many transplants does the given exchange represent.

Parameters:
Return type:

float

Returns:

the number of transplants

describe()

Describes what this objective optimises.

Return type:

str

Returns:

the description

property sense: Sense

This is a maximisation objective.

class EffectiveTwoWay

Bases: Objective

An objective to maximise the number of effective two-way transplants. For cycles, they must either have size two, or have a back-arc. All chains count as effective two-way exchanges. This is binary for each exchange. That is, either an exchange has or does not have an effective two-way exchange.

need_alt_embed: bool = True

Does this particular objective need alternate and embedded cycles built.

__init__()
value(graph, exchange)

Does the given exchange contain an effective two-way exchange?

Parameters:
Return type:

float

Returns:

1 if and only if it is effectively two-way

describe()

Describes what this objective optimises.

Return type:

str

Returns:

the description

property sense: Sense

This is a maximisation objective.

class BackArcs

Bases: Objective

An objective to maximise the number of back-arcs. Note that arcs back to a non-directed donor are not considered backarcs in this objective.

need_alt_embed: bool = True

Does this particular objective need alternate and embedded cycles built.

__init__()
value(graph, exchange)

How many backarcs does the given exchange contain?

Parameters:
Return type:

float

Returns:

The number of backarcs in the exchange

describe()

Describes what this objective optimises.

Return type:

str

Returns:

the description

property sense: Sense

This is a maximisation objective.

UK_age_score(d1, d2)

Calculate and return the age difference bonus and tiebreaker value for a given transplant where d1 is a Donor donating to the paired recipient of Donor d2. The age difference bonus is 3, if the ages of the two donors differ by at most 20, and the tie breaker is given by the equation

(70 - age_difference)^2 * 1e-5

Note that as a recipient may have multiple donors, this value is dependant not only on a Transplant in an Exchange, but also which Transplant will occur next. If d1 is a non-directed Donor, both the age difference bonus and the tiebreaker will be 0.

Parameters:

  • d1 (Donor) – The Donor donating to the paired recipient of d2

  • d2 (Donor) – A paired donor of d1

Return type:

tuple[float, float]

Returns:

A tuple containing the age difference bonus, and the tiebreaker value.

class UKScore

Bases: Objective

An objective to maximise the number of back-arcs.

is_integral: bool = False

Does this objective always return an integer value.

__init__()
value(graph, exchange)

What is the UK score of this exchange?

Parameters:
Return type:

float

Returns:

The UK score of this exchange

describe()

Describes what this objective optimises.

Return type:

str

Returns:

the description

property sense: Sense

This is a maximisation objective.

class ThreeWay

Bases: Objective

An objective to minimise the number of three-way exchanges. If no larger exchanges are allowed, this has the effect of increasing the number of two-way exchanges.

__init__()
value(graph, exchange)

Is the given exchange a three-way exchange.

Parameters:
Return type:

float

Returns:

1 if and only if it is a three-way exchange

describe()

Describes what this objective optimises.

Return type:

str

Returns:

the description

property sense: Sense

This is a minimisation objective.

class Model(instance, objectives, *, maxCycleLength, maxChainLength, build_alt_embed=0)

Bases: LpProblem

A base class for all models for KEPs. Any new models should inherit from this and implement all associated functions.

supports_full_details: bool = True

Does this model support describing all possible cycles and chains.

__init__(instance, objectives, *, maxCycleLength, maxChainLength, build_alt_embed=0)

Create a Model. Note that this base class has no implementation and should not be directly constructed.

Parameters:

  • instance (Instance) – The instance to build the model from

  • objectives (list[Objective]) – The list of objectives for this pool

  • maxCycleLength (int) – The maximum length of a cycle

  • maxChainLength (int) – The maximum length of a chain

  • build_alt_embed (int) –

    Whether to build alternate and embedded exchanges. build_alt_embed can be set to any of the following:

    1. Don’t build alternate and embedded cycles. Faster, if you don’t need alternate and embedded cycles

    2. Build all alternate and embedded cycles.

    3. Build only those alternate and embedded cycles that NHSBT expects

    4. Build only those alternate and embedded cycles that NHSBT expects, where embedded exchanges cannot use new donors

property cycles: ValuesView[Exchange]

Return the list of cycles in this model.

Returns:

the list of cycles

property chains: ValuesView[Exchange]

Return the list of chains in this model.

Returns:

the list of chains

property exchanges: list[Exchange]

Return the list of cycles and chains in this model.

Returns:

the list of cycles and chains

exchange_values(exchange)

Given an exchange, return the value of the exchange for each objective.

Parameters:

exchange (Exchange) – The exchange whose value is to be returned

Return type:

list[float]

Returns:

the list of values of this exchange

property graph: CompatibilityGraph

Return the graph for this model.

Returns:

the graph

addObjectiveConstraint(objective, value, index)

Add a constraint that ensures the previous objective keeps its value.

Parameters:

  • objective (Objective) – The previous objective

  • value (float) – The value the previous objective attained

  • index (int) – Which number objective is this (only used for naming the constraint)

solve(countSolutions=False, maxCount=None, solvingOptions=SolvingOptions(solver=<pulp.apis.coin_api.PULP_CBC_CMD object>, useRCVF=False))

Solve the model to find an optimal solution.

Parameters:

  • countSolutions (bool) – If true, count the number of distinct solutions found at each level of optimisation. Note that this solves a new optimisation problem for each such solution found, and thus can be very time-consuming.

  • maxCount (Optional[list[int]]) – If given, is a list of integers such that the counting of distinct solutions at the x’th objective should stop after counting maxCount[x] solutions.

  • solvingOptions (SolvingOptions) – A SolvingOptions object that contains information on how to solve single KEP instances.

Return type:

tuple[list[Exchange], SolvingStatistics, list[int]]

Returns:

A list of selected transplants, a list of the time taken to solve for each objective in the pool, and a list of the number of optimal solutions found for each objective

class PICEF(instance, objectives, *, maxCycleLength, maxChainLength, build_alt_embed=0)

Bases: Model

A model that represents each cycle by a variable, but otherwise represents edges in chains as a variable.

supports_full_details: bool = False

Does this model support describing all possible cycles and chains.

__init__(instance, objectives, *, maxCycleLength, maxChainLength, build_alt_embed=0)

Construct a PICEF model from an instance.

Parameters:

  • instance (Instance) – The instance to build the model from

  • objectives (list[Objective]) – The list of objectives for this pool

  • maxCycleLength (int) – The maximum length of a cycle

  • maxChainLength (int) – The maximum length of a chain

  • build_alt_embed (int) – Determines which alternative and embedded exchanges should be enumerated. For PICEF, this must be set to zero.

property cycles: ValuesView[Exchange]

Return the list of cycles in this model.

Returns:

the list of cycles

property chains: ValuesView[Exchange]

Return the list of chains in this model.

Returns:

the list of chains

property exchanges: list[Exchange]

Return the list of cycles and chains in this model.

Returns:

the list of cycles and chains

exchange_values(exchange)

Given an exchange, return the value of the exchange for each objective.

Parameters:

exchange (Exchange) – The exchange whose value is to be returned

Return type:

list[float]

Returns:

the list of values of this exchange

build_model()

Build the model. That is, create all the variables and constraints.

Return type:

None

addObjectiveConstraint(objective, value, index)

Adds a constraint that ensures the previous objective keeps its value.

Parameters:

  • objective (Objective) – The previous objective

  • value (float) – The value the previous objective attained

  • index (int) – Which number objective is this (only used for naming the constraint)

countSolutions(maxCount=None)

Count the number of distinct solutions available for this instance at this objective.

Note that this can drastically increase the running time (by several orders of magnitude) as for each distinct solution we need to solve a new IP model.

Return type:

int

solve(countSolutions=False, maxCount=None, solvingOptions=SolvingOptions(solver=<pulp.apis.coin_api.PULP_CBC_CMD object>, useRCVF=False))

Solve the model to find an optimal solution.

Parameters:

  • countSolutions (bool) – If true, count the number of distinct solutions found at each level of optimisation. Note that this solves a new optimisation problem for each such solution found, and thus can be very time-consuming.

  • maxCount (Optional[list[int]]) – If given, is a list of integers such that the counting of distinct solutions at the x’th objective should stop after counting maxCount[x] solutions.

  • solvingOptions (SolvingOptions) – A SolvingOptions object that contains information on how to solve single KEP instances.

Return type:

tuple[list[Exchange], SolvingStatistics, list[int]]

Returns:

A list of selected transplants, a list of the time taken to solve for each objective in the pool, and a list of the number of optimal solutions found for each objective

property objective_values: list[float]

The list of all objective values.

objective_value(objective_index)

Return the value of an objective, if it has been solved. If this model has not been solved, accessing this raises an error.

Parameters:

objective_index (int) – the index of the objective whose value is to be returned

Return type:

float

Returns:

the value of the objective as given by objective_index

class CycleAndChainModel(instance, objectives, *, maxCycleLength, maxChainLength, build_alt_embed=0)

Bases: Model

A model that represents each cycle or chain with a binary variable. Note that since CompatibilityGraph has one vertex per donor, and recipients may have multiple donors, this means that constraints may be needed to ensure at most one donor per recipient is selected.

__init__(instance, objectives, *, maxCycleLength, maxChainLength, build_alt_embed=0)

Construct a CycleAndChainModel from an instance.

Parameters:

  • instance (Instance) – The instance to build the model from

  • objectives (list[Objective]) – The list of objectives for this pool

  • maxCycleLength (int) – The maximum length of a cycle

  • maxChainLength (int) – The maximum length of a chain

  • build_alt_embed (int) –

    Whether to build alternate and embedded exchanges. build_alt_embed can be set to any of the following:

    1. Don’t build alternate and embedded cycles. Faster, if you don’t need alternate and embedded cycles

    2. Build all alternate and embedded cycles.

    3. Build only those alternate and embedded cycles that NHSBT expects

    4. Build only those alternate and embedded cycles that NHSBT expects, where embedded exchanges cannot use new donors

property cycles: ValuesView[Exchange]

Return the list of cycles in this model.

Returns:

the list of cycles

property chains: ValuesView[Exchange]

Return the list of chains in this model.

Returns:

the list of chains

property exchanges: list[Exchange]

Return the list of cycles and chains in this model.

Returns:

the list of cycles and chains

exchange_values(exchange)

Given an exchange, return the value of the exchange for each objective.

Parameters:

exchange (Exchange) – The exchange whose value is to be returned

Return type:

list[float]

Returns:

the list of values of this exchange

build_model()

Build the model. That is, create all the variables and constraints.

Return type:

None

addObjectiveConstraint(objective, value, index)

Adds a constraint that ensures the previous objective keeps its value.

Parameters:

  • objective (Objective) – The previous objective

  • value (float) – The value the previous objective attained

  • index (int) – Which number objective is this (only used for naming the constraint)

countSolutions(maxCount=None)

Count the number of distinct solutions available for this instance at this objective.

Note that this can drastically increase the running time (by several orders of magnitude) as for each distinct solution we need to solve a new IP model.

Return type:

int

solve(countSolutions=False, maxCount=None, solvingOptions=SolvingOptions(solver=<pulp.apis.coin_api.PULP_CBC_CMD object>, useRCVF=False))

Solve the model to find an optimal solution.

Parameters:

  • countSolutions (bool) – If true, count the number of distinct solutions found at each level of optimisation. Note that this solves a new optimisation problem for each such solution found, and thus can be very time-consuming.

  • maxCount (Optional[list[int]]) – If countSolutions is true, this list contains the number at which solution counting should stop (with one number per objective).

  • solvingOptions (SolvingOptions) – A SolvingOptions object that contains information on how to solve single KEP instances.

Return type:

tuple[list[Exchange], SolvingStatistics, list[int]]

Returns:

A list of selected transplants, a list of the time taken to solve for each objective in the pool, and a list of the number of optimal solutions found for each objective

property objective_values: list[float]

The list of all objective values.

objective_value(objective_index)

Return the value of an objective, if it has been solved. If this model has not been solved, accessing this raises an error.

Parameters:

objective_index (int) – the index of the objective whose value is to be returned

Return type:

float

Returns:

the value of the objective as given by objective_index