{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "{index} single: solver; cbc\n", "\n", "{index} single: solver; highs\n", "\n", "\n", "# BIM production variants" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "5ssUqKOaPVaE", "outputId": "38c1005a-39f4-4307-e305-19a4c9819396" }, "outputs": [], "source": [ "# install dependencies and select solver\n", "%pip install -q amplpy numpy matplotlib scikit-learn yfinance\n", "\n", "SOLVER = \"highs\"\n", "\n", "from amplpy import AMPL, ampl_notebook\n", "\n", "ampl = ampl_notebook(\n", " modules=[\"highs\"], # modules to install\n", " license_uuid=\"default\", # license to use\n", ") # instantiate AMPL object and register magics" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Two variants of the BIM problem: fractional objective and additional fixed costs\n", "\n", "Recall the BIM production model introduced earlier [here](bim.ipynb), that is\n", "\n", "$$\n", "\\begin{array}{rrcrclr}\n", "\\max \\quad \n", " & 12x_1 & + & 9x_2 \\\\\n", "\\text{s.t.} \\quad\n", " & x_1 & & & \\leq & 1000 &\\text{(silicon)}\\\\\n", " & & & x_2 & \\leq & 1500 &\\text{(germanium)}\\\\\n", " & x_1 & + & x_2 & \\leq & 1750 &\\text{(plastic)}\\\\\n", " & 4x_1 & + & 2x_2 & \\leq & 4800 &\\text{(copper)}\\\\\n", " & x_1 & , & x_2 & \\geq & 0.\n", "\\end{array}\n", "$$\n", "\n", "Assume the pair $(12,9)$ reflects the sales price (revenues) in € and not the profits made per unit produced. We then need to account for the production costs. Suppose that the production costs for $(x_1,x_2)$ chips are equal to a fixed cost of 100 (independent of the number of units produced) plus $7/6 x_1$ plus $5/6 x_2$. It is reasonable to maximize the difference between the revenues and the costs. This approach yields the following linear model:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Writing BIM_with_revenues_minus_costs.mod\n" ] } ], "source": [ "%%writefile BIM_with_revenues_minus_costs.mod\n", "\n", "var x1 >= 0;\n", "var x2 >= 0;\n", "\n", "var revenue = 12 * x1 + 9 * x2;\n", "var variable_cost = 7/6 * x1 + 5/6 * x2;\n", "\n", "param fixed_cost default 100;\n", "\n", "maximize profit: revenue - variable_cost - fixed_cost;\n", "\n", "s.t. silicon: x1 <= 1000;\n", "s.t. germanium: x2 <= 1500;\n", "s.t. plastic: x1 + x2 <= 1750;\n", "s.t. copper: 4 * x1 + 2 * x2 <= 4800;" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "id": "m33AGCU_PSJw" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "HiGHS 1.5.1:HiGHS 1.5.1: optimal solution; objective 15925\n", "2 simplex iterations\n", "0 barrier iterations\n", "x=(650.0,1100.0) value=15925.000 revenue=17700.00 cost=1775.00\n" ] } ], "source": [ "def BIM_with_revenues_minus_costs():\n", " m = AMPL()\n", " m.read(\"BIM_with_revenues_minus_costs.mod\")\n", "\n", " return m\n", "\n", "\n", "BIM_linear = BIM_with_revenues_minus_costs()\n", "BIM_linear.option[\"solver\"] = SOLVER\n", "BIM_linear.solve()\n", "\n", "print(\n", " \"x=({:.1f},{:.1f}) value={:.3f} revenue={:.2f} cost={:.2f}\".format(\n", " BIM_linear.var[\"x1\"].value(),\n", " BIM_linear.var[\"x2\"].value(),\n", " BIM_linear.obj[\"profit\"].value(),\n", " BIM_linear.var[\"revenue\"].value(),\n", " BIM_linear.var[\"variable_cost\"].value()\n", " + BIM_linear.param[\"fixed_cost\"].value(),\n", " )\n", ")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This first model has the same optimal solution as the original BIM model, namely $(650,1100)$ with a revenue of $17700$ and a cost of $1775$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Alternatively, we may aim to optimize the efficiency of the plan, expressed as the ratio between the revenues and the costs:\n", "\n", "$$\n", "\\begin{array}{lll}\n", "\\max \\quad \n", " & {\\dfrac{12x_1+9x_2}{7/6x_1 + 5/6x_2 + 100}} \\\\\n", "\\text{s.t.} \\quad \n", " & x_1 \\leq 1000 &\\text{(silicon)}\\\\\n", " & x_2 \\leq 1500 &\\text{(germanium)}\\\\\n", " & x_1 + x_2 \\leq 1750 &\\text{(plastic)}\\\\\n", " & 4x_1 + 2x_2 \\leq 4800 &\\text{(copper)}\\\\\n", " & x_1 , x_2 \\geq 0.\n", "\\end{array}\n", "$$\n", "\n", "In order to solve this second version we need to deal with the fraction appearing in the objective function by introducing an auxiliary variable $t \\geq 0$. More specifically, we reformulate the model as follows\n", "\n", "$$\n", "\\begin{array}{rrcrcrclr}\n", "\\max \\quad \n", " & 12y_1 & + & 9y_2 \\\\\n", "\\text{s.t.} \\quad \n", " & y_1 & & & & & \\leq & 1000 \\cdot t &\\text{(silicon)}\\\\\n", " & & & y_2 & & & \\leq & 1500 \\cdot t &\\text{(germanium)}\\\\\n", " & y_1 & + & y_2 & & & \\leq & 1750 \\cdot t &\\text{(plastic)}\\\\\n", " & 4y_1 & + & 2y_2 & & & \\leq & 4800 \\cdot t &\\text{(copper)}\\\\\n", "\t\t&7/6y_1 & + &5/6y_2 & + & 100y & = & 1 & \\text{(fraction)} \\\\ \n", " & y_1 & , & y_2 & , & t & \\geq & 0 \\\\\n", "\\end{array}\n", "$$\n", "\n", "Despite the change of variables, we can always recover the solution as $(x_1,x_2)= (y_1/t,y_2/t)$." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Writing BIM_with_revenues_over_costs.mod\n" ] } ], "source": [ "%%writefile BIM_with_revenues_over_costs.mod\n", "\n", "var y1 >= 0;\n", "var y2 >= 0;\n", "var t >= 0;\n", "\n", "var revenue = 12 * y1 + 9 * y2;\n", "var variable_cost = 7/6 * y1 + 5/6 * y2;\n", "\n", "param fixed_cost default 100;\n", "\n", "maximize profit: revenue;\n", "\n", "s.t. silicon: y1 <= 1000 * t;\n", "s.t. germanium: y2 <= 1500 * t;\n", "s.t. plastic: y1 + y2 <= 1750 * t;\n", "s.t. copper: 4 * y1 + 2 * y2 <= 4800 * t;\n", "\n", "s.t. frac: variable_cost + fixed_cost * t == 1;" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "HiGHS 1.5.1: \b\b\b\b\b\b\b\b\b\b\b\b\bHiGHS 1.5.1: optimal solution; objective 10.05076142\n", "4 simplex iterations\n", "0 barrier iterations\n", "x=(250.0,1500.0) value=10.051 revenue=16500.00 cost=1641.67\n" ] } ], "source": [ "def BIM_with_revenues_over_costs():\n", " m = AMPL()\n", " m.read(\"BIM_with_revenues_over_costs.mod\")\n", "\n", " return m\n", "\n", "\n", "BIM_fractional = BIM_with_revenues_over_costs()\n", "BIM_fractional.option[\"solver\"] = SOLVER\n", "BIM_fractional.solve()\n", "\n", "t = BIM_fractional.var[\"t\"].value()\n", "y1 = BIM_fractional.var[\"y1\"].value()\n", "y2 = BIM_fractional.var[\"y2\"].value()\n", "profit = BIM_fractional.obj[\"profit\"].value()\n", "variable_cost = BIM_fractional.var[\"variable_cost\"].value()\n", "fixed_cost = BIM_fractional.param[\"fixed_cost\"].value()\n", "revenue = BIM_fractional.var[\"revenue\"].value()\n", "\n", "print(\n", " \"x=({:.1f},{:.1f}) value={:.3f} revenue={:.2f} cost={:.2f}\".format(\n", " y1 / t,\n", " y2 / t,\n", " profit / (variable_cost + fixed_cost * t),\n", " revenue / t,\n", " variable_cost / t + fixed_cost,\n", " )\n", ")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The second model has optimal solution $(250,1500)$ with a revenue of $16500$ and a cost of $1641.667$." ] }, { "cell_type": "markdown", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "l5emuDb-2xFf", "outputId": "6909d47d-77be-4a3a-8b76-498362de06ea" }, "source": [ "The efficiency, measured as the ratio of revenue over costs for the optimal solution, is different for the two models. For the first model the efficiency is equal to $\\frac{17700}{1775}=9.972$, which is strictly smaller than that of the second model, that is $\\frac{16500}{1641.667}=10.051$." ] } ], "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.6" } }, "nbformat": 4, "nbformat_minor": 4 }