extensions:polytropes

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision		 Previous revision
Next revisionBoth sides next revision
extensions:polytropes [2020/03/18 11:31] – [Examples] joswigextensions:polytropes [2020/04/02 11:58] – [Download] joswig
Line 1: Line 1:
-====== Polytropes ======+====== polytropes ======
  
 This is the software companion to the article "The tropical geometry of shortest paths" by This is the software companion to the article "The tropical geometry of shortest paths" by
-[[https://page.math.tu-berlin.de/~joswig/|Michael Joswig]] and [[http://people.math.binghamton.edu/schroeter/|Benjamin Schröter]], [[https://arxiv.org/abs/1904.01082|arXiv:1904.01082]]+[[https://page.math.tu-berlin.de/~joswig/|Michael Joswig]] and [[http://people.math.binghamton.edu/schroeter/|Benjamin Schröter]], [[https://arxiv.org/abs/1904.01082|arXiv:1904.01082]]. 
 +Ewgenij Gawrilow co-authors the code. 
  
 We study parameterized versions of classical algorithms for computing shortest-path trees. This is most easily expressed in terms of tropical geometry. Applications include the enumeration of polytropes, i.e., ordinary convex polytopes which are also tropically convex, as well as shortest paths in traffic networks with variable link travel times. We study parameterized versions of classical algorithms for computing shortest-path trees. This is most easily expressed in terms of tropical geometry. Applications include the enumeration of polytropes, i.e., ordinary convex polytopes which are also tropically convex, as well as shortest paths in traffic networks with variable link travel times.
Line 8: Line 9:
 ===== Download ===== ===== Download =====
  
-[[http://page.math.tu-berlin.de/~joswig/software/polymake/polytropes-0.1.tar.xz|polytropes-0.1.tar.xz]] [18 Mar 2020], for polymake version 4.0+[[http://page.math.tu-berlin.de/~joswig/software/polymake/polytropes-0.1.tar.xz|polytropes-0.1.tar.xz]] [18 Mar 2020], for the upcoming polymake version 4.1 (but mostly usable for 4.0, too).
  
 ===== Installation ===== ===== Installation =====
Line 20: Line 21:
 Suppose this ends up at ''/your/path/polytropes-0.1''.  Then you start up polymake.  Within the polymake shell do: Suppose this ends up at ''/your/path/polytropes-0.1''.  Then you start up polymake.  Within the polymake shell do:
 <code> <code>
-import_extension "/your/path/poyltropes-0.1";+import_extension "/your/path/polytropes-0.1";
 </code> </code>
 Do not forget to use an absolute path!  Afterwards you are good to run the code.  This import needs to be performed only once.  The reference to the extension is permanently stored in ''$HOME/.polymake/prefer.pl''.  For more details there is a [[user_guide/extend/extensions|guide to polymake's extension system]]. Do not forget to use an absolute path!  Afterwards you are good to run the code.  This import needs to be performed only once.  The reference to the extension is permanently stored in ''$HOME/.polymake/prefer.pl''.  For more details there is a [[user_guide/extend/extensions|guide to polymake's extension system]].
Line 28: Line 29:
 This extension contributes to the application ''graph''. This extension contributes to the application ''graph''.
  
-In the application ''graph'' you can create a directed graph whose weights are allowed to be intervals with nonnegative rational boundaries or $+\infty$.  That is, we are in the case of [i]seperated variables[/i].+In the application ''graph'' you can create a directed graph whose weights are allowed to be intervals with nonnegative rational boundaries or $+\infty$.  That is, we are in the case of //separated variables//.
  
 We construct Example 8 from the paper (see Figure 3, loc. cit.). We construct Example 8 from the paper (see Figure 3, loc. cit.).
Line 138: Line 139:
 The nonnegativity is always implicit. The nonnegativity is always implicit.
  
-The actual feasibility of a shortest path tree is [i]not[/i] checked here.+The actual feasibility of a shortest path tree is //not// checked here.
 The second solution (which is the one shown in Figure 3) is subject to the conditions $-3+x\geq 0$ and $1-x\geq 0$, i.e., $x \geq 3$ and $x\leq 1$, which is impossible. The second solution (which is the one shown in Figure 3) is subject to the conditions $-3+x\geq 0$ and $1-x\geq 0$, i.e., $x \geq 3$ and $x\leq 1$, which is impossible.
 The feasibility can be checked via an LP oracle. The feasibility can be checked via an LP oracle.
  
  • extensions/polytropes.txt
  • Last modified: 2021/01/12 14:34
  • by 127.0.0.1