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 exchange

  • values (list[float]) – The value of this exchange for each objective

property exchange: Exchange

The underlying exchange.

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 exchanges

  • scores (list[float]) – the list of scores achieved for each objective

  • possible (list[ModelledExchange]) – the set of possible exchanges, and their values for each objective

  • statistics (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 objectives

  • maxCycleLength (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:

    1. Don’t build alternate and embedded cycles. Faster, if you don’t need alternate and embedded cycles

    2. Build all alternate and embedded cycles.

    3. Build only those alternate and embedded cycles that NHSBT expects

    4. 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 objectives: list[Objective]

The list of objectives for 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 consider

  • graph (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 solve

  • maxCycleLength (Optional[int]) – The longest cycle allowed. If not specified, we use the default from the Programme

  • maxChainLength (Optional[int]) – The longest chain allowed. If not specified, we use the default from the Programme

  • solvingOptions (SolvingOptions) – A SolvingOptions object that contains information on how to solve single KEP instances.

Return type:

tuple[Optional[Solution], Model]

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 period

  • scheduler (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 time

  • allow_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.