### Introduction to Orbital Branching

#### by Derrick Stolee

Orbital branching is an example of a method that started in combinatorial optimization but has been applied for computations in pure combinatorics. In this post, we’ll introduce this method while in the context of generating combinatorial objects. The major difference between this perspective and the original goal is that we are generating all feasible solutions (which are probably rare) while the original applications were finding optimal solutions (and feasible solutions were plentiful).

*Disclaimer: This post is adapted from a chapter of my dissertation.*

A property on a combinatorial object can be expressed as a set of constraints on a set of 0/1-valued variables. For example, graphs can be stored as indicator variables with value 1 if and only if is an edge. Then, a constraint can be satisfied when the equality holds. If all constraints , then the graph corresponding to these variables is 4-regular. Thus, a property can be expressed as the conjunction of several constraints, where holds if and only if all constraints hold.

Orbital branching is a technique to solve symmetric constraint systems using branch-and-bound techniques by selecting orbits of variables for the branch instead of a single variable. Orstrowski, Linderoth, Rossi, and Smriglio introduced orbital branching and applied the technique to covering and packing problems. The authors implemented the branching procedure into the optimization framework MINTO. This integration allowed interaction with existing heuristics such as clique cuts and the commercial optimization software IBM ILOG CPLEX. They also generalized the technique to include knowledge of subproblems within the context of Steiner systems.

There are three main components to orbital branching. First, a description of the constraint system must be implemented. Tightly integrated subcomponents of the system include the symmetry model of the constraints and the presolver. The symmetry model consists of a graph with vertices corresponding to the variables along with vertices encoding the structure of the system. The automorphism group of is computed using `nauty`

. The presolver reduces the number of variables and constraints by recognizing dependencies. Second, the constraint propagation algorithm takes existing choices from the branch-and-bound and fixes variables with forced values. Third, a **branching rule** decides which orbit of variables is selected for the branch.

### Variable Assignments

We shall consider a constraint problem where is a function on variables which take value in . A vector is a **variable assignment**. If , we say that variable is **unassigned**. We can compare two assignments with if and only if for all either or .

**Example.** An **strongly regular graph** is a -regular graph on vertices so that if is an edge, then and have common neighbors and if is not an edge, then and have common neighbors. Let be a variable assignment on variables corresponding to if and only if the th unordered pair of vertices is an edge. (See ranking and unranking of sets.)

Thus, a variable assignment maps to a **trigraph** which is given by a vertex set and the pairs are partitioned into three sets: **black edges**, **white edges**, and **gray edges**, where black edges are “definitely edges”, white edges are “definitely nonedges” and gray edges are “undecided pairs”. Two trigraphs and can be compared as if the corresponding variable assignments and have . Trigraphs and variable assignments are useful data structures when searching for strongly regular graphs because nonedges are fundamental to the structure of the graph.

Let be the boolean function that encodes whether or not the given variable assignment corresponds to an strongly regular graph. For later examples, we shall consider , and to be fixed and define . **End Example.**

Our goal is to generate all possible vectors so that . We shall build these vectors starting at the empty assignment and assign values to the variables. A naïve approach would be to brute-force check every possible assignment. Instead, we shall employ constraint detection and constraint propagation techniques.

- Let be an algorithm that returns only if for all where we have . (That is, all possible extensions of have the property .)
- Let be an algorithm that on input returns a variable assignment so that for all where so that , then . (That is, all possible vectors that have the property also have .)

The efficiency and strength of and will depend on the property (and the user’s knowledge about the property ). At minimum, could return if and only if has no unassigned variables and . Further, could simply return . Using some structure of the function can allow more complicated (and helpful) functions.

**Example.** When searching for an strongly regular graph, we can guarantee a few properties. Let be a variable assignment and be the associated trigraph. Note that the maximum degree of a graph () and neighborhoods () are monotone functions on the edge set of trigraphs with respect to . The following implications are then immediate:

- If , then . Therefore, if , then cannot extend to a strongly regular graph.
- If , then . Therefore, if , then cannot extend to a strongly regular graph.
- If , then every pair has . Therefore, if is an edge in and then cannot extend to a strongly regular graph.
- If , then every pair has . Therefore, if is a nonedge in and then cannot extend to a strongly regular graph.

Thus, a possible algorithm for is to return whenever , , or for some pair . Further, a possible algorithm for is to place assignments on unassigned variables whenever these constraints are sharp:

- If has degree , then for any vertex where the pair is unassigned, make be a nonedge.
- If has non-degree\footnote{The \textit{non-degree} of a vertex is the number of nonedge pairs containing .} , then for any vertex where the pair is unassigned, make be an edge.
- If is an edge in and then whenever is a vertex with an edge and unassigned, make be a nonedge. Similarly, if is unassigned and is an edge, make be a nonedge.
- If is a nonedge in and then whenever is a vertex with an edge and unassigned, make be a nonedge. Similarly, if is unassigned and is an edge, make be a nonedge.

**End Example.**

Given algorithms for and , we can build a full search algorithm using **branch-and-bound**. One missing ingredient is the function which selects an index of an unassigned variable (with ). Such a selection could be arbitrary, but it could also be carefully selected. This algorithm allows for **dynamic variable ordering**, which changes which variable we shall assign next in hopes that certain constraints will become sharp and the algorithm can assign several new values in one step. The full branch-and-bound algorithm is given as in Algorithm 1.

Algorithm 1. |

if |

return |

end if |

if |

if |

output |

end if |

return |

end if |

call |

call |

return |

By initializing this recursive algorithm on the empty assignment , all possible feasible solutions with will be written to output.

While branch-and-bound is a complete algorithm, it has no concern for the symmetries of the objects represented by the variable assignments. That is, perhaps the property is invariant under a certain set of permutations and so we should only generate variable assignments up to isomorphism. The next section defines these symmetries.

### Constraint Symmetries

Let be a permutation of order . Given a vector , the vector has value . That is, acts on the variables. An **automorphism** of a constraint problem is a permutation so that for every vector , . The set of automorphisms of form a group, denoted .

**Example.** When the variable assignment corresponds to a trigraph (as in the case of strongly regular graphs), we consider a permutation to be a **colored isomorphism** between two trigraphs and if for all pairs , the color of in matches the color of in . A property is **invariant** under colored isomorphsims if for any two isomorphic trigraphs. Therefore, for a property that is invariant under colored isomorphisms, where maps a pair to . That is, any permutation of the vertices corresponds to a map of the pairs and is invariant under these permutations. **End Example.**

Since we shall be making changes to the variable assignment , we want to track the symmetries of the system with respect to the current variable assignment. Thus, let be the set of permutations of the variable set so that is invariant under all extensions of the given variable assignment, and a variable is mapped to a variable with the same value:

**Example.** Recall that we know how to compute the automorphisms of trigraphs.

We shall focus on the action this group on the variables. The **orbit** of a variable is the set . Using these symmetries and considering orbits of unassigned variables instead of single variables, we can extend branch-and-bound to be symmetry-aware and reduce the number of isomorphic duplicates.

### Orbital Branching

Given a partial variable assignment , we compute the colored automorphism group and use this action on the variables to compute orbits. Orbital branching extends the standard branch-and-bound technique by selecting an orbit of unassigned variables. From a selected orbit , there are two branches:

- Select a representative and assign the variable .
- For all representatives , assigne the variable .

Notice that if there are non-trivial automorphisms, then there exists an orbit of size at least two. This makes the second branch assign more than one variable in a given time. The reason this process works is that assigning for *any* representative leads to the same variable assignment up to isomorphism. Since trying any *one* variable a zero results in an isomorphic variable assignment, we can just try one and in the second branch we can set all of the variables to the other value. Figure 1 shows the difference between branch-and-bound and orbital branching.

Algorithm 2 gives a full description of the orbital branching method. The algorithm follows a similar pattern to Algorithm 1 but uses a subroutine, denoted , to select an orbit of unassigned variables instead of just a single variable.

Algorithm 2. |

if |

return |

end if |

if |

if |

output |

end if |

return |

end if |

call |

for all |

call |

return |

**Example.** In the case of variable assignments corresponding to trigraphs, the first branch in the orbital branching algorithm selects a pair from the orbit and assigns that pair to be a nonedge. No matter which representative pair is selected from the orbit, the resulting trigraph is isomorphic to any other choice of representative. Therefore, an arbitrary representative suffices. Also, any assignment of edges and nonedges to this trigraph so that one of the representatives becomes a nonedge is isomorphic to some trigraph where our selected representative is a nonedge. Therefore, after checking all extensions where this representative is a nonedge we may assume that every pair from the orbit is an edge for other extensions.

**Note.** The orbital branching procedure could easily change to allow that in one branch the variable is set to 1 instead of 0 and in the other branch all variables of the orbit are assigned the value 0. Also, the choice of which branch has which value can be a dynamic decision. In some problems, the variables are not binary-valued, and in this case we must select a single value to send to the whole orbit and the other values must be individually tested on the given variable.

### Branching Rules

In the previous description of the orbital branching algorithm, we left the algorithm for to be an arbitrary algorithm. An instance of this algorithm is called a **branching rule**, as it dictates which variables are assigned in the current branch. In the original work by Ostrowski et al., a lot of attention was given to these branching rules. One reason is that they were working with combinatorial optimization problems where the “bounding” part of branch-and-bound is particularly useful. Hence, several of the branching rules used a continuous relaxation of the problem as advice to choosing an orbit.

Since we mostly consider exhaustively generating all feasible solutions to a combinatorial problem where the constraints are rarely simple to describe in a continuous setting, we ignore the original branching rules. Instead, we focus on the example of searching over trigraphs for our rules.

**Example.** Suppose we wish to select an orbit of unassigned pairs from a trigraph . The following list contains a few potential branching rules along with positive and negative effects.

**LargestOrbit:**Select an orbit of highest order.**Pro:**Maximizes amount of change in second branch.**Con:**Does not concern constraints. Can quickly remove symmetry from the graph.

**LargestConnOrbit:**Maintain a set of vertices where every vertex in is contained in at least one assigned pair. Select an orbit where all pairs have both endpoints in (if possible) or at least one endpoint in (otherwise). From these orbits, select the one of largest order.**Pro:**Builds graphs by filling in all pairs from a given set first. Attempts to maximize change in second branch.**Con:**Some of the orbits may be small when is nearly full, resulting in low symmetry for later orbit calculations.

**MaxDegreeSumOrbit:**Select an orbit of pairs where the degree and non-degree sums of and are maximum. Break ties by orbit size.**Pro:**Attempts to maximize tightness of constraints by fully specifying the edges and nonedges at vertices of high degree and nondegree.**Con:**The first branch leads to a single vertex with high nondegree, which leads to the orbit sizes decreasing rapidly.

### Orbital Branching and Canonical Deletion

From our example of searching for strongly regular graphs, we see that orbital branching can be used to search for combinatorial objects. This brings the technique into the combinatorial realm, where it can compete with canonical deletion. Orbital branching may seem weaker than canonical deletion, since we have no guarantee that every object is visited at most once. Even worse, when using orbital branching and you generate an object with no automorphisms, the technique becomes no better than brute-force search. However, there are situations when orbital branching is significantly more efficient than canonical deletion.

One reason the orbital branching technique may work better than canonical deletion is that the techniques have strengths in two opposite areas. Canonical deletion focuses on removing all isomorphic duplicates, but there is no known method to incorporate constraint propagation with canonical deletion. Orbital branching is built to naturally allow constraint propagation, but it only reduces the number of isomorphic duplicates.

Another reason is that the augmentation step for orbital branching involves exactly one automorphism calculation, and two augmentations. In canonical deletion, every possible augmentation must be attempted (up to isomorphism) and checked to see if it is a canonical augmentation. Depending on the augmentation step, this can be a very costly operation.

In the next post, we will investigate an extension of the orbital branching technique with a customized augmentation for a specific problem. This augmentation integrates well with orbital branching, but our attempt to integrate it with canonical deletion was less efficient. Our implementation with orbital branching is a very efficient algorithm; by executing the algorithm, we discovered several new graphs with the desired properties.

### References

G. L. Nemhauser, M. W. P. Savelsbergh, and G. C. Sigismondi. MINTO, a Mixed INTeger Optimizer. *Operations Research Letters*, 15:47–58, 1994.

J. Ostrowski, J. Linderoth, F. Rossi, and S. Smriglio. Orbital branching. In *IPCO ’07: Proceedings of the 12th international conference on Integer Programming and Combinatorial Optimization*, volume 4513 of LNCS, pages 104-118, Berlin, Heidelberg, 2007. Springer-Verlag.

J. Ostrowski, J. Linderoth, F. Rossi, and S. Smriglio. Constraint orbital branching. In A. Lodi, A. Panconesi, and G. Rinaldi, editors, *Integer Programming and Combinatorial Optimization, 13th International Conference, IPCO 2008*, Bertinoro, Italy, May 26-28, 2008, Proceedings, volume 5035 of Lecture Notes in Computer Science. Springer, 2008.

J. Ostrowski, J. Linderoth, F. Rossi, and S. Smriglio. Solving large Steiner triple covering problems. *Technical Reports of the Computer Sciences Department, University of Wisconsin-Madison*, (1663), 2009.

S. G. Hartke, D. Stolee, Uniquely -Saturated Graphs, *The Electronic Journal of Combinatorics*, 19(4), P6, 41pp. 2012.