{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "Michael Joswig (TU Berlin): Algorithmic Discrete Mathematics III, Winter 2018/19" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Solve a first linear program" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "$P = new Polytope(INEQUALITIES=>[[0,1,0,0],\n", "[1,-1,0,0],[0,0,1,0],[1,0,-1,0],[0,0,0,1],[1,0,0,-1]]);" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "$P->add(\"LP\",new LinearProgram(LINEAR_OBJECTIVE=>[0,1,1,1]));" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
Click here for additional output
\n", "
\n",
       "polymake: used package cdd\n",
       "  cddlib\n",
       "  Implementation of the double description method of Motzkin et al.\n",
       "  Copyright by Komei Fukuda.\n",
       "  http://www-oldurls.inf.ethz.ch/personal/fukudak/cdd_home/\n",
       "\n",
       "
\n", "
\n" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "print $P->LP->MINIMAL_VALUE;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "There is more information available." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0\n", "1 0 0 0\n", "{5}\n" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
Click here for additional output
\n", "
\n",
       "polymake: used package ppl\n",
       "  The Parma Polyhedra Library (PPL): A C++ library for convex polyhedra\n",
       "  and other numerical abstractions.\n",
       "  http://www.cs.unipr.it/ppl/\n",
       "\n",
       "
\n", "
\n" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "map { print $P->LP->$_, \"\\n\"}\n", "(\"MINIMAL_VALUE\", \"MINIMAL_VERTEX\", \"MINIMAL_FACE\");" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0:1 1 0 0\n", "1:1 1 1 0\n", "2:1 1 1 1\n", "3:1 1 0 1\n", "4:1 0 0 1\n", "5:1 0 0 0\n", "6:1 0 1 0\n", "7:1 0 1 1\n" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "print rows_labeled($P->VERTICES);" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1 0 0 0" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "print $P->VERTICES->[5];" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5:1 0 0 0\n" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "map { print $_, \":\", $P->VERTICES->[$_], \"\\n\" }\n", "(@{$P->LP->MINIMAL_FACE});" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Look at a slightly more interesting example\n", "This time we maximize." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "$Q = new Polytope(POINTS=>\n", "$P->VERTICES->minor(~[2],All));" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": [ "$Q->add(\"LP\",\n", "new LinearProgram(LINEAR_OBJECTIVE=>[0,1,1,1]));" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1:1 1 1 0\n", "2:1 1 0 1\n", "6:1 0 1 1\n" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "map { print $_, \":\", $Q->VERTICES->[$_], \"\\n\" }\n", "(@{$Q->LP->MAXIMAL_FACE});" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " Q\n", " \n", " \n", "\n", "\n", "\n", "\t\t
\n", "\t\t\t
\n", "\t\t\t\tTransparency\n", "\t\t\t\t\n", "\t\t\t
\n", "\t\t\t\n", "\t\t\t
\n", "\t\t\t\tRotation\n", "\t\t\t\t
\n", "\t\t\t\t\t
x-axis
\n", "\t\t\t\t\t
y-axis
\n", "\t\t\t\t\t
z-axis
\n", "\t\t\t\t\t\n", "\t\t\t\t
\n", "\n", "\t\t\t\t
Rotation speed
\n", "\t\t\t\t\n", "\n", "\t\t\t
\n", "\n", "\n", "\t\t\t
\n", "\t\t\t\tDisplay\n", "\t\t\t\t
\n", "\t\t\t\t\t
\n", "\t\t\t\t\t
Labels
\n", "\t\t\t\t
\n", "\t\t\t
\n", "\n", "\n", "\t\t\t
\n", "\t\t\t\tSVG\n", "\t\t\t\t
\n", "\t\t\t\t\t
\n", "\t\t\t\t\t\t Download
\n", "\t\t\t\t\t\t New tab
\n", "\t\t\t\t\t
\n", "\t\t\t\t\t\n", "\t\t\t\t
\n", "\t\t\t
\n", "\n", "\t\t
\t\n", "\t\t\n", "\t\t\n", "
\n", "\n", "\n", "\n", "\n", "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "
Click here for additional output
\n", "
\n",
       "polymake: used package threejs\n",
       "   Three.js is a lightweight cross-browser JavaScript library/API used to create and display animated 3D computer graphics on a Web browser.\n",
       "   See http://github.com/mrdoob for the source code.\n",
       "\n",
       "
\n", "
\n" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "$Q->VISUAL->MIN_MAX_FACE;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# LP feasibility" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "print $P->FEASIBLE;" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1 0 0 0" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "print $P->VALID_POINT;" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1 1/2 1/2 1/2" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "print $P->REL_INT_POINT;" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "polymake", "language": "polymake", "name": "polymake" }, "language_info": { "codemirror_mode": "perl", "file_extension": ".pl", "mimetype": "text/x-polymake", "name": "polymake" } }, "nbformat": 4, "nbformat_minor": 2 }