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:
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__()
- 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
Bases:
LpProblem
A base class for all models for KEPs. Any new models should inherit from this and implement all associated functions.
- __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) orLpMaximize
.
- 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 objectivevalue (
float
) – The value the previous objective attainedindex (
int
) – Which number objective is this (only used for naming the constraint)
- 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.
- __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) orLpMaximize
.
- 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 objectivevalue (
float
) – The value the previous objective attainedindex (
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