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__()
- 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
- 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 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 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:
graph (
CompatibilityGraph
) – The graph containing the exchangeexchange (
Exchange
) – A cycle or chain.
- 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
- 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:
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
- 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.
- 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:
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 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:
graph (
CompatibilityGraph
) – The graph containing the exchangeexchange (
Exchange
) – A cycle or chain.
- 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
- 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.
- __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
- 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 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 time-consuming.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
- 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.
- __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
- property graph: CompatibilityGraph
The graph used for this model.
- Returns:
The graph used for this model.
- 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 time-consuming.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
- 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 time-consuming.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