kep_solver.programme module
Handling of the rules, procedures and algorithms for a particular KEP.
- class ModelledExchange(exchange, values)
Bases:
object
An exchange as modelled, including its value for various objectives and any other relevant information.
- __init__(exchange, values)
Constructor for ModelledExchange. Contains the Exchange object, and also the value of this exchange for the various objectives in this model.
- Parameters:
exchange (
Exchange
) – The exchangevalues (
list
[float
]) – The value of this exchange for each objective
- property values: list[float]
The values of this exchange.
- class Solution(exchanges, scores, possible, statistics, numSolutions)
Bases:
object
A solution to one instance of a KEP. Contains the exchanges, and the set of objective values attained.
- __init__(exchanges, scores, possible, statistics, numSolutions)
Constructor for Solution. This class essentially just stores any information that may be useful.
- Parameters:
exchanges (
list
[ModelledExchange
]) – the list of selected exchangesscores (
list
[float
]) – the list of scores achieved for each objectivepossible (
list
[ModelledExchange
]) – the set of possible exchanges, and their values for each objectivestatistics (
SolvingStatistics
) – A number of statistics relating to obtaining this solution. This includes the time taken for various operations, as well as particulars of the solving process such as number of variables, number of constraints, number of non-zero coefficients, and details of any reduced cost variable fixing.numSolutions (
list
[int
]) – Either an empty list (if solutions weren’t counted) or a list such that the i’th entry in the list is the number of distinct solutions found for the i’th objective
- property times: list[TimeStep]
Get the time taken for various operations. Each element of the returned list is a tuple where the first item is a string description of some operation, and the second item is the time taken in seconds.
- Returns:
the list of times (and their descriptions)
- property selected: list[ModelledExchange]
Get the selected solution.
- Returns:
the list of exchanges selected.
- property values: list[float]
Get the Objective values of the selected solution.
- Returns:
the list of objective values
- property possible: list[ModelledExchange]
Return a list of all the possible chains and cycles that may be selected as ModelledExchange objects that contain the value of said exchange for each objective.
- Returns:
a list of cycles/chains as ModelledExchange objects
- property numSolutions: list[int]
Return the number of optimal solutions found for each objective.
- Returns:
a list of cycles/chains as ModelledExchange objects
- class Programme(objectives, maxCycleLength, maxChainLength, description, build_alt_embed=0, full_details=True, model=<class 'kep_solver.model.CycleAndChainModel'>)
Bases:
object
A kidney exchange programme (or more specifically, the objectives and parameters for a KEP).
- __init__(objectives, maxCycleLength, maxChainLength, description, build_alt_embed=0, full_details=True, model=<class 'kep_solver.model.CycleAndChainModel'>)
Constructor for Programme. This represents a set of objectives, and parameters for running matchings (such as maximum cycle and chain lengths).
- Parameters:
objectives (
list
[Objective
]) – the list of objectivesmaxCycleLength (
int
) – The longest cycle length allowed.maxChainLength (
int
) – The longest chain length allowed. Note that the length of a chain includes the non-directed donor.description (
str
) – A description of this programme.build_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
full_details (
bool
) – If True, try to return details for all possible exchanges (even the ones not selected). Note that this will fail on some models that don’t enumerate all possible exchnages.
- property build_alternates_and_embeds: bool
Will this programme build alternate and embedded exchanges.
- property description: str
A description of this programme.
- property maxCycleLength: int
The maximum length of cycles in this programme.
- property maxChainLength: int
The maximum length of chains in this programme. Note that this includes the non-directed donor, so a chain of length 1 only has a non-directed donor and no recipients.
- getOptimal(exchanges, graph)
Given a list of exchanges, return an optimal exchange, where optimality is determined by the objectives used.
- Parameters:
exchanges (
list
[Exchange
]) – The list of exchanges to considergraph (
CompatibilityGraph
) – The compatibility graph for these exchanges
- Return type:
Exchange
|None
- Returns:
An optimal exchange. If there are multiple exchanges that are all optimal, the first such exchange in the list is returned.
- solve_single(instance, *, maxCycleLength=None, maxChainLength=None, countSolutions=False, maxCount=None, solvingOptions=SolvingOptions(solver=<pulp.apis.coin_api.PULP_CBC_CMD object>, useRCVF=False))
Run a single instance through this programme, returning the solution, or None if no solution is found (e.g., if the solver crashes).
- Parameters:
instance (
Instance
) – The instance to solvemaxCycleLength (
Optional
[int
]) – The longest cycle allowed. If not specified, we use the default from the ProgrammemaxChainLength (
Optional
[int
]) – The longest chain allowed. If not specified, we use the default from the ProgrammesolvingOptions (
SolvingOptions
) – A SolvingOptions object that contains information on how to solve single KEP instances.
- Return type:
- Returns:
A tuple containing a Solution object, or None if an error occured, as well as the model that was solved.
- class DynamicSimulation(programme, periods, dynamic_instance, match_run_fn, scheduler, allow_bridge_donors=False, bridge_donor_attrition=<function DynamicSimulation.<lambda>>, recourse='Internal', solving_options=SolvingOptions(solver=<pulp.apis.coin_api.PULP_CBC_CMD object>, useRCVF=False))
Bases:
object
- __init__(programme, periods, dynamic_instance, match_run_fn, scheduler, allow_bridge_donors=False, bridge_donor_attrition=<function DynamicSimulation.<lambda>>, recourse='Internal', solving_options=SolvingOptions(solver=<pulp.apis.coin_api.PULP_CBC_CMD object>, useRCVF=False))
Create a simulation from the given parameters. Note that this will change the status of every recipient and donor to NotYetArrived.
- Parameters:
programme (
Programme
) – The Programme to use for optimisation.periods (
int
) – How many periods to simulate.instance – The dynamic instance containing donors, recipients, and transplants, and details on when people arrive, depart, become ill, and information on which transplants will fail a laboratory crossmatch.
match_run_fn (
Callable
[[int
,Iterable
[Recipient
],Iterable
[Donor
]],bool
]) – A function that takes as input the current period, as well as all DynamicParticipants and returns True if and only if a match run should occur in the given periodscheduler (
Callable
[[Exchange
],int
]) – A function that takes as input an Exchange, and returns an int such that this exchange would be attempted in that many periods timeallow_bridge_donors (
bool
) – If True, the last donor in a chain becomes a bridge donor for the next period, acting like a new non-directed donor.bridge_donor_attrition (
Callable
[[Donor
],float
]) – A function that takes as input a bridge donor, and returns the chance of attrition of this donor in a given period. The default is that bridge donors never leave due to attrition.recourse (
str
) – One of “Internal” or “None” (specifically, the string “None” and not the Python type None). If “Internal” then if an exchange fails, we attempt to find an exchange using a (not necessarily strict) subset of the same participants. If “None”, the exchange is allowed to fail and no recourse occurs.solving_options (
SolvingOptions
) – A SolvingOptions object allowing one to set various solving options.
- reset()
Reset all donors and recipients to have a status of NotYetArrived, and ensure we have no known failing transplants.
- Return type:
None
- run()
Run the simulation.
- Return type:
tuple
[list
[tuple
[Instance
,Model
,Solution
]],dict
[int
,list
[Exchange
]]]- Returns:
A tuple containing a list of Instance, Model, Solution triples
(one per matching run performed) as well as a dictionary mapping periods to the list of Exchanges performed in that period.