A brief tutorial on PORTA

What does PORTA do?

PORTA is a software package for analyzing polyhedra. One problem it can solve is:

Problem: Find H-representation of the convex hull of some given points
Input: a set S of points in n-dimensional space
Output: a minimal inequality system defining conv(S).

Minor note: If conv(S) is not full dimensional, PORTA will report some equations too.

For a longer tutorial on PORTA and Polymake, see the slides by Marc Pfetsch.

Example: Independent Sets

Consider the 5-vertex cycle graph C_5 on vertex set {1,2,3,4,5}. We can list all of its stable/independent sets:

ALL_STABLE_SETS = { {}, {1}, {2}, {3}, {4}, {5}, {1,3}, {1,4}, {2,4}, {2,5}, {3,5} }.

We can write these stable sets in terms of their characteristic vectors:

0 0 0 0 0
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 1 0 0
1 0 0 1 0
0 1 0 1 0
0 1 0 0 1
0 0 1 0 1

Here, each ROW represents a stable set. We can give PORTA this collection ALL_STABLE_SETS, and it will return the following inequality description of conv(ALL_STABLE_SETS):

( 1) -x1 <= 0
( 2) -x2 <= 0
( 3) -x3 <= 0
( 4) -x4 <= 0
( 5) -x5 <= 0
( 6) +x4+x5 <= 1
( 7) +x3+x4 <= 1
( 8) +x2+x3 <= 1
( 9) +x1 +x5 <= 1
( 10) +x1+x2 <= 1
( 11) +x1+x2+x3+x4+x5 <= 2

Inequalities (1)–(5) are the nonnegativity bounds; (6)–(10) are the edge inequalities; (11) is an odd-hole inequality.

How do I use PORTA?

  1. Download version 1.4.1
  2. Create the .poi file* which contains all the points in S. See the formatting in the example file StableSet_5cycle.poi
  3. Open command prompt and navigate to the folder porta-1.4.1\win32\bin\
  4. Run PORTA on the .poi file. For example, put the .poi file in the folder porta-1.4.1\win32\bin\ and use the command traf.bat StableSet_5cycle.poi
  5. PORTA will show its progress to the command prompt window and then create an output file. In our case, the output file is StableSet_5cycle.poi.ieq. The command prompt window will look like this:cmd.png

(*) The .poi file can be time consuming to create by hand, and there are a few ways to create them automatically. In my case, I usually write some simple code that enumerates all 0-1 vectors and writes the feasible vectors to a file. In my experience, PORTA can only handle instances with roughly 20 dimensions, so this enumeration procedure is not the bottleneck.

Advertisements

One thought on “A brief tutorial on PORTA

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s