{ "cells": [ { "cell_type": "markdown", "id": "f2d7b3c9", "metadata": {}, "source": [ "# Constrained Optimization\n", "\n", "Constrained optimization is a cornerstone of many scientific and engineering disciplines, aiming to find the best solution to a problem within a set of specified boundaries or constraints. Common types of constrained optimization problems include linear, nonlinear, integer or mixed-integer programming, among others. Specifically, Linear Programming (LP) and (Mixed)Integer Linear Programming (MILP) are two widely used techniques in this domain. LP involves problems where both the objective function and the constraints are linear, and the decision variables can take any continuous values. On the other hand, (M)ILP is a more specialized form where some or all of the decision variables are required to be integers. Both LP and (M)ILP are particularly useful in modeling network problems, including many problems typically used in network biology, due to their ability to handle complex interrelationships and constraints inherent in such systems.\n", "\n", "CORNETO offers an unified framwork for network learning from prior knowledge, where network inference problems are modelled through constrained optimization. Thanks to its modular backend implementation, different specialized mathematical optimization frameworks such as CVXPY or PICOS can be used to model and solve the optimization problems.\n", "\n", "Here we will see how can we use CORNETO as a multi-backend constrained optimization framework for very basic optimization problems. " ] }, { "cell_type": "markdown", "id": "082120aa", "metadata": {}, "source": [ "## The Knapsack Problem" ] }, { "cell_type": "markdown", "id": "89fc8e17", "metadata": {}, "source": [ "The knapsack problem is an optimization problem in which we are given a set of items, each with a weight and a value. We are also given a knapsack with a limited capacity. The goal is to select a subset of the items to put in the knapsack so that the total value of the items is maximized, while the total weight does not exceed the capacity of the knapsack.\n", "\n", "
\n", " \"Knapsack\"\n", "
\n", " \n", " Figure 1: Knapsack problem.\n", " \n", "
\n", "\n", "The knapsack problem can be formulated as a constrained optimization problem with binary variables as follows:\n", "\n", "$$ \\begin{align*}\n", "\\text{maximize} &\\quad \\sum_{i=1}^n v_i x_i \\\\\n", "\\text{subject to} &\\quad \\sum_{i=1}^n w_i x_i \\le c \\\\\n", "&\\quad x_i \\in \\{0, 1\\} \\quad \\forall i \\in \\{1, 2, \\dots, n\\}\n", "\\end{align*} $$\n", "\n", "We will see how to use CORNETO to easily model and solve to optimality this problem." ] }, { "cell_type": "code", "execution_count": 1, "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
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 corneto as cn\n", "\n", "cn.info()" ] }, { "cell_type": "code", "execution_count": 2, "id": "254a2ff5", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# CORNETO automatically selects one of the available mathematical programming backends.\n", "# By default, CVXPY is preferred. The default backend can be accessed with:\n", "\n", "cn.K" ] }, { "cell_type": "code", "execution_count": 3, "id": "1c1f2c03", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Expression(AFFINE, NONNEGATIVE, (1,))" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "obj1 = cn.K.Variable(\"obj1\", 1, vartype=cn.VarType.BINARY)\n", "obj2 = cn.K.Variable(\"obj2\", 1, vartype=cn.VarType.BINARY)\n", "obj3 = cn.K.Variable(\"obj3\", 1, vartype=cn.VarType.BINARY)\n", "obj4 = cn.K.Variable(\"obj4\", 1, vartype=cn.VarType.BINARY)\n", "obj5 = cn.K.Variable(\"obj5\", 1, vartype=cn.VarType.BINARY)\n", "\n", "total_value = 4 * obj1 + 2 * obj2 + 10 * obj3 + 1 * obj4 + 2 * obj5\n", "weight = 12 * obj1 + 1 * obj2 + 4 * obj3 + 1 * obj4 + 2 * obj5\n", "\n", "total_value" ] }, { "cell_type": "code", "execution_count": 4, "id": "f4e2fadd", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "problem = cn.K.Problem(\n", " constraints=sum(weight) <= 15,\n", " objectives=sum(total_value),\n", " direction=cn.Direction.MAX,\n", ")\n", "problem" ] }, { "cell_type": "code", "execution_count": 5, "id": "8c31f698", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'obj5': Variable((1,), boolean=True),\n", " 'obj4': Variable((1,), boolean=True),\n", " 'obj2': Variable((1,), boolean=True),\n", " 'obj1': Variable((1,), boolean=True),\n", " 'obj3': Variable((1,), boolean=True)}" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "problem.expr" ] }, { "cell_type": "code", "execution_count": 6, "id": "6cc6c9fb", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The max. value you can get with the backpack is $15.0\n" ] } ], "source": [ "# Now we solve the problem using a specific solver. If solver is not provided\n", "# one is automatically selected by the backend.\n", "sol = problem.solve()\n", "print(f\"The max. value you can get with the backpack is ${total_value.value[0]}\")" ] }, { "cell_type": "code", "execution_count": 7, "id": "9325feec", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([0.])" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Variables have the attribute 'value' to see their optimal value\n", "# Before solving the problem, the 'value' attribute is None\n", "obj1.value" ] }, { "cell_type": "markdown", "id": "ef4a003b", "metadata": {}, "source": [ "## A more complex knapsack" ] }, { "cell_type": "code", "execution_count": 8, "id": "8a61e6d1", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "===============================================================================\n", " CVXPY \n", " v1.3.2 \n", "===============================================================================\n", "(CVXPY) Sep 07 12:04:18 AM: Your problem has 50 variables, 1 constraints, and 0 parameters.\n", "(CVXPY) Sep 07 12:04:18 AM: It is compliant with the following grammars: DCP, DQCP\n", "(CVXPY) Sep 07 12:04:18 AM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)\n", "(CVXPY) Sep 07 12:04:18 AM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.\n", "-------------------------------------------------------------------------------\n", " Compilation \n", "-------------------------------------------------------------------------------\n", "(CVXPY) Sep 07 12:04:18 AM: Compiling problem (target solver=SCIPY).\n", "(CVXPY) Sep 07 12:04:18 AM: Reduction chain: FlipObjective -> Dcp2Cone -> CvxAttr2Constr -> ConeMatrixStuffing -> SCIPY\n", "(CVXPY) Sep 07 12:04:18 AM: Applying reduction FlipObjective\n", "(CVXPY) Sep 07 12:04:18 AM: Applying reduction Dcp2Cone\n", "(CVXPY) Sep 07 12:04:18 AM: Applying reduction CvxAttr2Constr\n", "(CVXPY) Sep 07 12:04:18 AM: Applying reduction ConeMatrixStuffing\n", "(CVXPY) Sep 07 12:04:18 AM: Applying reduction SCIPY\n", "(CVXPY) Sep 07 12:04:18 AM: Finished problem compilation (took 2.401e-02 seconds).\n", "-------------------------------------------------------------------------------\n", " Numerical solver \n", "-------------------------------------------------------------------------------\n", "(CVXPY) Sep 07 12:04:18 AM: Invoking solver SCIPY to obtain a solution.\n", "Solver terminated with message: Optimization terminated successfully. (HiGHS Status 7: Optimal)\n", "-------------------------------------------------------------------------------\n", " Summary \n", "-------------------------------------------------------------------------------\n", "(CVXPY) Sep 07 12:04:18 AM: Problem status: optimal\n", "(CVXPY) Sep 07 12:04:18 AM: Optimal value: 7.534e+03\n", "(CVXPY) Sep 07 12:04:18 AM: Compilation took 2.401e-02 seconds\n", "(CVXPY) Sep 07 12:04:18 AM: Solver (including time spent in interface) took 3.199e-02 seconds\n" ] }, { "data": { "text/plain": [ "Problem(Maximize(Expression(AFFINE, NONNEGATIVE, ())), [Inequality(Expression(AFFINE, NONNEGATIVE, ()))])" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# A larger example from:\n", "# https://developers.google.com/optimization/pack/knapsack\n", "\n", "values = [\n", " 360,\n", " 83,\n", " 59,\n", " 130,\n", " 431,\n", " 67,\n", " 230,\n", " 52,\n", " 93,\n", " 125,\n", " 670,\n", " 892,\n", " 600,\n", " 38,\n", " 48,\n", " 147,\n", " 78,\n", " 256,\n", " 63,\n", " 17,\n", " 120,\n", " 164,\n", " 432,\n", " 35,\n", " 92,\n", " 110,\n", " 22,\n", " 42,\n", " 50,\n", " 323,\n", " 514,\n", " 28,\n", " 87,\n", " 73,\n", " 78,\n", " 15,\n", " 26,\n", " 78,\n", " 210,\n", " 36,\n", " 85,\n", " 189,\n", " 274,\n", " 43,\n", " 33,\n", " 10,\n", " 19,\n", " 389,\n", " 276,\n", " 312,\n", "]\n", "\n", "weights = [\n", " 7,\n", " 0,\n", " 30,\n", " 22,\n", " 80,\n", " 94,\n", " 11,\n", " 81,\n", " 70,\n", " 64,\n", " 59,\n", " 18,\n", " 0,\n", " 36,\n", " 3,\n", " 8,\n", " 15,\n", " 42,\n", " 9,\n", " 0,\n", " 42,\n", " 47,\n", " 52,\n", " 32,\n", " 26,\n", " 48,\n", " 55,\n", " 6,\n", " 29,\n", " 84,\n", " 2,\n", " 4,\n", " 18,\n", " 56,\n", " 7,\n", " 29,\n", " 93,\n", " 44,\n", " 71,\n", " 3,\n", " 86,\n", " 66,\n", " 31,\n", " 65,\n", " 0,\n", " 79,\n", " 20,\n", " 65,\n", " 52,\n", " 13,\n", "]\n", "\n", "# We use matrix notation form\n", "obj = cn.K.Variable(\"obj\", len(values), vartype=cn.VarType.BINARY)\n", "total_value = values @ obj # matrix mul (1, values) x (objects, 1)\n", "total_weight = weights @ obj\n", "\n", "cn.K.Problem(\n", " constraints=total_weight <= 850, objectives=total_value, direction=cn.Direction.MAX\n", ").solve(verbosity=1)" ] }, { "cell_type": "code", "execution_count": 9, "id": "fc365050", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(7534.0, 850.0)" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "total_value.value, total_weight.value" ] } ], "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 }