Created
October 15, 2019 02:48
-
-
Save AseiSugiyama/1fa1e4a2c3e90e1393f4ff398c473143 to your computer and use it in GitHub Desktop.
Revisions
-
AseiSugiyama revised this gist
Oct 15, 2019 . 1 changed file with 12 additions and 1 deletion.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -5,14 +5,25 @@ "colab": { "name": "OptimizationNight#1.ipynb", "provenance": [], "collapsed_sections": [], "include_colab_link": true }, "kernelspec": { "name": "python3", "display_name": "Python 3" } }, "cells": [ { "cell_type": "markdown", "metadata": { "id": "view-in-github", "colab_type": "text" }, "source": [ "<a href=\"https://colab.research.google.com/gist/AseiSugiyama/1fa1e4a2c3e90e1393f4ff398c473143/optimizationnight-1.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>" ] }, { "cell_type": "code", "metadata": { -
Oct 15, 2019 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,504 @@ { "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "name": "OptimizationNight#1.ipynb", "provenance": [], "collapsed_sections": [] }, "kernelspec": { "name": "python3", "display_name": "Python 3" } }, "cells": [ { "cell_type": "code", "metadata": { "id": "gz-z7ecXxo-E", "colab_type": "code", "outputId": "aad1d475-b464-4c81-a2ca-6427f531436d", "colab": { "base_uri": "https://localhost:8080/", "height": 85 } }, "source": [ "!pip install ortools" ], "execution_count": 0, "outputs": [ { "output_type": "stream", "text": [ "Requirement already satisfied: ortools in /usr/local/lib/python3.6/dist-packages (7.4.7247)\n", "Requirement already satisfied: six>=1.10 in /usr/local/lib/python3.6/dist-packages (from ortools) (1.12.0)\n", "Requirement already satisfied: protobuf>=3.10.0 in /usr/local/lib/python3.6/dist-packages (from ortools) (3.10.0)\n", "Requirement already satisfied: setuptools in /usr/local/lib/python3.6/dist-packages (from protobuf>=3.10.0->ortools) (41.2.0)\n" ], "name": "stdout" } ] }, { "cell_type": "markdown", "metadata": { "id": "rpcpZ5gW8Rec", "colab_type": "text" }, "source": [ "# Hello, world" ] }, { "cell_type": "code", "metadata": { "id": "XlKNiGhyz77S", "colab_type": "code", "colab": {} }, "source": [ "from ortools.linear_solver import pywraplp" ], "execution_count": 0, "outputs": [] }, { "cell_type": "code", "metadata": { "id": "_ccFcqfH4TSV", "colab_type": "code", "outputId": "da97414a-6464-4ea6-dea4-96ea2c10daed", "colab": { "base_uri": "https://localhost:8080/", "height": 102 } }, "source": [ "# Define objective function\n", "def objective(x, y, z):\n", " return x + y + z\n", "\n", "# Create the linear solver\n", "solver = pywraplp.Solver('Hello, world',\n", " pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)\n", "\n", "# Create variables\n", "x = solver.IntVar(0, 1, 'x')\n", "y = solver.IntVar(0, 1, 'y')\n", "z = solver.IntVar(0, 1, 'z')\n", "\n", "# Set objective function\n", "solver.Maximize(objective(x, y, z))\n", "\n", "# Invoke the solver\n", "solver.Solve()\n", "\n", "# Display the results\n", "print('Solution:')\n", "print('Objective value =', solver.Objective().Value())\n", "print('x =', x.solution_value())\n", "print('y =', y.solution_value())\n", "print('z =', z.solution_value())" ], "execution_count": 0, "outputs": [ { "output_type": "stream", "text": [ "Solution:\n", "Objective value = 3.0\n", "x = 1.0\n", "y = 1.0\n", "z = 1.0\n" ], "name": "stdout" } ] }, { "cell_type": "markdown", "metadata": { "id": "KVI6eVWeBS6m", "colab_type": "text" }, "source": [ "目的関数自体が何度も呼ばれているわけではないことが次のようにすると確認できます。" ] }, { "cell_type": "code", "metadata": { "id": "e3ceyOw0A3XV", "colab_type": "code", "outputId": "da7054b4-19f7-4794-8157-08b1c932e2cf", "colab": { "base_uri": "https://localhost:8080/", "height": 119 } }, "source": [ "# Define objective function\n", "def objective(*args):\n", " print(\"objective function is called!\")\n", " return sum(args)\n", "\n", "# Create the linear solver\n", "solver = pywraplp.Solver('Hello, world, again',\n", " pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)\n", "\n", "# Create variables\n", "x = solver.IntVar(0, 1, 'x')\n", "y = solver.IntVar(0, 1, 'y')\n", "z = solver.IntVar(0, 1, 'z')\n", "\n", "# Set objective function\n", "solver.Maximize(objective(x, y, z))\n", "\n", "# Invoke the solver\n", "solver.Solve()\n", "\n", "# Display the results\n", "print('Solution:')\n", "print('Objective value =', solver.Objective().Value())\n", "print('x =', x.solution_value())\n", "print('y =', y.solution_value())\n", "print('z =', z.solution_value())" ], "execution_count": 0, "outputs": [ { "output_type": "stream", "text": [ "objective function is called!\n", "Solution:\n", "Objective value = 3.0\n", "x = 1.0\n", "y = 1.0\n", "z = 1.0\n" ], "name": "stdout" } ] }, { "cell_type": "markdown", "metadata": { "id": "m2tf_0iLCp48", "colab_type": "text" }, "source": [ "次のようにすると、 $x + y = 1$ の制約のもとで最適化が行われます。" ] }, { "cell_type": "code", "metadata": { "id": "_NXinQ8NBM6k", "colab_type": "code", "outputId": "417cd075-49d8-48d2-d1c7-f067f767eeb9", "colab": { "base_uri": "https://localhost:8080/", "height": 119 } }, "source": [ "# Define objective function\n", "def objective(*args):\n", " print(\"objective function is called!\")\n", " return sum(args)\n", "\n", "# Create the linear solver\n", "solver = pywraplp.Solver('Hello, world, again',\n", " pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)\n", "\n", "# Create variables\n", "x = solver.IntVar(0, 1, 'x')\n", "y = solver.IntVar(0, 1, 'y')\n", "z = solver.IntVar(0, 1, 'z')\n", "\n", "# Add constrains\n", "solver.Add(x + y == -1)\n", "\n", "# Set objective function\n", "solver.Maximize(objective(x, y, z))\n", "\n", "# Invoke the solver\n", "result = solver.Solve()\n", "\n", "# Display the results\n", "print('Solution:')\n", "print('Objective value =', solver.Objective().Value())\n", "print('x =', x.solution_value())\n", "print('y =', y.solution_value())\n", "print('z =', y.solution_value())" ], "execution_count": 0, "outputs": [ { "output_type": "stream", "text": [ "objective function is called!\n", "Solution:\n", "Objective value = 0.0\n", "x = 0.0\n", "y = 0.0\n", "z = 0.0\n" ], "name": "stdout" } ] }, { "cell_type": "markdown", "metadata": { "id": "OBFdKZLpLmwE", "colab_type": "text" }, "source": [ "# 線形計画問題\n", "\n", "- [The Glop Linear Solver](https://developers.google.com/optimization/lp/glop)に従い、次の問題を解きます\n", "- 目的関数 $3x + 4y$\n", "- 制約条件\n", "\n", "$$\n", "\\begin{align}\n", "x + 2y&\\le 14 \\\\\n", "3x - y&\\ge 0 \\\\\n", "x - y&\\le 2\n", "\\end{align}\n", "$$\n" ] }, { "cell_type": "code", "metadata": { "id": "DJg3dnguLq2U", "colab_type": "code", "outputId": "238edc72-f3b7-4971-8848-acb305062240", "colab": { "base_uri": "https://localhost:8080/", "height": 85 } }, "source": [ "# Create the linear solver\n", "solver = pywraplp.Solver('LinearProgrammingExample',\n", " pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)\n", "infinity = solver.infinity()\n", "\n", "# Create variables\n", "x = solver.NumVar(-infinity, infinity, 'x')\n", "y = solver.NumVar(-infinity, infinity, 'y')\n", "\n", "# Add constrains\n", "solver.Add(x + 2 * y <= 14)\n", "solver.Add(3 * x - y >= 0)\n", "solver.Add(x - y <= 2)\n", "\n", "# Set objective function\n", "solver.Maximize(3 * x + 4 * y)\n", "\n", "# Invoke the solver\n", "result = solver.Solve()\n", "\n", "# Display the results\n", "print('Solution:')\n", "print('Objective value =', solver.Objective().Value())\n", "print('x =', x.solution_value())\n", "print('y =', y.solution_value())" ], "execution_count": 0, "outputs": [ { "output_type": "stream", "text": [ "Solution:\n", "Objective value = 33.99999999999999\n", "x = 5.999999999999998\n", "y = 3.9999999999999996\n" ], "name": "stdout" } ] }, { "cell_type": "markdown", "metadata": { "id": "l1DTAP0ERxNH", "colab_type": "text" }, "source": [ "# 混合整数計画問題\n", "\n", "- [Mixed-Integer Programming](https://developers.google.com/optimization/mip/integer_opt)[^2] に従い、次の問題を解く\n", "- 目的関数 $x + 10y$\n", "- 制約条件: $x$, $y$ は次を満たす整数\n", "\n", "$$\n", "\\begin{align}\n", "x + 7y&\\le 17.5 \\\\\n", "x &\\le 3.5 \\\\\n", "x, y &\\ge 0\n", "\\end{align}\n", "$$\n" ] }, { "cell_type": "code", "metadata": { "id": "vCWwTdIbR6q4", "colab_type": "code", "outputId": "edae0698-bef2-46dc-bb81-544033346cb5", "colab": { "base_uri": "https://localhost:8080/", "height": 34 } }, "source": [ "# Create the mip solver with the CBC backend.\n", "solver = pywraplp.Solver('simple_mip_program',\n", " pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)\n", "\n", "# Create variables\n", "x = solver.IntVar(-infinity, infinity, 'x')\n", "y = solver.IntVar(-infinity, infinity, 'y')\n", "\n", "# Add constrains\n", "solver.Add(x + 7 * y <= 17.5)\n", "solver.Add(x <= 3.5)\n", "solver.Add(x >= 0)\n", "solver.Add(y >= 0)\n", "\n", "# Set objective function\n", "solver.Maximize(x + 10 * y)\n", "\n", "# Invoke the solver\n", "result = solver.Solve()\n", "\n", "# result corresponds the status of result of optimization.\n", "# result can be followings;\n", "# pywraplp.Solver.OPTIMAL #0\n", "# pywraplp.Solver.FEASIBLE #1\n", "# pywraplp.Solver.INFEASIBLE #2\n", "result" ], "execution_count": 0, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "0" ] }, "metadata": { "tags": [] }, "execution_count": 27 } ] }, { "cell_type": "code", "metadata": { "id": "qWnDZSOiEKXu", "colab_type": "code", "outputId": "aaa409ec-7736-4faa-a94b-c4f43d66f7f0", "colab": { "base_uri": "https://localhost:8080/", "height": 85 } }, "source": [ "\n", "# The solution looks legit (when using solvers others than\n", "# GLOP_LINEAR_PROGRAMMING, verifying the solution is highly recommended!).\n", "assert solver.VerifySolution(1e-7, True)\n", "\n", "# Display the results\n", "print('Solution:')\n", "print('Objective value =', solver.Objective().Value())\n", "print('x =', x.solution_value())\n", "print('y =', y.solution_value())" ], "execution_count": 0, "outputs": [ { "output_type": "stream", "text": [ "Solution:\n", "Objective value = 23.0\n", "x = 3.0\n", "y = 2.0\n" ], "name": "stdout" } ] }, { "cell_type": "markdown", "metadata": { "id": "LmuAx2Q9U_cn", "colab_type": "text" }, "source": [ "同じ問題について、線形計画問題として捉えて解くと結果は次のようになります。" ] }, { "cell_type": "code", "metadata": { "id": "7kgTBDg_VHvF", "colab_type": "code", "outputId": "a3017060-b590-4164-c03c-3edf6f870d0e", "colab": { "base_uri": "https://localhost:8080/", "height": 85 } }, "source": [ "# Create the mip solver with the CBC backend.\n", "solver = pywraplp.Solver('simple_mip_program',\n", " pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)\n", "\n", "# Create variables\n", "x = solver.NumVar(-infinity, infinity, 'x')\n", "y = solver.NumVar(-infinity, infinity, 'y')\n", "\n", "# Add constrains\n", "solver.Add(x + 7 * y <= 17.5)\n", "solver.Add(x <= 3.5)\n", "solver.Add(x >= 0)\n", "solver.Add(y >= 0)\n", "\n", "# Set objective function\n", "solver.Maximize(x + 10 * y)\n", "\n", "# Invoke the solver\n", "solver.Solve()\n", "\n", "# Display the results\n", "print('Solution:')\n", "print('Objective value =', solver.Objective().Value())\n", "print('x =', x.solution_value())\n", "print('y =', y.solution_value())" ], "execution_count": 0, "outputs": [ { "output_type": "stream", "text": [ "Solution:\n", "Objective value = 25.0\n", "x = 0.0\n", "y = 2.5\n" ], "name": "stdout" } ] } ] }