{ "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", "