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.
 __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 exchangeedge (
Edge
) – The edge, representing a transplantposition (
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:
graph (
CompatibilityGraph
) – The graph containing the exchangeexchange (
Exchange
) – A cycle or chain.
 Return type:
float
 describe()
Describes what this objective optimises.
 Return type:
str
 Returns:
the description

need_alt_embed:
 class TransplantCount
Bases:
Objective
An objective to maximise the number of transplants. Note that for a chain, the donation to the nondirected donor (which often would go to a deceaseddonor 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 exchangeedge (
Edge
) – The edge, representing a transplantposition (
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:
graph (
CompatibilityGraph
) – The graph containing the exchangeexchange (
Exchange
) – A cycle or chain.
 Return type:
float
 Returns:
the number of transplants
 describe()
Describes what this objective optimises.
 Return type:
str
 Returns:
the description
 class EffectiveTwoWay
Bases:
Objective
An objective to maximise the number of effective twoway transplants. For cycles, they must either have size two, or have a backarc. All chains count as effective twoway exchanges. This is binary for each exchange. That is, either an exchange has or does not have an effective twoway 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 twoway exchange?
 Parameters:
graph (
CompatibilityGraph
) – The graph containing the exchangeexchange (
Exchange
) – A cycle or chain.
 Return type:
float
 Returns:
1 if and only if it is effectively twoway
 describe()
Describes what this objective optimises.
 Return type:
str
 Returns:
the description

need_alt_embed:
 class BackArcs
Bases:
Objective
An objective to maximise the number of backarcs. Note that arcs back to a nondirected 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:
graph (
CompatibilityGraph
) – The graph containing the exchangeexchange (
Exchange
) – An exchange
 Return type:
float
 Returns:
The number of backarcs in the exchange
 describe()
Describes what this objective optimises.
 Return type:
str
 Returns:
the description

need_alt_embed:
 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 * 1e5
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 nondirected Donor, both the age difference bonus and the tiebreaker will be 0.
 class UKScore
Bases:
Objective
An objective to maximise the number of backarcs.
 __init__()
 value(graph, exchange)
What is the UK score of this exchange?
 Parameters:
graph (
CompatibilityGraph
) – The graph containing the exchangeexchange (
Exchange
) – An exchange
 Return type:
float
 Returns:
The UK score of this exchange
 describe()
Describes what this objective optimises.
 Return type:
str
 Returns:
the description
 class ThreeWay
Bases:
Objective
An objective to minimise the number of threeway exchanges. If no larger exchanges are allowed, this has the effect of increasing the number of twoway exchanges.
 __init__()
 value(graph, exchange)
Is the given exchange a threeway exchange.
 Parameters:
graph (
CompatibilityGraph
) – The graph containing the exchangeexchange (
Exchange
) – A cycle or chain.
 Return type:
float
 Returns:
1 if and only if it is a threeway exchange
 describe()
Describes what this objective optimises.
 Return type:
str
 Returns:
the description
 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 fromobjectives (
list
[Objective
]) – The list of objectives for this poolmaxCycleLength (
int
) – The maximum length of a cyclemaxChainLength (
int
) – The maximum length of a chainbuild_alt_embed (
int
) –Whether to build alternate and embedded exchanges. build_alt_embed can be set to any of the following:
Don’t build alternate and embedded cycles. Faster, if you don’t need alternate and embedded cycles
Build all alternate and embedded cycles.
Build only those alternate and embedded cycles that NHSBT expects
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 objectivevalue (
float
) – The value the previous objective attainedindex (
int
) – Which number objective is this (only used for naming the constraint)
 solve(countSolutions=False, maxCount=None, solver=None)
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 timeconsuming.solver – An instantiated PuLP solver. If empty, a solver will be created and used
 Return type:
tuple
[list
[Exchange
],list
[tuple
[str
,float
]],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

supports_full_details:
 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 fromobjectives (
list
[Objective
]) – The list of objectives for this poolmaxCycleLength (
int
) – The maximum length of a cyclemaxChainLength (
int
) – The maximum length of a chainbuild_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 objectivevalue (
float
) – The value the previous objective attainedindex (
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, solver=None)
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 timeconsuming.solver – An instantiated PuLP solver. If empty, a CBC solver is created and used
 Return type:
tuple
[list
[Exchange
],list
[tuple
[str
,float
]],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

supports_full_details:
 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 fromobjectives (
list
[Objective
]) – The list of objectives for this poolmaxCycleLength (
int
) – The maximum length of a cyclemaxChainLength (
int
) – The maximum length of a chainbuild_alt_embed (
int
) –Whether to build alternate and embedded exchanges. build_alt_embed can be set to any of the following:
Don’t build alternate and embedded cycles. Faster, if you don’t need alternate and embedded cycles
Build all alternate and embedded cycles.
Build only those alternate and embedded cycles that NHSBT expects
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 objectivevalue (
float
) – The value the previous objective attainedindex (
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, solver=None)
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 timeconsuming.solver – An instantiated PuLP solver. If empty, a CBC solver is created and used
 Return type:
tuple
[list
[Exchange
],list
[tuple
[str
,float
]],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