## Constraint Programming Approaches for the Discretizable Molecular Distance Geometry Problem

Moira MacNeil ∗ 1 and Merve Bodur † 1

1 Department of Mechanical and Industrial Engineering, University of Toronto

## Abstract

The Distance Geometry Problem (DGP) seeks to find positions for a set of points in geometric space when some distances between pairs of these points are known. The so-called discretization assumptions allow us to discretize the search space of DGP instances. In this paper, we focus on a key subclass of DGP, namely the Discretizable Molecular DGP, and study its associated graph vertex ordering problem, the Contiguous Trilateration Ordering Problem (CTOP), which helps solve DGP. We propose the first constraint programming formulations for CTOP, as well as a set of checks for proving infeasibility, domain reduction techniques, symmetry breaking constraints and valid inequalities. Our computational results on random and pseudo-protein instances indicate that our formulations outperform the state-of-the-art integer programming formulations.

Keywords. Discretizable Molecular Distance Geometry, discretization order, Contiguous Trilateration Ordering, constraint programming, combinatorial optimization

## 1 Introduction

In its essence, Distance Geometry seeks to find positions for a set of points in geometric space when some distances between pairs of these points are known [8, 17]. This has many applications, including in molecular geometry, where Nuclear Magnetic Resonance (NMR) spectroscopy gives estimates of some interatomic distances and the three-dimensional structure must be determined [8]. Here, the points to be positioned are the atoms of a molecule. As seen in Figure 1a, we have a set of five atoms and know some pairwise distances between them. We would like to give the atoms coordinates in Euclidean space so that the distances are preserved; a possible three-dimensional mapping of these atoms is pictured in Figure 1b. In wireless sensor localization, the positions of wireless sensors such as smartphones must be determined using the estimated distance between sensors, but there is also a fixed component of the network such as routers [13]. Other applications include astronomy, robotics, statics and graph rigidity, graph drawing, and clock synchronization [8, 17, 13]. More recent applications have arisen from a new variant of the Distance Geometry Problem (DGP), namely dynamical DGP, including air traffic control, crowd simulation, multirobot formation, and human motion retargeting [17].

The input to the DGP can be represented as a graph, say G , where the vertices are the points we would like to position and weighted edges represent known distances between two points. Formally, we give the definition from [8].

∗ m.macneil@mail.utoronto.ca

† bodur@mie.utoronto.ca

Figure 1: (a) A set of points, 1 , 2 , . . . , 5, and known pairwise distances. (b) An embedding of these points in three dimensions.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-c5df20d4-c845-49b4-908e-fc5a9e293417.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-2f24851c-3a08-4eec-8898-8474edb8466d.jpg)

Definition 1 (Distance Geometry Problem) . Given an integer K &gt; 0 , and a simple, undirected graph G = ( V E , ) with edge weights w : E → (0 , ∞ ) , find a function x : V → R K such that for all { u, v } ∈ E :

$$\| x ( u ) - x ( v ) \| = w ( u, v ).$$

If this function x exists, it is called a realization for G , we also refer to the realization as an embedding of G . For example, Figure 1b shows a realization with K = 3 for the graph in Figure 1a, which does not have a realization when K = 2. We assume G is connected, since determining if a disconnected graph has a valid realization is equivalent to determining if its connected components have a realization [1]. We also assume the norm in Definition 1 is the Euclidean norm for the remainder of this paper, however this need not be the case. We also note that there exists a form of the problem where the function need not satisfy the strict equality in Definition 1, but rather must satisfy w u,v l ( ) ≤ ‖ x u ( ) -x v ( ) ‖ ≤ w u ( u, v ) for lower and upper bounds on the weights w u,v l ( ) and w u ( u, v ) respectively; this is called the interval DGP [3, 10].

The DGP with integer weights is NP -Complete for K = 1 and NP -Hard for K &gt; 1 [19], motivating the need for solution methods that are able to solve the problem in practice. Solution methods for the DGP include nonlinear programming, semi-definite programming, and the geometric build-up methods [17, 13, 15, 6]. If the distances between all pairs of vertices in G are known, i.e., G is complete, and we assume a solution exists in R K , there is a procedure for finding the realization by solving a series of linear equations [8, Chapter 3].

In most applications, the input graph is not complete, i.e., not all pairwise distances are known. In such a case, there exists an iterative procedure to position the vertices. In this procedure, we begin by choosing K vertices for which all pairwise distances are known; without loss of generality, we may position them at any coordinates which satisfy all their pairwise distances. Next, we choose a vertex with enough pairwise distances (at least K ) relative to the previously positioned vertices and fix its position using this information. We repeat, fixing vertices with at least K pairwise distances to the previously fixed vertices, until we have a realization. This procedure is the idea behind the branch-and-prune (BP) algorithm, whose success depends on choosing the right fixing order [8, 13, 15, 16]. Thus we first aim to find the order in which the BP algorithm should iterate over vertices [9]. The class of DGP instances possessing such an order is called Discretizable DGPs

(DDGPs). Otherwise, there may still be a realization, but the instance does not have enough distance information to determine one using the BP algorithm; as such it could be more difficult to find. We note that the input to these discretized ordering problems is an unweighted graph, and the output is a vertex order which is given as input together with the actual pairwise distances to the BP algorithm to find a realization. We direct the reader to [8, 13] for a formal definition and more detailed explanation of DDGPs and the BP algorithm.

In this paper, we study a key subclass of DDGPs, namely the Discretizable Molecular Distance Geometry Problem (DMDGP) [8] for which the literature is quite limited, as compared to other DDGPs. The ordering problem associated with DMDGP is the Contiguous Trilateration Ordering Problem (CTOP). Taking an unweighted graph as input, CTOP searches for an ordering of the vertices that ensures the first K vertices are pairwise adjacent and each subsequent vertex in the order is adjacent to the K immediately previously ranked vertices. The motivation for solving CTOP, instead of a relaxation of the problem, comes from the key application of realizing protein backbones with NMR data, since a certain structure is required to compute interatomic distances using covalent bond lengths and angles between them. These orders also have desirable properties: an order that is a solution to CTOP exhibits symmetries in the BP tree, so to find all solutions for a DMDGP the BP algorithm only needs to be applied to find a single solution and the rest can be enumerated using symmetry [8, Chapter 5]. There are other ordering problems associated with DDGPs, one of the most commonly studied being the Discretizable Vertex Ordering Problem (DVOP) which relaxes the need for vertices to be adjacent to the immediately previous vertices to any vertex of lower rank. We remark that the solution to CTOP is a solution to DVOP but the converse is not true.

DVOP has been shown to be polynomially solvable via a greedy algorithm in fixed dimension [7]. Moreover, integer programming methods have been used to find DVOP orders which are optimal with respect to some measure of their BP tree size [18], and algorithms finding partial orders that optimize the BP search space have been proposed [4]. In contrast to DVOP, CTOP is shown to be NP -complete and several integer programming formulations have been proposed to solve it on small instances [1]. In [14], the same underlying graph structure as one of the integer programming formulations of [1] is used and an order is constructed using a path in this graph. The algorithm is applied directly to small protein instances and the authors note it cannot be extended to large molecules. As such, we consider [1] the only work of comparison for our study.

The BP algorithm was first proposed for CTOP in [9], and in [2] answer set programming was shown to improve the performance of the BP algorithm for CTOP. Furthermore, DMDGP vertex orders with repeated vertices, called re-orders, are considered [10], their computational complexity is analyzed [1] and further studied in detail [11].

The rest of the paper is organized as follows. In Section 2, we present in detail the CTOP and review two existing integer programming (IP) formulations from the literature. In Section 3, we introduce three novel constraint programming (CP) formulations for CTOP. We then present, in Section 4, a structural study of CTOP which may eventually aid in its solution. Finally, in Section 5, we present a computational study which compares the CP and IP models, and which demonstrates the current utility and drawbacks of the structural findings.

We note that an overview of our paper, namely the models from the literature as well as our proposed models and structural ideas, is provided in Table 2 of Appendix D.

## 2 Preliminaries

In this section, we introduce the common notation used in the paper, provide the problem definition and briefly present the existing formulations for the problem.

## 2.1 Notation

glyph[negationslash]

All sets are denoted calligraphically. Let G = ( V E , ) be an undirected graph, where V is the set of vertices and E is the set of edges. The adjacency matrix of G is denoted by A , i.e., A v,u = 1 if and only if edge { u, v } ∈ E . Denote the neighbourhood of a vertex v as N ( v ), i.e., N ( v ) = { u ∈ V : { u, v } ∈ E} . Thus v / ∈ N ( v ) and the degree of v is d v ( ) = |N ( v ) . | We let G [ V ′ ] = ( V ′ , E ′ ) be the subgraph of G induced by V ′ ⊆ V , and thus E ′ = {{ u, v } ∈ E : u, v ∈ V } ′ . A clique , K , in G is a set of vertices { v , v 1 2 , . . . , v |K| } ⊆ V such that { v , v i j } ∈ E for all v , v i j ∈ K such that v i = v j . Similarly, a stable set , SS , in G is a set of vertices { u , . . . , u 1 |SS| } ⊆ V such that { u , u i j } ∈ E / for all u , u i j ∈ SS . We define an adjacent predecessor of a vertex v ∈ V as u ∈ V with { u, v } ∈ E such that u precedes v in a vertex order, and we define a contiguous predecessor of a vertex v ∈ V as u ∈ V with { u, v } ∈ E , such that there is no w ∈ V with { w,v } ∈ E / between v and u in the vertex order. Thus, u is an adjacent predecessor that immediately precedes v in the order, meaning there is no non-adjacent vertex between u and v in the vertex order.

For a, b ∈ Z + , a ≤ b , we introduce the notation [ a ] = { 0 1 , , . . . , a } and [ a, b ] = { a, a +1 , . . . , b } . If a &gt; b , then [ a, b ] = ∅ , similarly if a &lt; 0, then [ a ] = ∅ . Indices follow these conventions: indices start at 0, so that the possible positions of a vertex order are [ |V| 1]. We let |V| = n , and use |V| in relation to vertices and n in relation to ranks, i.e., positions, of a vertex order.

Finally, we introduce the set V d K,K [ + ] δ = { v ∈ V : d v ( ) ∈ [ K,K + ] δ } for some fixed positive integer δ , the set of vertices with degrees in [ K,K + ]. δ

## 2.2 Problem Definition

Given an integer dimension K , the Discretizable Molecular Distance Geometry Problem (DMDGP) [1] is the problem of finding a realization in R K given a simple, connected, undirected graph instance, G = ( V E , ), possessing a total order of its vertices that satisfies the following:

- (i) the first K vertices in the order form a clique in the input graph G , and
- (ii) each vertex with rank ≥ K has at least K contiguous predecessors . That is, for each vertex at position k ∈ [ K,n -1] along with the vertices at positions [ k -K,k -1] form a ( K +1)-clique in the input graph.

We refer to a total order that satisfies (i) and (ii) as a DMDGP order , and a clique satisfying (i) as the initial clique . We say an instance for which a DMDGP order exists is feasible , otherwise it is infeasible. The problem of determining whether a DMDGP order exists for G is known as the Contiguous Trilateration Ordering Problem (CTOP) [1]. An instance of CTOP, i.e., an integer K &gt; 0 and a simple, undirected, connected graph G = ( V E , ), will be denoted ( G = ( V E , ) , K ) or simply ( G,K ). Cassioli et al. [1] proved CTOP is NP -complete.

We can restate points (i) and (ii) of the definition using a key property of the problem structure, as mentioned in [1]:

Definition 2 (DMDGP Order) . Given an integer dimension K , a DMDGP order is a total order of the vertices of a simple, connected, undirected graph G = ( V E , ) , so that the order forms a series of ( K +1) -cliques which overlap by at least K vertices.

We note that there may be extra edges between vertices than those that form the overlapping cliques. This important property is depicted in Figure 2b for Example 1. Considering this overlapping clique structure, we refer to the first of those overlapping cliques as the initial ( K +1) -clique .

Figure 2: (a) A graph instance which is feasible for CTOP with K = 2. (b) Overlapping cliques of the order( v , v 4 2 , v 3 , v 1 , v 5 , v 0 ).

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-bf06972e-086a-47f5-91a2-6b5bbd104ae1.jpg)

Example 1. The graph given in Figure 2a with K = 2 is a feasible instance for CTOP. A possible DMDGP order is ( v , v 4 2 , v 3 , v 1 , v 5 , v 0 ) . Clearly, since they are adjacent { v , v 4 2 } form a clique, v 3 is adjacent to both of its immediate predecessors: v , 4 and v 2 , so { v , v 4 2 , v 3 } form a ( K +1) -clique in the input graph. Similarly, v 1 is adjacent to v , 2 and v 3 , forming a ( K +1) -clique in the input graph and so on.

## 2.3 Existing Integer Programming Models

Prior to this work, Cassioli et al. [1] present three integer programming (IP) formulations for CTOP. Below we summarize their properties, while we provide their full details for completeness in Appendix A.

- · The vertex-rank formulation ( IP VR ): They introduce |V|× n binary variables indicating vertexrank assignment. Then, the model contains ( |V| + n )-many 1-1 assignment constraints and ( |V| × n )-many clique constraints.
- · The clique digraph formulation ( IP CD ): They enumerate all ordered cliques of size ( K +1) in G , define a clique digraph D with vertices as those ordered cliques and arcs for pairs of cliques that suitably overlap to follow each other in the order (as in Figure 2b). We note D is exactly the pseudo de Bruijn graph structure described in [14]. Then, the CTOP solution corresponds to a path in D . This IP model has digraph arc variables, first clique and last clique variables, and precedence variables 1 for vertices in G .
- · The unordered clique relaxation ( IP RELAX ): They relax the strict clique ordering constraints of the clique digraph formulation, and solve this relaxation as a first check for the existence of a DMDGP order. The benefit of this formulation is that it reduces the number of variables in ( IP CD ), because we have reduced the worst case number of vertices in the D by a factor of ( K +1)!. When a solution to ( IP RELAX ) is found, it must be verified as this solution does not necessarily yield a DMDGP order. The verification is a simple check to ensure the linear order solution forms a DMDGP order. The strength in this formulation is that if ( IP RELAX ) is infeasible, there is no DMDGP order for the instance.

Regarding the vertex-rank formulation ( IP VR ), we prove that its LP relaxation is always feasible.

1 In [1], the variables for predecessors are given as w uv , we believe this is a typo that the variables are in fact their y uv variables which are our p uv variables in the version provided in Appendix A.2.

Proposition 1. The LP relaxation of ( IP VR ) on any instance G = ( V E , ) with K ≥ 2 is feasible.

$$P r o o f. \, \text{See Appendix A.1.}$$

This observation can be taken as a sign of the ( IP VR ) model being weak. In fact, we observe in our computational experiments that especially for infeasible instances, a large number of branchand-bound nodes are processed due to LP relaxations (and cuts driven on them) not being strong enough to prune infeasible branches early on.

On the other hand, we note that the clique digraph model (its relaxation) mostly suffers from the large number of ordered (unordered) cliques, and hits either the time or memory limit in our numerical experiments.

Lastly, we note that as mentioned in [1], ( IP VR ) works better for feasible instances, while ( IP CD ) works better for infeasible instances. However, none of them scale well with the size of the input graph, which motivates our work on developing alternative formulations and study of the structure of DMDGP orders.

## 3 Constraint Programming Models

Constraint Programming (CP) is a natural approach to distance geometry ordering problems since CTOP is a Constraint Satisfiability Problem (CSP) where the optimal solution is one that merely satisfies all constraints [12]. Unlike Constraint Optimization Problems where the optimal solution minimizes or maximizes some objective function subject to the constraints, CSPs do not have an objective function. CP has been shown to work well for problems with a permutation structure [20] and allows the leveraging of global constraints such as AllDifferent. To our knowledge, no CP model for CTOP has ever been proposed. The flexibility of CP allows for three possible formulations for CTOP.

The first formulation follows naturally from ( IP VR ), from [1]. We define integer variables r v equal to the rank of vertex v ∈ V in the order.

$$( \mathbb { C P } ^ { \text{RANK} } ) \colon \, & \text{AllDifferent} ( r _ { 0 }, r _ { 1 }, \dots, r _ { | \mathcal { V } | - 1 } ) & & ( 1 a )$$

glyph[negationslash]

$$| r _ { u } - r _ { v } | \geq K + 1 & & \forall \ u, v \in \mathcal { V } \ s. t. \ u \neq v, \{ u, v \} \notin \mathcal { E } & & ( 1 b )$$

$$r _ { v } \in [ n - 1 ] & & \forall \ v \in \mathcal { V } & & ( 1 c )$$

Using the global constraint AllDifferent (1a), we enforce that each vertex has a unique rank. Together with the domain constraints, (1c), this is equivalent to the one-to-one assignment constraints, in ( IP VR ), since each rank has a possible domain of [ n -1] and we are enforcing the constraint over all the rank variables which are indexed by the vertices, i.e., |V| = n variables. To enforce clique constraints, (1b), we use the idea that if two vertices do not have an edge between them, they cannot be in the same ( K +1)-clique. In other words their ranks must have a difference of at least K + 1. This constraint completely models the clique constraints and the predecessor constraints since if their rank difference is ≤ K then vertices u and v must be in the same clique which contradicts there being no edge between them. We note constraints (1b) can also be expressed using a minimum distance constraint, however our experiments show that the constraints as stated above had better performance.

Secondly, we present what is called a dual formulation in CP [20], where the values and variable meanings are swapped. Let integer variable v r represent the vertex in position r of the order and let table( E ) denote the table which contains a tuple for each edge in E .

$$( \text{CP} ^ { \text{VERTEX} } ) \colon \text{AllDifferent} ( v _ { 0 }, v _ { 1 },.., v _ { n - 1 } )$$

$$& ( v _ { i }, v _ { j } ) \in \text{table} ( \mathcal { E } ) & & \forall \ i \in [ 0, n - K - 1 ], j \in [ i + 1, i + K ] & & ( 2 b ) \\ & v _ { r } \in [ | \mathcal { V } | - 1 ] & & \forall \ r \in [ n - 1 ] & & ( 2 c )$$

In (2a) we enforce that each rank has a unique vertex, again using AllDifferent. To enforce the clique and predecessor constraints (2b), we use the CP notion of table constraints . These are global constraints that can be seen as an extension of domain constraints for a set of decision variables, where only certain predefined value combinations are allowed for those variables. Explicitly capturing some relationships between variables, they lead to improved propagation in the CP solver. In Constraints (2b), in order to ensure the overlapping clique structure required, we enforce that for any pair of ranks that differ by at most K , the vertices assigned to these positions in the order must be adjacent in G , thus they should correspond to the two endpoints of an edge in G . Finally, (2c) enforces the domain of the variables.

The last CP model is the result of combining the rank and vertex models into a single model by channelling the variables using an inverse constraint . It uses the constraints for predecessors and cliques from both formulations. This is useful because redundant constraints may actually help CP solvers perform more inference and discover feasible solutions in a shorter amount of time. Having defined v and r variables as before, the combined model is as follows:

$$( \mathbb { C P } ^ { \text{COMBINED} } ) \colon AllDifferent(v_{0},v_{1},..,v_{n-1} )$$

glyph[negationslash]

$$v \, \text{and} \, \text{values as you, use common use in as inova.} \\ \mathbb { P } \text{COMBINED} \, \colon \text{AllDifferent} ( v _ { 0 }, v _ { 1 },.., v _ { n - 1 } ) & & ( 3 a ) \\ & \text{AllDifferent} ( r _ { 0 }, r _ { 1 },.., r _ { | \mathcal { V } | - 1 } ) & & ( 3 b ) \\ & | r _ { u } - r _ { v } | \geq K + 1 & & \forall \, u, v \in \mathcal { V } \, s. t. \ u \neq v, \{ u, v \} \not \in \mathcal { E } & & ( 3 c ) \\ & ( v _ { i }, v _ { j } ) \in \text{table} ( \mathcal { E } ) & & \forall \, i \in [ 0, n - K - 1 ], j \in [ i + 1, i + K ] & & ( 3 d ) \\ & \text{inverse} ( r, v ) & & & & ( 3 e ) \\ & r _ { v } \in [ n - 1 ] & & \forall \, v \in \mathcal { V } & & ( 3 f ) \\ & v _ { r } \in [ | \mathcal { V } | - 1 ] & & \forall \, r \in [ n - 1 ] & & ( 3 g ) \\ \text{information} \, \text{ the inverse constraint} \, ( 3 e ) \text{ enforces the relation} \, ( r. \, = i ) = ( n. \, = i ) \text{ which also}$$

In this formulation, the inverse constraint (3e) enforces the relation ( r u = ) j ≡ ( v j = u ), which also makes the AllDifferent constraints in the vertex and rank models redundant. However we include them in the model, as when using the appropriate CP parameters they improve the results.

## 4 Structural Analysis of CTOP

In this section we present a study of the structure of DMDGP orders that we believe can lead to improvements for the formulations presented in Section 3. We present these structural findings as checks for infeasible instances, procedures for reducing the domains and breaking symmetries in DMDGP orders, and a class of valid inequalities.

## 4.1 Infeasibility Checks

We begin the discussion of the structure of CTOP by introducing some simple checks which will immediately indicate if an instance ( G,K ) is infeasible. The first check arises from the fact that every vertex needs at least K neighbours to be a part of a ( K +1)-clique.

Infeasibility Check 1 (Minimum Degree) . Given (G, K), if ∃ v ∈ V such that d v ( ) &lt; K then G does not have a DMDGP order for K .

Similarly, it is possible to determine a lower bound on the number of edges in G .

Proposition 2. Given (G, K), the minimum number of edges in G to have a DMDGP order is ( |V| 1 2 ) K -1 2 K 2 .

Proof. See B.1.

Proposition 2 leads to a second check for infeasibility.

Infeasibility Check 2 (Minimum Edges) . Given (G, K), if |E| &lt; ( |V| 1 2 ) K -1 2 K 2 then this instance is infeasible.

Example 2. The graph in Figure 3 is infeasible with K = 2 and K = 3 . For K = 2 , the instance passes Infeasibility Check 1 as every vertex has at least two neighbours. However Infeasibility Check 2 proves it is infeasible as the graph has |E| = 8 and the minimum number of edges for K = 2 is (6 -0 5)2 . -0 5(2 . 2 ) = 9 . For K = 3 , we can prove this instance is infeasible using Infeasibility Check 1 since d v ( 4 ) = 2 .

Figure 3: A graph which is infeasible for CTOP with K = 2 and K = 3.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-82aba746-d815-44fb-914b-f6666cb6bf5d.jpg)

Cassioli et al. [1] establish a lower bound on the degree of a vertex, which depends on its position in the order. If a vertex has degree K then it can only be placed in the first or last position, since it can only appear in a single ( K +1)-clique. If there are more than two vertices with degree exactly K the instance must be infeasible as there are only two available positions for these vertices. Similarly, there are four positions available for a vertex with degree K + 1; ranks 0 1 , , n -2 , n -1, so if there are more than four vertices with degree K +1, the instance is infeasible. This argument can be extended to the frequency of all vertices of degree strictly less than 2 K . We formalize the argument of Cassioli et al. [1] as Infeasibility Checks. We introduce the set V d K,K [ + ] δ = { v ∈ V | d v ( ) ∈ [ K,K + ] δ } for some fixed positive integer δ , to help express these arguments. We call vertices v with d v ( ) &lt; 2 K small degree vertices and vertices v with d v ( ) ≥ 2 K large degree vertices .

Infeasibility Check 3 (Upper Bound on Small Degree Vertices) . Given an instance (G, K), if ∃ δ ∈ [ K -1] such that ∣ ∣ V d K,K [ + ] δ ∣ ∣ ≥ 2( δ +1) + 1 then this instance is infeasible.

Example 3. Consider the graph in Figure 4a with K = 3 . We will see that it is infeasible by Infeasibility Check 3. Note that this instance cannot be proved infeasible by Infeasibility Check 1 but can be proved infeasible by Infeasibility Check 2. Since K = 3 , we have δ ∈ [1 , 2] . First let δ = 1 , we have

$$\mathcal { V } ^ { d [ 3, 4 ] } = \{ v _ { 0 }, v _ { 1 }, v _ { 2 }, v _ { 3 }, v _ { 4 } \}$$

and ∣ ∣ V d [3 4] , ∣ ∣ = 5 . The right-hand side of the expression in Infeasibility Check 3 with δ = 1 is

$$2 ( 1 + 1 ) + 1 = 5$$

and so we are able to say this instance is infeasible.

(a) A graph that is infeasible for CTOP with K = 3. (b) A graph that is infeasible for CTOP with K = 2.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-568ff328-2a46-4964-971a-5ab2e15146ad.jpg)

Figure 4: Two graphs that are infeasible for CTOP.

Similarly, we have a lower bound on the number of vertices with larger degree. Since the central ( n -2 K ) vertices in the order are in at least 2 K cliques, they must all have degree of at least 2 K , meaning there must be enough vertices with large degree to occupy these ( n -2 K ) positions.

Infeasibility Check 4 (Lower Bound on Large Degree Vertices) . Given (G, K), with n ≥ (2 K +1) , if ∣ ∣ V d [2 K,n -1] ∣ ∣ ≤ n -(2 K +1) then the instance is infeasible.

Example 4. Consider the graph in Figure 4b with K = 2 . We will see that it is infeasible by Infeasibility Check 4. Note that this instance cannot be proven infeasible by Infeasibility Check 1 or by Infeasibility Check 2. We have n = 5 = 2 K +1 and so V d [4 4] , = ∅ thus ∣ ∣ V d [4 4] , ∣ ∣ = 0 . We also have n -2 K -1 = 0 , and so we are able to say this instance is infeasible.

## 4.2 Domain Reduction

We are able to exploit some structural characteristics of CTOP to help prune variable domains in the CP formulations. Let the domain of an integer variable x be given by D x .

First, we extend the lower bounds on the degree of a vertex given by Cassioli et al. [1] to set the domains for rank variables. As observed previously, a DMDGP order is a series of overlapping cliques of size (at least) K +1. In the minimal case, the first and last vertices in the order are in exactly one clique, the second and second to last vertices are in two cliques, and so on. The central ( |V| 2 K ) vertices are in at least 2 K cliques. From this we can infer the minimum number of neighbours required by a vertex at a given rank.

Domain Reduction Rule 1 (Domain Reduction for Small Degree Vertices) . Given an instance (G, K), we can define the domain for the rank variables as follows:

$$\mathcal { D } _ { r _ { v } } = \begin{cases} [ d ( v ) - K ] \cup [ n - 1 - ( d ( v ) - K ), n - 1 ] & \text{ if } d ( v ) < 2 K \\ [ n - 1 ] & \text{ otherwise} \end{cases}$$

Example 5. Consider the graph in Figure 5 with K = 2 . It has two vertices with degree strictly less than 2 K : v 0 and v 4 . By Domain Reduction Rule 1 we can reduce the domain of both vertices so that their new domains are D r v 0 = { 0 1 4 5 , , , } and D r v 4 = { 0 5 , } .

We are able to extend domain reduction to the vertices that are adjacent to small degree vertices. The intuition is that if a vertex has small degree, the position of its neighbours cannot be too far from that vertex. If the position of a small degree vertex v ∗ has already been limited, its neighbours must be within the first or the last d v ( ∗ ) vertices of the order since they are all connected to v ∗ .

Domain Reduction Rule 2 (Domain Reduction for Neighbourhood of Small Degree Vertices) . Given an instance (G, K), with n ≥ (2 K +1) , for all v ∗ ∈ V d K, [ 2 K -1]

Figure 5: A graph instance feasible for CTOP with K = 2, to illustrate Domain Reduction Rule 1.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-bf066e3f-b36f-47cb-901a-014ceb9089ae.jpg)

$$\mathcal { D } _ { r _ { v } } = [ d ( v ^ { * } ) ] \cup [ n - 1 - d ( v ^ { * } ), n - 1 ] \ \forall \ v \in \mathcal { N } ( v ^ { * } ).$$

Example 6. Consider the graph in Figure 6 with K = 2 . For Domain Reduction Rule 2, we have V d [2 3] , = { v , v 0 7 } . The neighbours of v 7 are v 5 and v 4 . Since they both have degree greater than 2 K , their domains would not have been reduced by Domain Reduction 1. We reduce their domains as follows

$$\mathcal { D } _ { r _ { v _ { 5 } } } = \mathcal { D } _ { r _ { v _ { 4 } } } = \{ 0, 1, 2, 5, 6, 7 \}.$$

For the neighbours of v 0 , we notice that [ d v ( ∗ )] ∪ [ n -1 -d v ( ∗ ) , n -1] = [ n -1] , so we will not be able to reduce their domains.

Figure 6: A graph instance feasible for CTOP with K = 2, to illustrate Domain Reduction Rule 2.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-650834a6-048b-46f5-aee3-701a71e3a3fc.jpg)

## 4.3 Symmetry Breaking

As observed in [1], reversing a DMDGP order also gives a DMDGP order. We establish that these are not the only symmetries present in DMDGP orders, and present strategies for breaking these symmetries. We begin by a simple condition to break the reverse symmetry. First, notice that if there is a single vertex that has degree K without loss of generality we can fix its position to 0. If there is a second vertex with degree K we can fix its position to n -1, noting that there are at most two vertices of degree K in a DMDGP order due to Infeasibility Check 3.

$$\begin{array} { l } \text{Symmetry Breaking Condition 1 } ( \text{Degree K} ). \text{ If $\mathcal{V}^{[K,K]} = \{v_{i}$} \}, \text{ then let r} _ { v _ { i } } = 0. \text{ If $\mathcal{V}^{[K,K]} =$} \\ \{ v _ { i }, v _ { j } \}, \text{ then let r} _ { v _ { i } } = 0 \text{ and } r _ { v _ { j } } = n - 1. \end{array}$$

Next, we observe that if two vertices have the same neighbourhood excluding each other, they are interchangeable in the DMDGP order since they will have exactly the same contiguous predecessors. This guarantees a DMDGP order, since the only condition we need to meet to preserve the order

if we interchange two vertices is ensuring that they have the appropriate contiguous predecessors. We call this symmetry pairwise symmetry , which can be broken by imposing an arbitrary order on the pair of such symmetric vertices. Ideally, we would identify a large set of such vertices and order them. However, identifying such vertex sets can be computationally expensive. We instead identify two types of vertex sets that will allow for easy detection and breaking of pairwise symmetry. Specifically, we consider stable sets and cliques in the input graph.

Symmetry Breaking Condition 2 (Stable Set) . For a stable set SS = { v , v 1 2 , . . . , v k } ⊆ V such that N ( v i ) = N ( v j ) ∀ v , v i j ∈ SS we enforce that r v 1 &lt; r v 2 &lt; · · · &lt; r v k .

Symmetry Breaking Condition 3 (Clique) . For a clique K = { v , v 1 2 , . . . , v k } ⊆ V such that N ( v i ) \ K = N ( v j ) \ K , ∀ v , v i j ∈ K we enforce that r v 1 &lt; r v 2 &lt; · · · &lt; r v k .

In our experiments, we examine only cliques of size three or less, since we are usually unable to find large cliques satisfying Condition 3. Furthermore, we are able to conditionally extend these symmetry breaking conditions to include more vertices. Consider, for example, two vertices v and u whose neighbourhoods differ only by one vertex w ∈ N ( v ). If in the DMDGP order w is at least K +1 positions away from v , the edge connecting them is not necessary to enforce precedence in the order, that is, w is not an contiguous predecessor of v and vice versa. In this case we can essentially consider u and v as having the same neighbourhood and so can impose symmetry breaking on them. For some set S ⊆ V we denote N S ( ) = ∪ v ∈S N ( v ) \ S , the set of all vertices, outside of S that are adjacent to a vertex in S .

Symmetry Breaking Condition 4 (Extended Stable Set) . Let SS be a stable set meeting Condition 2 or a single vertex not in any stable set meeting Condition 2. For a vertex v ∈ V\ SS∪N SS ( ( )) such that N ( v ) \ N ( SS ) = { w } we enforce the logical constraints:

$$| r _ { v } - r _ { w } | \geq K + 1 \implies r _ { v } < r _ { u } \, \forall \, u \in \mathcal { S S }.$$

If we have enforced an ordering for SS already, we need only add the constraint

$$| r _ { v } - r _ { w } | \geq K + 1 \implies r _ { v } < r _ { v _ { 1 } }.$$

Symmetry Breaking Condition 5 (Extended Clique) . Let K be a clique meeting Condition 3 or a single vertex not in any clique meeting Condition 3. For a vertex v ∈ N K ( ) such that ( N ( v ) ∪ { v } ) \ ( N K ∪K ( ) ) = { w } we enforce the logical constraints

$$| r _ { v } - r _ { w } | \geq K + 1 \implies r _ { v } < r _ { u } \, \forall \ u \in \mathcal { K }.$$

Finally, if we have not been able to break any symmetry via any of the previous ways we can arbitrarily choose two vertices and impose an order on them.

Symmetry Breaking Condition 6 (Arbitrary) . For any v , v 1 2 ∈ V enforce that r v 1 &lt; r v 2 .

An example of the strength of symmetry breaking with K = 2 can be found in Appendix C. In our experiments, we first test for Symmetry Breaking Conditions 2 and 3 and then for Symmetry Breaking Conditions 4 and 5, breaking the symmetry where possible. If none of these conditions are met, we test for symmetry using Symmetry Breaking Condition 1, because it is unlikely we will have a vertex with degree exactly K if n is large. Finally, if all previous Symmetry Breaking Conditions have failed, we break the symmetry using Symmetry Breaking Condition 6.

## 4.4 A Class of Valid Inequalities

Next, we develop the structure of a class of valid inequalities for CTOP. We note that the focus of this study is not the practical application of these valid inequalities but the underlying structural analysis that leads to them. We proceed with the following intuition: if we identify some subset S ⊆ V such that the induced subgraph of S does not have a DMDGP order, the entire set S cannot appear consecutively in the order.

If for a given instance, ( G,K ), we are able to identify subsets S ⊆ V whose induced graphs, G [ S ], do not have DMDGP orders for K , we can add cuts to enforce that the difference between the maximum rank and the minimum rank of any element in S is at least |S| . Let r max , r min denote the maximum rank and the minimum rank of any vertex in S , respectively. The valid inequality is

$$r _ { m a x } - r _ { m i n } \geq | \mathcal { S } |.$$

We can improve this cut by examining the vertex in S with the smallest degree in the induced subgraph. Let E S [ ] be the edge set of G [ S ], and let δ miss S ( v ) = |{ u ∈ S\{ } | v ( v, u ) / ∈ E S }| [ ] , i.e., the number of edges with one endpoint at v ∈ S missing from G [ S ] and let δ miss S = max v ∈S δ miss S ( v ). If K &gt; |S|δ miss S , the difference between the maximum rank and the minimum rank must be greater than δ miss S + K , because the v ∈ S which has δ miss S , cannot be in a clique with δ miss S of the vertices in S , so we need at minimum δ miss S extra vertices between the vertices of S in the order. Otherwise, if K ≤ |S| δ miss S , the difference in ranks must be greater than |S| which is the inequality (4). So, the valid inequality is

$$r _ { \max } - r _ { \min } \geq \max \{ | \mathcal { S } |, \delta _ { \mathcal { S } } ^ { \min s s } + K \}.$$

Example 7. For the graph in Figure 7 with K = 3 , consider S = { v , v 0 3 , v 4 , v 5 } where G [ S ] has no DMDGP order since |E S | [ ] = 4 and Infeasibility Check 2 gives a lower bound of 6 edges for a DMDGP order. We have

$$\delta _ { \mathcal { S } } ^ { m i s s } = \max \{ \delta _ { \mathcal { S } } ^ { m i s s } ( v _ { 0 } ), \delta _ { \mathcal { S } } ^ { m i s s } ( v _ { 3 } ), \delta _ { \mathcal { S } } ^ { m i s s } ( v _ { 4 } ), \delta _ { \mathcal { S } } ^ { m i s s } ( v _ { 5 } ) \}$$

$$\delta _ { \mathcal { S } } ^ { m i s s } = \max \{ 2, 0, 1, 1 \}$$

so we have max {| S , δ | miss S + K } = max 4 2 + 3 { , } = 5 . Thus (5) gives:

$$r _ { m a x } - r _ { m i n } \geq 5$$

which is stronger than the original (4) ,

$$r _ { m a x } - r _ { m i n } \geq 4.$$

Note that this may not have been the case with a different choice of S .

The task of finding subsets of vertices S so that the subgraph induced by S does not have a DMDGP order is as difficult as determining if the whole graph has a DMDGP order. Thus, we would like to find sets of vertices with the most edges missing in their induced subgraph. As the sets with the most missing edges are stable sets, we can consider stable sets in G as candidate S sets. For any stable set SS , no pair of vertices can appear in the same ( K + 1)-clique. Thus, each pair of vertices in SS needs to have a difference in their ranks of at least K +1, meaning the minimum rank and maximum rank must have a difference of ( |SS| 1)( K + 1). The inequality becomes

$$r _ { m a x } - r _ { m i n } \geq ( | \mathcal { S } \mathcal { S } | - 1 ) ( K + 1 ).$$

Figure 7: Graph with DMDGP order ( v , v 5 4 , v 3 , v 2 , v 1 , v 0 ) for K = 3.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-b45ce90e-61b7-4ad0-9f29-8b4c202edc4f.jpg)

Example 8. Using the graph from Figure 7 and K = 3 , consider SS = { v , v 0 5 } . The inequality (6) is:

$$r _ { m a x } - r _ { m i n } & \geq ( 2 - 1 ) ( 3 + 1 ) \\ r _ { m a x } - r _ { m i n } & \geq 4$$

This observation also yields a simple check for infeasibility.

Infeasibility Check 5. Given ( G,K ) , if the size of the maximum stable set in G is greater than n K +1 +1 , we can immediately say G does not have a DMDGP order with K .

Proposition 3. The inequalities (5) and (6) are incomparable.

Proof. See B.2.

Example 9. Take the wheel graph W 7 , as pictured in Figure 8, with K = 3 . The maximum stable sets are { 1 3 5 , , } and { 2 4 6 , , } which have size 3 . The right-hand side of the inequality in Infeasibility Check 5 is 7 3+1 +1 = 2 75 . ≤ 3 . Thus we can say immediately that this instance is infeasible.

Figure 8: A wheel graph with seven vertices, W 7 .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-b6f7d58a-097f-484d-9add-233ffa48f0e8.jpg)

In fact, we are able to generalize this for all wheel graphs.

Proposition 4. For any wheel graph, W n , with K ≥ 2 , if n is odd and n ≥ K +1 K -1 or if n is even and n ≥ 2 K +1 K -1 there is no DMDGP order.

$$P r o o f. \, \text{See B.3}.$$

Finally, we define these valid inequalities so that they may be added to the ( CP RANK ) and ( CP COMBINED ) formulations. Given a stable set SS ⊆ V , and the rank variables r v we have two options to implement the valid inequalities, as follows:

$$\max \{ r _ { v } | v \in \mathcal { S S } \} - \min \{ r _ { v } | v \in \mathcal { S S } \} \geq ( | \mathcal { S S } | - 1 ) ( K + 1 )$$

$$\text{MinDistance} ( \{ r _ { v } | v \in \mathcal { S } \mathcal { S } \}, K + 1 )$$

where the constraint (8) is a minimum distance constraint which ensures that all variables it acts upon take values at least K +1 apart from each other.

## 5 Computational Results

## 5.1 Experimental Setup

To solve the IPs we use the solver IBM ILOG CPLEX version 12.8.0 and to solve the CPs we use IBM ILOG CP Optimizer version 12.8.0. All models were implemented in C++ and run on MacOs with 16GB RAM and a 2.3 GHz Intel Core i5 processor, using a single thread. The default IP and CP parameters were used with the exception of in ( CP COMBINED ) where extended inference was invoked on the AllDifferent constraints. We use K = 3 for all experiments as this is the value of K frequently used in applications. The time limit is set to 7200 seconds. (We also tested the small random instances with K = 4 and K = 5; their results are provided in Tables 12 and 13 of Appendix E, respectively. We note the results were similar to those with K = 3.)

## 5.2 Instances

We perform our numerical experiments on a test data set consisting of randomly generated graphs 2 and pseudo-protein graphs . 3

Random Instances Wedivide the random test set into small instances , having n ∈ { 20 25 , , . . . , 60 } and the expected edge density (measured as D = 2 |E| n n ( -1) ) in { 0 3 . , 0 5 . , 0 7 . } , and medium-sized instances which have n ∈ { 65 70 , . . . , 100 } and the expected edge density in { 0 2 . , 0 3 . , 0 4 . , 0 5 . } . For each n , density pair, we generate three graph instances using the dense gnm random graph() method in the NetworkX Python package [5], which chooses a graph uniformly at random from the set of all graphs with n vertices and m edges. These are Erd˝s-R´ enyi random o G n,M ( ) graphs.

Table 1 presents a summary of the instances. We remark that a portion of the instances were unsolved by any method; we denote these as unsolved instances.

Table 1: Random graph instances.

|        | n      | D               | #           | Instances   | # Feasible # Infeasible   | # Unsolved   |
|--------|--------|-----------------|-------------|-------------|---------------------------|--------------|
| small  | 20-60  | 0.3 0.5 0.7     | 27 27 27    | 0 20 27     | 27 7 0                    | 0 0 0        |
| Total  |        |                 | 81          | 47          | 33                        | 0            |
| medium | 65-100 | 0.2 0.3 0.4 0.5 | 24 24 24 24 | 0 0 13 24   | 24 10 0 0                 | 0 14 11 0    |
| Total  |        |                 | 96          | 37          | 34                        | 25           |

We remark that for the small instance data set, all 27 graph instances with D = 0 3 were . infeasible and all 27 graph instances with D = 0 7 were feasible. . When D = 0 5, . we have 7 instances which are infeasible, all of which have n = 20 , n = 25 or n = 30, the 20 feasible instances have n ≥ 30. For medium-sized instances, preliminary results showed all instances with D &gt; 0 5 . were feasible and solved in less than a second. For this reason we focus our study on instances

2 Random instances can be found at https://sites.google.com/site/mervebodr/home/DMDGP\_Instances.zip . 3 Pseudo-protein instances can be found at https://gitlab.insa-rennes.fr/Jeremy.Omer/MinDouble .

with D ≤ 0 5, which give more insights into the solution methods. . The 24 instances with D = 0 2 . were infeasible and the 24 instances with D = 0 5 were feasible. . The instances with D = 0 3 and . D = 0 4 were more difficult to solve. . For instances with D = 0 3, we found 10 infeasible instances, . those with n = 65 70 75 80, with all others unsolved. , , , For medium-sized instances with D = 0 4, . 13 instances were feasible with 11 others unsolved.

Pseudo-Protein Instances The pseudo-protein instances are similar to those used in [18] and were provided by the authors of that paper. They are generated using existing instances of the Protein Data Bank, which are cut to the required number of vertices and then reduced in density by randomly removing edges. This test data set has 209 instances with vertices in { 30 40 50 60 , , , } and expected edge density in [0 03 0 12]. . , . We remark of these pseudo-protein instances 192 are infeasible and 17 are feasible.

## 5.3 Computational Results and Discussion

In this section, we provide our observations based on a thorough computational study. All the detailed experimental result tables are provided in Appendix E. Here, we summarize our main findings by first outlining the results, without the addition of improvements from Section 4, of the novel CP formulations as compared to the IP formulations from the literature. Then in Sections 5.4 and 5.5 we present a preliminary study of the structural findings and valid inequalities, respectively.

We begin by noting that the IP formulations from the literature do not perform well against the CP formulations, which can be seen in detail in Table 3 of Appendix E. ( IP CD ) is able to solve instances with D = 0 3 and . n ≤ 40 in less than a second. These are also the instances that are infeasible. However, for higher densities, and as n increases, ( IP CD ) either hits the time limit or memory limit with 50% of the instances hitting the time or memory limit for ( IP CD ), due to the large number of ordered cliques for larger and more dense instances. On average the instances have 165 875 ordered cliques, with the smallest number of ordered cliques being 48 and the largest being , 1 406 256 cliques. Table 5 of Appendix E shows that ( , , IP RELAX ) has performance similar to ( IP CD ), performing best when the number of vertices is small and when the density is low. For n ≥ 30, ( IP RELAX ) is unable to solve any feasible instance (all of which have D = 0 5 or . D = 0 7) without . running out of time or memory. In fact, when the time limit is hit, we are still in the root node of the tree, for instances with n ≥ 50. Even when we relax the ordering constraints on the cliques, we still have a large number of unordered cliques. The smallest number of unordered cliques for an instance is 2 and the largest is 58 , 594, on average an instance has 6 , 911 unordered cliques. ( IP VR ) begins to hit the time limit at n = 25 and for n ≥ 35 it is only able to solve one instance with D &lt; 0 7. . This confirms the observations of [1], but we have also shown that neither ( IP CD ) nor ( IP VR ) scale well.

We next compare our CP formulations with the vertex-rank IP formulation ( IP VR ) of [1]. In Figure 9, we provide performance profiles for the solutions times of different models on small instances. Note that solution times are given in a logarithmic scale. We observe that the CP formulations all outperform ( IP VR ). For small feasible instances, as seen in Figure 9a, ( CP RANK ) is able to solve 29 instances in less than a second. However, for feasible instances ( CP COMBINED ) and ( CP VERTEX ) perform the best overall, with ( CP VERTEX ) solving one more instances than ( CP COMBINED ) within the time limit. The performance profile for small infeasible instances in Figure 9b shows that ( CP COMBINED ) has the best performance on these instances.

Table 3 of Appendix E also reveals that ( CP RANK ) is able to solve instances with D = 0 7 . in less than a second, however, it begins to hit the time limit for n ≥ 35 when D = 0 3. . For D = 0 5, ( . CP RANK ) is able to solve instances but is almost always outperformed by ( CP COMBINED )

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-3b5ccd9c-f4c7-453b-a5bb-f15575cab94a.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-23932003-1304-4b1f-8915-77033a75b546.jpg)

- (a) Small feasible instances
- (b) Small infeasible instances

Figure 9: Solution times of the models for small instances.

and ( CP VERTEX ). We also remark that after 25 vertices, with D = 0 5, the number of choice points . for solving with ( CP RANK ) exceed one million for all but two instances.

Overall, we conclude lower density instances are more challenging for the CP models. However, high density ( D = 0 7) is trivial even with 60 vertices. . For these reasons, we focus on densities less than or equal to 0 5, . but increase the number of densities considered. Due to their poor performance, we exclude the IPs from further study. We now direct our focus to the CP models for medium-sized instances.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-74421617-aa70-47db-b7f6-07bfde825b98.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-f722871d-1a2e-4a36-96f2-85bcb1eccef8.jpg)

- (a) Medium-sized feasible instances
- (b) Medium-sized infeasible instances

Figure 10: Solution times of the constraint programming models for medium-sized instances.

The performance profiles for the solutions times of different models on medium-sized instances are given in Figure 10 and the detailed results table can be found in Table 4 of Appendix E. We observe that ( CP RANK ) is outperformed by ( CP COMBINED ) and ( CP VERTEX ) in both the feasible and infeasible cases; it is unable to solve any infeasible instances. In the feasible case, ( CP VERTEX ) solves 6 more instances than ( CP COMBINED ) within the time limit, however in the infeasible case, ( CP COMBINED ) solves 5 more instances than ( CP VERTEX ) within the time limit. Overall, ( CP VERTEX ) is able to solve one more instance than ( CP COMBINED ) before the time limit is reached. We note however, that for medium-sized instances 25 of the instances were unsolved by any method. For these medium-sized instances, those with D = 0 2 or . D = 0 5 were all solved in less than 2 minutes. .

The D = 0 3 and . D = 0 4 instances are more difficult with only 13 of 24 instances with . D = 0 4 . solved and no instances with D = 0 3 and . n ≥ 85 solved. Thus there is still opportunity to improve the CP formulations.

Finally, we compare the best performing CP formulations, ( CP COMBINED ) and ( CP VERTEX ), with ( IP VR ) on the pseudo-protein instances. As seen in Figure 11, the results can be found in Tables 6 to 9 of Appendix E. We observe that ( CP VERTEX ) and ( CP COMBINED ) outperform ( IP VR ), which is only able to solve 39 instances in total within the time limit. ( CP COMBINED ) has the best performance on these instances solving every instance in less than 32 seconds. ( CP VERTEX ) is unable to solve 9 instances before the time limit is hit. We observe that of the instances ( CP VERTEX ) is unable to solve, 8 have n ≥ 40 and they are those that have the highest density. Overall, we conclude that the CP formulations perform very well on pseudo-protein instances.

Figure 11: Solution times for pseudo-protein instances.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-4f21ffc7-68ac-4e48-acb3-36be1913f583.jpg)

## 5.4 Preliminary Computational Study of Structural Findings

In this section, we present a preliminary study of the structural findings of Section 4. We implement them on ( CP COMBINED ) and test on the small random instances. In the worst case it takes 0.12 seconds to check for infeasibility and then apply domain reduction and symmetry breaking. For both the domain reduction and the symmetry breaking, we apply the infeasibility checks before solving. The infeasibility checks are able to prove four instances are infeasible without having to solve a mathematical program.

Solution times for ( CP COMBINED ) on small instances with domain reduction only and the symmetry breaking only, as well as both domain reduction and symmetry breaking together, and with no additions are shown in Figure 12. In total, for the set of 81 small instances, Infeasibility Check 1 was able to solve two instances and Infeasibility Check 3 was also able to solve two instances. Domain Reduction Rule 1 was applied to 12 instances. Finally, Symmetry Breaking Condition 4 was applied to 33 instances, Symmetry Breaking Condition 5 was applied to 32 instances, and Symmetry Breaking Condition 6 was applied to 37 instances. None of the instances could be deemed infeasible using Infeasibility Checks 2 and 4. We were also unable to apply Domain Reduction Rule 2, and could not use Symmetry Breaking Conditions 1, 2, 3 for these instances.

We present the results in Table 10 of Appendix E. We focus on small instances since we were unable to apply any of the findings other than arbitrary symmetry breaking to the medium-sized instances. We also see that the solution time with the addition of some combination of the structural strategies is decreased for 63 of the 81 instances. We believe this is because as n increases, an

instance is less likely to have degree less than 2 K , since K is small with respect to n and it is less likely that two vertices will have the same neighbourhoods. We observe that for feasible instances, symmetry breaking is slightly detrimental to the performance of ( CP COMBINED ) and that adding only domain reduction gives very similar results to no additions at all. However, for infeasible instances, we observe that domain reduction alone improves upon ( CP COMBINED ), and has similar performance to when both symmetry breaking and domain reduction are added to the model.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-a8f0fb30-2873-4d0b-a418-e5460163b3ad.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-e2b3be24-37e6-4f3d-9aba-6d8972240ebc.jpg)

- (a) Small feasible instances
- (b) Small infeasible instances

Figure 12: Solution times of the alternatives for structural findings.

For the majority of instances there exists an addition of one or more structural finding to the model that improves the solution time as compared to ( CP COMBINED ) on its own. Thus we conclude that the structural findings are beneficial for this data set. We also see that as the instance size increases we are unable to find these key structures in the graph. This motivates the future work of incorporating these structural insights into the CP search tree for further propagation opportunities and apply them at every node of the search tree to some subset of the order.

## 5.5 Preliminary Computational Study of Valid Inequalities

To provide insight into the class of valid inequalities using stable sets, (7) and (8), presented in Section 4.4, we study the impact of adding all possible valid inequalities to both ( CP RANK ) and ( CP COMBINED ) before solving. We use the Networkx Python package to enumerate all maximal stable sets for each small instance; the total time to enumerate these sets is 2 55 seconds. . We then add the valid inequalities (7) or (8) to the model as constraints using these stable sets and compare against the formulations without the valid inequalities. We remark that this is by no means a complete study of the impact of the valid inequalities but is meant to provide insight that even with a naive implementation there are cases where the valid inequalities are useful. The complete results table can be found in Table 11 of Appendix E

Figure 13a shows the results for small feasible instances. We observe that adding the valid inequalities was only slightly detrimental for both ( CP RANK ) and ( CP COMBINED ) and that the inequalities (7) have better performance than the inequalities (8). In the infeasible case, Figure 13b, both forms of the valid inequalities increase the number of instances solved by ( CP RANK ) within the time limit and the speed at which they were solved. For ( CP COMBINED ) on the smallest infeasible instances, the formulations with valid inequalities (7) and (8) dominate the formulation without. In fact, the formulations with valid inequalities are able to solve some of these instances with 0 choice points, which is notable. As the size of the instances grows, ( CP COMBINED ) without valid

inequalities has better performance. This is most likely as a result of the larger instances having more stable sets and the subsequent models having a large number of constraints as a result.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-3d413636-faf2-4285-92b1-9d9a2e4c5a84.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-9e0b61a7-959e-42d8-a9f6-a907e14dc557.jpg)

- (a) Small feasible instances

(b) Small infeasible instances

Figure 13: Solution times of the alternatives for valid inequalities (VI).

We conclude that in this preliminary implementation the valid inequalities are useful in small, low density instances and to improve ( CP RANK ) on infeasible instances. Future work on this topic includes further analysis to select a small enough subset of the stable sets that the number of constraints will not be too large and that will have a large impact on solution times. We remark however that the valid inequalities show promise given a more suitable implementation, such as a specialized propagator for the CP formulations.

## 6 Conclusion

We propose the first CP formulations for the CTOP and compare them against two existing IP formulations in the literature. Applying ideas from both the CP and IP literature, and by studying the structure of DMDGP orders, we introduce three classes of additions to formulations for CTOP, namely infeasibility checks, domain reduction, and symmetry breaking. We also provide the first class of valid inequalities for CTOP.

Our computational results show our models outperform the state-of-the-art IP formulations. They also indicate that the additions to the models based on structural findings are useful for infeasible instances, but may negatively impact the amount of time it takes to solve feasible instances. Nonetheless, they give important insight into the structure of CTOP and show promise for improvement and extension.

Acknowledgements We are grateful to Leo Liberti for introducing us to the area of distance geometry and this topic in particular. We would also like to thank J´r´my Omer for kindly providing e e the pseudo-protein instances similar to those used in [18].

## References

- [1] A. Cassioli, O. G¨ unl¨k, u C. Lavor, and L. Liberti, Discretization vertex orders in distance geometry , Discr. Appl. Math. 197 (2015), 27-41.

- [2] D. Gon¸ calves, J. Nicolas, A. Mucherino, and C. Lavor, ' Finding optimal discretization orders for molecular distance geometry by answer set programming ,' Recent Advances in Computational Optimization , S. Fidanova (ed.), Springer, 2016, pp. 1-15.
- [3] D.S. Gon¸ calves, A. Mucherino, C. Lavor, and L. Liberti, Recent advances on the interval distance geometry problem , J. Global Optim. 69 (2017), 525-545.
- [4] D.S. Gon¸ calves and A. Mucherino, Optimal partial discretization orders for discretizable distance geometry , Int. Trans. Oper. Res. 23 (2016), 947-967.
- [5] A. Hagberg, P. Swart, and D.S. Chult, Exploring network structure, dynamics, and function using NetworkX , Tech. report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008.
- [6] N. Krislock and H. Wolkowicz, Explicit sensor network localization using semidefinite representations and facial reductions , SIAM J. Optim. 20 (2010), 2679-2708.
- [7] C. Lavor, J. Lee, A. Lee-St. John, L. Liberti, A. Mucherino, and M. Sviridenko, Discretization orders for distance geometry problems , Optim. Lett. 6 (2012), 783-796.
- [8] C. Lavor, L. Liberti, W.A. Lodwick, and T.M. da Costa, An Introduction to Distance Geometry applied to Molecular Geometry , Springer, 2017.
- [9] C. Lavor, L. Liberti, N. Maculan, and A. Mucherino, The discretizable molecular distance geometry problem , Comput. Optim. Appl. 52 (2012), 115-146.
- [10] C. Lavor, L. Liberti, and A. Mucherino, The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances , J. Global Optim. 56 (Jul 2013), 855-871.
- [11] C. Lavor, M. Souza, L.M. Carvalho, and L. Liberti, On the polynomiality of finding K DMDGP reorders , Discr. Appl. Math. 267 (2019), 190 - 194.
- [12] C. Lecoutre, Constraint Networks: Targeting Simplicity for Techniques and Algorithms , John Wiley &amp; Sons, 2013.
- [13] L. Liberti, C. Lavor, N. Maculan, and A. Mucherino, Euclidean distance geometry and applications , SIAM Review 56 (2014), 3-69.
- [14] A. Mucherino, A pseudo de Bruijn graph representation for discretization orders for distance geometry , Bioinformatics and Biomedical Engineering, Springer International Publishing, 2015, pp. 514-523.
- [15] A. Mucherino, On the Discretization of Distance Geometry: Theory, Algorithms and Applications, Habilitation ` diriger des recherches, IRISA, 2018. a
- [16] A. Mucherino, C. Lavor, and L. Liberti, The discretizable distance geometry problem , Optim. Lett. 6 (2012), 1671-1686.
- [17] A. Mucherino, C. Lavor, L. Liberti, and N. Maculan, Distance Geometry: Theory, Methods, and Applications , Springer Science &amp; Business Media, 2012.
- [18] J. Omer and D.S. Gon¸ calves, An integer programming approach for the search of discretization orders in distance geometry problems , Optim. Lett. 14 (2020), 439-452.
- [19] J. Saxe, Embeddability of Weighted Graphs in K -space is Strongly NP-hard , CMU-CS-80-102, CarnegieMellon University, Department of Computer Science, 1980.
- [20] B.M. Smith, Dual models in constraint programming , Tech. report, School of Computing, University of Leeds, 2001.

## A Details of the Existing IP Models

Prior to this work, Cassioli et al. [1] present two IP formulations for CTOP.

## A.1 The vertex-rank IP

Let x vr be a binary variable, which takes value 1 if a vertex v ∈ V is receives rank r ∈ [ n -1] in the order, and 0 otherwise. Since CTOP is a satisfiability problem, we are simply looking for a feasible order; there is no objective. The so-called vertex-rank IP formulation is as follows:

$$G$$

$$\int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array}} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { \begin{array} { c } \int _ { 1 } } } } } } } } } } } \end{array} } \end{array} } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } ) } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } \ } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } }. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \.. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ \\ \text{trans} \quad \quad \quad$$

Constraints (9a) and (9b) enforce a one-to-one assignment between the vertices and the ranks, so that each vertex appears exactly once in the order and that each rank gets exactly one vertex. Constraints (9c) enforce that there must be an initial clique of size K , i.e., that the vertices in positions [ K -1] are all adjacent to their predecessors. Constraints (9d) enforce each vertex with a rank in [ K,n -1] has at least K contiguous predecessors. Finally, constraints (9e) ensure the binary domain of the vertex-rank variables.

Proof of Proposition 1. We claim that setting x vr = 1 n for all v ∈ V , r ∈ [ n -1] always yields a feasible solution to the LP relaxation of ( IP VR ). We show the proposed solution satisfies all LP constraints. For constraints (9a), fixing v ∈ V gives

$$\sum _ { r \in [ n - 1 ] } \frac { 1 } { n } = n \cdot \frac { 1 } { n } = 1.$$

Similarly, for constraints (9b), fixing r ∈ [ n -1] gives

$$\sum _ { v \in \mathcal { V } } \frac { 1 } { n } = | \mathcal { V } | \cdot \frac { 1 } { n } = n \cdot \frac { 1 } { n } = 1.$$

For constraints (9c), for any v ∈ V and r ∈ [1 , K -1] we have

$$\sum _ { u \in \mathcal { N } ( v ) } \sum _ { j \in [ r - 1 ] } \frac { 1 } { n } \geq \sum _ { j \in [ r - 1 ] } \frac { 1 } { n } = r \frac { 1 } { n }$$

where the inequality follows from |N ( v ) | ≥ 1 since G is connected. Finally, for constraints (9d), for any v ∈ V and r ∈ [ K,n -1] we have

$$\sum _ { u \in \mathcal { N } ( v ) } \sum _ { j \in [ r - K, r - 1 ] } \frac { 1 } { n } \geq \sum _ { j \in [ r - K, r - 1 ] } \frac { 1 } { n } = K \cdot \frac { 1 } { n }$$

again, due to |N ( v ) | ≥ 1 since G is connected.

Thus x vr = 1 n satisfies all constraints and the LP relaxation is feasible. glyph[square]

## A.2 The clique digraph IP and its relaxation

As stated in Key Property 2, a DMDGP order is a series of overlapping induced ( K +1)-cliques in G , which cover all the vertices and share K vertices between adjacent pairs. Define a clique digraph D = ( O A , ), where O is the index set of all ordered cliques { o j } j ∈O of size K + 1 in the input graph G , where o j = ( v , v j 1 j 2 , . . . , v j K +1 ), i.e., represented simply by its ordered vertices. There is an arc ( o , o i j ) ∈ A between o , o i j ∈ O if v i K +1 = v j K , i.e., if the two cliques overlap by K vertices and differ only by the first and the last vertex respectively. For instance, in the example given in Figure 2, there will be an arc in A between the vertices corresponding to the ordered 3-cliques ( v , v 4 2 , v 3 ) and ( v , v 2 3 , v 1 ). Let glyph[lscript] i be the last vertex of a clique o i ∈ O . In this setting a DMDGP order is described by a path (of cliques) P = ( o , o 1 2 , . . . , o n -K ) in D where { v ∈ o c 1 } ∪ { glyph[lscript] i : i ∈ [2 , n -K ] } = V . That is, the initial clique and the last vertices of all other cliques cover V . For instance, the DMDGP order given in Figure 2b is described by the path of cliques o 1 = ( v , v 4 2 , v 3 ) , o 2 = ( v , v 2 3 , v 1 ) , o 3 = ( v , v 3 1 , v 5 ) and o 4 = ( v , v 1 5 , v 0 ).

Define binary variables x ij = 1 if the arc ( i, j ) ∈ A is selected in the path solution P , 0 otherwise. Let the binary variable γ j = 1 if j ∈ O is the first clique in P and λ j = 1 if j ∈ O is the last clique in P . Define binary precedence variables p uv = 1 if u ∈ V precedes v ∈ V in the DMDGP order. Then the clique digraph IP formulation is as follows:

$$( \mathbb { I P } ^ { \mathbb { C D } } ) \colon \min \sum _ { ( i, j ) \in \mathcal { A } } x _ { i j }$$

glyph[negationslash]

glyph[negationslash]

$$\text{ne binary variables} x _ { i j } = 1 \, \text{if the arc} \, ( i, j ) \in \mathcal { A } \, \text{is selected in the path solution} \, P, 0 \text{otherwise}. \text{binary variable} \, \gamma _ { j } = 1 \, \text{if } j \in \mathcal { O } \, \text{is the first clique in} \, P \, \text{and} \, \lambda _ { j } = 1 \, \text{if } j \in \mathcal { O } \, \text{is the last clique} \, \gamma _ { j } = 1 \, \text{if } j \in \mathcal { O } \, \text{is the third} \, \text{and} \, \lambda _ { j } = 1 \, \text{if } j \in \mathcal { O } \, \text{is the last clique} \, \gamma _ { j } = 1 \, \text{if } j \in \mathcal { O } \, \text{is the last clique} \, \gamma _ { j } = 1 \, \text{if } j \in \mathcal { O } \, \text{is the last clique} \, \gamma _ { j } = 1 \, \text{if } j \in \mathcal { O } \, \text{is the last clique} \, \gamma _ { j } = 1 \, \text{if } j \in \mathcal { O } \, \text{is the last clique} \, \gamma _ { j } = 1 \, \text{if } j \in \mathcal { O } \, \text{is the last clique} \, \gamma _ { j } = 1 \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \int \, \end{array} \, ( \text{[MPCP]} ) \colon \min \, \sum _ { \substack { x _ { i j } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal{A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ (i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j )
 \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \cdot \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal { A } \\ ( i, j ) \in \mathcal$$

glyph[negationslash]

Objective (10a) imposes that we will select the minimum number of arcs required to form the path

P . Constraints (10b) and (10c) ensure there is exactly one initial clique and one last clique selected. Constraints (10d) ensure that flow balance holds in the path P except at the first and last path vertices which have one arc out and one arc in respectively. These flow balance constraints also ensure a correct predecessor relationship between the cliques in P . Constraints (10e) ensure each clique has at most one successor, one if it is in the path and not the last clique and none otherwise. Constraints (10f) ensure that the cliques selected cover all the vertices in V . Constraints (10g) and (10h) impose a linear order among vertex pairs and triplets. Constraints (10i), (10j), and (10k) 4 ensure that each clique is ordered. Constraints (10i) impose that v i k precedes vertex v i k +1 if ordered clique i has an outgoing arc in the path solution P . Constraints (10j) ensure that if arc ( i, j ) ∈ A is selected in P , the vertex of j not in i , v , is preceded by all other vertices of j in i , which have been ordered by (10i). Constraints (10k) are similar to (10i), except they order the vertices of the first and last clique. Finally, constraints (10l), (10m), (10n), and (10o) enforce the binary domains of all variables.

( IP CD ) is disadvantaged by the potential number of vertices in the clique digraph D , as the cardinality of O can be quite large even for relatively sparse graphs. To reduce the number of variables in ( IP CD ), Cassioli et al. [1] present a relaxation of the clique digraph formulation which considers unordered cliques. The idea is to relax the ordering constraints in the formulation and to solve this relaxation as a first check for the existence of a DMDGP order. In this case, the worst case number of vertices in D can be reduced by a factor of ( K +1)!. Let O now denote the set of unordered cliques of size K +1 in G . Let binary variable z j = 1 if the unordered clique j ∈ O is used in P . The unordered clique IP relaxation of ( IP CD ) is as follows:

$$( \mathbb { I P } ^ { \text{RELAX} } ) \colon \min \ \sum \ x _ { i j }$$

$$s. t. \ ( 1 0 b ) - ( 1 0 h )$$

$$\text{red clique } IP \text{ relaxation of } ( \mathbb { I P C D } ) \text{ is as follows: } \\ \text{LAX} ) \colon \min \sum _ { ( i, j ) \in \mathcal { A } } x _ { i j } & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &  & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \text{1a} ) \\ \text{same as in } ( \mathbb { I P C D } ). \text{ However, we have relaxed the clique ordering constraints, } \\ \text{--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dclots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\Dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ Dots--\ P C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C c C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C CC C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C$$

(11a) and(11b) are the same as in ( IP CD ). However, we have relaxed the clique ordering constraints, (10i)-(10k), so now constraints (11c) ensure we have that if arc ( i, j ) ∈ A is selected in P , all u ∈ o i precede vertex v , the only vertex of j not in i . Constraints (11d) ensure we have correctly linked the arc variables and clique variables to the indicator z j , so that it is 1 if a clique is part of an arc selected in the solution path P , while the indicator for the first clique is activated through constraints (11e). The constraints (11f) impose that each vertex appears in at most K +1 cliques. These constraints are another relaxation, since to make it exact we would need to enforce that all vertices except the first and last K appear in K +1 cliques; however this will require many more variables to express. Finally constraints (11g) and (11h) enforce the variable domains.

When a solution to ( IP RELAX ) is found, it must be verified as this solution does not necessarily yield a DMDGP order. The verification is a simple check to ensure the p solution forms a DMDGP

4 In [1], the variables for predecessors are given as w uv , only in these constraints. We believe this is a typo that the variables are in fact p uv .

order. The strength in this formulation is that if ( IP RELAX ) is infeasible, there is no DMDGP order for the instance.

## B Selected Proofs

## B.1 Proof of Proposition 2

Proof. Minimally, the vertex in position 0 must be adjacent to K vertices since it is in a ( K +1)clique, similarly for the vertex in position n -1. The vertex in position 1 is in two ( K +1)-cliques since it is in the initial clique but also is an adjacent predecessor of the vertex in position K +1; similarly for the vertex in position n -2. We extend this logic to all vertices in the order, noting that the centre |V| 2 K vertices in the order, i.e., the ones in positions [ K,n -K -1], must all be in 2 K cliques, as seen in Figure 14. This minimal case analysis gives a lower bound on the order:

minimum degree:

Figure 14: Minimum degree requirement for ranks in a DMDGP order.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-42969880-24b5-4e91-97ad-b6531109f658.jpg)

number of edges in a DMDGP order. For each vertex from position 0 to position n -1 we sum over the minimum degree in G to have a DMDGP order. Note that we divide by two to avoid double counting since the input graph is undirected.

$$\text{counting} & \simeqslant \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \colon$\end{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{ $\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\	$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$	\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\ \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \hat \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \attrib$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$\quad \text{$_}} \text{$_}} \text{$_}} \text{$_}} \text{$_}} \text{$_}} \text{$_}} \text{$_}} \text{$_}} \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \text{$_ } \end{array}$$

Thus the minimum number of edges for a DMDGP order is ( |V| 1 2 ) K -1 2 K 2 .

## B.2 Proof of Proposition 3

Proof. We first show that there exists an instance for which (5) dominates (6). Consider the graph, G 1 , shown in Figure 15a and let K = 3. Let S 1 = { v , v 1 2 , v 3 , v 4 , v 5 } . Then G 1 [ S 1 ] = G 1 does not have a DMDGP order due to Infeasibility Check 1, e.g., since v 3 cannot be in the initial clique and cannot have K contiguous predecessors.

Figure 15: Graphs used to compare valid inequalities (5) and (6).

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-cb0bf4bf-57cb-49e7-883c-257993c4a094.jpg)

To find the inequality (5), we calculate max v ∈S 1 δ miss S 1 ( v ) = δ miss S 1 ( v 3 ) = 3 and find:

$$r _ { m a x } - r _ { m i n } \geq \max \{ | \mathcal { S } _ { 1 } |, \delta _ { \mathcal { S } _ { 1 } } ^ { m i s s } + K \}$$

$$r _ { m a x } - r _ { m i n } \geq \max \{ 5, 3 + 3 \}$$

$$r _ { m a x } - r _ { m i n } \geq 6$$

The instance only has 5 vertices in total, so this single inequality is enough to prove the instance does not have a DMDGP order. The largest stable set in the graph in Figure 15a has cardinality two; using any of these stable sets as SS 1 makes the inequality (6)

$$r _ { m a x } - r _ { m i n } \geq ( | \mathcal { S } \mathcal { S } _ { 1 } | - 1 ) ( K + 1 ) & & ( 1 4 a )$$

$$r _ { m a x } - r _ { m i n } \geq ( 2 - 1 ) ( 3 + 1 ) & & ( 1 4 b )$$

$$r _ { m a x } - r _ { m i n } \geq 4$$

which is not sufficient to prove the infeasibility of the instance. Thus (5) dominates (6) in this instance.

We now show that there exists an instance for which (6) dominates (5). Consider the graph, G 2 , shown in Figure 15b and let K = 3. A maximum stable set in G 2 is SS 2 = { u , u 1 3 , u 5 } , making the inequality (6):

$$r _ { m a x } - r _ { m i n } \geq ( | \mathcal { S } \mathcal { S } _ { 2 } | - 1 ) ( K + 1 )$$

$$r _ { m a x } - r _ { m i n } \geq ( 3 - 1 ) ( 3 + 1 )$$

$$r _ { m a x } - r _ { m i n } & \geq 8 & ( 1 5 c )$$

Setting S 2 = SS 2 , then G [ S 2 ] does not have a DMDGP order due to Infeasibility Check 1.We calculate max u ∈S 2 δ miss S 2 ( u ) = 2 and find

$$r _ { m a x } - r _ { m i n } \geq \max \{ | \mathcal { S } _ { 2 } |, \delta _ { \mathcal { S } _ { 2 } } ^ { m i s s } + K \}$$

$$r _ { m a x } - r _ { m i n } \geq \max \{ 3, 2 + 3 \}$$

$$r _ { m a x } - r _ { m i n } \geq 5$$

Thus (6) dominates (5), and we may conclude that (5) and (6) are incomparable.

## B.3 Proof of Proposition 4

Proof. Let the vertices in the wheel be indexed as in Figure 8, i.e., the centre vertex has index 0, while the ones in the peripheral cycle are indexed from [1 , n ] counter clock-wise starting at an arbitrary one.

- · Case 1: When n is odd, a maximum stable set in W n is { 1 3 , , . . . , n - } 2 with size n -1 2 . For the right-hand side of the inequality in Infeasibility Check 5 to hold, we need

$$\text{aliy in Infeasibility Check 5} \\ \frac { n - 1 } { 2 } \geq \frac { n } { K + 1 } + 1 \\ \frac { n } { 2 } - \frac { n } { K + 1 } \geq \frac { 1 } { 2 } \\ n \left ( \frac { 1 } { 2 } - \frac { 1 } { K + 1 } \right ) \geq \frac { 1 } { 2 } \\ n \geq \frac { K + 1 } { K - 1 }. \\ \text{n, a maximum stable set in}$$

- · Case 2: Similarly, when n is even, a maximum stable set in W n is { 1 3 , , . . . , n - } 3 with size n 2 . So we need

$$\frac { n } { 2 } & \geq \frac { n } { K + 1 } + 1 \\ n \left ( \frac { 1 } { 2 } - \frac { 1 } { K + 1 } \right ) \geq 1 \\ n & \geq 2 \frac { K + 1 } { K - 1 }.$$

$$n \, \subset \, \ n$$

$$n \geq 2 \frac { K + 1 } { K - 1 }.$$

Thus the inequalities hold.

## C Example

Example 10. We will demonstrate the strength of symmetry breaking on the graph in Figure 16 with K = 2 .

Figure 16: A graph instance which is feasible for CTOP with K = 2.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00048v2-figure-7ef5e81d-aaee-4d9d-bdf5-d12011d060ee.jpg)

This instance has 12 feasible DMDGP orders:

$$( v _ { 4 }, v _ { 3 }, v _ { 2 }, v _ { 1 }, v _ { 0 }, v _ { 5 } ) & \quad ( v _ { 5 }, v _ { 0 }, v _ { 1 }, v _ { 2 }, v _ { 3 }, v _ { 4 } ) \quad ( v _ { 4 }, v _ { 3 }, v _ { 2 }, v _ { 5 }, v _ { 0 }, v _ { 1 } ) \\ ( v _ { 1 }, v _ { 0 }, v _ { 5 }, v _ { 2 }, v _ { 3 }, v _ { 4 } ) & \quad ( v _ { 4 }, v _ { 2 }, v _ { 3 }, v _ { 1 }, v _ { 5 }, v _ { 0 } ) \quad ( v _ { 0 }, v _ { 5 }, v _ { 1 }, v _ { 3 }, v _ { 2 }, v _ { 4 } ) \\ ( v _ { 4 }, v _ { 3 }, v _ { 2 }, v _ { 1 }, v _ { 5 }, v _ { 0 } ) & \quad ( v _ { 0 }, v _ { 5 }, v _ { 1 }, v _ { 2 }, v _ { 3 }, v _ { 4 } ) \quad ( v _ { 4 }, v _ { 2 }, v _ { 3 }, v _ { 5 }, v _ { 1 }, v _ { 0 } ) \\ ( v _ { 0 }, v _ { 1 }, v _ { 5 }, v _ { 3 }, v _ { 2 }, v _ { 4 } ) & \quad ( v _ { 4 }, v _ { 3 }, v _ { 2 }, v _ { 5 }, v _ { 1 }, v _ { 0 } ) \quad ( v _ { 0 }, v _ { 1 }, v _ { 5 }, v _ { 2 }, v _ { 3 }, v _ { 4 } )$$

We begin by noticing that V d [2 2] , = { v 4 } so we fix r v 4 = 0 and eliminate half the orders, leaving the orders:

$$( v _ { 4 }, v _ { 3 }, v _ { 2 }, v _ { 1 }, v _ { 0 }, v _ { 5 } ) & \quad ( v _ { 4 }, v _ { 2 }, v _ { 3 }, v _ { 1 }, v _ { 5 }, v _ { 0 } ) \quad ( v _ { 4 }, v _ { 3 }, v _ { 2 }, v _ { 5 }, v _ { 0 }, v _ { 1 } ) \\ ( v _ { 4 }, v _ { 3 }, v _ { 2 }, v _ { 1 }, v _ { 5 }, v _ { 0 } ) & \quad ( v _ { 4 }, v _ { 3 }, v _ { 2 }, v _ { 5 }, v _ { 1 }, v _ { 0 } ) \quad ( v _ { 4 }, v _ { 2 }, v _ { 3 }, v _ { 5 }, v _ { 1 }, v _ { 0 } )$$

There are no stable sets meeting Symmetry Breaking Condition 2, and the only clique meeting Symmetry Breaking Condition 3 is { v , v 1 5 } . Thus we enforce r v 1 &lt; r v 5 and eliminate another three orders, leaving three remaining orders:

$$( v _ { 4 }, v _ { 3 }, v _ { 2 }, v _ { 1 }, v _ { 0 }, v _ { 5 } ) \ \ ( v _ { 4 }, v _ { 3 }, v _ { 2 }, v _ { 1 }, v _ { 5 }, v _ { 0 } ) \ \ ( v _ { 4 }, v _ { 3 }, v _ { 2 }, v _ { 5 }, v _ { 0 }, v _ { 1 } ).$$

Since we have found a clique in Symmetry Breaking Condition 3, we first examine Symmetry Breaking Condition 5. Beginning with K = { v , v 1 5 } and v = v 2 , we have

$$\left ( \mathcal { N } ( v _ { 2 } ) \cup \{ v _ { 2 } \} \right ) \, \left ( \mathcal { N } ( \{ v _ { 1 }, v _ { 5 } \} ) \cup \{ v _ { 1 }, v _ { 5 } \} ) = \{ v _ { 0 }, v _ { 1 }, v _ { 2 }, v _ { 3 }, v _ { 4 }, v _ { 5 } \} \, \langle \{ v _ { 0 }, v _ { 1 }, v _ { 2 }, v _ { 3 }, v _ { 5 } \} = \{ v _ { 4 } \}$$

so w = v 4 and we can add the following logical constraints:

$$| r _ { v _ { 2 } } - r _ { v _ { 4 } } | & \geq 3 \implies r _ { v _ { 2 } } < r _ { v _ { 5 } } \\ | r _ { v _ { 2 } } - r _ { v _ { 4 } } | & \geq 3 \implies r _ { v _ { 2 } } < r _ { v _ { 1 } }$$

In fact, the latter suffices since we have already added r v 1 &lt; r v 5 . Unfortunately this does not remove any solutions from the pool. We now try K = { v 0 } and v = v 5 . In this case we have w = v 3 and add

$$| r _ { v _ { 5 } } - r _ { v _ { 3 } } | \geq 3 \implies r _ { v _ { 5 } } < r _ { v _ { 0 } }$$

which removes a further order, yielding the remaining orders:

$$( v _ { 4 }, v _ { 3 }, v _ { 2 }, v _ { 1 }, v _ { 5 }, v _ { 0 } ) \ \ ( v _ { 4 }, v _ { 3 }, v _ { 2 }, v _ { 5 }, v _ { 0 }, v _ { 1 } ).$$

Finally, we extend K = { v 3 } using v = 2 , giving w = v 0 and the logical constraint:

$$| r _ { v _ { 2 } } - r _ { v _ { 0 } } | \geq 3 \implies r _ { v _ { 2 } } < r _ { v _ { 3 } }$$

Thus symmetry breaking has reduced the solution space to a single DMDGP order:

$$( v _ { 4 }, v _ { 3 }, v _ { 2 }, v _ { 5 }, v _ { 0 }, v _ { 1 } )$$

## D Summary of the paper

Table 2 provides a summary of the models from the literature as well as all of our proposed formulations and structural insights.

28

DMDGP:

Given a graph

G

V E

= (

,

Table 2: Summary of CTOP formulations and structural findings.

) and integer

K &gt;

0, minimally, a DMDGP order is a series of (

K

+1)-cliques which overlap by at least

| FORMULATIONS Literature                                                                                                                                                                                   | Variables                                     | Domain                                                                                                     | Number                                                                     | Constraints                                                                                                                                                                                   | Number                                                                                                          | Comments                                                                                                                                                     |
|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|-----------------------------------------------|------------------------------------------------------------------------------------------------------------|----------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------|
| Vertex-rank ( IP VR ) Clique Digraph ( IP CD )                                                                                                                                                            | x vr x o i o j γ o j λ o j p uv               | { 0 , 1 } { 0 , 1 } { 0 , 1 } { 0 , 1 } { 0 , 1 }                                                          | n 2 |O| 2 |O| |O| |V| 2                                                    | 1-1 assignment clique select initial and last clique flow balance successor vertex covering precedence clique ordering select initial and last flow balance successor                         | 2 n n 2 2 |O| |O| |V| |V| 2 + |V| 3 (2 K +1) ×|O| 2                                                             | Enumerate ordered ( K +1)-cliques                                                                                                                            |
| Clique Digraph Relax. ( IP RELAX )                                                                                                                                                                        | x o i o j γ o j λ o j p uv                    | { 0 , 1 } { 0 , 1 } { 0 , 1 } { 0 , 1 }                                                                    | |O| 2 |O| |O| n 2                                                          | clique vertex covering precedence relaxed clique ordering no. times vertex in clique                                                                                                          | 2 |O| |O| |V| |V| 2 + |V| 3 2 |O| 2 + |O| |V|                                                                   | Enumerate ( K +1)-cliques If infeasible, no DMDGP order o.w., may or may not have DMDGP order                                                                |
| New CP Rank ( CP RANK ) CP Vertex ( CP VERTEX ) CP Combined ( CP COMBINED )                                                                                                                               | r v v r r v v                                 | [ n - 1] [ |V| - 1] [ n - 1]                                                                               | n n n n                                                                    | AllDifferent clique AllDifferent clique AllDifferent and inverse clique                                                                                                                       | 1 |V| 2 1 |V| 2 3 2 |V| 2                                                                                       | Combines CP Rank and CP Vertex                                                                                                                               |
| STRUCTURAL FINDINGS Infeasibility Checks Minimum Degree Minimum Edges UB on Small Deg. Vertices LB on Large Deg. Vertices Max Stable Set Domain Reduction Small Deg. Vertices Neighb. Small Deg. Vertices | r |E| ∣ ∣ V d ∣ ∣ V d [ d ( v ) - K [ d ( v ∗ | [ |V| - 1] d ( v ) < < ( |V| - 1 2 K,K + δ ] ∣ ∣ > [2 K,n - 1] ∣ ∣ ≤ n SS > n K ∪ [ n - 1 - )] ∪ [ n - 1 - | K K - 1 2 K 2 2( δ +1) +1 - (2 K +1) +1 +1 ( d ( v ) - K ) d ( v ∗ ) , n - | Symmetry Breaking Arbitrary Degree K Stable Set Same Neighbours Clique Same Neighbours Extended Stable Set Extended Clique Valid Inequalities Vertex Subset Improved Vertex Subset Stable Set | r v 1 < r v i = 0 and r v 1 < r v 2 r v 1 < r v 2 | r v - r w | ≥ K | r v - r w | ≥ K r max - r r max - r r max | r v 2 r v j = n - 1 < · · · < r v k < · · · < r v k +1 = ⇒ r v < r u +1 = ⇒ r v < r u min ≥ |S| min ≥ max {|S| , δ miss S + K } - r min ≥ ( |SS| - 1)( K +1) |

K

vertices.

## E DMDGP Results

We provide the following tables:

- · Table 3 compares the integer programming formulations from the literature [1], namely the vertex-rank formulation ( IP VR ) and the clique digraph formulation ( IP CD ), with the newly proposed constraint programming formulations, namely the rank-based primal formulation ( CP RANK ), the vertex-based dual formulation ( CP VERTEX ) and the combined formulation ( CP COMBINED ) on the small instances for a variety of densities with K = 3.
- · Table 4 compares the CP formulations ( CP RANK ), ( CP VERTEX ), and ( CP COMBINED ) on the medium-sized instances for low to medium densities with K = 3.
- · Table 5 compares the IP Clique Digraph formulations ( IP CD ) and ( IP RELAX ) on small instances with K = 3.
- · Tables 6, 7, 8, and 9 compare the ( IP VR ), ( CP VERTEX ), and ( CP COMBINED ) formulations with K = 3 on pseudo-protein instances with 30 40 50 , , , and 60 vertices respectively.
- · Table 10 compares the ( CP COMBINED ) formulation with K = 3, with and without the additions from the structural analysis, on small instances. It also gives the rule that was applied and to how many vertices or sets using the following conventions:
- -[Inf r ] refers to Infeasibility Check r , either 1 or 3.
- -[DR ] refers to Domain Reduction Rule 1 which has been applied to r r vertices.
- -[E SS s ] refers to Symmetry Breaking Condition 4 which has been applied to s stable sets.
- -[E K c ] refers to Symmetry Breaking Condition 5 which has been applied to c cliques
- -[Arb] refers to an arbitrary ordering on two vertices, as in Symmetry Breaking Condition 6.

We note that Infeasibility Checks 2 and 4, Domain Reduction Rule 2, and Symmetry Breaking Conditions 1, 2, 3 are excluded from the table since they were never applied.

- · Table 11 compares ( CP RANK ) and ( CP COMBINED ) with valid inequalities in the form (7) and (8) and without valid inequalities. Valid inequalities are generated for every stable set in each instance and added before solving.
- · Table 12 compares the vertex-rank formulation ( IP VR ) with CP formulations ( CP RANK ), ( CP VERTEX ), and ( CP COMBINED ) on the small instance with K = 4.
- · Table 13 compares the vertex-rank formulation ( IP VR ) with CP formulations ( CP RANK ), ( CP VERTEX ), and ( CP COMBINED ) on the small instance with K = 5.

For the instances, we have

- · 'Status': Feasibility status of the instance; 'Feas.' and 'Infeas.' if it is proven to be feasible and infeasible by any of the methods, respectively, 'Unsol.' otherwise as it is not solved by any method.

In particular, for random instances we have

- · ' n ': The number of vertices in the input graph.
- -n ∈ { 20 25 , , . . . , 60 } for the small instances.
- -n ∈ { 65 70 , , . . . , 100 } for the medium-sized instances.
- · ' D ': The edge density of the input graph.
- -D ∈ { 0 3 . , 0 5 . , 0 7 . } for the small instances.
- -D ∈ { 0 2 . , 0 3 . , 0 4 . , 0 5 . } for the medium-sized instances.
- · 'Inst.': The assigned instance number from { 1 2 3 , , } for each ( n, D ) combination.

## For pseudo-protein instances we have

- · 'Protein Inst.': the Protein Data Bank protein which was modified to create the instance.
- · 'Ratio': the approximate average edge to vertex ratio of the instance.

## We also have

- · 'Time': Solution time in seconds if the instance is solved in the given time limit, 'TL' if the instance hit the time limit, 'MEM' if the instance hit the memory limit.
- · 'BB Nodes': The number of branch-and-bound nodes explored (for the IP formulations); exact if it is less than one thousand, lower bound rounded to the closest million otherwise where a single decimal point is used up to between one million for a better accuracy.
- · 'Ch.Pts.': The number of choice points (for the CP formulations); the number convention is the same as the 'BB Nodes'.
- · 'Solved': indicates if a feasible solution was found.
- · 'DMDGP found': 'Yes' if the feasible solution is a DMDGP order, 'No' otherwise.
- · '# cliques': the number of ordered and unordered cliques for ( IP CD ) and ( IP RELAX ) respectively.

Table 3: Integer programming and constraint programming results for small instances

|    |     |         |                               | ( IP VR )              | ( IP VR )            | ( IP CD )          | ( IP CD )   | ( CP RANK )           | ( CP RANK )             | ( CP VERTEX )       | ( CP VERTEX )          | ( CP COMBINED )        | ( CP COMBINED )          |
|----|-----|---------|-------------------------------|------------------------|----------------------|--------------------|-------------|-----------------------|-------------------------|---------------------|------------------------|------------------------|--------------------------|
| n  | D   | Inst.   | Status                        | Time                   | BB Nodes             | Time               | BB Nodes    | Time                  | Ch.Pts.                 | Time                | Ch.Pts.                | Time                   | Ch.Pts.                  |
| 20 | 0.3 | 1 2 3   | Infeas. Infeas. Infeas.       | 41.43 0.01 29.08       | 5981 0 5188          | 0.00 0.00 0.00     | 0 0 0       | 0.16 0.13 0.15        | 8937 7286 8255          | 0.10 0.01 0.01      | 1987 130 122           | 0.01 0.00 0.00         | 72 17 20                 |
|    | 0.5 | 1 2 3   | Infeas. Infeas. Infeas.       | 132.53 156.95 27.35    | 52865 79733 8844     | 4.13 5.66 1.86     | 0 0 0       | 0.21 0.13 0.15        | 10850 7408 8279         | 0.80 0.65 0.78      | 9705 8402 8836         | 0.91 0.29 0.20         | 9423 3909 2519           |
| 25 | 0.3 | 3 1 2 3 | Feas. Infeas. Infeas. Infeas. | 0.27 0.02 105.34 59.15 | 112 0 6376 5303      | TL 0.00 0.00 0.00  | 0 0 0 0     | 0.00 10.35 8.86 6.55  | 15 417400 382191 276282 | 0.01 0.21 0.23 0.01 | 128 3779 4184 184      | 0.00 0.02 0.02 0.01    | 65 194 160 123           |
|    | 0.5 | 1 2 3   | Infeas. Infeas. Infeas.       | 3835.96 TL TL          | 882598 > 1.8M > 1.8M | 0.03 962.72 632.05 | 0 0 0       | 34.84 114.68 31.15    | > 1.1M > 3.1M > 1.0M    | 22.00 33.40 7.76    | 195704 328076 57986    | 0.23 16.01 7.47        | 2415 100057 44433        |
|    | 0.7 | 1 2 3   | Feas. Feas. Feas.             | 5.70 0.56 0.43         | 3902 251 39          | MEM MEM MEM        | - - -       | 0.00 0.00 0.00        | 39 109 26               | 0.02 0.00 0.01      | 578 24 171             | 0.01 0.00 0.01         | 45 30 141                |
| 30 | 0.3 | 1 2 3   | Infeas. Infeas.               | 843.31 639.51          | 52684 33523          | 0.00 0.00          | 0 0         | 308.12 368.72         | > 9.2M > 9.6M           | 0.25                | 3204                   | 0.45                   | 3225 2191                |
|    | 0.5 | 1 2 3   | Infeas. Feas. Infeas. Feas.   | 531.50 TL TL TL        | 31092 > 1.2M 954489  | 0.00 TL TL         | 0 0 0       | 251.35 66.41 TL 89.47 | > 7.3M > 2.8M > 102M    | 0.43 0.43 67.56 TL  | 4152 4874 613865 > 27M | 0.33 0.50 53.36 601.23 | 3429 299863 > 2.7M 29699 |
|    | 0.7 | 1 2 3   | Feas. Feas. Feas.             | 0.72 1.16 2.24         | > 1.2M 203 540 1285  | TL MEM MEM MEM     | 0 - - -     | 0.00 0.00 0.00        | > 4.3M 33 112 33        | 2.07 0.01 0.00 0.00 | 24663 147 34 33        | 4.60 0.02 0.01 0.03    | 195 27 379               |
| 35 | 0.3 | 1 2     | Infeas. Infeas.               | TL                     | 529463               | 0.00 0.00 0.00     | 0 0         | TL TL                 | > 308M 363M             | 1.17 0.55           |                        |                        | 3517 4033                |
|    |     | 3 1     | Infeas. Feas. Feas.           | TL TL                  | 463579 244370        |                    | 0           | TL                    | > > 267M                | 0.55                | 7248 4819 4341         | 0.59 0.89 0.81         | 4043                     |
|    |     | 2       |                               | TL TL                  | > 1.4M > 1.0M > 1.0M | TL TL              | 0 0         | 279.32 26.89          | > 13M 1.2M              |                     | 30082 526013           | 7.14 16.28             | 40622                    |
|    | 0.5 | 3       | Feas.                         | TL                     |                      | TL                 | 0           | 4825.99               | > > 271M                | 2.95 45.94 39.62    | 383353                 | TL                     | 113300 > 32M             |
|    | 0.7 | 1 2     | Feas. Feas.                   | 1.33 1.35              | 95 166               | MEM MEM            | - -         | 0.00 0.01             | 39 267                  | 0.01 0.00           | 34 33                  | 0.01 0.03              | 34 273                   |

|    |     | 3     | Feas.                   | 1.58              | 74                   | MEM             | -     | 0.00                | 37                  | 0.00              | 33                 | 0.01              | 30                   |
|----|-----|-------|-------------------------|-------------------|----------------------|-----------------|-------|---------------------|---------------------|-------------------|--------------------|-------------------|----------------------|
| 40 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | TL TL TL          | 253348 179520 215387 | 0.00 0.00 0.00  | 0 0 0 | TL TL TL            | > 323M > 41M > 40M  | 1.58 0.87 1.52    | 7482 5143 8490     | 2.04 1.41 1.07    | 6156 4789 4191       |
|    | 0.5 | 1 2 3 | Feas. Feas. Feas.       | TL TL TL          | > 1.0M 878086 831307 | MEM MEM MEM     | - - - | 557.97 37.55 35.85  | > 24M > 1.6M > 1.5M | 6.58 11.35 6.93   | 56710 111152 66262 | 266.57 9.10 23.88 | > 1.31M 51413 130898 |
|    | 0.7 | 1 2 3 | Feas. Feas. Feas.       | 1.33 2.77 2.21    | 0 123 50             | MEM MEM MEM     | - - - | 0.00 0.00 0.00      | 36 44 176           | 0.05 0.00 0.09    | 577 39 1074        | 0.02 0.01 0.01    | 166 34 68            |
| 45 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | TL TL TL          | 167176 99401 119535  | 0.01 0.01 1.89  | 0 0 0 | TL TL TL            | > 298M > 42M > 41M  | 6.92 4.74 4.76    | 21970 17489 19927  | 8.70 1.19 1.70    | 18790 3473 5194      |
|    | 0.5 | 1 2 3 | Feas. Feas. Feas.       | 242.69 TL TL      | 10702 565030 676199  | MEM MEM MEM     | - - - | 9.75 237.99 33.00   | 430149 > 10M > 1.4M | 4.61 12.61 4.52   | 41180 103490 38613 | 3.56 3.85 3.37    | 16486 18158 16901    |
| 50 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | TL TL TL          | 68691 103348 69546   | 0.02 7.04 0.02  | 0 0 0 | TL TL TL            | > 280M > 37M > 37M  | 12.36 7.36 14.36  | 32724 23010 38069  | 4.32 13.50 10.53  | 9124 27987 19301     |
|    | 0.5 | 1 2 3 | Feas. Feas. Feas.       | TL TL TL          | 283084 554285 473504 | MEM MEM MEM     | - - - | 287.47 32.18 153.82 | > 12M > 1.3M > 6.3M | 16.59 0.59 7.04   | 113189 4490 50776  | 42.87 1.63 7.83   | 169360 7874 31997    |
|    | 0.7 | 1 2 3 | Feas. Feas. Feas.       | 6.59 9.27 9.01    | 273 195 201          | MEM MEM MEM     | - - - | 0.00 0.00 0.00      | 52 46 48            | 0.01 0.01 0.06    | 51 48 669          | 0.01 0.05 0.03    | 47 315 190           |
| 55 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | TL TL TL          | 49459 51372 46087    | 14.13 0.03 0.03 | 0 0 0 | TL TL TL            | > 261M > 32M > 32M  | 13.78 17.57 16.85 | 29494 36651 31236  | 28.38 30.21 29.51 | 43711 44814 43579    |
|    | 0.5 | 1 2 3 | Feas. Feas. Feas.       | TL TL TL          | 475709 483159 390397 | MEM MEM MEM     | - - - | 158.49 1.92 52.05   | > 6.2M 73055 > 1.9M | 23.19 7.62 5.85   | 155633 49245 32292 | 20.74 17.80 41.29 | 80931 65528 164410   |
|    | 0.7 | 1 2 3 | Feas. Feas. Feas.       | 16.19 14.80 11.65 | 141 439 193          | MEM MEM MEM     | - - - | 0.00 0.00 0.00      | 359 72 53           | 0.09 0.20 0.01    | 804 1801 52        | 0.02 0.02 0.01    | 77 110 50            |
| 60 | 0.3 | 1 2   | Infeas. Infeas.         | TL TL             | 24403 14867          | 4061.37 26.81   | 0 0   | TL TL               | > 268M > 34M        | 92.01 23.44       | 147378 44252       | 57.55 34.55       | 66028 43375          |

|     |   3 | Infeas.   | TL    |   18187 | 0.07   | 0   |     TL | > 42M   |   73.24 |   135352 |   11.73 |   16208 |
|-----|-----|-----------|-------|---------|--------|-----|--------|---------|---------|----------|---------|---------|
| 0.5 |   1 | Feas.     | TL    |  349369 | MEM    | -   |  92.38 | > 3.4M  |   14.37 |    85998 |    9.01 |   30615 |
|     |   2 | Feas.     | TL    |  141418 | MEM    | -   | 117.15 | > 5.5M  |    9.27 |    59659 |   25.93 |   91975 |
|     |   3 | Feas.     | TL    |  279238 | MEM    | -   |   4.05 | 191858  |   27.21 |   174109 |   45.13 |  158247 |
| 0.7 |   1 | Feas.     | 34.36 |     180 | MEM    | -   |   0    | 56      |    0.03 |      212 |    0.06 |     277 |
|     |   2 | Feas.     | 25.75 |     596 | MEM    | -   |   0    | 69      |    0.03 |      221 |    0.02 |     102 |
|     |   3 | Feas.     | 35.99 |     278 | MEM    | -   |   0    | 61      |    0.01 |       60 |    0.03 |     107 |

Table 4: Constraint programming results for medium-sized instances

|    |     |       |                 | ( CP RANK )   | ( CP RANK )   | ( CP VERTEX )   | ( CP VERTEX )   | ( CP COMBINED )   | ( CP COMBINED )   |
|----|-----|-------|-----------------|---------------|---------------|-----------------|-----------------|-------------------|-------------------|
| n  | D   | Inst. | Status          | Time          | Ch.Pts.       | Time            | Ch.Pts.         | Time              | Ch.Pts.           |
| 65 | 0.2 | 1     | Infeas.         | TL            | 265M          | 4.60            | 12430           | 2.46              | 3781              |
|    |     | 2     | Infeas.         | TL            | 266M          | 5.01            | 12963           | 3.50              | 4263              |
|    |     | 3     | Infeas.         | TL            | 267M          | 8.09            | 16647           | 2.49              | 3574              |
|    | 0.3 | 1     | Infeas.         | TL            | 297M          | 352.77          | 428908          | 86.21             | 79144             |
|    |     | 2     | Infeas.         | TL            | 294M          | 2659.91         | 3.8M            | 22.35             | 23589             |
|    |     | 3     | Infeas.         | TL            | 295M          | 116.46          | 149767          | 213.19            | 200152            |
|    | 0.4 | 1     | Unsol.          | TL            | 292M          | TL              | > 24M           | TL                | > 14M             |
|    |     | 2     | Unsol.          | TL            | 294M          | TL              | > 26M           | TL                | > 14M             |
|    |     | 3     | Unsol.          | TL            | 293M          | TL              | > 22M           | TL                | > 13M             |
|    | 0.5 | 1     | Feas.           | 27.63         | > 1.2M        | 3.84            | 22151           | 7.75              | 23745             |
|    |     | 2     | Feas.           | 319.69        | > 13M         | 46.63           | 248767          | 19.81             | 60984             |
|    |     | 3     | Feas.           | 73.69         | > 3.1M        | 20.23           | 120980          | 70.21             | 229712            |
| 70 | 0.2 | 1     | Infeas.         | TL            | 246M          | 2.47            | 6133            | 7.46              | 10838             |
|    |     | 2     | Infeas.         | TL            | 249M          | 3.89            | 8936            | 3.32              | 4681              |
|    |     | 3     | Infeas.         | TL            | 247M          | 9.58            | 19539           | 4.11              | 4635              |
|    | 0.3 | 1     | Infeas.         | TL            | 271M          | TL              | > 8.4M          | 2424.76           | > 2.3M            |
|    |     | 2     | Infeas.         | TL            | 277M          | 587.53          | 676349          | 65.50             | 59863             |
|    |     | 3     | Infeas.         | TL            | 268M          | 1692.80         | > 2.2M          | 304.72            | 262913            |
|    | 0.4 | 1     | Unsol.          | TL            | 274M          | TL              | 22M             | TL                | > 14M             |
|    |     | 2     | Feas.           | TL            | 276M          | 1596.55         | > 4.9M          | 6490.16           | > 12M             |
|    |     | 3     | Unsol.          | TL            | 274M          | TL              | > 21M           | TL                | > 13M             |
|    | 0.5 | 1     | Feas.           | 53.29         | > 2.2M        | 19.95           | 95724           | 6.06              | 16960             |
|    |     | 2     | Feas.           | 15.79         | 657645        | 11.01           | 54130           | 51.68             | 146234            |
|    |     | 3     | Feas.           | 153.93        | > 6.4M        | 23.30           | 108045          | 26.21             | 67902             |
| 75 | 0.2 | 1     | Infeas.         | TL            | 232M          | 13.70           | 20500           | 4.54              | 5683              |
|    |     | 2     | Infeas.         | TL            | 228M          | 21.23           | 39721           | 2.57              | 3272              |
|    |     | 3     | Infeas.         | TL            | 234M          | 13.82           | 23875           | 3.38              | 4321              |
|    | 0.3 | 1     | Infeas.         | TL            | 250M          | TL              | > 7.3M          | 2388.75           | > 2.0M            |
|    |     | 2     | Infeas.         | TL            | 253M          | TL              | > 7.6M          | 2627.21           | > 2.2M            |
|    |     | 3     | Infeas.         | TL            | 249M          | TL              | > 7.8M          | 1393.82           | > 1.1M            |
|    | 0.4 | 1     | Unsol.          | TL            | 256M          | TL              | > 17M           | TL                | > 11M             |
|    |     | 2     | Feas.           | TL            | 255M          | 4720.92         | > 13M           | TL                | > 13M             |
|    |     | 3     | Unsol.          | TL            | 258M          | TL              | > 21M           | TL                | > 13M             |
|    | 0.5 | 1     | Feas.           | 52.18         | 2.1M          | 8.98            | 36417           | 13.41             | 32718             |
|    |     | 2     | Feas.           | 30.63         | > 12.M        | 6.24            | 26811           | 25.00             | 65955             |
|    |     | 3     | Feas.           | 29.06         | > 1.1M        | 10.25           | 44649           | 52.63             | 137809            |
| 80 | 0.2 | 1     | Infeas.         | TL            | 217M          | 10.54           | 14933           | 21.26             | 22259             |
|    |     | 2     | Infeas.         | TL            | 208M          | 4.92            | 7799            | 11.85             | 13623             |
|    |     | 3     | Infeas.         | TL            | 217M          | 10.48           | 15404           | 16.55             | 18362             |
|    | 0.3 | 1     | Unsol.          | TL            | 235M          | TL              | 6.8M            | TL                | > 5.7M            |
|    |     | 2     | Unsol.          | TL            | 236M          | TL              | 6.8M            | TL                | > 5.5M            |
|    |     | 3     | Infeas.         | TL            | 234M          | TL              | > 7.1M          | 5465.09           | > 4.0M            |
|    | 0.4 | 1     | Feas.           | TL            | 242M          | 198.71          | 546437          | TL                | > 11M             |
|    |     | 2     | Unsol.          | TL            | 240M          | TL              | > 17M           | TL                | > 11M             |
|    |     | 3     | Unsol.          | TL            | 241M          | TL              | > 20M           | TL                | > 11M             |
|    |     | 1     |                 |               |               |                 |                 |                   | 15534             |
|    | 0.5 |       | Feas.           | 8.63          | 325945        | 30.99           | 118909          | 7.02              |                   |
|    |     | 2     | Feas.           | 9.16          | 366384        | 4.49            | 16480           | 19.60             | 44067             |
|    |     | 3     | Feas.           | 22.14         | 835657        | 12.22           | 43777           | 34.61             | 76300             |
| 85 | 0.2 | 1 2   | Infeas. Infeas. | TL TL         | 198M 195M     | 21.74 18.74     | 26137 25012     | 6.59 33.92        | 5974 30334        |

|     |     | 3   | Infeas.     | TL          | 194M          | 21.51       | 27435        | 5.46       | 5022        |
|-----|-----|-----|-------------|-------------|---------------|-------------|--------------|------------|-------------|
|     | 0.3 | 1   | Unsol.      | TL          | 220M          | TL          | > 7.2M       | TL         | > 5.3M      |
|     |     | 2   | Unsol.      | TL          | 218M          | TL          | > 6.5M       | TL         | > 5.2M      |
|     |     | 3   | Unsol.      | TL          | 218M          | TL          | > 7.8M       | TL         | > 5.6M      |
|     | 0.4 | 1   | Unsol.      | TL          | 226M          | TL          | 1.78E+07     | TL         | > 10M       |
|     |     | 2   | Feas.       | TL          | 225M          | 2666.80     | > 6.8M       | 3726.22    | > 5.7M      |
|     |     | 3   | Feas.       | TL          | 227M          | TL          | > 13M        | 2492.79    | > 3.7M      |
|     | 0.5 | 1   | Feas.       | 25.75       | 958375        | 18.42       | 44029        | 6.32       | 13251       |
|     |     | 2   | Feas.       | 16.45       | 604637        | 33.96       | 80773        | 2.26       | 5249        |
|     |     | 3   | Feas.       | 25.58       | 916732        | 9.04        | 20806        | 35.66      | 78389       |
| 90  | 0.2 | 1   | Infeas.     | TL          | 183M          | 52.08       | 40320        | 20.69      | 17215       |
|     |     | 2   | Infeas.     | TL          | 181M          | 60.12       | 50875        | 51.51      | 39634       |
|     |     | 3   | Infeas.     | TL          | 186M          | 42.69       | 32850        | 26.70      | 20576       |
|     | 0.3 | 1   | Unsol.      | TL          | 201M          | TL          | > 5.3M       | TL         | > 5.3M      |
|     |     | 2   | Unsol.      | TL          | 201M          | TL          | > 5.8M       | TL         | > 4.7M      |
|     |     | 3   | Unsol.      | TL          | 185M          | TL          | > 6.6M       | TL         | > 5.4M      |
|     | 0.4 | 1   | Feas.       | TL          | 197M          | 5786.42     | > 13M        | TL         | > 10M       |
|     |     | 2   | Feas.       | TL          | 192M          | 2306.22     | > 5.1M       | TL         | > 8.7M      |
|     |     | 3   | Feas.       | TL          | 197M          | 1577.54     | > 3.3M       | TL         | > 9.6M      |
|     | 0.5 | 1   | Feas.       | 35.62       | > 1.2M        | 27.13       | 91993        | 24.86      | 48101       |
|     |     | 2   | Feas.       | 12.85       | 450199        | 2.12        | 6440         | 41.59      | 76803       |
|     |     | 3   | Feas.       | 197.06      | 6.7M          | 14.68       | 42569        | 80.77      | 160588      |
| 95  | 0.2 | 1   | Infeas.     | TL          | 168M          | 52.59       | 48464        | 49.39      | 33305       |
|     |     | 2   | Infeas.     | TL          | 178M          | 35.94       | 34804        | 37.93      | 27387       |
|     |     | 3   | Infeas.     | TL          | 187M          | 58.82       | 60428        | 47.19      | 34976       |
|     | 0.3 | 1   | Unsol.      | TL          | 182M          | TL          | > 5.8M       | TL         | > 4.8M      |
|     |     | 2   | Unsol.      | TL          | 190M          | TL          | 6.4M         | TL         | > 4.8M      |
|     |     | 3   | Unsol.      | TL          | 189M          | TL          | > 5.7M       | TL         | > 4.8M      |
|     | 0.4 | 1   | Feas.       | TL          | 181M          | 1482.63     | > 2.8M       | TL         | > 9.0M      |
|     |     | 2   | Feas.       | TL          | 180M          | TL          | > 14M        | TL         | > 9.1M      |
|     |     | 3   | Feas.       | TL          | 177M          | TL          | > 14M        | TL         | > 8.9M      |
|     | 0.5 | 1   | Feas.       | 0.75        | 18309         | 1.53        | 4223         | 6.74       | 11955       |
|     |     | 2   | Feas.       | 15.60       | 407153        | 77.00       | 246670       | 26.07      | 45377       |
|     |     | 3   | Feas.       | 2.62        | 65770         | 26.97       | 89663        | 11.23      | 18867       |
| 100 | 0.2 | 1   | Infeas.     | TL          | 141M          | 52.52       | 49457        | 44.07      | 30257       |
|     |     | 2   | Infeas.     | TL          | 171M          | 51.74       | 45165        | 88.06      | 56078 48202 |
|     |     | 3   | Infeas.     | TL          | 169M          | 79.87       | 55536        | 89.22      |             |
|     | 0.3 | 1   | Unsol.      | TL          | 178M          | TL          | > 5.7M       | TL         | > 4.5M      |
|     |     | 2   | Unsol.      | TL          | 177M          | TL          | > 5.7M       | TL         | > 4.6M      |
|     |     | 3   | Unsol.      | TL          | 177M          | TL          | > 5.5M       | TL         | > 4.4M      |
|     | 0.4 | 1   | Feas.       | TL          | 193M          | 3712.55     | > 7.4M       | TL         | > 8.5M      |
|     |     | 2   | Unsol.      | TL          | 186M          | TL          | > 1.2M       | TL         | > 8.5M      |
|     |     | 3   | Feas.       | TL          | 192M          | 5567.75     | > 1.1M       | 4220.47    | > 5.0M      |
|     | 0.5 | 1   | Feas.       | 27.81       | 856316        | 9.95        | 27349        | 50.73      | 81993       |
|     |     | 2 3 | Feas. Feas. | 12.77 25.64 | 389470 782540 | 36.75 29.37 | 119129 79750 | 3.51 56.99 | 5929 95817  |

Table 5: Results for ( IP CD ) and ( IP RELAX ) on small instances.

|    |     |       |         | ( IP RELAX )   | ( IP RELAX )   | # Cliques   | # Cliques    | Time      | Time         | BB Nodes   | BB Nodes     |
|----|-----|-------|---------|----------------|----------------|-------------|--------------|-----------|--------------|------------|--------------|
| n  | D   | Inst. | Status  | Solved         | DMDGP found    | ( IP CD )   | ( IP RELAX ) | ( IP CD ) | ( IP RELAX ) | ( IP CD )  | ( IP RELAX ) |
| 20 | 0.3 | 1     | Infeas. | -              | -              | 168         | 7            | 0.00      | 0.00         | 0          | 0            |
|    |     | 2     | Infeas. | -              | -              | 48          | 2            | 0.00      | 0.00         | 0          | 0            |
|    |     | 3     | Infeas. | -              | -              | 96          | 4            | 0.00      | 0.00         | 0          | 0            |
|    | 0.5 | 1     | Infeas. | -              | -              | 1656        | 69           | 4.13      | 2.08         | 0          | 0            |
|    |     | 2     | Infeas. | -              | -              | 1920        | 80           | 5.66      | 1.83         | 0          | 0            |
|    |     | 3     | Infeas. | -              | -              | 1272        | 53           | 1.86      | 0.00         | 0          | 0            |
|    | 0.7 | 1     | Feas.   | Yes            | No             | 13872       | 578          | TL        | 5308.77      | 0          | 6287         |
|    |     | 2     | Feas.   | Yes            | No             | 12000       | 500          | TL        | 2217.26      | 0          | 7172         |
|    |     | 3     | Feas.   | Yes            | No             | 13872       | 578          | TL        | 2105.65      | 0          | 3579         |
| 25 | 0.3 | 1     | Infeas. | -              | -              | 288         | 12           | 0.00      | 0.00         | 0          | 0            |
|    |     | 2     | Infeas. | -              | -              | 216         | 9            | 0.00      | 0.00         | 0          | 0            |
|    |     | 3     | Infeas. | -              | -              | 96          | 4            | 0.00      | 0.00         | 0          | 0            |
|    | 0.5 | 1     | Infeas. | -              | -              | 4776        | 199          | 0.03      | 0.01         | 0          | 0            |
|    |     | 2     | Infeas. | -              | -              | 4368        | 182          | 962.72    | 4095.70      | 0          | 7968         |
|    |     | 3     | Infeas. | -              | -              | 3960        | 165          | 632.05    | TL           | 0          | 18996        |
|    | 0.7 | 1     | Feas.   | No             | -              | 36360       | 1515         | MEM       | TL           | -          | 287          |
|    |     | 2     | Feas.   | No             | -              | 34344       | 1431         | MEM       | TL           | -          | 180          |
|    |     | 3     | Feas.   | Yes            | No             | 32856       | 1369         | MEM       | 4536.87      | -          | 333          |
| 30 | 0.3 | 1     | Infeas. | -              | -              | 264         | 11           | 0.00      | 0.01         | 0          | 0            |
|    |     | 2     | Infeas. | -              | -              | 240         | 10           | 0.00      | 0.01         | 0          | 0            |
|    |     | 3     | Infeas. | -              | -              | 360         | 15           | 0.00      | 0.01         | 0          | 0            |
|    | 0.5 | 1     | Feas.   | No             | -              | 10896       | 454          | TL        | TL           | 0          | 3742         |
|    |     | 2     | Unsol.  | -              | -              | 9264        | 386          | TL        | TL           | 0          | 3293         |
|    |     | 3     | Feas.   | -              | -              | 9960        | 415          | TL        | TL           | 0          | 2866         |
|    | 0.7 | 1     | Feas.   | No             | -              | 73872       | 3078         | MEM       | TL           | -          | 12           |
|    |     | 2     | Feas.   | No             | -              | 72888       | 3037         | MEM       | TL           | -          | 6            |
|    |     | 3     | Feas.   | No             | -              | 76488       | 3187         | MEM       | TL           | -          | 3            |
| 35 | 0.3 | 1     | Infeas. | -              | -              | 864         | 36           | 0.00      | 0.01         | 0          | 0            |
|    |     | 2     | Infeas. | -              | -              | 576         | 24           | 0.00      | 0.01         | 0          | 0            |
|    |     | 3     | Infeas. | -              | -              | 696         | 29           | 0.00      | 0.01         | 0          | 0            |
|    | 0.5 | 1     | Feas.   | No             | -              | 18888       | 787          | TL        | TL           | 0          | 1457         |
|    |     | 2     | Feas.   | No             | -              | 21408       | 892          | TL        | TL           | 0          | 1828         |
|    |     | 3     | Feas.   | No             | -              | 20304       | 846          | TL        | TL           | 0          | 605          |
|    | 0.7 | 1     | Feas.   | No             | -              | 143616      | 5984         | MEM       | TL           | -          | 0            |
|    |     | 2     | Feas.   | No             | -              | 151056      | 6294         | MEM       | TL           | -          | 0            |

|    |     | 3   | Feas.           |       |     | 140976   | 5874        | MEM        | TL      | -   | 0   |
|----|-----|-----|-----------------|-------|-----|----------|-------------|------------|---------|-----|-----|
| 40 | 0.3 | 1   | Infeas.         | -     | -   | 1776     | 74          | 0.00       | 0.01    | 0   | 0   |
|    |     | 2   | Infeas.         | -     | -   | 816      | 34          | 0.00       | 0.01    | 0   | 0   |
|    |     | 3   | Infeas.         | -     | -   | 1344     | 56          | 0.00       | 0.01    | 0   | 0   |
|    | 0.5 | 1   | Feas.           | No    | -   | 34680    | 1445        | MEM        | TL      | -   | 56  |
|    |     | 2   | Feas.           | No    | -   | 37056    | 1544        | MEM        | TL      | -   | 72  |
|    |     | 3   | Feas.           | No    | -   | 35160    | 1465        | MEM        | TL      | -   | 48  |
|    | 0.7 | 1   | Feas.           | No    | -   | 250608   | 10442       | MEM        | TL      | -   | 0   |
|    |     | 2   | Feas.           | No    | -   | 265440   | 11060       | MEM        | TL      | -   | 0   |
|    |     | 3   | Feas.           | No    | -   | 256224   | 10676       | MEM        | TL      | -   | 0   |
| 45 | 0.3 | 1   | Infeas.         | -     | -   | 2136     | 89          | 0.01       | 0.02    | 0   | 0   |
|    |     | 2   | Infeas.         | -     | -   | 2472     | 103         | 0.01       | 0.02    | 0   | 0   |
|    |     | 3   | Infeas.         | -     | -   | 2376     | 99          | 1.89       | 0.02    | 0   | 0   |
|    | 0.5 | 1   | Feas.           | No    | -   | 55032    | 2293        | MEM        | TL      | -   | 0   |
|    |     | 2   | Feas.           | No    | -   | 56664    | 2361        | MEM        | TL      | -   | 2   |
|    |     | 3   | Feas.           | No    | -   | 54360    | 2265        | MEM        | TL      | -   | 5   |
|    | 0.7 | 1   | Feas.           | No    | -   | 412416   | 17184       | MEM        | MEM     | -   | -   |
|    |     | 2   | Feas.           | No    | -   | 404088   | 16837       | MEM        | MEM     | -   | -   |
|    | 0.3 | 3   | Feas.           | No    | -   | 423720   | 17655       | MEM        | MEM     | -   | -   |
| 50 |     | 1   | Infeas.         | -     | -   | 4536     | 189         | 0.02       | 0.02    | 0   | 0   |
|    |     | 2   | Infeas.         | -     | -   | 3768     | 157         | 7.04       | 0.42    | 0 0 | 0   |
|    |     | 3   | Infeas.         | -     | -   | 4296     | 179         | 0.02       | 0.03    |     | 0   |
|    | 0.5 | 1   | Feas.           | No    | -   | 87552    | 3648        | MEM        | TL      | -   | 0   |
|    |     | 2   | Feas.           | No    | -   | 83544    | 3481        | MEM        | TL      | -   | 0   |
|    |     | 3   | Feas.           | No    | -   | 82680    | 3445        | MEM        | TL MEM  | - - | 0   |
|    | 0.7 | 1   | Feas.           | No    | -   | 621552   | 25898 27386 | MEM MEM    |         |     | -   |
|    |     | 2 3 | Feas.           | No    | -   | 657264   |             |            | MEM     | -   | - - |
| 55 | 0.3 | 1   | Feas.           | No    | -   | 662352   | 27598       | MEM        | MEM     | -   | 0   |
|    |     | 2   | Infeas. Infeas. | - -   | -   | 5328     | 222 204     | 14.13 0.03 | 539.85  | 0   | 0   |
|    |     | 3   | Infeas.         |       | -   | 4896     | 232         |            | 0.04    | 0   |     |
|    |     |     |                 | -     | -   | 5568     |             | 0.03       | 0.03    | 0   | 0   |
|    | 0.5 | 1 2 | Feas. Feas.     | No No | -   | 127608   | 5317 5400   | MEM MEM    | TL      | -   | 0   |
|    |     | 3   |                 |       | -   | 129600   |             |            | TL      | -   | 0   |
|    |     | 1   | Feas.           | No    | -   | 126168   | 5257        | MEM        | TL      | -   | 0   |
|    | 0.7 | 2   | Feas. Feas.     | No No | - - | 958200   | 39925 39456 | MEM MEM    | MEM MEM | - - | - - |
|    |     | 3   |                 | No    | -   | 946944   |             |            |         |     |     |
|    |     |     | Feas.           |       |     | 994824   | 41451       | MEM        | MEM     | -   | -   |
| 60 | 0.3 | 1   | Infeas.         | -     | -   | 8976     | 374         | 4061.37    | TL      | 0   | 0   |
|    |     |     |                 |       |     |          | 287         | 26.81      |         |     | 0   |
|    |     | 2   | Infeas.         | -     | -   | 6888     |             |            | 371.402 | 0   |     |

|     |   3 | Infeas.   | -   | - 8424    |        | 351 0.07   | 0.05   | 0   | 0   |
|-----|-----|-----------|-----|-----------|--------|------------|--------|-----|-----|
| 0.5 |   1 | Feas.     | No  | - 171840  | 188496 | 7854 MEM   | TL     | -   | 0   |
|     |   2 | Feas.     | No  | -         |   7160 | MEM        | TL     | -   | 0   |
|     |   3 | Feas.     | No  | - 184728  |   7697 | MEM        | TL     | -   | 0   |
| 0.7 |   1 | Feas.     | No  | - 1406256 |  58594 | MEM        | MEM    | -   | -   |
|     |   2 | Feas.     | No  | - 1363296 |  56804 | MEM        | MEM    | -   | -   |
|     |   3 | Feas.     | No  | - 1379184 |  57466 | MEM        | MEM    | -   | -   |

Table 6: Integer programming and constraint programming results for pseudo-protein instances with 30 vertices.

|               |       |         | IP VR )   | IP VR )   | ( CP VERTEX )   | ( CP VERTEX )   | ( CP COMBINED )   | ( CP COMBINED )   |
|---------------|-------|---------|-----------|-----------|-----------------|-----------------|-------------------|-------------------|
| Protein Inst. | Ratio | Status  | Time      | BB Nodes  | Time            | Ch.Pts.         | Time              | Ch.Pts.           |
| 1a70          | 3.2   | Infeas. | 4604.21   | 52219     | 1.08            | 6709            | 0.41              | 2859              |
|               | 3.6   | Infeas. | 2225.23   | 39693     | 4.18            | 23385           | 0.91              | 4328              |
|               | 4     | Infeas. | TL        | 56015     | 4.32            | 38727           | 0.80              | 3867              |
| 1bpm          | 3.2   | Infeas. | 322.34    | 8808      | 1.65            | 8308            | 0.35              | 2238              |
|               | 3.6   | Infeas. | TL        | 56680     | 3.41            | 15735           | 0.69              | 3013              |
|               | 4     | Infeas. | TL        | 42352     | 97.97           | 750383          | 0.66              | 3352              |
| 1crn          | 3.2   | Infeas. | 3369.59   | 34243     | 1.12            | 6849            | 0.63              | 3539              |
|               | 3.6   | Infeas. | 1792.99   | 19305     | 2.61            | 13252           | 0.63              | 2756              |
|               | 4     | Infeas. | TL        | 99938     | 29.08           | 223126          | 1.61              | 5645              |
| 1fs3          | 3.2   | Infeas. | 807.31    | 18352     | 1.46            | 9041            | 0.42              | 2189              |
|               | 3.6   | Infeas. | TL        | 54702     | 15.51           | 94649           | 0.40              | 2129              |
|               | 4     | Infeas. | TL        | 50079     | 298.60          | > 2.0M          | 0.34              | 2111              |
| 1hoe          | 3.2   | Infeas. | TL        | 38688     | 0.76            | 5497            | 0.35              | 1923              |
|               | 3.6   | Infeas. | 5055.60   | 71768     | 1.07            | 6907            | 0.45              | 2399              |
|               | 4     | Infeas. | TL        | 86792     | 0.33            | 5118            | 1.47              | 7793              |
| 1jk2          | 3.2   | Infeas. | 1767.65   | 16345     | 0.53            | 5054            | 0.04              | 199               |
|               | 3.6   | Infeas. | TL        | 69336     | 13.57           | 95799           | 0.61              | 3090              |
|               | 4     | Infeas. | TL        | 67076     | 158.49          | > 1.1M          | 0.81              | 3611              |
| 1m40          | 3.2   | Infeas. | TL        | 56590     | 1.22            | 8650            | 0.04              | 175               |
|               | 3.6   | Infeas. | TL        | 89419     | 8.37            | 47765           | 0.99              | 4695              |
|               | 4     | Feas.   | 1.47      | 0         | 0.20            | 4136            | 0.04              | 125               |
| 1mbn          | 3.2   | Infeas. | 4942.26   | 79612     | 1.44            | 8725            | 0.64              | 3012              |
|               | 3.6   | Infeas. | TL        | 89117     | 95.72           | 909899          | 0.96              | 3635              |
|               | 4     | Feas.   | 1.10      | 0         | 0.29            | 6369            | 0.03              | 125               |
| 1mqq          | 3.2   | Infeas. | 611.58    | 9189      | 1.65            | 10436           | 0.04              | 120               |
|               | 3.6   | Infeas. | 1625.82   | 28685     | 6.77            | 40807           | 0.76              | 4132              |
|               | 4     | Infeas. | 3920.73   | 85169     | TL              | > 10M           | 0.49              | 3057              |
| 1n4w          | 3.2   | Infeas. | 1081.08   | 19770     | 0.76            | 4815            | 0.40              | 2078              |
|               | 3.6   | Infeas. | 2589.28   | 45410     | 3.12            | 16796           | 0.41              | 2121              |
|               | 4     | Infeas. | TL        | 61732     | 375.82          | > 2.3M          | 0.72              | 3742              |
| 1pht          | 3.2   | Infeas. | 2199.55   | 26860     | 1.15            | 8173            | 0.42              | 2360              |
|               | 3.6   | Infeas. | TL        | 49646     | 4.45            | 20621           | 0.75              | 3353              |
|               | 4     | Infeas. | 2002.63   | 28365     | 498.87          | > 3.0M          | 0.83              | 3841              |
| 1poa          | 3.2   | Infeas. | 1789.90   | 28365     | 1.09            | 7930            | 0.66              | 2828              |
|               | 3.6   | Infeas. | TL        | 50532     | 4.13            | 27347           | 0.82              | 3843              |
|               | 4     | Infeas. | TL        | 75421     | 0.40            | 7478            | 0.74              | 3911              |
| 1ppt          | 3.2   | Infeas. | 3392.28   | 47378     | 0.99            | 5799            | 0.35              | 1769              |
|               | 3.6   | Infeas. | TL        | 91485     | 31.51           | 224397          | 0.63              | 2425              |
|               | 4     | Feas.   | 0.00      | 0         | 0.03            | 442             | 0.03              | 146               |
| 1ptq          | 3.2   | Infeas. | 1848.53   | 25844     | 0.61            | 5312            | 0.78              | 4445              |
|               | 3.6   | Infeas. | TL        | 58213     | 1.82            | 9084            | 0.81              | 5014              |
|               | 4     | Infeas. | TL        | 43553     | 6.89            | 38551           | 0.58              | 2917              |
| 1rgs          | 3.2   | Infeas. | 839.14    | 10360     | 0.57            | 5043            | 0.02              | 172               |
|               | 3.6   | Infeas. | TL        | 44037     | 2.15            | 14020           | 0.69              | 3633              |
|               | 4     | Infeas. | TL        | 104246    | 1370.58         | > 7.4M          | 0.54              | 3057              |
| 1rwh          |       | Infeas. | 3217.58   |           |                 |                 | 0.60              | 2786              |
|               | 3.6   | Feas.   | 158.48    | 6669      | 0.17            | 2760            | 0.02              | 69                |
|               | 3.2   |         |           | 53607     | 0.92            | 6084            |                   |                   |

|      |   4 | Feas.   | 2.01    |     0 |   0.27 |   5142 |   0.05 |   204 |
|------|-----|---------|---------|-------|--------|--------|--------|-------|
| 2e7z | 3.2 | Infeas. | 2279.91 | 27233 |   0.97 |   5272 |   0.56 |  2957 |
|      | 3.6 | Infeas. | 1673.16 | 20537 |   1.48 |   8026 |   0.71 |  3252 |
|      | 4   | Infeas. | TL      | 60329 |   6.82 |  40804 |   0.7  |  3718 |
| 2erl | 3.2 | Infeas. | 1474.13 | 23389 |   1.58 |   8805 |   0.67 |  3455 |
|      | 3.6 | Feas.   | 1.42    |     0 |   0.08 |   1094 |   0.06 |   193 |
|      | 4   | Feas.   | 0.78    |     0 |   0.07 |    816 |   0.06 |   228 |
| 3b34 | 3.2 | Infeas. | 1114.74 | 15921 |   1.04 |   7269 |   0.61 |  3176 |
|      | 3.6 | Infeas. | TL      | 75837 |   8.21 |  43068 |   0.62 |  3367 |
|      | 4   | Feas.   | 449.81  | 12928 |   0.34 |   5408 |   0.03 |   154 |

Table 7: Integer programming and constraint programming results for pseudo-protein instances with 40 vertices.

|               |         |                 | IP VR )    | IP VR )     | ( CP VERTEX )   | ( CP VERTEX )   | ( CP COMBINED )   | ( CP COMBINED )   |
|---------------|---------|-----------------|------------|-------------|-----------------|-----------------|-------------------|-------------------|
| Protein Inst. | Ratio   | Status          | Time       | BB Nodes    | Time            | Ch.Pts.         | Time              | Ch.Pts.           |
| 1a70          | 3.2 3.6 | Infeas. Infeas. | TL TL      | 10204 25380 | 1.67 5.75       | 8308 30493      | 0.61 0.83         | 2950 3628         |
| 1bpm          | 3.2 3.6 | Infeas. Infeas. | TL TL      | 16123 19203 | 2.50 5.88       | 8143 19069      | 0.79 0.72         | 4058 3902         |
| 1crn          | 3.2 3.6 | Infeas. Infeas. | 4224.48 TL | 10435 19448 | 1.79 3.45       | 8465 15341      | 0.94 0.80         | 4454 3656         |
| 1fs3          | 3.2 3.6 | Infeas. Infeas. | TL TL      | 15318 24270 | 3.28 5.76       | 12003 21182     | 1.14 0.92         | 5309 4782         |
| 1hoe          | 3.2 3.6 | Infeas. Infeas. | TL TL      | 15870 20005 | 2.72 8.03       | 14777 32487     | 0.61 0.57         | 3247 3070         |
| 1jk2          | 3.2 3.6 | Infeas. Infeas. | TL TL      | 19556 21651 | 1.73 8.46       | 7675 22447      | 0.75 1.12         | 3450 4337         |
| 1m40          | 3.2 3.6 | Infeas. Infeas. | TL TL      | 15787 16298 | 2.31 19.67      | 12037 91045     | 0.71 0.75         | 3246 3293         |
| 1mbn          | 3.2 3.6 | Infeas. Infeas. | TL TL      | 20084 16910 | 1.99 7.69       | 12083 38286     | 0.74 0.72         | 3270 3056         |
| 1mqq          | 3.2 3.6 | Infeas. Infeas. | TL TL      | 17641 18693 | 1.82 2.10       | 8174 10345      | 0.67 0.91         | 3265 4288         |
| 1n4w          | 3.2 3.6 | Infeas. Infeas. | TL TL      | 16383 19753 | 1.39 5.65       | 8671 22930      | 0.63 0.69         | 3605 3629         |
| 1pht          | 3.2 3.6 | Infeas. Infeas. | TL TL      | 14685 15589 | 0.85 5.57       | 4909 21237      | 0.81 1.32         | 3526 5594         |
| 1poa          | 3.2 3.6 | Infeas. Infeas. | TL TL      | 13663 12606 | 1.64 19.96      | 8102 74199      | 0.74 0.73         | 4087 3410         |
| 1ppt          | 3.2 3.6 | Infeas. Infeas. | TL TL      | 15439 17335 | 1.37 5.89       | 6606 22059      | 0.65 0.99         | 3043 4279         |
| 1ptq          | 3.2 3.6 | Infeas. Infeas. | TL TL      | 13100 18384 | 1.55 3.68       | 7891 12410      | 1.21 1.50         | 6627 5066         |
| 1rgs          | 3.2 3.6 | Infeas. Infeas. | TL TL      | 12877 20928 | 1.11 3.42       | 5351 14811      | 0.91 0.88         | 5290 3708         |
| 1rwh          | 3.2 3.6 | Infeas. Infeas. | TL TL      | 17670 18284 | 3.39 7.78       | 14650 40109     | 0.92 0.74         | 3995 3084         |
| 2e7z          | 3.2 3.6 | Infeas.         | TL         | 12302 18263 | 1.14 1.18       | 5144            | 0.03 0.57         | 158 3358          |
|               |         | Infeas.         | TL         |             |                 | 6855            |                   |                   |
| 3b34          | 3.2 3.6 | Infeas. Infeas. | TL TL      | 17831 21114 | 2.07 15.03      | 9040 67777      | 0.74 1.10         | 3415 5087         |

Table 8: Integer programming and constraint programming results for pseudo-protein instances with 50 vertices.

|                     |                                         |                                                                                                     | ( IP VR )                                    | ( IP VR )                                                           | ( CP VERTEX )                                                       | ( CP VERTEX )                                                             | ( CP COMBINED )                                             | ( CP COMBINED )                                  |
|---------------------|-----------------------------------------|-----------------------------------------------------------------------------------------------------|----------------------------------------------|---------------------------------------------------------------------|---------------------------------------------------------------------|---------------------------------------------------------------------------|-------------------------------------------------------------|--------------------------------------------------|
| Protein Inst.       | Ratio                                   | Status                                                                                              | Time                                         | BB Nodes                                                            | Time                                                                | Ch.Pts.                                                                   | Time                                                        | Ch.Pts.                                          |
| 1a70                | 3.2                                     | Infeas.                                                                                             | TL                                           | 7146                                                                | 1.28                                                                | 6806                                                                      | 2.03                                                        | 4484                                             |
|                     | 3.6                                     | Infeas.                                                                                             | TL                                           | 15102                                                               | 9.97                                                                | 24153                                                                     | 2.03                                                        | 3884                                             |
|                     | 4                                       | Infeas.                                                                                             | TL                                           | 10292                                                               | 7.11                                                                | 24801                                                                     | 15.99                                                       | 20542                                            |
| 1bpm                | 3.2                                     | Infeas.                                                                                             | TL                                           | 7896                                                                | 3.78                                                                | 7000                                                                      | 2.62                                                        | 6094                                             |
|                     | 3.6                                     | Infeas.                                                                                             | TL                                           | 9105                                                                | 7.76                                                                | 13444                                                                     | 3.22                                                        | 5509                                             |
|                     | 4                                       | Infeas.                                                                                             | TL                                           | 9105                                                                | 151.23                                                              | 376910                                                                    | 5.31                                                        | 6452                                             |
| 1crn                | 3.2                                     | Infeas.                                                                                             | TL                                           | 6500                                                                | 2.96                                                                | 7266                                                                      | 1.46                                                        | 4060                                             |
|                     |                                         |                                                                                                     | TL                                           | 9784                                                                | 10.10 112.13                                                        | 17726                                                                     | 2.22 4.17                                                   |                                                  |
|                     | 3.6                                     | Infeas.                                                                                             |                                              | 11951                                                               |                                                                     | 225468                                                                    |                                                             | 5324 7249                                        |
| 1fs3                | 3.2                                     | Infeas. Infeas.                                                                                     | TL TL                                        | 7316 7872 9452 8573                                                 | 4.30 7.15                                                           | 294908 9275 15433                                                         | 1.87 1.63 2.02                                              | 4557                                             |
|                     | 4                                       | Infeas.                                                                                             | TL                                           | 7392 10346                                                          | 6.25 14.68                                                          | 13825 23511                                                               | 1.78                                                        |                                                  |
|                     | 4 3.2                                   | Infeas. Infeas. Infeas. Infeas.                                                                     | TL TL                                        |                                                                     | 110.03 213.36                                                       | 488661                                                                    | 1.66                                                        | 4663 4514                                        |
|                     | 3.6                                     |                                                                                                     |                                              |                                                                     |                                                                     |                                                                           |                                                             |                                                  |
|                     |                                         |                                                                                                     |                                              |                                                                     |                                                                     |                                                                           |                                                             | 5222                                             |
| 1hoe                | 3.6                                     |                                                                                                     | TL                                           |                                                                     |                                                                     |                                                                           | 1.09                                                        | 4186 3419                                        |
|                     | 4                                       |                                                                                                     | TL TL                                        |                                                                     |                                                                     | 14930                                                                     |                                                             | 6384                                             |
| 1jk2                | 3.2 3.6                                 | Infeas. Infeas.                                                                                     | TL                                           | 9050 5357                                                           | 7.28 25.67                                                          | 57594                                                                     | 2.53 1.84                                                   | 3814                                             |
|                     | 4                                       | Infeas.                                                                                             | TL                                           | 11742                                                               | TL                                                                  | > 10M                                                                     | 2.66                                                        | 5037                                             |
| 1m40 1mbn 1mqq 1n4w | 3.2 3.6 4 3.2 3.6 4 3.2 3.6 4 3.2 3.6 4 | Infeas. Infeas. Feas. Infeas. Infeas. Feas. Infeas. Infeas. Infeas. Infeas. Infeas. Infeas. Infeas. | TL TL TL TL TL 43.38 TL TL TL TL TL TL TL TL | 6602 6961 9741 6016 8144 0 6916 8605 9741 6339 7337 11659 7345 7241 | 5.22 14.62 8.83 5.21 18.61 0.46 1.28 9.20 3891.61 4.22 7.69 TL 9.75 | 12346 25275 15982 9520 35128 4451 4949 21491 > 10M 7807 18797 > 10M 15474 | 2.05 3.25 1.73 2.07 3.82 0.20 1.60 1.24 2.31 2.05 3.40 1.56 | 4617 4917 4541 3869 6732 355 3457 3180 5368 5166 |
|                     | 4                                       | Infeas.                                                                                             |                                              |                                                                     |                                                                     | 246037                                                                    | 2.31                                                        |                                                  |
|                     |                                         |                                                                                                     |                                              |                                                                     |                                                                     |                                                                           |                                                             | 5105                                             |
|                     | 3.2                                     | Infeas.                                                                                             | TL                                           | 8142                                                                | 4.29                                                                | 9617                                                                      | 2.34                                                        |                                                  |
| 1rgs                |                                         |                                                                                                     |                                              | 8386                                                                |                                                                     |                                                                           |                                                             | 4932                                             |
|                     |                                         |                                                                                                     |                                              |                                                                     | 11.18                                                               | 20037                                                                     |                                                             |                                                  |
|                     | 3.6                                     | Infeas.                                                                                             | TL                                           |                                                                     |                                                                     |                                                                           | 4.23                                                        | 7259                                             |
|                     | 4                                       | Infeas.                                                                                             | TL                                           |                                                                     |                                                                     | > 1.5M                                                                    |                                                             |                                                  |
|                     |                                         |                                                                                                     |                                              |                                                                     |                                                                     |                                                                           |                                                             | 4620 6199 3694                                   |
|                     |                                         |                                                                                                     |                                              | 6879                                                                |                                                                     | 27143                                                                     | 2.41 3.76                                                   | 5578                                             |
| 1pht                | 3.2 3.6                                 | Infeas.                                                                                             | TL TL                                        | 11534 10109 16751                                                   | 9.18 16.07 TL                                                       |                                                                           |                                                             | 6898                                             |
| 1poa                | 4 3.2                                   | Infeas. Infeas. Infeas. Infeas.                                                                     | TL TL                                        | 12752 10449                                                         | 5.36 10.93                                                          | > 10M                                                                     | 2.58                                                        | 6642                                             |
|                     | 3.6 4                                   | Infeas.                                                                                             | TL                                           | 7559                                                                | 10.56                                                               | 9633                                                                      | 2.43 4.52                                                   | 5675                                             |
| 1ppt                |                                         |                                                                                                     | TL                                           |                                                                     |                                                                     | 18310 36356                                                               | 2.75                                                        | 8118                                             |
|                     |                                         |                                                                                                     |                                              |                                                                     |                                                                     |                                                                           |                                                             | 5962                                             |
|                     | 3.2 3.6                                 | Infeas. Infeas.                                                                                     | TL TL                                        | 6853 6624                                                           | 5.69 10.70                                                          | 10104 26856                                                               | 1.82 2.71                                                   | 4462                                             |
|                     |                                         |                                                                                                     |                                              |                                                                     |                                                                     |                                                                           |                                                             | 6355                                             |
|                     | 4                                       | Feas.                                                                                               |                                              | 0                                                                   | 2.11                                                                | 10992                                                                     | 0.49                                                        | 1083                                             |
|                     |                                         |                                                                                                     | 59.23                                        |                                                                     |                                                                     |                                                                           |                                                             |                                                  |
| 1ptq                | 3.2                                     | Infeas.                                                                                             | TL                                           | 9839                                                                | 5.66                                                                | 9239                                                                      | 0.09                                                        | 201                                              |
|                     | 3.6                                     | Infeas.                                                                                             |                                              |                                                                     |                                                                     | 17610                                                                     | 1.46                                                        | 4008                                             |
|                     |                                         |                                                                                                     |                                              |                                                                     | 104.55                                                              |                                                                           | 1.86                                                        |                                                  |
|                     |                                         |                                                                                                     |                                              | 10428                                                               | 543.82                                                              |                                                                           |                                                             |                                                  |
|                     | 3.2                                     |                                                                                                     | TL                                           |                                                                     | 5.47                                                                | 10119                                                                     | 1.84                                                        | 4771                                             |
| 1rwh                |                                         |                                                                                                     |                                              |                                                                     |                                                                     |                                                                           |                                                             |                                                  |
|                     | 3.6                                     | Feas.                                                                                               | TL                                           | 22330                                                               | 17.36                                                               | 29275                                                                     | 3.43                                                        | 6460                                             |

|      |   4 | Feas.   | 45.23   |     0 |   0.36 |   3087 |   0.61 |   1391 |
|------|-----|---------|---------|-------|--------|--------|--------|--------|
| 2e7z | 3.2 | Infeas. | TL      |  6765 |   2.48 |   6875 |   1.38 |   3520 |
|      | 3.6 | Infeas. | TL      | 12889 |   2.64 |   6208 |   1.56 |   4491 |
|      | 4   | Infeas. | TL      |  6452 |   6.83 |  13232 |   1.5  |   4294 |
| 2erl | 3.2 | Infeas. | TL      |  9874 |   0.86 |   4322 |   2.79 |   5408 |
|      | 3.6 | Feas.   | TL      |  6658 |   9.49 |  20867 |   2.41 |   5720 |
|      | 4   | Feas.   | TL      |  8051 |   0.44 |   2596 |   0.2  |    656 |
| 3b34 | 3.2 | Infeas. | TL      |  7185 |   7.34 |  13553 |   2.13 |   3678 |
|      | 3.6 | Infeas. | TL      |  9065 |  24.01 |  39688 |   3.13 |   5008 |
|      | 4   | Feas.   | TL      |  6337 |  12.33 |  31489 |   0.17 |    190 |

Table 9: Integer programming and constraint programming results for pseudo-protein instances with 60 vertices.

|                          |                                                   |                                                                                                                                                           | IP VR )                                                | IP VR )                                                                      | ( CP VERTEX )                                                                            | ( CP VERTEX )                                                                                                          | ( CP COMBINED )                                                   | ( CP COMBINED )                                                  |
|--------------------------|---------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------|--------------------------------------------------------|------------------------------------------------------------------------------|------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------|-------------------------------------------------------------------|------------------------------------------------------------------|
| Protein Inst.            | Ratio                                             | Status                                                                                                                                                    | Time                                                   | BB Nodes                                                                     | Time                                                                                     | Ch.Pts.                                                                                                                | Time                                                              | Ch.Pts.                                                          |
| 1a70                     | 3.2                                               | Infeas.                                                                                                                                                   | TL                                                     | 2162                                                                         | 1.86                                                                                     | 5387                                                                                                                   | 4.60                                                              | 7243                                                             |
|                          | 3.6                                               | Infeas.                                                                                                                                                   | TL                                                     | 1569                                                                         | 14.32                                                                                    | 24469                                                                                                                  | 3.62                                                              | 5593                                                             |
|                          | 4                                                 | Infeas.                                                                                                                                                   | TL                                                     | 4112                                                                         | 63.92                                                                                    | 208576                                                                                                                 | 4.71                                                              | 5972                                                             |
| 1bpm                     | 3.2                                               | Infeas.                                                                                                                                                   | TL                                                     | 2470                                                                         | 12.52                                                                                    | 17783                                                                                                                  | 4.81                                                              | 8603                                                             |
|                          | 3.6                                               | Infeas.                                                                                                                                                   | TL                                                     | 4552                                                                         | 16.45                                                                                    | 22124                                                                                                                  | 4.53                                                              | 7544                                                             |
|                          | 4                                                 | Infeas.                                                                                                                                                   | TL                                                     | 4579                                                                         | 883.70                                                                                   | > 2.5M                                                                                                                 | 3.03                                                              | 5205                                                             |
| 1crn                     | 3.2                                               | Infeas.                                                                                                                                                   | TL                                                     | 5388                                                                         | 5.01                                                                                     | 8665                                                                                                                   | 2.99                                                              | 4680                                                             |
|                          | 3.6                                               | Infeas.                                                                                                                                                   | TL                                                     | 5276                                                                         |                                                                                          | 21222 107859 5960                                                                                                      | 1.89 3.32 2.82 5.35 2.96                                          | 4094                                                             |
|                          | 4                                                 | Infeas.                                                                                                                                                   | TL                                                     | 3553                                                                         | 12.21 66.04                                                                              |                                                                                                                        |                                                                   | 4889                                                             |
|                          | 3.2 3.6                                           | Infeas.                                                                                                                                                   | TL TL                                                  | 2827 3210                                                                    | 15.68 6.88                                                                               | 19761                                                                                                                  |                                                                   | 5243                                                             |
|                          |                                                   | Infeas. Infeas. Infeas.                                                                                                                                   | TL                                                     |                                                                              | 4.00 122.71 11.54                                                                        | 200511 8497 17607                                                                                                      |                                                                   |                                                                  |
|                          | 4 3.2                                             | Infeas. Infeas. Infeas.                                                                                                                                   | TL                                                     | 2659                                                                         | 45.33 7.59 16.28                                                                         | 74613                                                                                                                  | 3.08 3.94 3.23                                                    | 6147                                                             |
| 1fs3                     |                                                   |                                                                                                                                                           |                                                        |                                                                              |                                                                                          |                                                                                                                        |                                                                   | 7913                                                             |
|                          |                                                   |                                                                                                                                                           |                                                        |                                                                              |                                                                                          |                                                                                                                        |                                                                   | 6191                                                             |
| 1hoe                     |                                                   |                                                                                                                                                           | TL                                                     | 2964                                                                         |                                                                                          |                                                                                                                        |                                                                   | 6314 5704                                                        |
|                          | 3.6 4                                             |                                                                                                                                                           | TL                                                     | 3038 3552                                                                    |                                                                                          |                                                                                                                        |                                                                   |                                                                  |
| 1jk2                     | 3.2 3.6                                           | Infeas.                                                                                                                                                   | TL TL                                                  | 2507                                                                         |                                                                                          | 9389 24274                                                                                                             | 2.98 2.81                                                         | 5266 5023                                                        |
|                          | 4                                                 | Infeas.                                                                                                                                                   | TL                                                     | 3157 4371                                                                    | TL                                                                                       | > 10M                                                                                                                  | 8.77                                                              | 8028                                                             |
| 1mbn 1mqq 1n4w 1pht 1poa | 3.6 4 3.2 3.6 4 3.2 3.6 4 3.2 3.6 4 3.2 3.6 4 3.2 | Infeas. Feas. Infeas. Infeas. Feas. Infeas. Infeas. Infeas. Infeas. Infeas. Infeas. Infeas. Infeas. Infeas. Infeas. Infeas. Infeas. Infeas. Feas. Infeas. | TL TL TL TL 337.83 TL TL TL TL TL TL TL TL TL TL TL TL | 3884 4456 6118 2449 0 2768 1688 4145 3458 3140 2470 4294 2964 5039 6631 2964 | 12.42 TL 8.95 27.01 0.67 6.87 22.91 822.07 29.58 42.86 TL 8.16 23.95 TL 12.21 6.97 25.83 | 16835 > 10M 9752 28484 4579 12974 40966 > 2.3M 37360 75204 > 10M 10860 31120 > 10M 14890 28235 200508 33033 29695 6181 | 3.80 1.89 4.39 4.83 0.50 3.47 6.25 2.54 5.97 10.50 3.94 6.82 4.60 | 5321 4124 6040 5907 788 5302 6501 4434 8089 10129 5816 8938 6525 |
| 1ptq                     | 3.6 4                                             | Infeas.                                                                                                                                                   | TL                                                     |                                                                              | 137.23 11.73                                                                             | 225316 14780                                                                                                           | 3.69 5.17                                                         | 7273                                                             |
| 1rgs                     | 3.2                                               |                                                                                                                                                           |                                                        | 2809                                                                         |                                                                                          |                                                                                                                        | 4.47                                                              | 7566                                                             |
|                          |                                                   |                                                                                                                                                           |                                                        |                                                                              | 19.36                                                                                    |                                                                                                                        |                                                                   | 7067                                                             |
|                          | 3.6                                               | Infeas.                                                                                                                                                   |                                                        |                                                                              |                                                                                          |                                                                                                                        |                                                                   |                                                                  |
|                          |                                                   |                                                                                                                                                           |                                                        | 1977                                                                         |                                                                                          |                                                                                                                        |                                                                   |                                                                  |
|                          |                                                   |                                                                                                                                                           | TL                                                     |                                                                              |                                                                                          | 19959                                                                                                                  |                                                                   |                                                                  |
|                          |                                                   |                                                                                                                                                           |                                                        |                                                                              |                                                                                          |                                                                                                                        |                                                                   | 6685                                                             |
|                          |                                                   |                                                                                                                                                           |                                                        |                                                                              | 165.05                                                                                   |                                                                                                                        | 5.40                                                              |                                                                  |
|                          |                                                   |                                                                                                                                                           |                                                        |                                                                              |                                                                                          |                                                                                                                        | 5.52 7.01                                                         | 7892 7891                                                        |
|                          | 4 3.2                                             |                                                                                                                                                           | TL                                                     |                                                                              |                                                                                          |                                                                                                                        | 6.34                                                              | 7700                                                             |
| 1ppt                     |                                                   | Infeas. Infeas.                                                                                                                                           | TL TL                                                  |                                                                              |                                                                                          |                                                                                                                        |                                                                   |                                                                  |
|                          | 3.6                                               |                                                                                                                                                           | TL                                                     | 0                                                                            | 1.36                                                                                     |                                                                                                                        | 4.69 5.65                                                         | 5929                                                             |
|                          | 3.6 4 3.2                                         | Infeas.                                                                                                                                                   | TL                                                     | 4923 2536 2336                                                               | 20.25 48.19 18.64                                                                        |                                                                                                                        |                                                                   |                                                                  |
|                          |                                                   |                                                                                                                                                           |                                                        | 1919                                                                         | 18.45                                                                                    |                                                                                                                        | 31.91                                                             | 33583                                                            |
|                          |                                                   |                                                                                                                                                           |                                                        | 5121                                                                         |                                                                                          |                                                                                                                        |                                                                   | 6564 1416                                                        |
|                          |                                                   |                                                                                                                                                           |                                                        |                                                                              |                                                                                          |                                                                                                                        | 0.81                                                              |                                                                  |
|                          |                                                   |                                                                                                                                                           | 308.24                                                 |                                                                              |                                                                                          |                                                                                                                        |                                                                   |                                                                  |
|                          |                                                   |                                                                                                                                                           |                                                        |                                                                              |                                                                                          | 10543                                                                                                                  |                                                                   | 6297                                                             |
|                          |                                                   |                                                                                                                                                           |                                                        | 3832                                                                         |                                                                                          | 41147                                                                                                                  | 2.71 2.24                                                         | 6036                                                             |
|                          | 4                                                 | Infeas.                                                                                                                                                   | TL                                                     |                                                                              |                                                                                          |                                                                                                                        |                                                                   |                                                                  |
|                          |                                                   | Infeas.                                                                                                                                                   |                                                        |                                                                              | 9.88                                                                                     | 13424                                                                                                                  |                                                                   |                                                                  |
|                          |                                                   |                                                                                                                                                           |                                                        | 1886                                                                         |                                                                                          |                                                                                                                        |                                                                   |                                                                  |
|                          |                                                   |                                                                                                                                                           |                                                        |                                                                              |                                                                                          | 388631                                                                                                                 |                                                                   |                                                                  |
|                          | 3.2                                               |                                                                                                                                                           | TL                                                     | 2433                                                                         |                                                                                          |                                                                                                                        | 2.30                                                              | 7539                                                             |
| 1rwh                     | 3.6                                               | Feas.                                                                                                                                                     | TL                                                     | 3921                                                                         | 112.27                                                                                   | 195205                                                                                                                 | 4.97                                                              |                                                                  |
|                          |                                                   |                                                                                                                                                           |                                                        |                                                                              |                                                                                          |                                                                                                                        |                                                                   | 4230                                                             |

|      |   4 | Feas.   | TL   |   2129 |    TL |   > 10M |   6.80 |   8249 |
|------|-----|---------|------|--------|-------|---------|--------|--------|
| 2e7z | 3.2 | Infeas. | TL   |   4451 |  6.34 |    9646 |   2.22 |   4402 |
|      | 3.6 | Infeas. | TL   |   4121 |  7.66 |   12791 |   2.83 |   5708 |
|      | 4   | Infeas. | TL   |   2964 | 13.86 |   20982 |   4.25 |   8036 |
| 2erl | 3.2 | Infeas. | TL   |   4909 | 10.05 |   15384 |   3.07 |   6982 |
|      | 3.6 | Feas.   | TL   |   2964 | 19.63 |   33199 |   4.37 |   5631 |
|      | 4   | Feas.   | TL   |   3607 | 20.88 |   61487 |   1.39 |   2615 |
| 3b34 | 3.2 | Infeas. | TL   |   3668 |  8.87 |   12555 |   4.65 |   7953 |
|      | 3.6 | Infeas. | TL   |   2751 | 17.47 |   21804 |   6.33 |   7882 |
|      | 4   | Feas.   | TL   |   2080 | 19.22 |   43537 |   0.91 |   1435 |

Table 10: Results for structural findings with ( CP COMBINED ) on small instances. In the structural findings rule column we use the convention (all)/(inf. checks &amp; dom. red.)/(inf. checks &amp; sym. break.). We have [Inf] for Infeasibility Check 1 or 3, [DR] for Domain Reduction Rule 1, [E SS ] and [E K ], and [Arb] for Symmetry Breaking Condition 4, 5, and 6 respectively.

|    |     |       |                         | ( CP COMBINED )   | ( CP COMBINED )     | Structural Findings                                        | Structural Findings                                                   | Structural Findings                                                    |
|----|-----|-------|-------------------------|-------------------|---------------------|------------------------------------------------------------|-----------------------------------------------------------------------|------------------------------------------------------------------------|
| n  | D   | Inst. | Status                  | Time              | Ch.Pts.             | Time                                                       | Ch.Pts.                                                               | Rule                                                                   |
| 20 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | 0.01 0.00 0.00    | 72 17 20            | 0.00 0.00 0.00                                             | 0 0 0                                                                 | [Inf 3] [Inf 1] [Inf 3]                                                |
|    | 0.5 | 1 2 3 | Infeas. Infeas. Infeas. | 0.91 0.29 0.20    | 9423 3909 2519      | 0.76/1.12/ 0.57 0.22/0.27/0.39 0.01/0.01/0.29              | 6691/9423/6691 2282/2857/5041 51/60/3192                              | [E SS 8], [E K 9] [DR1], [E SS 7] , [E K 10] [DR1], [E SS 5] , [E K 2] |
|    | 0.7 | 1 2 3 | Feas. Feas. Feas.       | 0.01 0.00 0.00    | 129 30 65           | 0.35/0.01/0.26 0.04/0.00/0.04 0.04/0.01/0.04               | 4280/129/4280 508/30/508 525/65/525                                   | [E SS 10] , [E K 27] [E SS 9] , [E K 14] [E SS 7] , [E K 10]           |
| 25 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | 0.02 0.02 0.01    | 194 160 123         | 0.00 0.00/ 0.00/0.03 0.00/ 0.00/0.02                       | 0 0/0/149 5/5/141                                                     | [Inf 1] [DR6], [E SS 13] , [E K 3] [DR3], [E SS 2]                     |
|    | 0.5 | 1 2 3 | Infeas. Infeas. Infeas. | 0.23 16.01 7.47   | 2415 100057 44433   | 0.01/ 0.01/0.27 6.23/19.11/ 5.04 9.86/8.98/7.97            | 58/32/2938 28957/100057/28957 44481/44433/44481                       | [DR1], [E SS 6] , [E K 2] [E K 3] [E SS 1] , [E K 5]                   |
|    | 0.7 | 1 2 3 | Feas. Feas. Feas.       | 0.01 0.00 0.01    | 45 30 141           | 0.03/ 0.01/0.03 0.01/ 0.00/0.02 0.02/ 0.01/0.02            | 344/45/344 146/30/146 193/141/193                                     | [E SS 12] , [E K 9] [E SS 2] , [E K 7] [E SS 4] , [E K 4]              |
| 30 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | 0.45 0.33 0.50    | 3225 2191 3429      | 0.00/ 0.00/0.39 0.00/0.00/0.52 0.00/0.00/0.41              | 4/4/2300 4/7/3191 4/4/2375                                            | [DR4], [E SS 8] , [E K 3] [DR2], [E SS 3] , [E K 3] [DR2], [E SS 6]    |
|    | 0.5 | 1 2 3 | Feas. Infeas. Feas.     | 53.36 601.23 4.60 | 299863 > 2.7M 29699 | 636.95/63.02/599.51 378.71/739.33/ 360.23 95.22/5.47/92.70 | > 2.96M/299863/ > 2.96M > 1.65M/ > 2.79M/ > 1.65M 510639/29699/510639 | [E SS 1] , [E K 1] [E K 1] [E SS 1] , [E K 2]                          |
|    | 0.7 | 1 2 3 | Feas. Feas. Feas.       | 0.02 0.01 0.03    | 195 27 379          | 0.01/0.02/0.01 0.01/ 0.00/0.01 0.01/0.03/ 0.00             | 102/195/102 110/27/110 38/379/38                                      | [E K 3] [E SS 1] , [E K 2] [E SS 1] , [E K 2]                          |
| 35 | 0.3 | 1 2   | Infeas. Infeas.         | 0.59 0.89         | 3517 4033           | 0.51/0.83/ 0.46 0.01/0.03/0.83                             | 2294/3517/2294 13/54/3663                                             | [E SS 1] , [E K 1] [DR1], [E SS 1] [DR1], [E SS 3] , [E                |
|    | 0.5 | 3 1   | Infeas. Feas.           | 0.81 7.14         | 4043 40622          | 0.01/ 0.01/0.69 7.33/8.60/ 7.10                            | 14/23/3894 38431/40622/38431                                          | K 1] [Arb]                                                             |

|    |     | 2 3   | Feas. Feas.             | 16.28 TL          | 113300 > 32M         | 42.44/19.83/41.66 TL                                     | 270719/113300/270719 > 31M/ > 27.8M/ > 25.9M                  | [E K 2] [E SS 1] , [E K 1]                                |
|----|-----|-------|-------------------------|-------------------|----------------------|----------------------------------------------------------|---------------------------------------------------------------|-----------------------------------------------------------|
|    | 0.7 | 1 2 3 | Feas. Feas. Feas.       | 0.01 0.03 0.01    | 34 273 30            | 0.01/0.01/0.01 0.01/0.03/0.01 0.01/ 0.01/0.01            | 29/34/29 64/273/64 35/30/35                                   | [E SS 2] , [E K 1] [E SS 4] , [E K 7] [E K 1]             |
| 40 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | 2.04 1.41 1.07    | 6156 4789 4191       | 1.35/1.96/1.51 1.02/1.41/1.16 0.96/1.10/1.18             | 3982/6156/3982 3722/4789/3722 3605/4191/3605                  | [Arb] [E SS 2] [Arb]                                      |
|    | 0.5 | 1 2 3 | Feas. Feas. Feas.       | 266.57 9.10 23.88 | > 1.31M 51413 130898 | 62.65/260.67/75.04 23.13/ 8.97/28.55 14.82/23.55/18.47   | 292947/ > 1.31M/292947 123236/51413/123236 78090/130898/78090 | [Arb] [E SS 1] [Arb]                                      |
|    | 0.7 | 1 2 3 | Feas. Feas. Feas.       | 0.02 0.01 0.01    | 166 34 68            | 0.02/ 0.02/0.03 0.01/ 0.01/0.01 0.02/0.01/0.03           | 201/166/201 41/34/41 168/68/168                               | [Arb] [E K 2] [E SS 1]                                    |
| 45 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | 8.70 1.19 1.70    | 18790 3473 5194      | 20.89/ 8.68/25.50 0.01/ 0.01/1.87 0.02/0.02/2.19         | 42295/18790/42295 28/42/4140 53/44/5857                       | [Arb] [DR1], [E SS 1] , [E K 1] [DR1], [E SS 4] , [E K 2] |
|    | 0.5 | 1 2 3 | Feas. Feas. Feas.       | 3.56 3.85 3.37    | 16486 18158 16901    | 6.27/3.61/7.99 17.21/3.91/19.71 15.47/3.49/15.66         | 28503/16486/28503 80109/18158/80109 71792/16901/71792         | [Arb] [Arb] [Arb]                                         |
|    | 0.7 | 1 2 3 | Feas. Feas. Feas.       | 0.01 0.01 0.02    | 39 50 129            | 0.02/ 0.01/0.01 0.01/ 0.01/0.02 0.01/0.02/ 0.01          | 120/39/120 118/50/118 56/129/56                               | [Arb] [E SS 1] [Arb]                                      |
| 50 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | 4.32 13.50 10.53  | 9124 27987 19301     | 30.00/ 4.19/30.00 12.64/13.55/12.80 12.31/10.57/12.03    | 51350/9124/51350 23178/27987/23178 22526/19301/22526          | [Arb] [E SS 1] [Arb]                                      |
|    | 0.5 | 1 2 3 | Feas. Feas. Feas.       | 42.87 1.63 7.83   | 169360 7874 31997    | 34.59/41.88/ 34.37 12.88/1.78/12.88 8.40/7.90/8.16       | 133525/169360/133525 50547/7874/50547 32742/31997/32742       | [Arb] [Arb] [Arb]                                         |
|    | 0.7 | 1 2 3 | Feas. Feas. Feas.       | 0.01 0.05 0.03    | 47 315 190           | 0.01/0.01/ 0.01 0.03/0.04/ 0.03 0.04/ 0.04/0.04          | 56/47/56 179/315/179 251/190/251                              | [Arb] [E K 1] [Arb]                                       |
| 55 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | 28.38 30.21 29.51 | 43711 44814 43579    | 25.16/28.46/ 24.87 26.59/29.34/ 26.11 80.02/ 29.47/79.87 | 35017/43711/35017 37584/44814/37584 116831/43579/116831       | [Arb] [Arb] [Arb]                                         |
|    | 0.5 | 1 2   | Feas. Feas.             | 20.74 17.80       | 80931 65528          | 43.39/ 20.40/42.40 16.34/17.70/ 15.66                    | 165702/80931/165702 56948/65528/56948                         | [Arb] [Arb]                                               |

|     |   3 | Feas.         | 41.29   | 164410         | 4.11/41.13/ 4.00     | 14519/164410/14519   | [Arb]   |
|-----|-----|---------------|---------|----------------|----------------------|----------------------|---------|
| 0.7 |   1 | Feas. 0.02    | 77      | 0.07/0.02/0.06 |                      | 325/77/325           | [Arb]   |
|     |   2 | Feas.         | 0.02    | 110            | 0.02/0.02/ 0.01      | 60/110/60            | [Arb]   |
|     |   3 | Feas.         | 0.01    | 50             | 0.01/0.01/0.02       | 53/50/53             | [Arb]   |
| 0.3 |   1 | Infeas. 57.55 | 66028   | 49.83/56.92/   | 47.48                | 54255/66028/54255    | [Arb]   |
|     |   2 | Infeas.       | 34.55   | 43375          | 106.82/ 34.10/100.19 | 130443/43375/130443  | [Arb]   |
|     |   3 | Infeas.       | 11.73   | 16208          | 47.04/12.03/45.29    | 55064/16208/55064    | [Arb]   |
| 0.5 |   1 | Feas. 9.01    |         | 30615          | 25.30/ 8.87/24.81    | 83164/30615/83164    | [Arb]   |
|     |   2 | Feas.         | 25.93   | 91975          | 1.46/26.25/ 1.46     | 4929/91975/4929      | [Arb]   |
|     |   3 | Feas.         | 45.13   | 158247         | 28.33/45.35/ 27.09   | 94049/158247/94049   | [Arb]   |
| 0.7 |   1 | Feas. 0.06    |         | 277            | 0.02/0.04/0.02       | 90/277/90            | [Arb]   |
|     |   2 | Feas.         | 0.02    | 102            | 0.03/0.02/0.02       | 95/102/95            | [Arb]   |
|     |   3 | Feas.         | 0.03    | 107            | 0.02/0.03/0.02       | 61/107/61            | [Arb]   |

Table 11: ( CP RANK ) and ( CP COMBINED ) results with and without valid inequalities on small instances.

|    |     |       |               | ( CP RANK ) No Valid Inequ.   | ( CP RANK ) No Valid Inequ.   | ( CP Valid   | ( CP Valid   | ( CP RANK ) Valid Inequ. (8)   | ( CP RANK ) Valid Inequ. (8)   | ( CP COMBINED ) No Valid Inequ.   | ( CP COMBINED ) No Valid Inequ.   | ( CP COMBINED ) Valid Inequ. (7)   | ( CP COMBINED ) Valid Inequ. (7)   | ( CP COMBINED ) Valid Inequ. (8)   | ( CP COMBINED ) Valid Inequ. (8)   |
|----|-----|-------|---------------|-------------------------------|-------------------------------|--------------|--------------|--------------------------------|--------------------------------|-----------------------------------|-----------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|
| n  | D   | Inst. | Status        | Time                          | Ch.Pts.                       | Time         | Ch.Pts.      | Time                           | Ch.Pts.                        | Time                              | Ch.Pts.                           | Time                               | Ch.Pts.                            | Time                               | Ch.Pts.                            |
| 20 | 0.3 | 1     | Infeas.       | 0.16                          | 8937                          | 0.00         | 0            | 0.00                           | 0                              | 0.01                              | 72                                | 0.00                               | 0                                  | 0.00                               | 0                                  |
|    |     | 2     | Infeas.       | 0.13                          | 7286                          | 0.00         | 0            | 0.00                           | 0                              | 0.00                              | 17                                | 0.00                               | 0                                  | 0.00                               | 0                                  |
|    |     | 3     | Infeas.       | 0.15                          | 8255                          | 0.00         | 0            | 0.00                           | 0                              | 0.00                              | 20                                | 0.00                               | 0                                  | 0.00                               | 0                                  |
|    | 0.5 | 1     | Infeas.       | 0.21                          | 10850                         | 0.32         | 14216        | 0.30                           | 1437                           | 0.91                              | 9423                              | 0.30                               | 2483                               | 0.05                               | 43                                 |
|    |     | 2     | Infeas.       | 0.13                          | 7408                          | 0.00         | 0            | 0.00                           | 0                              | 0.29                              | 3909                              | 0.00                               | 0                                  | 0.00                               | 0                                  |
|    |     | 3     | Infeas.       | 0.15                          | 8279                          | 0.00         | 0            | 0.00                           | 0                              | 0.20                              | 2519                              | 0.00                               | 0                                  | 0.00                               | 0                                  |
|    | 0.7 | 1     | Feas.         | 0.00                          | 55                            | 0.00         | 55           | 0.00                           | 22                             | 0.01                              | 129                               | 0.01                               | 139                                | 0.02                               | 52                                 |
|    |     | 2     | Feas.         | 0.00                          | 57                            | 0.00         | 100          | 0.00                           | 41                             | 0.00                              | 30                                | 0.00                               | 21                                 | 0.00                               | 18                                 |
|    |     | 3     | Feas.         | 0.00                          | 15                            | 0.00         | 15           | 0.00                           | 70                             | 0.00                              | 65                                | 0.00                               | 38                                 | 0.01                               | 37                                 |
| 25 | 0.3 | 1     | Infeas.       | 10.35                         | 417400                        | 0.00         | 0            | 0.00                           | 0                              | 0.02                              | 194                               | 0.00                               | 0                                  | 0.00                               | 0                                  |
|    |     | 2 3   | Infeas.       | 8.86                          | 382191 276282                 | 0.00         | 0            | 0.00                           | 0                              | 0.02                              | 160                               | 0.00                               | 0                                  | 0.00                               | 0                                  |
|    | 0.5 |       | Infeas.       | 6.55                          | > 1.1M                        | 0.00         | 0            | 0.00                           | 0                              | 0.01                              | 123                               | 0.00                               | 0                                  | 0.00                               | 0                                  |
|    |     | 1     | Infeas.       | 34.84                         |                               | 26.49        | 685824       | 316.86                         | 772434                         | 0.23                              | 2415                              | 0.39                               | 2360                               | 8.88                               | 7301                               |
|    |     | 2     | Infeas.       | 114.68                        | > 3.1M                        | 148.21       | > 3.1M       | 925.41                         | > 2.2M                         | 16.01                             | 100057                            | 3.83                               | 14463                              | 23.82                              | 15192                              |
|    | 0.7 | 3 1   | Infeas.       | 31.15                         | > 1.0M                        | 28.53        | 764517       | 136.46                         | 306420                         | 7.47                              | 44433                             | 6.45                               | 24621                              | 66.20                              | 51144                              |
|    |     |       | Feas.         | 0.00                          | 39                            | 0.00         | 44           | 0.00                           | 37                             | 0.01                              | 45                                | 0.01                               | 41                                 | 0.01                               | 22                                 |
|    |     | 2     | Feas.         | 0.00                          | 109                           | 0.00         | 96           | 0.01                           | 94                             | 0.00                              | 30                                | 0.00                               | 30                                 | 0.01                               | 30                                 |
|    |     | 3     | Feas.         | 0.00                          | 26                            | 0.00         | 24           | 0.00                           | 24                             | 0.01                              | 141                               | 0.01                               | 96                                 | 0.02                               | 55                                 |
| 30 | 0.3 | 1     | Infeas.       | 308.12                        | > 9.2M                        | 0.00         | 0            | 0.00                           | 0                              | 0.45                              | 3225                              | 0.00                               | 0                                  | 0.00                               | 0                                  |
|    |     | 2     | Infeas.       | 368.72                        | > 9.6M                        | 0.00         | 0            | 0.00                           | 0                              | 0.33                              | 2191                              | 0.00                               | 0                                  | 0.00                               | 0                                  |
|    | 0.5 | 1     | Feas.         | 66.41                         | > 2.8M                        | 399.01       | > 8.9M       | 410.51                         | 491916                         | 53.36                             | 299863                            | 174.39                             | 536030                             | 68.03                              | 24923 > 1.1M                       |
|    |     | 2 3   | Infeas.       | TL                            | > 102M                        | TL           | > 69M        | TL                             | > 12M                          | 601.23                            | > 2.7M                            | 440.38                             | > 1.2M                             | 1992.09                            |                                    |
|    |     | 1     | Feas.         | 89.47                         | > 4.3M                        | 14.59        | 385619       | 241.45                         | 324683                         | 4.60                              | 29699                             | 7.99                               | 29176                              | 17.65                              | 10231                              |
|    | 0.7 |       | Feas.         |                               | 33                            | 0.00         | 33           | 0.01                           | 26                             | 0.02                              | 195                               | 0.01                               | 60                                 | 0.02                               | 25                                 |
|    |     |       |               | 0.00                          |                               |              |              | 0.02                           | 145                            | 0.01                              |                                   |                                    |                                    | 0.01                               |                                    |
|    |     | 2     | Feas.         | 0.00                          | 112                           | 0.00         | 112          |                                |                                |                                   | 27                                | 0.01                               | 27                                 |                                    | 27                                 |
|    |     | 3     | Feas.         | 0.00                          | 33                            | 0.00         | 45           | 0.00                           | 26                             | 0.03                              | 379                               | 0.02                               | 146                                | 0.04                               | 108                                |
| 35 | 0.3 | 1     | Infeas.       | TL                            | > 308M                        | 0.00         | 0            | 0.00                           | 0                              | 0.59                              | 3517                              | 0.00                               | 0                                  | 0.00                               | 0                                  |
|    |     | 2     | Infeas.       | TL                            | > 363M                        | 110.50       | 563403       | 31.92                          | 2086                           | 0.89                              | 4033                              | 2.41                               | 3193                               | 0.00                               | 0                                  |
|    | 0.5 | 3 1   | Infeas. Feas. | TL 279.32                     | > 267M > 13M                  | 0.00 193.97  | 0 > 3.3M     | 0.00 7186.72                   | 0 > 7.8M                       | 0.81 7.14                         | 4043 40622                        | 0.00 3.83                          | 0 10891                            | 0.00 118.01                        | 0 36465                            |
|    |     | 2     | Feas.         | 26.90                         | > 1.2M                        | 240.25       | > 4.3M       | 5396.89                        | > 5.0M                         | 16.28                             | 113300                            | 35.43                              | 115515                             | 1171.81                            | 312715                             |
|    |     | 3     | Feas.         | 4825.99                       | > 271M                        | TL           | > 126M       | TL                             | > 7.6M                         | TL                                | > 32M                             | TL                                 | > 17M                              | TL                                 | > 1.6M                             |
|    | 0.7 | 1     | Feas.         | 0.00                          | 39                            | 0.00         | 39           | 0.01                           | 39                             | 0.01                              | 34                                | 0.01                               | 34                                 | 0.02                               | 32                                 |
|    |     | 2     | Feas.         | 0.01                          | 267                           | 0.00         | 153          | 0.03                           | 148                            | 0.03                              | 273                               | 0.02                               | 161                                | 0.14                               | 244                                |
|    |     | 3     | Feas.         | 0.00                          | 37                            | 0.00         | 37           | 0.01                           | 34                             | 0.01                              | 30                                | 0.01                               | 29                                 | 0.02                               | 29                                 |
| 40 | 0.3 | 1     | Infeas.       | TL                            | > 323M                        | TL           | > 17M        | 432.91                         | 8263                           | 2.04                              | 6156                              | 6.16                               | 3921                               | 12.32                              | 181                                |
|    |     | 2     | Infeas.       | TL                            | > 41M                         | TL           | > 18M        | 165.18                         | 5009                           | 1.41                              | 4789                              | 4.84                               | 3566                               | 219.15                             | 3148                               |

50

|    | 0.5   | 3 1   | Infeas. Feas.   | TL 557.97   | > 40M > 24M   | 0.00 303.39   | 0 > 4.6M      | 0.00 5605.79   | 0 > 3.2M      | 1.07 266.57               | 4191 > 1.31M   | 0.00 12.75    | 0 31396      | 0.00 276.68     | 0 50931                    |
|----|-------|-------|-----------------|-------------|---------------|---------------|---------------|----------------|---------------|---------------------------|----------------|---------------|--------------|-----------------|----------------------------|
| 45 |       | 1 2   | Infeas.         | TL          | > 298M > 42M  | TL            | > 9.7M > 9.5M | TL TL TL       | 104876 107926 | 0.01 0.01 0.02 4.32 13.50 | 9124           | 161.61        | 22507        | 0.06            | 8173 7567 2914 55262 56644 |
|    |       |       | Infeas.         |             |               |               | 174           | 0.01           |               |                           | 130898         | 19.54         |              | 509.06 0.15     | 188                        |
|    | 0.7   | 3 1   | Feas. Feas.     | 35.85 0.00  | > 1.5M 36     | 1137.01 0.00  | > 15M 38      | 902.60         | 499362 38     | 23.88 0.02                | 166            | 0.03          | 48549 283    |                 | 91720                      |
|    |       | 2     | Feas.           | 0.00        | 44            | 0.00          | 42            | 0.01           | 38            | 0.01                      | 34             | 0.01          | 34           | 0.02            | 34                         |
|    |       | 3     | Feas.           | 0.00        | 176           | 0.01          |               | 0.02           | 95            | 0.01                      | 68             | 0.01          | 55           | 0.04            | 45                         |
|    | 0.3   |       |                 |             |               |               |               |                |               | 8.70                      | 18790          | 20.73         | 8150         | 962.23          |                            |
|    |       |       |                 | TL          |               | TL            |               |                |               | 1.19                      | 3473           | 10.10         | 3491         | 956.66          |                            |
|    |       | 3     | Infeas.         | TL          | > 41M         | TL            | > 9.3M        |                | 99303         | 1.70                      | 5194           | 34.17         | 11702        | 324.14          |                            |
|    | 0.5   | 1     | Feas.           | 9.75        | 430149        | 166.41        | > 1.7M        | 318.31         | 118536        | 3.56                      | 16486          | 4.26          | 8190         | 441.80          |                            |
|    |       | 2     | Feas.           | 237.99      | > 10M         | 3.05          | 31172         | 1624.20        | 629324        | 3.85                      | 18158          | 31.37         | 63228        | 479.33          |                            |
|    |       | 3     | Feas.           | 33.00       | > 1.4M        | 46.96         | 503027        | 716.85         | 279338        | 3.37                      | 16901          | 32.08         | 65216        | 68.78           | 9630                       |
|    | 0.7   | 1     | Feas.           | 0.00        | 41            | 0.00          | 41            | 0.02           | 41            |                           | 39             | 0.01          | 39           | 0.04            | 39                         |
|    |       | 2     | Feas.           | 0.00        | 40            | 0.00          | 40            | 0.02           |               |                           | 50             | 0.01          |              | 0.05            | 41                         |
|    |       |       |                 |             |               |               |               |                | 40            |                           |                |               | 50           |                 |                            |
|    |       | 3     | Feas.           | 0.00        | 46            | 0.00          | 46            | 0.02           | 46            |                           | 129            | 0.01          | 43           |                 | 43                         |
| 50 | 0.3   | 1     | Infeas.         | TL          | > 280M        | TL            | > 4.4M        | TL             | 74390         |                           |                |               |              | TL              | 32760                      |
|    |       | 2     | Infeas.         | TL          | > 37M         | TL            | > 4.5M        | TL             | 59130         |                           | 27987          | 140.46        | 22270        | 5351.81         | 31011                      |
|    | 0.5   | 3 1   | Infeas. Feas.   | TL 287.47   | > 37M > 12M   | TL 163.74     | > 5.1M > 1.2M | TL TL          | 67298 > 1.8M  | 10.53 42.87               | 19301 169360   | 175.55 190.01 | 26347 252874 | 2199.80 2445.86 | 9757 189609                |
|    |       | 2     |                 |             |               |               |               | 2189.57        |               |                           | 7874           | 44.49         | 63756        |                 |                            |
|    |       | 3     | Feas.           | 32.18       | > 1.3M        | 580.73        | > 4.5M        | 2473.37        | 545226        | 1.63                      | 31997          | 35.65         | 50602        | 341.80 689.58   | 28374 60568                |
|    | 0.7   | 1     | Feas.           | 153.82      | > 6.3M 52     | 47.11 0.00    | 389615 52     | 0.04           | 672790 52     | 7.83 0.01                 | 47             | 0.02          | 46           | 0.05            | 46                         |
|    |       |       | Feas.           | 0.00        |               |               | 46            |                | 46            |                           |                |               |              | 0.33            |                            |
|    |       | 2 3   | Feas.           | 0.00        | 46            | 0.00          |               | 0.03           |               | 0.05                      | 315            | 0.04          | 207          |                 | 316                        |
|    |       |       | Feas.           | 0.00        | 48            | 0.00          | 48            | 0.04           | 47            | 0.03                      | 190            | 0.05          | 315          | 0.23            | 184                        |
| 55 | 0.3   | 1     | Infeas.         | TL          | > 261M        | TL            | > 2.7M        | TL             | 40493         | 28.38                     | 43711          | 445.88        | 37658        | TL              | 19497                      |
|    |       | 2     | Infeas.         | TL          | > 32M         | TL            | > 2.3         | TL             | 41882         | 30.21                     | 44814          | 484.76        | 40614        | TL              | 19229                      |
|    |       | 3     | Infeas.         | TL          | > 32M         | TL            | > 2.0M        | TL             | 43661         | 29.51                     | 43579          | 747.05        | 53709        | TL              | 17987                      |
|    | 0.5   | 1     | Feas.           | 158.49      | > 6.2M        | 586.18        | > 2.9M        | TL             | > 1.3M        | 20.74                     | 80931          | 100.10        | 109235       | 910.18          | 49640                      |
|    |       | 2     | Feas.           | 1.92        | 73055         | 191.31        | 965794        | TL             | > 1.2M        | 17.80                     | 65528          | 3.49          | 4182         | 2624.05         | 149206                     |
|    |       | 3     | Feas.           | 52.05       | > 1.9M        | 1145.82       | > 5.5M        | TL             | > 1.2M        | 41.29                     | 164410         | 56.95         | 57712        | 389.25          | 29137                      |
|    | 0.7   | 1     | Feas.           | 0.01        | 359           | 0.01          | 359           | 0.21           | 359           | 0.02                      | 77             | 0.02          | 77           | 0.07            | 51                         |
|    |       | 2     | Feas.           | 0.00        | 72            | 0.00          | 57            | 0.06           | 58            | 0.02                      | 110            | 0.03          | 110          | 0.13            | 97                         |
|    |       | 3     | Feas.           | 0.00        | 53            | 0.00          | 53            | 0.05           | 53            | 0.01                      | 50             | 0.02          | 50           | 0.07            | 50                         |
| 60 | 0.3   | 1     | Infeas.         | TL          | > 268M        | TL            | > 1.2M        | TL             | 23774         | 57.55                     | 66028          | 1437.04       | 65519        | TL              | 9736                       |
|    |       | 2     | Infeas.         | TL          | > 34M         | TL            | > 1.4M        | TL             | 23783         | 34.55                     | 43375          | 1198.51       | 59577        | TL              | 10259                      |
|    |       | 3     | Infeas.         | TL          | > 42M         | TL            | > 1.2M        | TL             | 19530         | 11.73                     | 16208          | 1680.11       | 77254        | TL              | 10427                      |
|    | 0.5   | 1     | Feas.           | 92.38       | > 3.4M        | 4917.59       | > 15M         | 3424.66        | 397466        | 9.01                      | 30615          | 73.19         | 51839        | 1991.10         | 80881                      |
|    |       | 2     |                 | 117.15      | > 5.5M        | 1619.21       | > 4.9M        | TL             | 892884        | 25.93                     | 91975          | 93.32         | 68047        | 653.37          | 26614                      |
|    |       | 3     | Feas. Feas.     | 4.06        | 191858        | 1508.85       | > 4.6M        | TL             | 831355        | 45.13                     | 158247         | 97.81         | 71611        | 578.10          | 22709                      |
|    | 0.7   | 1     | Feas.           | 0.00        | 56            | 0.01          | 56            | 0.08           | 58            | 0.06                      | 277            | 0.07          | 201          | 0.56            | 213                        |
|    |       | 2     | Feas.           | 0.00        | 69            | 0.01          | 69            | 0.08           | 65            | 0.02                      | 102            | 0.04          | 89           | 0.25            | 121                        |
|    |       | 3     | Feas.           | 0.00        | 61            | 0.00          | 61            | 0.08           | 61            | 0.03                      | 107            | 0.04          | 100          | 0.15            | 80                         |

Table 12: Integer programming and constraint programming results for small instances with K = 4.

|    |     |       |                         | ( IP VR )              | ( IP VR )            | CP RANK )            | CP RANK )            | ( CP VERTEX )     | ( CP VERTEX )          | ( CP COMBINED )      | ( CP COMBINED )   |
|----|-----|-------|-------------------------|------------------------|----------------------|----------------------|----------------------|-------------------|------------------------|----------------------|-------------------|
| n  | D   | Inst. | Status                  | Time                   | BB Nodes             | Time                 | Ch.Pts.              | Time              | Ch.Pts.                | Time                 | Ch.Pts.           |
| 20 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | 0.02 0.02 14.63        | 0 0 1766             | 0.05 0.04 0.05       | 4119 3743 4700       | 0.13 0.01 0.01    | 2148 130 122           | 0.01 0.00 0.00       | 41 15 18          |
|    | 0.5 | 1 2 3 | Infeas. Infeas. Infeas. | 151.22 150.63 26.96    | 35904 43948 7067     | 0.04 0.06 0.04       | 3907 4784 4081       | 0.98 0.54 0.27    | 10887 6671 3727        | 0.18 0.15 0.14       | 2769 2283 2413    |
|    | 0.7 | 1 2 3 | Infeas. Feas. Feas.     | 469.12 80.48 118.75    | 461021 69308 130092  | 0.17 0.06 0.05       | 12750 4586 4330      | 0.75 0.01 0.17    | 12906 90 4067          | 0.35 0.08 0.11       | 4544 1223 1850    |
| 25 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | 0.03 1.28 84.55        | 0 81 8340            | 0.15 0.17 0.16       | 11375 12552 12273    | 0.28 0.39 0.02    | 3329 4433 195          | 0.00 0.00 0.00       | 24 24 24          |
|    | 0.5 | 1 2 3 | Infeas. Infeas. Infeas. | 3119.92 922.16 5308.83 | 409927 152551 612028 | 0.21 0.23 0.27       | 15897 15235 14552    | 4.03 3.50 0.88    | 26179 22598 7925       | 0.22 1.30 1.70       | 2311 9671 15395   |
|    | 0.7 | 1 2 3 | Feas. Feas. Feas.       | 938.42 49.33 897.73    | 617552 28632 585133  | 0.03 0.00 0.00       | 1632 16 262          | 0.21 0.13 0.21    | 3713 2110              | 0.03 0.01 0.30       | 404 138 3700      |
| 30 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | 1657.41 409.25 465.75  | 96860 15383 13689    | 1.73 1.93            | 107240 116365 111944 | 0.44 0.43 0.62    | 3605 3327 3240         | 0.36 0.02            | 3107 176          |
|    | 0.5 | 1 2 3 | Infeas. Infeas. Infeas. | TL 6583.73 4724.45     | 757211 740577 407545 | 1.60 5.56 2.19 4.47  | 320783 129629 248937 | 15.88 12.80 13.09 | 4085 63070 52330 52204 | 0.44 6.64 11.49 4.59 | 3324 35678 68315  |
|    | 0.7 | 1 2 3 | Feas. Feas. Feas.       | 289.41 29.90 100.54    | 106546 6603 34296    | 0.01 0.02 0.01       | 755 1548 202         | 0.10 0.02 0.36    | 1510 160 4945          | 0.06 0.00 0.11       | 27408 652 32 1359 |
|    | 0.3 | 1 2   | Infeas. Infeas. Infeas. | TL TL                  | 436782 370456        | 134.40 113.42 123.22 | > 5.1M > 4.1M > 4.6M | 1.96              | 8293 5579              |                      | 4982              |
| 35 |     | 3     | Infeas.                 | 2023.44                | 114771               |                      |                      | 0.94 1.07         | 5629                   | 0.8 0.64 0.4         | 4154 2647         |
|    | 0.5 | 1     | Infeas.                 | TL TL                  | 656397               | TL 3662.71           | > 54M 29M            | 81.02 164.30      | 221437 448088          | 7.05 15.49           |                   |
|    |     | 2     | Infeas.                 |                        | 776543               | 1051.57              | > 16M                | 74.49             |                        | 7.11                 | 27524 51428 25365 |
|    |     | 3 1   | Feas.                   | TL                     | 486490               | 0.00                 | 231                  | 0.09              | 200395 1077            | 0.10                 | 981               |
|    | 0.7 |       |                         | 33.44                  | 3689                 |                      |                      |                   |                        |                      |                   |

|    |     | 2 3   | Feas. Feas.             | 1571.77 595.49       | 495769 139304        | 0.02 0.02      | 808 1018        | 0.24 0.11               | 2838 1242           | 0.09 0.01            | 711 53               |
|----|-----|-------|-------------------------|----------------------|----------------------|----------------|-----------------|-------------------------|---------------------|----------------------|----------------------|
| 40 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | TL TL TL             | 265019 305095 217531 | TL TL TL       | 71M > 84M > 85M | 2.22 1.54 2.85          | 6771 5664 7553      | 0.73 0.79 0.78       | 3733 3593 2834       |
|    | 0.5 | 1 2 3 | Infeas. Infeas. Infeas. | TL TL TL             | 360082 438086 415471 | TL TL TL       | 261M 168M 274M  | 2948.92 3390.71 6409.50 | > 6.7M > 6.7M > 13M | 141.83 81.13 2764.87 | 284038 173020 > 6.8M |
|    | 0.7 | 1 2 3 | Feas. Feas. Feas.       | 666.80 331.76 155.55 | 136654 53872 31293   | 0.00 0.03 0.01 | 59 1243 569     | 0.01 0.50 0.33          | 42 5232 3622        | 0.07 0.05 0.07       | 493 272 401          |
| 45 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | TL TL TL             | 132679 151554 202731 | TL TL TL       | 292M 282M 282M  | 2.33 3.43 12.96         | 6785 10945 30174    | 4.32 1.63 1.04       | 9812 4568 2985       |
|    | 0.5 | 1 2 3 | Unsol. Unsol. Infeas.   | TL TL TL             | 358323 256614 240206 | TL TL TL       | 268M 263M 264M  | TL TL TL                | > 14M > 11M > 13M   | TL TL 2522.79        | > 13M > 13M > 5.0M   |
|    | 0.7 | 1 2 3 | Feas. Feas. Feas.       | 638.97 334.81 535.36 | 78964 40918 81341    | 0.01 0.02 0.00 | 585 1281 154    | 0.32 0.05 0.01          | 2657 448 39         | 0.06 0.06 0.37       | 381 357 1824         |
| 50 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | TL TL TL             | 94664 87880 80362    | TL TL TL       | 268M 265M 268M  | 2.51 12.23 16.63        | 7119 20971 29196    | 2.07 4.92 4.05       | 3975 9123 7206       |
|    | 0.5 | 1 2 3 | Unsol. Unsol. Unsol.    | TL TL TL             | 177651 206930 251349 | TL TL TL       | 267M 268M 258M  | TL TL TL                | > 12M > 15M > 11M   | TL TL TL             | > 12M > 14M > 12M    |
| 55 | 0.3 | 1 2   | Infeas. Infeas. Infeas. | TL TL                | 71914 81055          | TL TL          | 250M 240M 245M  | 5.41 4.39               | 11918 10416         | 7.16 12.97           | 11161 20981          |
|    |     | 3     | Unsol. Unsol.           | TL TL                | 89114                | TL TL          | 271M            | 6.4 TL                  | 11517               | 12.76 TL             | 19334                |
|    | 0.5 | 1 2   | Unsol.                  | TL                   | 85361 130393 126944  | TL TL          | 261M 259M       | TL TL                   | > 13M > 18M > 13M   | TL TL                | > 14M > 14M > 13M    |
|    |     | 3     |                         | TL                   | 5186 330             | 0.00 0.01      | 191 596         |                         | 3967                | 0.24                 | 112 847              |
|    | 0.7 | 1 2   | Feas. Feas.             | 284.61 24.35         |                      |                |                 | 0.22 0.70               | 1343                | 0.03                 |                      |

|    |     |   3 | Feas.         | 37.15    | 2010   | 0.02   | 1036   | 1.01   | 5537   | 0.26   | 1049   |
|----|-----|-----|---------------|----------|--------|--------|--------|--------|--------|--------|--------|
| 60 | 0.3 |   1 | Infeas.       | TL 28137 | TL     |        | 217M   | 10.97  | 13076  | 24.86  | 32076  |
|    |     |   2 | Infeas.       | TL       | 44258  | TL     | 219M   | 6.68   | 11115  | 19.58  | 24322  |
|    |     |   3 | Infeas.       | TL       | 34610  | TL     | 225M   | 5.41   | 11166  | 16.22  | 22205  |
|    | 0.5 |   1 | Unsol. TL     |          | 101410 | TL     | 247M   | TL     | 14M    | TL     | > 12M  |
|    |     |   2 | Unsol.        | TL       | 41575  | TL     | 241M   | TL     | > 15M  | TL     | > 12M  |
|    |     |   3 | Unsol.        | TL       | 106377 | TL     | 241M   | TL     | > 13M  | TL     | > 12M  |
|    | 0.7 |   1 | Feas. 6017.35 |          | 407628 | 0.00   | 86     | 5.42   | 23318  | 0.11   | 352    |
|    |     |   2 | Feas.         | 1214.95  | 56628  | 0.00   | 83     | 0.02   | 57     | 0.10   | 324    |
|    |     |   3 | Feas.         | TL       | 476817 | 0.01   | 188    | 0.48   | 2279   | 0.32   | 1154   |

Table 13: Integer programming and constraint programming results for small instances with K = 5.

|    |     |       |                                 | ( IP VR )               | ( IP VR )            | CP RANK )        | CP RANK )            | ( CP VERTEX )      | ( CP VERTEX )          | ( CP COMBINED )          | ( CP COMBINED )           |
|----|-----|-------|---------------------------------|-------------------------|----------------------|------------------|----------------------|--------------------|------------------------|--------------------------|---------------------------|
| n  | D   | Inst. | Status                          | Time                    | BB Nodes             | Time             | Ch.Pts.              | Time               | Ch.Pts.                | Time                     | Ch.Pts.                   |
| 20 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas.         | 0.02 0.02 0.01          | 0 0 0                | 0.04 0.03 0.04   | 2328 1999 2781       | 0.07 0.02 0.01     | 1259 130 122           | 0.01 0.00 0.00           | 33 11 11                  |
|    | 0.5 | 1 2 3 | Infeas. Infeas. Infeas.         | 191.06 122.32 37.00     | 44255 28105 8895     | 0.05 0.03 0.04   | 3169 1393 2849       | 0.91 0.44 0.71     | 7899 5393 6201         | 0.00 0.00 0.00           | 31 39 44                  |
|    | 0.7 | 1 2 3 | Infeas. Infeas. Infeas.         | 505.80 335.17 820.60    | 349338 133414 652067 | 0.03 0.03 0.06   | 1851 1701 3825       | 182.39 26.19 90.76 | > 1.6M 197049 803267   | 0.14 0.32 0.14           | 1719 3276 1825            |
| 25 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas.         | 0.04 0.06 116.29        | 0 0 6401             | 0.16 0.16 0.17   | 7820 8422 8190       | 0.27 0.48 0.03     | 2447 3579 203          | 0.00 0.00 0.00           | 22 21 21                  |
|    | 0.5 | 1 2 3 | Infeas. Infeas. Infeas.         | 1391.46 2809.62 1443.81 | 142974 448424 303980 | 0.25 0.21 0.18   | 12930 10815 9714     | 5.21 7.20 0.89     | 25382 34474 6439       | 0.21 0.29 0.74           | 2291 2803 5088            |
|    | 0.7 | 1 2 3 | Infeas. Infeas. Infeas.         | TL TL TL                | > 2.7M > 2.8M > 2.2M | 1.00 2.12 0.35   | 46804 90033 20355    | 23.74 0.73 10.91   | 234324 7014 54638      | 3.96 30.21 8.14          | 21644 151484 42058        |
| 30 | 0.3 | 1 2 3 | Infeas. Infeas.                 | 4.99 636.99 183.72      | 126 31600 3752       | 0.35 0.31 0.33   | 19531 18559 18437    | 0.71 0.50 0.61     | 3373 2784              | 0.04 0.03                | 197 136                   |
|    | 0.5 | 1 2 3 | Infeas. Infeas. Infeas. Infeas. | 3788.00 4736.50 TL      | 337024 586718 972437 | 0.37 0.35 0.45   | 19557 18599 22852    | 9.57 14.45 3.13    | 3359 38321 52503       | 0.65 6.57 3.43           | 2834 27912 14117          |
|    | 0.7 | 1 2 3 | Feas. Feas. Infeas.             | TL TL TL                | > 2.0M > 1.9M > 1.6M | 3.11 58.81 15.54 | 150263 > 2.1M 620857 | 0.77 3.27 2.20     | 14829 6573 21596 18217 | 0.75 24.08 152.65 125.98 | 4313 105791 610624 524235 |
| 35 | 0.3 | 1 2   | Infeas. Infeas.                 | TL 2137.43              | 359977 91145         | 2.74 2.97        | 138637 141146        | 2.10 1.52          | 6048 4779              | 0.94                     | 4291 3821                 |
|    |     | 3     | Infeas. Infeas.                 | 4307.47                 | 233693               | 3.12             | 151733 279610        | 1.29 68.92         | 3931                   | 0.86 0.70                | 3088                      |
|    |     |       |                                 | TL                      |                      | 7.03             |                      |                    | 182675                 | 8.54                     | 24841                     |
|    | 0.5 | 1 2 3 | Infeas. Infeas.                 | TL TL                   | 534518 656907 587741 | 14.95 4.86       | 608382 229164        | 65.41 6.49         | 180277 30797           | 1.74 17.00               | 6768 50351                |
|    |     | 1     | Feas.                           |                         |                      |                  | 469116               | 7.15               | 46085                  | 4.50                     | 19556                     |
|    | 0.7 |       |                                 | TL                      | > 1.4M               | 9.52             |                      |                    |                        |                          |                           |

|    |     | 2 3   | Feas. Feas.             | TL TL    | > 1.1M > 1.1M        | 4.20 3.09               | 193790 154090        | 1.95 1.27              | 13057 7565           | 3.51 10.54           | 17862 52395          |
|----|-----|-------|-------------------------|----------|----------------------|-------------------------|----------------------|------------------------|----------------------|----------------------|----------------------|
| 40 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | TL TL TL | 333285 229471 211256 | 119.11 155.16 104.14    | > 4.1M > 5.2M > 3.7M | 4.07 2.54 4.55         | 8198 6669 8530       | 0.92 0.97 0.86       | 3394 3731 2843       |
|    | 0.5 | 1 2 3 | Infeas. Infeas. Infeas. | TL TL TL | 458432 371653 396698 | 344.76 510.21 5087.14   | > 9.3M > 12M > 38M   | 145.64 500.00 244.45   | 289686 > 1.1M 505231 | 41.67 38.18 24.46    | 87672 85013 49619    |
|    | 0.7 | 1 2 3 | Feas. Feas. Feas.       | TL TL TL | 535758 670389 937572 | 0.29 0.09 0.90          | 12523 4619 43550     | 0.21 0.63 3.51         | 1385 4541 21150      | 1.69 17.85 7.56      | 7094 74072 30361     |
| 45 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | TL TL TL | 135467 232693 55174  | 5518.61 6272.02 3673.19 | > 55M > 53M > 47M    | 3.53 9.89 13.29        | 6874 14189 20436     | 1.59 1.31 1.48       | 4307 3951 3976       |
|    | 0.5 | 1 2 3 | Infeas. Infeas. Infeas. | TL TL TL | 278625 232872 303773 | TL TL TL                | > 218M > 106M > 81M  | 637.30 780.27 432.90   | > 1.1M > 1.4M 781403 | 136.85 110.67 222.79 | 238278 193891 429400 |
|    | 0.7 | 1 2 3 | Feas. Feas. Feas.       | TL TL TL | 472603 318990 501706 | 0.40 1.89 0.12          | 17200 87167 5592     | 0.23 1.17 2.71         | 1099 5892 11500      | 8.02 1.61 2.13       | 28759 6457 7594      |
| 50 | 0.3 | 1 2 3 | Infeas. Infeas. Infeas. | TL TL TL | 64925 110402 98998   | TL Tl TL                | > 237M > 245M > 255M | 15.54 21.19 20.91      | 18430 23110 23991    | 1.39 3.17 3.43       | 3166 6447 6887       |
|    | 0.5 | 1 2 3 | Infeas. Infeas. Infeas. | TL TL TL | 162536 210962 260323 | TL TL TL                | > 233M > 239M > 232M | 737.45 1312.52 1183.21 | > 1.0M > 1.7M > 1.7M | 195.94 243.31 104.67 | 282238 357799 138847 |
| 55 |     | 1 2   | Infeas. Infeas. Infeas. | TL TL    | 104453 85637         | TL                      | > 239M > 236M > 229M | 6.62 6.83              | 9246 9855            | 8.70 9.63            | 13047 13325          |
|    | 0.3 | 3 1   | Infeas. Infeas.         | TL       | 108780               | TL TL                   | > 225M               | 8.36                   | 9401                 | 7.47                 | 10662                |
|    |     | 2     |                         | TL TL    | 194290 177382        | TL                      | > 229M               | 3072.97 TL             | > 3.3M > 7.8M        | 187.38 608.52 556.74 | 215082 747595        |
|    | 0.5 | 3     | Infeas.                 | TL       | 178030               | TL TL                   | > 236M               | 1832.92                | > 1.9M               |                      | 710114               |
|    | 0.7 | 1 2   | Feas. Feas.             | TL TL    | 424089 576079        | 0.99 0.17               | 43149 8805           | 12.52 0.07             | 40991 268            | 5.30 3.05            | 14487 8574           |

|    |     |   3 | Feas.   | TL   |   681599 | 0.08   | 3503   | 0.48    | 1805   |    1.93 | 5704   |
|----|-----|-----|---------|------|----------|--------|--------|---------|--------|---------|--------|
| 60 | 0.3 |   1 | Infeas. | TL   |    62940 | TL     | > 225M | 11.97   | 11279  |   14.06 | 16012  |
|    |     |   2 | Infeas. | TL   |    49613 | TL     | > 218M | 10.09   | 9977   |   11.35 | 13002  |
|    |     |   3 | Infeas. | TL   |    59458 | TL     | > 227M | 11.68   | 11811  |   10.02 | 12664  |
|    | 0.5 |   1 | Infeas. | TL   |   129562 | TL     | > 222M | TL      | > 5.5M | 1637.26 | > 1.6M |
|    |     |   2 | Infeas. | TL   |   111390 | TL     | > 219M | 4101.51 | > 3.6M | 2344.86 | > 2.7M |
|    |     |   3 | Infeas. | TL   |   116471 | TL     | > 213M | TL      | > 5.9M |  948.2  | 985413 |
|    | 0.7 |   1 | Feas.   | TL   |   443140 | 0.28   | 11656  | 26.26   | 78599  |    4.94 | 11475  |
|    |     |   2 | Feas.   | TL   |   512861 | 0.26   | 10280  | 10.53   | 30672  |    2.27 | 5374   |
|    |     |   3 | Feas.   | TL   |   366181 | 0.75   | 30265  | 30.83   | 89825  |    7.04 | 16879  |
Moira MacNeil Merve Bodur
Constraint Programming Approaches to the Discretizable Molecular Distance Geometry Problem
The Distance Geometry Problem (DGP) seeks to find positions for a set of
points in geometric space when some distances between pairs of these points are
known. The so-called discretization assumptions allow to discretize the search
space of DGP instances. In this paper, we study the Discretizable Molecular
Distance Geometry Problem whose feasible solutions provide a discretization
scheme for the DGP. We propose the first constraint programming formulations as
well as a set of checks for proving infeasibility, domain reduction techniques,
symmetry breaking constraints and valid inequalities. Our computational results
indicate that our formulations outperform the state-of-the-art integer
programming formulations, both for feasible and infeasible instances.