6

Consider the boolean quadric polytope, which is defined on a complete graph $G=(V,E)$ as:

$$QP = \{(x,z) \in \{0,1\}^{V+E} : x_ix_j=z_{ij} \}$$

Now we can generate for small examples with tools like porta, polymake the complete linear description. However the description becomes fast exponential increasing, which makes the output difficult to analyze and quickly makes the approach infeasible.

Now one of the reason the output becomes exponential is that there is a huge symmetry in this polytope, consider for example the facet class:

$$x_i \geq 0 \ \forall i \in V $$

Then the output of polymake would list each of these constraints, however one for example $x_1 \geq 0$ is enough, since the other follow by symmetry.

Is it possible to remove this symmetry from the polytope and be able to generate the complete reduced description (faster)?

user3680510
  • 3,655
  • 6
  • 26

1 Answers1

4

Have a look at PANDA. It's a new alternative to porta/polymake with some improvements. One of the features it has is the possibility for specifying symmetry properties to accelerate the computation. Section 2.3 (Exploitation of symmetry) of the paper provides relevant details (your example is also mentioned).

Edit: Here is the website where PANDA can be downloaded.

rasul
  • 2,140
  • 7
  • 23