Skip to main content

A Python package for reading and solving single instances of kidney exchange problems.

Project description

kep_solver

This Python package is devoted to various algorithms, procedures and mechanisms that are useful when studying kidney exchange programmes in general. It is written and maintained by William Pettersson.

Requirements

kep_solver runs on Python 3.10 or higher. As long as you install via pip, all other requirements will be handled by pip

Quick start with notebooks

Binder

This package provides two sample notebooks in the notebooks folder. You can access either of these using MyBinder.

Please note that MyBinder, as a free service, does have limits on its use. For more intensive use, or where the privacy of the data you use is important, you can self-install using the following instructions.

Quick start self-install

Create a virtual environment for kep_solver

mkvirtualenv kep_solver

Install kep_solver

pip install kep_solver

Download a sample JSON file from https://kep-web.optimalmatching.com/static/jsons/sample-1.json

Run the following Python commands

# Import the required functions
from kep_solver.fileio import read_json
from kep_solver.programme import Programme
from kep_solver.model import TransplantCount

# Read some input
instance = read_json("sample-1.json")

# Create a transplant pool with one objective.
# We will allow cycles to have at most 3 donor/recipient pairs and allow chains
# to have have at most 2 donors (i.e., one non-directed donor and one
# donor/recipient pair).
programme = Programme([TransplantCount()],
                       description="My first KEP",
                       maxCycleLength=3,
                       maxChainLength=2)

# Solve our instance
solution, model = programme.solve_single(instance)

# Print the solution
for selected in solution.selected:
    print(f"Selected {selected}")

Current features

  • Reading instance files (json and XML formats)

  • Creation of compatibility graphs

  • Solving for the following objectives (single, or hierarchical)

    • Maximise the number of transplants
    • Maximise the number of backarcs
    • Maximise the number of effective 2-way exchanges
    • Minimise the number of three-cycles
    • Maximise the score using the UK scoring mechanisms

While the above objectives are exactly those in use by NHSBT when running the UKLKSS (the UK national KEP), I do intend to add further objectives

Expected users

I expect this software to be useful to researchers. Depending on what questions you want answered, you can either test policy changes to determine how they affect the running of a KEP, or you can implement new models or objectives to see how they perform

Documentation

Full documentation for kep_solver can be found at https://kep-solver.readthedocs.io/en/latest/.

Interface

This is just a Python module for now, a web-interface that demonstrates a basic use case is viewable at https://kep-web.optimalmatching.com, and the source code for said website is online at https://gitlab.com/wpettersson/kep_web

Future plans

  • More objective functions
  • Supporting transnational pools
  • Implementation of faster models and modelling techniques

Contributing

I welcome input from others, whether you have ideas for improvements or want to submit code. Details on contributing can be found in CONTRIBUTING.md. You can also get in touch directly, or raise an issue

Licensing

This software is licensed under the Affero GPL v3 License, as described in LICENSE.

TO THE EXTENT PERMITTED BY LAW, THIS SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Acknowledgements

This software has been supported by the Engineering and Physical Sciences Research Council (EPSRC) grants EP/T004878/1 (Multilayer Algorithmics to Leverage Graph Structure) and EP/X013618/1 (KidneyAlgo: New Algorithms for UK and International Kidney Exchange).

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

kep_solver-4.0.0.tar.gz (547.3 kB view details)

Uploaded Source

Built Distribution

kep_solver-4.0.0-py3-none-any.whl (78.5 kB view details)

Uploaded Python 3

File details

Details for the file kep_solver-4.0.0.tar.gz.

File metadata

  • Download URL: kep_solver-4.0.0.tar.gz
  • Upload date:
  • Size: 547.3 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/6.1.0 CPython/3.13.5

File hashes

Hashes for kep_solver-4.0.0.tar.gz
Algorithm Hash digest
SHA256 45a0c204fef8cdf26a45cb5852a5406b7e95bc35e9fdea0d86c10d552769f71b
MD5 8b2c4aed660603f3fd26bbd98f1106eb
BLAKE2b-256 fd4aa6d9e61a1ef1b3c64488f0cb8efc59a5606c4636c9d47fecd33ea3a51c97

See more details on using hashes here.

File details

Details for the file kep_solver-4.0.0-py3-none-any.whl.

File metadata

  • Download URL: kep_solver-4.0.0-py3-none-any.whl
  • Upload date:
  • Size: 78.5 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/6.1.0 CPython/3.13.5

File hashes

Hashes for kep_solver-4.0.0-py3-none-any.whl
Algorithm Hash digest
SHA256 b0b7486befde5f3983603b5da08328aa381ef9e9587978c637fe9be1fd303182
MD5 06c4e31b8b9d23e07ace31d497b96a89
BLAKE2b-256 b0f88f5788cfaab2c9941ea8fedf4315ea30d10b4eee8f071046cd864f925984

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page