Finding Facets Using Polymake: A Step-by-Step Guide for Mac Users

Yajun Lu
Feb 12, 2025
source: Polymake

Introduction to Polymake

Polymake is a powerful open-source software system designed for researching polytopes and related geometric structures. Developed by mathematicians Ewgenij Gawrilow and Michael Joswig, it has become an essential tool in computational geometry and mathematical research [1]. The software excels in analyzing geometric objects, particularly in computing facets of polytopes.

Step-by-Step Guide

1. Download and Install Polymake

Visit the official Polymake download page at: https://polymake.org/doku.php/download/start

Follow the installation instructions specific to your Mac system.

2. Launch Polymake

Open Terminal on your Mac and type:

polymake

This command launches the Polymake interactive shell.

3. Prepare Your Integer Programming Formulation

Before using Polymake, you’ll need to create a .lp file containing your Integer Programming (IP) formulation. You can use optimization solvers like Gurobi or others to write this file. For example, you might create a formulation for a maximum 2-robust 2-club problem [2] for the below graph:

      1
     / \
    2---3
     \ /
      4
     / \
    5---6
     \ /
      7

Maximize
  x1 + x2 + x3 + x4 + x5 + x6 + x7
Subject To
 R0: x1 + x2 - x3 <= 1
 R1: x1 - x2 + x3 <= 1
 R2: 2 x1 - x2 - x3 + 2 x4 <= 2
 R3: 2 x1 + 2 x5 <= 2
 R4: 2 x1 + 2 x6 <= 2
 R5: 2 x1 + 2 x7 <= 2
 R6: - x1 + x2 + x3 - x4 <= 1
 R7: x2 - x3 + x4 <= 1
 R8: 2 x2 - x4 + 2 x5 <= 2
 R9: 2 x2 - x4 + 2 x6 <= 2
 R10: 2 x2 + 2 x7 <= 2
 R11: - x2 + x3 + x4 <= 1
 R12: 2 x3 - x4 + 2 x5 <= 2
 R13: 2 x3 - x4 + 2 x6 <= 2
 R14: 2 x3 + 2 x7 <= 2
 R15: x4 + x5 - x6 <= 1
 R16: x4 - x5 + x6 <= 1
 R17: 2 x4 - x5 - x6 + 2 x7 <= 2
 R18: - x4 + x5 + x6 - x7 <= 1
 R19: x5 - x6 + x7 <= 1
 R20: - x5 + x6 + x7 <= 1
Bounds
Binaries
 x1 x2 x3 x4 x5 x6 x7
End

4. Load Your LP File into Polymake

Once you have your .lp file ready, use the following command in Polymake:

$p = lp2poly('/Users/yajunlu/Desktop/test.lp');

Note: Replace the file path with the actual path to your .lp file on your system.

5. View lattice points (Optional)

To see the lattice points of your polytope, use:

print $p->LATTICE_POINTS;

This command will display lattice points:

Lattice points:
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 1
1 0 0 0 0 0 1 0
1 0 0 0 0 1 0 0
1 0 0 0 0 1 1 1
1 0 0 0 1 0 0 0
1 0 0 0 1 1 1 0
1 0 0 0 1 1 1 1
1 0 0 1 0 0 0 0
1 0 1 0 0 0 0 0
1 0 1 1 1 0 0 0
1 1 0 0 0 0 0 0
1 1 1 1 0 0 0 0
1 1 1 1 1 0 0 0

6. Generate and Display Facet-Defining Inequalities

To obtain the facet-defining inequalities, execute these two commands:

$s = new Polytope(POINTS=>$p->LATTICE_POINTS, COORDINATE_LABELS=>$p->COORDINATE_LABELS);
print_constraints($s);

The expected output will show all facet-defining inequalities of your polytope as follows:

Facets:
0: x7 >= 0
1: x6 >= 0
2: x5 >= 0
3: -x2 + x5 - x6 - x7 >= -1
4: -x3 + x5 - x6 - x7 >= -1
5: -x2 - x5 >= -1
6: -x3 - x5 >= -1
7: -x3 - x6 >= -1
8: -x2 - x6 >= -1
9: -x1 + x2 - x3 + x5 - x6 - x7 >= -1
10: -x1 + x2 - x3 - x5 >= -1
11: -x1 + x2 - x3 - x6 >= -1
12: -x1 + x2 - x3 - x5 + x6 - x7 >= -1
13: -x1 - x2 + x3 + x5 - x6 - x7 >= -1
14: -x1 - x2 + x3 - x5 >= -1
15: -x1 - x2 + x3 - x6 >= -1
16: -x1 - x2 + x3 - x5 + x6 - x7 >= -1
17: -x3 - x5 + x6 - x7 >= -1
18: -x2 - x5 + x6 - x7 >= -1
19: x1 >= 0
20: -x1 - x2 + x3 + x4 - x5 - x6 + x7 >= -1
21: x3 >= 0
22: x2 >= 0
23: -x1 + x2 - x3 + x4 - x5 - x6 + x7 >= -1
24: x1 - x2 - x3 + x4 + x5 - x6 - x7 >= -1
25: x1 - x2 - x3 + x4 - x5 - x6 + x7 >= -1
26: x4 >= 0
27: x1 - x2 - x3 + x4 - x5 + x6 - x7 >= -1
28: -x1 + 2 x2 - x3 - x4 + 2 x5 - x6 - x7 >= -1
29: -x1 + 2 x2 - x3 - x4 - x5 + 2 x6 - x7 >= -1
30: -x1 + 2 x2 - x3 - x4 - x5 + x6 >= -1
31: -x1 + 2 x2 - x3 - x4 + x5 - x6 >= -1
32: -x1 - x2 + 2 x3 - x4 + 2 x5 - x6 - x7 >= -1
33: -x1 - x2 + 2 x3 - x4 - x5 + 2 x6 - x7 >= -1
34: -x1 - x2 + 2 x3 - x4 - x5 + x6 >= -1
35: -x1 - x2 + 2 x3 - x4 + x5 - x6 >= -1
36: -x2 + x3 - x4 + x5 - x6 >= -1
37: -x2 + x3 - x4 - x5 + x6 >= -1
38: x2 - x3 - x4 + x5 - x6 >= -1
39: x2 - x3 - x4 - x5 + x6 >= -1
40: -x2 + x3 - x4 - x5 + 2 x6 - x7 >= -1
41: x2 - x3 - x4 - x5 + 2 x6 - x7 >= -1
42: -x2 + x3 - x4 + 2 x5 - x6 - x7 >= -1
43: x2 - x3 - x4 + 2 x5 - x6 - x7 >= -1

Troubleshooting Tips

  • If Polymake doesn’t launch, verify that it’s properly installed and added to your system’s PATH
  • Ensure your .lp file is properly formatted and contains valid constraints
  • Check file permissions if you encounter access issues when reading the .lp file

References

[1] Gawrilow, E., & Joswig, M. (2000). polymake: a Framework for Analyzing Convex Polytopes. In Polytopes—Combinatorics and Computation (pp. 43-73). Birkhäuser, Basel.
[2] Lu, Y., Salemi, H., Balasundaram, B., & Buchanan, A. (2022). On fault-tolerant low-diameter clusters in graphs. INFORMS Journal on Computing, 34(6), 3181-3199.

Yajun Lu
Yajun Lu
Assistant Professor of Analytics & Operations Management

My research interests are broadly in Business Analytics, Healthcare Analytics and Operations, Graph-based Data Mining, Social Media Analytics, Network Optimization, and Artificial Intelligence.