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.

__init__()
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__()
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.

__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.

__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.

__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

Bases: LpProblem

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

supports: list[type[Objective]] = []
__init__()

Creates an LP Problem

This function creates a new LP Problem with the specified associated parameters

Parameters:

  • name – name of the problem used in the output .lp file

  • sense – of the LP problem objective. Either LpMinimize (default) or LpMaximize.

Returns:

An LP Problem

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[kep_solver.graph.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

support(objective)

Can this model solve for the given objective.

Parameters:

objective (Objective) – The objective to solve

Return type:

bool

Returns:

Can this model solve the given objective

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

Solve the model to find an optimal solution.

Return type:

list[Exchange]

Returns:

A list of selected transplants

class CycleAndChainModel(instance, objectives, *, maxCycleLength, maxChainLength)

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.

supports: list[type[Objective]] = [<class 'kep_solver.model.TransplantCount'>]
__init__(instance, objectives, *, maxCycleLength, maxChainLength)

Creates an LP Problem

This function creates a new LP Problem with the specified associated parameters

Parameters:

  • name – name of the problem used in the output .lp file

  • sense – of the LP problem objective. Either LpMinimize (default) or LpMaximize.

Returns:

An LP Problem

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[kep_solver.graph.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)

solve()

Solve the model to find an optimal solution.

Return type:

list[Exchange]

Returns:

A list of selected transplants

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