{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Graphs and linear programming\n", "\n", "This tutorial will guide you through linear programming in Sage with an emphasis on graph theory. It is intended for beginners.\n", "\n", "## What is linear programming (LP)?\n", "\n", "A linear program is the sum of two information:\n", "\n", "- A linear function, called the objective, which is to be maximized\n", " or minimized (e.g. 2 x - y)\n", "- Linear constraints on the variables (e.g. 3 x + y ≤ 2 and 5 x - 9 y = 1)\n", "\n", "The solver will then try to find a solution to the system of constraints such that the objective function is optimized, and return the values of the variables.\n", "\n", "**Exercise:**\n", "- Look at the documentation of `MixedIntegerLinearProgram`\n", "- Construct and solve the following linear program\n", "\n", " * objective (to be maximized) 2 x - y\n", " * constraint 1: 3 x + y ≤ 2\n", " * constraint 2: 2 x - 3 y ≤ 8\n", " * constraint 3: 8 x + y ≥ -8\n", "\n", "- Draw the polyhedron associated to the constraints" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## What is a Mixed Integer Linear Program (MILP) ?\n", "\n", "It is simply a Linear Program such that some variables are forced to take integer values instead of real values. This difference becomes very important when one learns that solving a Linear Program can be done in polynomial time while solving a general Mixed Integer Linear Program is usually NP-Complete (= it can take exponential time, according to a widely-spread belief that P is not equal to NP).\n", "\n", "**Exercise:**\n", "\n", "- Solve the same problem as in the previous exercise but using integer variables\n", "- Plot the polyhedron of constraints together with the integer points in its interior\n", "- Check that some of the corners are not lattice points and that the optimum is not reached on a vertex!" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Why is Linear Programming so useful ?\n", "\n", "Linear programming is very useful in many optimization and graph-theoretical problems because of its expressivity. Most of the time, a natural linear program can be easily written to solve a problem whose solution will be quickly computed thanks to the wealth of heuristics already contained in linear program solvers. It is often hard to theoretically find out the execution time of a Linear Program, though they give very interesting results in practice.\n", "\n", "For more information, you can consult the Wikipedia page dedicated to linear programming : http://en.wikipedia.org/wiki/Linear_programming" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Playing with graphs\n", "\n", "Our aim is now to illustrate some usage of mixed integer linear program for graphs.\n", "\n", "To build a graph (command `Graph`) or a digraph (command `DiGraph`) you just need to provide the adjacency as a dictionary. For example\n", "\n", " G = Graph({0: [1, 2, 3], 1: [3], 2: [0,1]})\n", "\n", "Once a graph is built you can access to many of its properties. Among them, we will mostly use\n", "\n", "- `G.num_verts()`: for the number of vertices\n", "- `G.num_edges()`: for the number of edges\n", "- `G.vertices()`: the list of vertices\n", "- `G.edges()`: the list of edges (together with labels)\n", "- `G.neighbors(v)`: the list of the neighbors of a vertex `v`\n", "- `G.plot()`: make a picture of the graph\n", "\n", "**Exercise:**\n", "\n", "- Build the graph proposed above and get various of its properties together with a picture (do not forget to access documentation and/or use tab completion)\n", "- Build a directed graph and do the same" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Prebuilt graphs\n", "\n", "Sage also come with a huge list of prebuilt graphs that are available as `graphs.NameOfTheGraph()` as example\n", "\n", " P = graphs.PetersenGraph() # the Petersen graph\n", " K = graphs.CompleteGraph(5) # the complete graph on 5 vertices\n", "\n", "and a bit of digraphs such as\n", "\n", " D = digraphs.DeBruijn(2,3) # the De Bruijn digraph on binary words of length 3" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Vertex Cover in a graph\n", "\n", "In the Vertex Cover problem, we are given a graph $G$ and we want to find a subset $S$ of its vertices of minimal cardinality such that each edge $e$ is incident to at least one vertex of $S$.\n", "\n", "
\n", "\n", "\n", "In order to achieve it, we define a binary variable $b_v$ for each vertex $v$. And minimize $$\\quad\\sum_{v \\in G} b_v$$\n", "subject to the constraints\n", "- $\\forall v \\in V(G)$, the variable $b_v$ is binary\n", "- $\\forall (u,v) \\in E(G),\\ b_u + b_v \\geq 1$\n", "\n", "\n", "**Exercise:**\n", "\n", "- Check that the MILP formulation is actually correct\n", "- Implement it in Sage and check it on some graphs" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Maximum matching in a Graph\n", "\n", "In the maximum matching problem, we are given a graph $G$, and we are looking for a set of edges $M$ of maximum cardinality such that no two edges from $M$ are adjacent.\n", "\n", "
\n", "\n", "We are considering a variable $b_e$ for each edge $e$ of the graph and maximize $$\\sum_{e \\in E(G)} b_e$$\n", "subject to the constraints\n", "- $\\forall e \\in E(G)$, the variable $b_e$ is binary\n", "- $\\forall v \\in V(G)$, we have $\\displaystyle \\sum_{(u,v) \\in E(G)} b_{uv} \\leq 1$\n", "\n", "**Exercise:**\n", "- Check that the MILP formulation is actually correct\n", "- Implement the maximum matching in Sage and check it on some graphs" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Maximum Independent Set\n", "\n", "A maximum independent set in a graph is a maximum set of vertices which are not connected to each other.\n", "\n", "
\n", "\n", "\n", "**Exercise:**\n", "- Find a MILP formulation for the maximum independent set problem\n", "- Implement this in Sage and check it on some graphs" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Hamiltoninan path\n", "\n", "We now explain how MILP can be used to solve a delicate problem: testing whether a graph is Hamiltonian. If you have a doubt about the definition, have a look at [wikipedia](https://en.wikipedia.org/wiki/Hamiltonian_path). This program is a little more subtle than the previous one since conditions are dynamically added to the solver.\n", "\n", "Let $G$ be a graph in which we want to find a Hamiltonian path (or disprove that such path exists). We consider a binary variable $b_e$ for each edge. As in the maximum matching we consider $H(b) = \\{e \\in E(G):\\ b_e = 1\\}$ as a subgraph of $G$.\n", "\n", "**Exercise:**\n", "- Formulate in terms of linear inequalities the fact that $H(b) = \\{e \\in E(G):\\ b_e = 1\\}$ should be a disjoint union of cycles.\n", "- Find a linear equality that forces $H(b)$ to pass through all vertices.\n", "- Could you find linear inequalities that express that $H(b)$ is connected?\n", "\n", "As you might have guess, connectivity is too many equations (with a lot of redundancy if not done carefully). The idea is to do not set these inequalities at the begining! We will just consider the MILP corresponding to a disjoint union of path $H$ that pass through all vertices. Then we will repeat the following loop\n", " 1. ask for a solution $H(b)$ of the current problem\n", " 2. if $H(b)$ is connected we are done\n", " 3. otherwise, $H(b)$ determines a [cut](https://en.wikipedia.org/wiki/Cut_%28graph_theory%29) and we add a linear constraint that forbids this particular cut\n", " \n", "**Challenge:** Write the above program!" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This worksheet has been compiled from [this very nice webpage of Nathann Cohen](http://www.steinertriples.fr/ncohen/tut/LP/) who sadly left Sage development. Some of the exercises actually correspond to how these problems are implemented in Sage. You can have a look at the source code of graphs." ] } ], "metadata": { "kernelspec": { "display_name": "SageMath", "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.10" } }, "nbformat": 4, "nbformat_minor": 1 }