{ "cells": [ { "cell_type": "markdown", "id": "f2d7b3c9", "metadata": {}, "source": [ "# Prize-Collecting Steiner Trees (PCSTs)\n", "\n", "The PCST is a generalization of the [Steiner Tree problem](steiner-trees.ipynb). In PCST, each vertex has a prize associated with it, and each edge has a cost. The objective is to find a tree that maximizes the difference between the total prize collected from the vertices in the tree and the total cost of the edges used. Unlike the Steiner Tree problem, where you must connect all terminal vertices, in PCST, you can choose to exclude some vertices (even terminal vertices) if the cost of connecting them is too high relative to their prize. The optimization problem is defined as:\n", "\n", "\n", "$$ \\text{argmin}_{x_v, y_e} L(x_v, y_e) = \\sum_{e \\in E} c_e y_e - \\sum_{v \\in V} p_v x_v $$\n", "\n", "Where $c_e$ is the cost of edge $e$, $p_v$ is the prize of vertex $v$, $x_v$ is a binary variable indicating whether vertex $v$ is included in the tree, and $y_e$ is a binary variable indicating whether edge $e$ is included in the tree.\n", " " ] }, { "cell_type": "code", "execution_count": 13, "id": "a1684e94", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", "
\n", " \n", " \n", " \n", " \n", "
Installed version:v0.9.2-beta.1 (latest: v0.9.1-alpha.3)
Available backends:CVXPY v1.3.2, PICOS v2.4.17
Default backend (corneto.K):CVXPY
Installed solvers:CBC, CLARABEL, COPT, CPLEX, CVXOPT, DIFFCP, ECOS, ECOS_BB, GLPK, GLPK_MI, GUROBI, MOSEK, OSQP, PROXQP, SCIP, SCIPY, SCS
Graphviz version:v0.20.1
Repository:https://github.com/saezlab/corneto
\n", "
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import numpy as np\n", "\n", "import corneto as cn\n", "\n", "cn.info()" ] }, { "cell_type": "markdown", "id": "ef4a003b", "metadata": {}, "source": [ "We will create an undirected graph, where each edge has a weight of 1.0" ] }, { "cell_type": "code", "execution_count": 5, "id": "23edb7c3", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "A\n", "\n", "A\n", "\n", "\n", "\n", "B\n", "\n", "B\n", "\n", "\n", "\n", "A->B\n", "\n", "\n", "\n", "\n", "C\n", "\n", "C\n", "\n", "\n", "\n", "A->C\n", "\n", "\n", "\n", "\n", "D\n", "\n", "D\n", "\n", "\n", "\n", "A->D\n", "\n", "\n", "\n", "\n", "F\n", "\n", "F\n", "\n", "\n", "\n", "A->F\n", "\n", "\n", "\n", "\n", "E\n", "\n", "E\n", "\n", "\n", "\n", "B->E\n", "\n", "\n", "\n", "\n", "K\n", "\n", "K\n", "\n", "\n", "\n", "B->K\n", "\n", "\n", "\n", "\n", "C->F\n", "\n", "\n", "\n", "\n", "D->C\n", "\n", "\n", "\n", "\n", "D->E\n", "\n", "\n", "\n", "\n", "I\n", "\n", "I\n", "\n", "\n", "\n", "D->I\n", "\n", "\n", "\n", "\n", "E->F\n", "\n", "\n", "\n", "\n", "G\n", "\n", "G\n", "\n", "\n", "\n", "F->G\n", "\n", "\n", "\n", "\n", "H\n", "\n", "H\n", "\n", "\n", "\n", "F->H\n", "\n", "\n", "\n", "\n", "H->E\n", "\n", "\n", "\n", "\n", "H->K\n", "\n", "\n", "\n", "\n", "I->F\n", "\n", "\n", "\n", "\n", "I->K\n", "\n", "\n", "\n", "\n", "J\n", "\n", "J\n", "\n", "\n", "\n", "J->A\n", "\n", "\n", "\n", "\n", "J->C\n", "\n", "\n", "\n", "\n", "J->G\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from corneto._graph import EdgeType\n", "\n", "G = cn.Graph()\n", "G.add_edges(\n", " [\n", " (\"A\", \"B\"),\n", " (\"A\", \"C\"),\n", " (\"A\", \"D\"),\n", " (\"D\", \"C\"),\n", " (\"D\", \"E\"),\n", " (\"B\", \"E\"),\n", " (\"E\", \"F\"),\n", " (\"A\", \"F\"),\n", " (\"F\", \"G\"),\n", " (\"F\", \"H\"),\n", " (\"H\", \"E\"),\n", " (\"I\", \"F\"),\n", " (\"D\", \"I\"),\n", " (\"J\", \"C\"),\n", " (\"J\", \"G\"),\n", " (\"C\", \"F\"),\n", " (\"J\", \"A\"),\n", " (\"I\", \"K\"),\n", " (\"H\", \"K\"),\n", " (\"B\", \"K\"),\n", " ],\n", " type=EdgeType.UNDIRECTED,\n", " weight=1,\n", ")\n", "G.plot()" ] }, { "cell_type": "code", "execution_count": 7, "id": "302346d5", "metadata": {}, "outputs": [], "source": [ "# We will put prizes only in two nodes\n", "\n", "prizes = {\"G\": 10, \"B\": 10}" ] }, { "cell_type": "code", "execution_count": 9, "id": "b74e8310", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Edge cost: 3.0\n", "Prizes: 20.0\n" ] } ], "source": [ "from corneto.methods.steiner import exact_steiner_tree\n", "\n", "P, Gc = exact_steiner_tree(G, prizes)\n", "P.solve(solver=\"SCIPY\")\n", "\n", "for n, o in zip([\"Edge cost\", \"Prizes\"], P.objectives):\n", " print(f\"{n}:\", o.value)" ] }, { "cell_type": "code", "execution_count": 15, "id": "dd8ce278", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "A\n", "\n", "A\n", "\n", "\n", "\n", "B\n", "\n", "B\n", "\n", "\n", "\n", "A->B\n", "\n", "\n", "\n", "\n", "B-*\n", "\n", "\n", "\n", "\n", "B->B-*\n", "\n", "\n", "\n", "\n", "J\n", "\n", "J\n", "\n", "\n", "\n", "J->A\n", "\n", "\n", "\n", "\n", "G\n", "\n", "G\n", "\n", "\n", "\n", "J->G\n", "\n", "\n", "\n", "\n", "*-G\n", "\n", "\n", "\n", "\n", "*-G->G\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Gc.edge_subgraph(np.where(P.symbols[\"_flow_i\"].value)[0]).plot()" ] }, { "cell_type": "markdown", "id": "89842ab1", "metadata": {}, "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.10.10" }, "toc": { "base_numbering": 1, "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": false, "title_cell": "Table of Contents", "title_sidebar": "Contents", "toc_cell": false, "toc_position": {}, "toc_section_display": true, "toc_window_display": false } }, "nbformat": 4, "nbformat_minor": 5 }