Polytopes associated with symmetry handling

Abstract

This paper investigates a polyhedral approach to handle symmetries in mixed-binary programs. We study symretopes, i.e., the convex hulls of all binary vectors that are lexicographically maximal in their orbit with respect to the symmetry group. These polytopes turn out to be quite complex. For practical use, we therefore develop an integer programming formulation with ternary coefficients, based on knapsack polytopes arising from a single lexicographic order enforcing inequality. We show that for these polytopes, the optimization as well as the separation problem of minimal cover inequalities can be solved in almost linear time. We demonstrate the usefulness of this approach by computational experiments, showing that it is competitive with state-of-the-art methods and is considerably faster for specific problem classes.

Appendices

Appendix

A Visualization of the algorithm described in Theorem 23

In this section, we present an example for the application of the algorithm $\mathcal {A}$ described in the proof of Theorem 23. To this end, consider the permutation $\gamma = (1,4)(2,5,7,8,3,6)$ and the objective $w = (2,1,3,-\,3,-\,2,1,-\,2,0)^\top$. We extend w to $W = (w, \mathbb {O}{})$ as objective for $\mathrm {Q}_{\gamma }$. Figure 3a shows which entry in the second column of a vertex of $\mathrm {Q}_{\gamma }$ is equal to the entry in its first column.

Fig. 3

Visualization of the optimization algorithm over $\mathrm {Q}_{\gamma }$. a Visualization of $\gamma (X^1) = X^2$, b Implications of $c = 5$, c Row fixings above $c = 5$, d Fixings below $c = 5$

If $c = 4$, we want to determine a vertex x of $\mathrm {P}_{\gamma }$ which maximizes w and which has critical row $c = 4$ if considered as the vertex $X {\,:}{=\,}(x, \gamma (x))$ of $\mathrm {Q}_{\gamma }$. First, $\mathcal {A}$ detects that $X^1_4 = 1$ and $X^2_4 = 0$ because 4 is the critical row of X, and it analyzes which further entries have to be 1 or 0 due to the permutation property of the second column. Since $\gamma (4) = 1$, $\mathcal {A}$ concludes that $X^2_1 = 1$ holds. Furthermore, $X^1_1 = 1$ because row 1 is above the critical row 4 and thus, constant. Iteratively, $\mathcal {A}$ would set $X^2_4 = 1$ because $\gamma (1) = 4$. But this is a contradiction because $X^2_4$ is 0, since row 4 is critical. $\mathcal {A}$ detects this contradiction and terminates: row 4 cannot be critical.

If $c = 5$, $\mathcal {A}$ detects that $X^1_5 = 1$ and $X^2_5 = 0$. Since $\gamma (5) = 7$, we have $X^2_7 = 1$; similarly, because $\gamma ^{-1}(5) = 2$ and $\gamma ^{-2}(5) = 6$, 2 is the smallest power k of $\gamma ^{-1}$ such that $\gamma ^{-k}(5) \ge 5$. Hence, row 2 has to be a constant 0-row and $X^1_6 = 0$ because row 5 is critical. Figure 3b illustrates the implications from critical row 5.

Then, we fix the unfixed rows above the critical row. These rows are rows 1, 3, and 4. To this end, we compute the sets

$$\begin{aligned}&F_1 = \{(1,1), (4,2), (4,1), (1,2)\},\\&F_3 = \{(3,1),(3,2),(8,1),(6,2)\},\; \text {and}\\&F_4 = F_1. \end{aligned}$$

Fixing any $(i,j) \in F_1$ fixes all other entries in $F_1$ to the same value. Because $W^1_1 + W^2_1 + W^1_4 + W^2_4 = w_1 + w_4 = -1 < 0$ we can conclude that any vertex of $\mathrm {Q}_{\gamma }$ which maximizes W and which has critical row 5 has 0-s in rows 1 and 4. Similarly, fixing any $(i,j) \in F_3$ fixes all other entries in $F_3$ to the same value. Since $W^1_3 + W^2_3 + W^1_8 + W^2_6 = 3 > 0$ the entries in $F_3$ of each vertex of $\mathrm {Q}_{\gamma }$ which maximizes W and which has critical row 5 are equal to 1. This observation is visualized in Fig. 3c.

Finally, we have to set the unfixed entries below critical row 5. The only unfixed entries are (7, 1) and $(\gamma (7),2) = (8,2)$. Because $W^1_7 + W^2_8 = w_7 = -2 < 0$, we set $X^1_7 = X^2_8 = 0$. Now, all entries of X are fixed and a maximizer of W with critical row 5 is found, see Fig. 3d.

B Proof of Claim 3.4

In this section, we provide the missing proof of Claim 3.4

Claim

Every non-trivial facet F of $\mathrm {O}_{m}$ contains m vertices of $\mathrm {O}_{m}$ whose first columns are affinely independent and are not equal to $\mathbb {1}$. Moreover, F contains m vertices of $\mathrm {O}_{m}$ whose second columns are affinely independent and are not equal to 0.

Proof

Kaibel and Loos [30] showed that every non-trivial facet defining inequality of $\mathrm {O}_{m}$ is characterized by a vector $\kappa \in \{0,1,2,3\}^{m}$ with the following properties:

• there exists $i \in [m]$ such that $\kappa _j = 0$ for all $j \in \{i + 1, \dots , m\}$,

• $\kappa _j \ne 0$ for all $j \in [i]$, and

• $\kappa _1 = \kappa _i = 3$.

Define $\alpha = \alpha (\kappa ) \in \mathbb {R}^{m \times 2}$ via

$$\begin{aligned} \alpha _j = {\left\{ \begin{array}{ll} 0, &{} \quad \text {if }\; j > i,\\ 1, &{} \quad \text {if }\; j \in \{i-1, i\},\\ \alpha _{j+1}, &{} \quad \text {if }\; j< i - 1 \text { and } \kappa _{j+1} \ne 3,\\ 2\alpha _{j+1}, &{} \quad \text {if }\; j < i - 1 \text { and } \kappa _{j+1} = 3. \end{array}\right. } \end{aligned}$$

Then the corresponding facet defining inequality $\sum _{j = 1}^m (a_{j1}X_{j1} + a_{j2} X_{j2}) \le \beta$ is given by

$$\begin{aligned} (a_{j1}, a_{j2}) = {\left\{ \begin{array}{ll} (0,0), &{} \quad \text {if }\; \kappa _j = 0,\\ (-\alpha _j,0), &{} \quad \text {if }\; \kappa _j = 1,\\ (0,\alpha _j), &{}\quad \text {if }\; \kappa _j = 2,\\ (-\alpha _j, \alpha _j), &{}\quad \text {if }\; \kappa _j = 3, \end{array}\right. } \end{aligned}$$

and $\beta {\,:}{=\,}\sum _{j \,:\,\kappa _j = 2} \alpha _j$.

In the following, it suffices to show only the first part of the claim, because the second part follows by applying the map $x \mapsto 1 - x$ to all variables, exchanging the variables of the first and second column, and flipping the meaning of $\kappa _j = 1$ and $\kappa _j = 2$. Furthermore, it is sufficient to consider only those vectors $\kappa$ with $\kappa _m = 3$, cf. Loos [37, Lem. 3.62].

To prove the first part of the claim, define for every $j \in [m]$ the matrix $X^j$ as follows. If $j < m$, define

$$\begin{aligned} (X^j_{k1}, X^j_{k2}) {\,:}{=\,}{\left\{ \begin{array}{ll} (1,1), &{} \quad \text {if }\; k < j \text { and } \kappa _k = 2,\\ (1,0), &{} \quad \text {if }\; k = j,\\ (0,1), &{} \quad \text {if }\; k > j,\\ (0,0), &{} \quad \text {otherwise.} \end{array}\right. } \end{aligned}$$

For $j = m$, we define $(X^m_{k1}, X^m_{k2}) {\,:}{=\,}(1,1)$ if $k = m$ or $\kappa _k = 2$. Otherwise, we set $(X^m_{k1}, X^m_{k2}) {\,:}{=\,}(0,0)$.

These matrices are vertices of the orbisack. Moreover, the first columns of these matrices are affinely independent, because the support of the first column of $X^j$ is contained in [j] and $X^j_{j1} = 1$. By a careful consideration of all possible cases, one can show that $X^j$, $j \in [m]$, is contained in the facet associated with $\kappa$. In “Appendix C”, we provide some examples that give an intuition why the latter statement holds. But we refrain from providing the arguments in the corresponding case distinction. $\square$

C Illustration of the vertices constructed in Proposition 38

Table 5 illustrates the vertices constructed in the proof of Proposition 38 of the orbisack facets associated with $\kappa ^1 = (3,3,1,1,3,1,3)$, $\kappa ^2 = (3,3,2,2,3,2,3)$, and $\kappa ^3 = (3,3,2,1,3,2,3)$. The first column of the table provides the facet inequality of the corresponding vector $\kappa$. The remaining columns contain the vertices $X^1$, ..., $X^7$.

Table 5 Vertices of some orbisack facets that are constructed in the proof of Proposition 38

D Visualization of symmetry handling decisions

In this section, we explain the steps in our procedure that adds symmetry handling inequalities to a binary program. We denote with P(A, b, w) the binary program $\max \,\{ {w}^\top x \,:\,Ax \le b,\; x \in \{0,1\}^{\bar{n}}\}$, where $A \in \mathbb {R}^{m \times \bar{n}}$ and $b \in \mathbb {R}^m$ for some positive integers m and $\bar{n}$. Furthermore, we abbreviate the formulation symmetry group of P(A, b, w) with $\bar{\varGamma }$.

Due to Proposition 5, we treat each factor $\varGamma$ of $\bar{\varGamma }$ separately, and we classify a factor $\varGamma$ as essential if $\varGamma$ is acting as an orbitope on P(A, b, w) or if there is $n \in \mathbb {N}$ such that $\varGamma = \mathcal {S}_{n}$ or $\varGamma = \mathcal {C}_{n}$. Otherwise, we classify the factor as non-essential. In the latter case, we handle the symmetries of $\varGamma$ only if we expect that it is worthwhile to do so. Based on preliminary tests, we decided to handle non-essential symmetries if one of the following conditions hold. In this case, we set a parameter $\alpha \leftarrow 1$, otherwise we set $\alpha \leftarrow 0$.

• 1. If more than $95{\%}$ of the variables of P(A, b, w) are affected by $\varGamma$, we classify these problems as highly symmetric.

• 2. If the amount of affected variables lies between 5 and $95{\%}$, we handle non-essential symmetries if $\frac{\log _{10}|\varGamma |}{\text {number of generators}}$ is at most 0.55, because the number of generators in comparison to the number of elements in $\varGamma$ is not too small.

Algorithm 2 visualizes the procedure that determines which symmetry handling inequalities are added to P(A, b, w).