Skip to content

Instantly share code, notes, and snippets.

@AseiSugiyama

AseiSugiyama/optimizationnight-1.ipynb

Created October 15, 2019 02:48
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save AseiSugiyama/1fa1e4a2c3e90e1393f4ff398c473143 to your computer and use it in GitHub Desktop.
Save AseiSugiyama/1fa1e4a2c3e90e1393f4ff398c473143 to your computer and use it in GitHub Desktop.
Download ZIP
OptimizationNight#1.ipynb
Display the source blob
Display the rendered blob
Raw
optimizationnight-1.ipynb
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"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": {
"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"
}
]
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment