{ "cells": [ { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Mixed Integer Linear Programming demo (IMA 2017)\n", "==========================\n", "\n", "We show how Sage can be used to do linear optimization with different kind of real numbers:\n", "- floating point numbers (GLPK, CBC/Coin-OR, ...)\n", "- rational (PPL)\n", "- algebraic numbers (Sage generic implementation)" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Example 1\n", "----------\n", "\n", "Let us consider the following problem\n", "\n", "maximize $f(x_0,x_1,x_2) = 3x_0 + 2x_1 + x_2$ under the constraints\n", "- $x_0 \\geq 0$, $x_1 \\geq 0$, $x_2 \\geq 0$\n", "- $7 x_0 \\leq x_1 + x_2$\n", "- $5 x_1 \\leq 3 x_2$\n", "- $9 x_0 + 8 x_1 + 7 x_2 = 27$" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "deletable": true, "editable": true }, "outputs": [], "source": [ "MixedIntegerLinearProgram?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "M = MixedIntegerLinearProgram()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "deletable": true, "editable": true }, "outputs": [], "source": [ "x = M.new_variable(nonnegative=True)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "M.add_constraint(7*x[0] <= x[1] + x[2])\n", "M.add_constraint(5*x[1] <= 3*x[2])\n", "M.add_constraint(9*x[0] + 8 *x[1] + 7*x[2] == 27)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "deletable": true, "editable": true }, "outputs": [], "source": [ "M.set_objective(3*x[0] + 2*x[1] + x[2])" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "M.solve()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "M.get_values(x)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "deletable": true, "editable": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "M.get_backend()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "deletable": true, "editable": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "deletable": true, "editable": true }, "outputs": [], "source": [ "# to solve over rationals, just rerun the example by setting\n", "#\n", "# M = MixedIntegerLinearProgram(solver='PPL')\n", "#\n", "#######################################################\n", "#\n", "# or to use CBC\n", "# needs to install cbc first with\n", "#\n", "# $ sage -i cbc\n", "# $ sage -b\n", "#\n", "# and then\n", "#\n", "# M = MixedIntegerLinearProgram(solver='CBC')" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Solving over $\\mathbb{Q}[\\sqrt{5}]$\n", "--------------------------------------\n", "\n", "We consider the regular dodecahedron and maximize the linear functional $\\sqrt{5} x_0 + x_1 + x_2$ on it.\n", "\n", "(why is it not in the documentation!?)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "deletable": true, "editable": true }, "outputs": [], "source": [ "poly = polytopes.dodecahedron()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "poly" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "deletable": true, "editable": true }, "outputs": [], "source": [ "lp, x = poly.to_linear_program(solver='InteractiveLP', return_variable=True)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "lp" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "lp.show()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "deletable": true, "editable": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "K = poly.base_ring()\n", "K" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "deletable": true, "editable": true }, "outputs": [], "source": [ "sqrt5 = K.gen()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "sqrt5**2" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "lp.set_objective(sqrt5 * x[0] + x[1] + x[2]) " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "lp.solve()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "deletable": true, "editable": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "vals = lp.get_values(x)\n", "opt = vector((vals[0], vals[1], vals[2]))\n", "obj = vector((sqrt5, 1, 1))" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "vals" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "print opt" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "poly.plot(alpha=0.3) + \\\n", "point3d([opt], color='red', pointsize=50) +\\\n", "arrow(opt, opt+obj/2, color='yellow')" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "deletable": true, "editable": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "deletable": true, "editable": true }, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 8.1.beta3", "language": "", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.13" } }, "nbformat": 4, "nbformat_minor": 2 }