# Best of Both Worlds: Solving the Cyclic Bandwidth Problem by Combining Pre-existing Knowledge and Constraint Programming Techniques

Guillaume Fertin<fnref n="1" /> ID, Eric Monfroy<fnref n="2" /> ID, and Claudia Vasconcellos-Gaete<fnref n="2" /> (✉) ID

**Abstract.** Given an optimization problem, combining knowledge from both (i) structural or algorithmic known results and (ii) new solving techniques, helps gain insight and knowledge on the aforementioned problem by tightening the gap between lower and upper bounds on the sought optimal value. Additionally, this gain may be further improved by iterating (i) and (ii) until a fixed point is reached.

In this paper, we illustrate the above through the classical CYCLIC BANDWIDTH problem, an optimization problem which takes as input an undirected graph $G = (V, E)$ with $|V| = n$, and asks for a labeling $\varphi$ of $V$ in which every vertex $v$ takes a unique value $\varphi(v) \in [1; n]$, in such a way that $B_c(G, \varphi) = \max\{\min_{uv \in E(G)}\{|\varphi(u) - \varphi(v)|; n - |\varphi(u) - \varphi(v)|\}\}$, called the *cyclic bandwidth of G*, is minimized.

Using the classic benchmark from the Harwell-Boeing sparse matrix collection introduced in [16], we show how to combine (i) previous results from the CYCLIC BANDWIDTH literature, and (ii) new solving techniques, which we first present, and then implement, starting from the best results obtained in step (i). We show that this process allows us to determine the optimal cyclic bandwidth value for half of the instances of our benchmark, and improves the best known bounds for a large number of the remaining instances.

**Keywords:** Graph Labeling · Cyclic Bandwidth · Lower Bounds · Upper Bounds · Constraint Programming · Solver

## 1 Introduction

The classical CYCLIC BANDWIDTH problem is an optimization problem that takes as input an undirected graph $G = (V, E)$ with $|V| = n$ and asks for a labeling $\varphi$ of $V$ in which every vertex $v$ takes a unique value $\varphi(v) \in [1; n]$, in such a way that $B_c(G, \varphi) = \max\{\min_{uv \in E(G)}\{|\varphi(u) - \varphi(v)|; n - |\varphi(u) - \varphi(v)|\}\}$ (i.e., the *cyclic bandwidth of G*) is minimized.

<footnote n="1">¹ Nantes Université, École Centrale Nantes, CNRS, LS2N, UMR 6004, 44000 Nantes, France
guillaume.fertin@univ-nantes.fr</footnote>

<footnote n="2">² LERIA, Université d'Angers, Angers, France
{eric.monfroy, claudia.vasconcellos}@univ-angers.fr</footnote>
The CYCLIC BANDWIDTH problem was first presented in [11] within the framework of creating a ring interconnection network for a group of computers. This problem can be regarded as a modification of the widely recognized BANDWIDTH MINIMIZATION problem, originally proposed by Harper [6] in 1964. For a comprehensive historical overview, readers can refer to the survey by Chinn et al. [2]. The BANDWIDTH MINIMIZATION problem also asks for a labeling $\varphi$, i.e., a bijection from $V$ to $[1; n]$, using a computed value of $B(G, \varphi) = \max_{uv \in E}\{|\varphi(u) - \varphi(v)|\}$. The BANDWIDTH MINIMIZATION problem asks for a labeling $\varphi^*$ such that $B(G, \varphi^*)$ is minimized. It can be seen that both problems are related in the sense for any graph $G$, we have $B_c(G) \le B(G)$.

The CYCLIC BANDWIDTH has been extensively studied. Its complexity has been established as NP-hard, even in the scenario of trees with a maximum degree of 3 [13]. Furthermore, the specific value of $B_c(G)$ has been ascertained for graphs within distinct categories, including paths, cycles, Cartesian products of paths (or cycles, or a combination of both), full $k$-ary trees, complete graphs, complete bipartite graphs, and unit interval graphs [3, 8, 12, 13].

More recent papers are concerned with designing efficient heuristics for CYCLIC BANDWIDTH (see, e.g., [19,20,22]) or BANDWIDTH MINIMIZATION (see, e.g., [15,17,18]). For both problems, execution time, upper bounds, or lower bounds are considered, examined, and tested on a subset of the classical Harwell-Boeing sparse matrix collection<fnref n="1" />.

Other investigations studied the correlation between $B_c(G)$ and $B(G)$, with a specific focus on identifying conditions that guarantee the equality $B(G) = B_c(G)$ [4,9,14]. Another set of results focuses on establishing bounds for $B_c(G)$, particularly lower bounds, in the context of general graphs [4,25]. Initially, it is evident that for any graph $G$, $B_c(G) \ge \frac{\Delta(G)}{2}$, where $\Delta(G)$ represents the maximum degree of $G$. Furthermore, across all graphs $G$, the relationship $\frac{B(G)}{2} \le B_c(G) \le B(G)$ holds, with the leftmost bound stemming from [14]. Various other lower bounds have been derived in the literature, many of which are grounded in density ("propagation") considerations, or a relevant cycle basis of the examined graph (refer to, e.g., [4,25]).

In this paper, we propose the Recycling algorithm, orchestrating some existing results, both experimental and theoretical, based on bandwidth and cyclic bandwidth. For the 113 Harwell-Boeing graph instances proposed in [16], the Recycling algorithm is either able to tighten bounds, prove optimization, and find the optimum of the bandwidth or cyclic bandwidth.

Constraint programming (CP) [23] is a problem-solving paradigm for solving combinatorial problems using techniques issued from artificial intelligence, computer science, and operations research. In CP, rather than describing how to solve the problem, users formulate the problem by defining decision variables interconnected by constraints. As said by E. Freuder, "Constraint Programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it."

<footnote n="1">¹ see, e.g., https://math.nist.gov/MatrixMarket/collections/hb.html and https://sparse.tamu.edu/HB</footnote>
The constraints encompass various types of variables (such as Boolean, bounded integers, etc.) and constraint types (including linear, non-linear arithmetic, symbols, etc.). In CP, a model represents a problem, and an instance is given by a model and some data. In our case, the problem consists of generating a graph labeling minimizing the cyclic bandwidth of graphs, and an instance is the instantiation of the model with a given graph. The direct modeling in CP of the cyclic bandwidth problem is very close to its mathematical formulation. However, this model is not well-suited for CP, and not efficiently solved.

Here, we propose a more original model, taking advantage of the strengths of CP. This model is based on constraints in extension [1], i.e., table constraints [10] considering the candidate labelings of two vertices linked by an edge to respect a given cyclic bandwidth value. This model is thus a satisfiability model for computing a labeling value less or equal to a given $k$. This $k$ can easily be minimized by an efficient dichotomy algorithm considering a property of the problem: if there is a cyclic labeling of value $k$, there is also one of size $k + 1$, and if there is no labeling of value $k$, none of value $k - 1$ exists. This model is solved more efficiently than the direct model and may improve the results of the Recycling algorithm, which in turn offers the possibility to better solve the CP model. A fixed-point application of the sequence Recycling algorithm, CP model solving, is thus beneficial.

Experimentally, on the 113 instances selected in [16], our method proves highly powerful, as it optimally solves half of the 113 instances. More precisely, the fixed point of our Recycling algorithm and CP model solving proves the optimality of 63 instances, determines the optimal value of 56 instances, and improves the bounds of one instance.

This paper is organized as follows: Sect. 2 presents the CYCLIC BANDWIDTH problem along with some existing results for it, or for its related problem, BANDWIDTH MINIMIZATION. Section 3 presents the Recycling algorithm and how it orchestrates the existing results from literature. Section 4 presents an optimization function for the Recycling Algorithm, using constraint programming. Finally, Sect. 5 presents the results obtained using the Recycling algorithm and its optimization.

# 2 The Cyclic Bandwidth Problem and Existing Results

## 2.1 The Problem

The CYCLIC BANDWIDTH problem is a graph labeling problem that can be formulated as follows. Let $G(V, E)$ be a finite undirected graph (called the *guest graph*) of order $n$, and $C_n(V', E')$ be a cycle graph (called the *host graph*) with $|V'| = n$. An embedding of $G$ in $C_n$ is an injection $\phi: V \to V'$. The *cyclic distance* $d_c$ between two vertices $u, v \in V$ linked by an edge of $E$ is defined by:

$$d_c(u, v) = \min\{|\phi(u) - \phi(v)|, n - |\phi(u) - \phi(v)|\} \quad (1)$$
The cyclic bandwidth of an embedding $\phi: V \to V'$ is the maximum distance between two vertices:

$$B_c(G, \phi) = \max_{u,v \in E}\{d_c(u, v)\} \qquad (2)$$

The cyclic bandwidth problem consists in finding an embedding $\phi^*$ among the set $\mathcal{E}$ of embeddings from $G$ to $C_n$ such that $B_c(G, \phi^*)$ is minimum:

$$B_C^*(G) = \min_{\phi \in \mathcal{E}} \{B_c(G, \phi)\} \qquad (3)$$

## 2.2 Metaheuristics Results

CYCLIC BANDWIDTH and BANDWIDTH MINIMIZATION are both NP-complete problems. Solving any of these two problems requires exploring very large search spaces, hence it is not surprising that most of the methods developed to solve them are metaheuristics. In this section, we present some relevant algorithms and results that lately will become inputs for our Recycling algorithm. The first three metaheuristics solve BANDWIDTH MINIMIZATION (also known as MATRIX BANDWIDTH MINIMIZATION, or MBMP), while the last one is a recent algorithm developed for CYCLIC BANDWIDTH.

Martí's enhanced Branch-and-Bound [15]. This is one of the few exact methods proposed to solve MBMP. It takes advantage of a solution provided by a GRASP method to reduce the size of the tree to explore, focusing only in the branch for $b_t = b_{up} - 1$, with $b_{up}$ being the solution provided by GRASP. It is also the first exact method to provide upper and lower bounds for some large instances ($|V| > 500$).

Mladenovic's VNS. In [17] the authors propose a local search algorithm known as Variable Neighborhood Search (VNS) that combines reduced neighborhoods, fast local search procedures, and specific neighborhood structures (from [21]). Additionally, they use the number of critical vertices as a secondary objective function, to deal with several neighborhoods having the same bandwidth. Their results outperform several other heuristics in terms of solution quality and computing time required, and they improve the best-known solutions for 42 (out of the 113) Harwell-Boeing instances.

Pop's genetic algorithm [18]. Using a list of interchange of rows or columns as individuals and a problem-specific genetic operator called pruning, this algorithm was successfully tested in the 113 Harwell-Boeing instances. Their results improve the best-known bandwidth values for almost a third of the graphs, and outperforming methods like the already described VNS [17] and Martí's branch-and-bound [15].

Ren's New Iterated Local Search (NILS). This is a metaheuristic proposed in [20] to solve the CYCLIC BANDWIDTH problem. Starting from a random initial solution, it iterates over a local optimization (a dedicated Tabu search, DTS) and adds two perturbation strategies, to escape local optimum traps and explore
unvisited areas. When the DTS stagnates, a Direct perturbation is triggered to modify the current solution, using a randomized shift-insert operator. If this perturbation also stagnates, then a Strong perturbation is triggered to apply a destruction-reconstruction heuristic, moving some uncritical vertices closer to the critical ones.

The NILS algorithm was applied to 85 standard graphs (paths, cycles, caterpillars, etc.) and 28 Harwell-Boeing instances; from these 28 graphs, NILS improved 4 existing results (compared against [19,22]) and matched all other best results obtained.

## 2.3 Theoretical Structural Results

We summarize here three structural properties about $B_c^*(G)$ (and possibly $B^*(G)$) that apply to any graph $G$, and that rely on polynomial time computations [4]. They allow to: (i) obtain lower bounds for $B_c^*(G)$, (ii) determine conditions under which $B_c^*(G) = B^*(G)$ and, in certain conditions, (iii) given a labeling for CYCLIC BANDWIDTH, provide a labeling for BANDWIDTH MINIMIZATION, of same value. All these properties will be used in our Recycling algorithm (see Sect. 3).

*Extended density.* Theorem 1 in [4] gives a lower bound for $B_c^*(G)$ based on the neighborhood “up to distance $i$” for any vertex $u \in V(G)$ and any (relevant) value of $i$. It can be seen as a generalization of the obvious $\frac{\Delta(G)}{2}$ lower bound. Theorem 3 in [4] is in the same spirit, but considers the neighborhood (up to distance $i$) of any pair of vertices connected by an edge in $G$.

*Cycle basis considerations.* Lower bounds on $B_c^*(G)$ can also be obtained by computing the length $\ell$ of the longest cycle in a cycle basis of $G$ (the notion of cycle basis being a classical graph-theoretical notion, see e.g. [5]). This is the purpose of Theorem 9 in [4], which actually contains two results: a lower bound for $B_c^*(G)$ based on $\ell$, and a condition under which $B_c^*(G) = B^*(G)$.

*Relabeling.* Another interesting result from [4] is its Algorithm 1, which provides a labeling $\phi'$ for the BANDWIDTH MINIMIZATION problem, given a labeling $\phi$ for the CYCLIC BANDWIDTH problem, in such a way that $B(G, \phi') \le B_c(G, \phi)$. Note that this result is only guaranteed under some conditions described in Lemma 8 in [4]. This result may be useful as it may decrease upper bounds on $B^*(G)$, which in turn, may lead us to conclude that $B^*(G) = B_c^*(G)$ (see Algorithms 2 and 4 in Sect. 3 for more details).

# 3 Recycling Algorithm: Orchestration of Existing Results

The Recycling algorithm we propose here is based on results of previous works, and part of its structure is directed by some theorems of [4] (see Sect. 2.3). For sake of readability, from now on (and if clear from the context), we will denote
by $B_c^*$ (resp. $B^*$) the optimal value $B_c^*(G)$ (resp. $B^*(G)$). The inputs for the Recycling algorithm are described in Table 1, whereas the Recycling algorithm is described in Algorithms 1 to 4.

<table><caption>**Table 1.** Inputs for the Recycling algorithm</caption><thead><tr><th></th><th>input</th><th>description</th></tr></thead><tbody><tr><td rowspan="3">Graph</td><td>G</td><td>A graph</td></tr><tr><td>n</td><td>Order of G</td></tr><tr><td>ℓ</td><td>Length of the longest cycle in a cycle basis of G</td></tr><tr><td rowspan="4">Bandwidth</td><td>lb<sub>B_Marti</sub></td><td>Bandwidth lower bound from Martí et al. [15]</td></tr><tr><td>ub<sub>B_Marti</sub></td><td>Bandwidth upper bound from Martí et al. [15]</td></tr><tr><td>ub<sub>B_Pop</sub></td><td>Bandwidth upper bound from Pop et al. [18]</td></tr><tr><td>ub<sub>B_Mladenovic</sub></td><td>Bandwidth upper bound from Mladenovic et al. [17]</td></tr><tr><td rowspan="2">Cyclic Bandwidth</td><td>ub<sub>C_NILS</sub></td><td>Cyclic Bandwidth upper bound from Ren et al. [20]</td></tr><tr><td>lb_density</td><td>Cyclic Bandwidth lower bound from the extended density notion [4]</td></tr></tbody></table>

# 4 Cyclic Bandwidth as an Optimization Constrained Problem

Constraint programming [23] (CP) is a paradigm for solving combinatorial problems using a wide range of methods issued from artificial intelligence, computer science and operations research. In CP, users focus on the “what”, not on the “how”: this means that users declaratively state the problem, not how to solve it. Hence, a problem is described as a constraint satisfaction problem (CSP) or constrained optimization problem (COP): a CSP is defined by some decision variables, each one with its domain (its candidate values) and constraints (relations) linking these variables; a COP is given by a CSP and an objective function to be optimized.

To model the CYCLIC BANDWIDTH problem, we consider finite domain decision variables, i.e., bounded integer variables, and arithmetic constraints. A label corresponds to a finite domain variable ranging from 1 to $n$, i.e., $\mathcal{N} = \{1, \dots, n\}$ is a set of $n$ labels, and for each $v \in V$, the variable $\phi_v$ represents the label of $v$:

$$ \forall v \in V, \phi_v \in \mathcal{N} \qquad (4) $$
**Algorithm 1.** The Recycling Algorithm

▷ Collect all knowledge about lower and upper bounds for $B^*$ and $B_c^*$
$lb_C \leftarrow \max\{lb\_density, \min\{lb_{B\_Mart\_i}, \lceil \frac{n}{l} \rceil\}}$
$ub_C \leftarrow ub_{C\_NILS}$
$lb_B \leftarrow lb_{B\_Mart\_i}$
$ub_B \leftarrow \min\{ub_{B\_Mart\_i}, ub_{B\_Pop}, ub_{B\_Mladen\_ovic}\}$

▷ Compare the lower (resp. upper) bounds and adjust

if $lb_B < lb_C$ then
$lb_B \leftarrow lb_C$

end if

if $ub_B < ub_C$ then
$ub_C \leftarrow ub_B$

end if

▷ If $ub_C < lb_B$ then $B_c^* \neq B^*$, otherwise check whether equality holds

if $ub_C \ge lb_B$ then
`eq_or_unknown()`

end if

**Algorithm 2.** `eq_or_unknown()`

if $ub_B \le \lceil \frac{n}{l} \rceil$ then
`update bounds()`

else
`try_relabeling()`

end if

▷ In that case, $B_c^* = B^*$ and bounds should be updated

▷ $B_c^* = ? B^*$ Relabeling is then tested.

## 4.1 Arithmetic (or Direct) Model

This model is a direct translation of the mathematical definition of the problem. The constraints of the arithmetic model are:

- All the labels must be unique:

$$ \texttt{AllDifferent}\{\phi_v | v \in V\} \qquad (5) $$

with AllDifferent [7] being the standard global constraint<fnref n="1" /> which states that all variables in this constraint must be pairwise different.

- Cyclic bandwidth of the current labeling $\phi$:

$$ B_c(G, \phi) = \max_{(u,v) \in E} \{d_c(\phi_u, \phi_v)\} \qquad (6) $$

where $B_c(G, \phi)$ is a finite domain variable ranging from 1 to $n-1$. Note that $d_c$ has been defined in Sect. 2.1.

<footnote n="1">¹ A global constraint provides some abstractions to improve expressiveness, but also are treated more efficiently by the solver using some dedicated algorithms.</footnote>
**Algorithm 3. update bounds()**

▷ Note: this algorithm is invoked only if $B^* = B_c^*$
▷ Note: if $ub_C$ improved $ub_B$, relabeling gives a labeling of value $ub_B$ for bandwidth
$ub_B, ub_C \leftarrow \min\{ub_B, ub_C\}$
$lb_B, lb_C \leftarrow \max\{lb_B, lb_C\}$

if $ub_B = lb_B$ then
$B^*, B_c^* \leftarrow lb_C$
end if

▷ We have reached the optimum for both problems

**Algorithm 4. try_relabeling()**

if $ub_B > ub_C$ then
$ub'_B \leftarrow$ apply_relabeling() ▷ Algorithm 1 from [4] – see Section 2.3
if $ub'_B < ub_B$ then
$ub_B \leftarrow ub'_B$
$eq_or_unknown()$ ▷ We can test again whether $B^* = B_c^*$
end if
end if

– Optimization to find the labeling $\phi^*$ that minimizes the cyclic bandwidth:

$$B_c^*(G) = \text{minimize } B_c(G, \phi) \qquad (7)$$

where $B_c(G)$ is a finite domain variable ranging from 1 to $n-1$.

The arithmetic model $\mathcal{M}_A^*$ is thus:

$$\mathcal{M}_A^* = (4) \wedge (5) \wedge (6) \wedge (7)$$

However, in terms of efficiency, a constraint solver uses dynamically and intensively the constraints to prune/reduce the search space, and it cannot take full advantage of this formulation since most of the problem is in the objective function.

## 4.2 Finite Domain Extensional Constraint Model for Satisfiability

We now consider finite domain extensional constraints (see, e.g., [1]), also known as table constraints [10]: a constraint is defined by enumerating the allowed (resp. forbidden) tuples of constants satisfying (resp. violating) it. Then, we enforce a tuple of variables to be an element of this table (using the `in` keyword). There are several types of table constraints and we use the classic one.

We have first to change the problem into a satisfiability problem: given an integer $k$, find a labeling $\phi$ such that $B_c(G, \phi) \le k$. Now, let us consider $\mathcal{L}(k)$, the set of possible pairs of labels for pairs of vertices linked by an edge:

$$\mathcal{L}(k) = \{(\ell, \ell') | \ell, \ell' \in \mathcal{N}^2, \ell \neq \ell', \min\{|\ell - \ell'|, n - |\ell - \ell'|\} \le k\}$$

The finite domain variables we need are the same as for the $\mathcal{M}_A$ model. The constraints are the following:
- All labels must be different. For this, we use the AllDifferent constraints as above (see (5)).

- Labels must respect the cyclic bandwidth of cost k w.r.t. distance $d_c$, i.e.

$$ \forall (u, v) \in E, (\phi_u, \phi_v) \text{ in } \mathcal{L}(k) \qquad (8) $$

Thus, the finite domain extensional constraint satisfiability model is:

$$ \mathcal{M}_E = (4) \wedge (5) \wedge (8) $$

## 4.3 Possible Improvements

To break symmetries, i.e., to remove some symmetric solutions that could be derived from remaining solutions, we can add the constraint:

$$ \phi_{u_{\Delta}} = 1 \qquad (9) $$

where $u_{\Delta}$ is the vertex of highest degree. This constraint removes $n-1$ cyclic permutation solutions that can be recovered later on (if necessary) by rotation of the remaining solution. This constraint thus reduces the search space. Note that we could assign 1 to the label of any vertex. However, intuitively, we feel that fixing the vertex of highest degree is more efficient.

As the labeling is cyclic, this means that we can turn one way (counterclockwise for example) or the other (clockwise). This symmetry can be broken to enforce one direction by ordering any two labels:

$$ \phi_u \ge \phi_v \qquad (10) $$

Note that $u$ and $v$ can be any label, but fixing $u = u_{\Delta}$ and $v$ the vertex having the second highest degree seems a good intuition. Constraints (9) and (10) can be added to models $\mathcal{M}_E$ and $\mathcal{M}_A^*$.

Some redundant constraints can also be added. For example, consider all the cycles of size 3 in $G$. Then, we can build a table of 3-uples representing the “legal” labeling of 3 vertices for a cyclic bandwidth of cost $k$. Although too expensive in the general case, this kind of redundant constraint can be added beneficially only around the vertex of the highest degree for example.

## 4.4 From Satisfiability to Optimization Models

It is obvious that if there is a cyclic labeling of cost $k$, there is also one of cost $k+1$ and, using the contraposition, if there is no labeling of cost $k$, then none of cost $k-1$ exists. We propose to use the satisfiability model $\mathcal{M}_E$ inside a dichotomy algorithm (see Algorithm 5) benefiting from the above property.

This optimization function (as described in Algorithm 5) can be called with the lower bound $lb = \lceil \Delta/2 \rceil$ (where $\Delta$ is the maximum degree of $G$) and the upper bound $ub = \lfloor n/2 \rfloor$. When knowing better bounds, such as the ones returned by our Recycling Algorithm, this function will be more efficient and
<caption>**Algorithm 5. optimization()**</caption>

k<sub>best</sub> ← ub
while lb < ub do
  k ← (ub + lb) div 2
  L ← {(ℓ, ℓ') ∈ N<sup>2</sup> | ℓ ≠ ℓ', min{|ℓ − ℓ'|, n − |ℓ − ℓ'| ≤ k}}
  if solve(M<sub>E</sub>, L) is SAT then
    ub ← k
    k<sub>best</sub> ← ub
  else
    lb ← k + 1
end if
end while
return k

will succeed more often in a reasonable time. The **solve** function creates the required model and solves it with an appropriate solver, i.e., a finite domain (FD) solver for $\mathcal{M}_E$.

*Iterating Recycling and Optimization algorithms.* Both the Recycling and Optimization algorithms aim at reducing the search interval, whose extremities are respectively the lower and upper bounds for $B_c^*(G)$, for any instance $G$. Obviously, if this interval is reduced to one value, then we have determined the optimal value $B_c^*(G)$. If not, then it is possible to iteratively apply Algorithms 1 and 5, aiming at further reducing the search interval, until a fixed point is reached.

## 5 Results

The benchmark we use here to evaluate performances of both our Recycling algorithm (Algorithm 1) and our Optimization algorithm (Algorithm 5) on the CYCLIC BANDWIDTH problem, is the classic 113 Harwell-Boeing benchmark [16], extracted from the Harwell-Boeing sparse matrix collection.

The results are shown Table 2 (33 medium-sized instances of our benchmark), along with Tables 3 and 4 (remaining 80 instances). In these three tables, we describe, in the three first columns, the name of each instance, its number of vertices and edges. The four subsequent columns, collectively called *inputs*, respectively provide the best lower and upper bounds for the BANDWIDTH MINIMIZATION and the CYCLIC BANDWIDTH problems. These four values correspond to the ones obtained by applying lines 1–4 of Algorithm 1. The two following columns, collectively called *Recycling algorithm*, respectively indicate whether $B_c^* = B^*$, and the search interval (lower bound/upper bound) for $B_c^*$ obtained after applying Algorithm 1. Finally, the rightmost column *value* indicates either the optimal value $B_c^*$ computed by Algorithm 5, or a lower/upper bound interval for $B_c^*$. In this column, ‘-’ indicates that the Optimization algorithm timed out.

*Results obtained by our Recycling algorithm.* Algorithm 1 (lines 1–4), by simply gathering the best knowledge from literature and (when applicable) by relying on the fact that $B_c^* = B^*$, can provide optimal values $B_c^*$, or drastically
<table><caption>**Table 2.** Results for 33 medium Harwell-Boeing instances. The results with an * in the Recycling algorithm column indicates a discrepancy between the Recycling algorithm and the optimization function</caption><thead><tr><th rowspan="2">Instance</th><th rowspan="2">vertices</th><th rowspan="2">edges</th><th colspan="4">Inputs</th><th rowspan="2">Recycling algorithm<br>B<sub>c</sub><sup>*</sup> = B<sup>*</sup>? value</th><th rowspan="2">Opt. algorithm<br>value</th></tr><tr><th>lb<sub>B</sub></th><th>ub<sub>B</sub></th><th>lb<sub>C</sub></th><th>ub<sub>C</sub></th></tr></thead><tbody><tr><td>pores_1</td><td>30</td><td>103</td><td>7</td><td>7</td><td>7</td><td>7</td><td>yes</td><td>7</td><td>7</td></tr><tr><td>ibm32</td><td>32</td><td>90</td><td>11</td><td>11</td><td>8</td><td>9</td><td>no</td><td>[8, 9]</td><td>9</td></tr><tr><td>bcspwr01</td><td>39</td><td>46</td><td>5</td><td>5</td><td>4</td><td>4</td><td>no</td><td>4</td><td>4</td></tr><tr><td>bcsstk01</td><td>48</td><td>176</td><td>16</td><td>16</td><td>12</td><td>12</td><td>no</td><td>12</td><td>12</td></tr><tr><td>bcspwr02</td><td>49</td><td>59</td><td>7</td><td>7</td><td>7</td><td>7</td><td>yes</td><td>7</td><td>7</td></tr><tr><td>curtis54</td><td>54</td><td>124</td><td>10</td><td>10</td><td>8</td><td>8</td><td>no</td><td>8</td><td>8</td></tr><tr><td>will157</td><td>57</td><td>127</td><td>6</td><td>6</td><td>6</td><td>6</td><td>yes</td><td>6</td><td>6</td></tr><tr><td>impcol_b</td><td>59</td><td>281</td><td>19</td><td>19</td><td>14</td><td>17</td><td>no</td><td>[14, 17]</td><td>17</td></tr><tr><td>steam3</td><td>80</td><td>424</td><td>7</td><td>7</td><td>7</td><td>7</td><td>yes</td><td>7</td><td>7</td></tr><tr><td>ash85</td><td>85</td><td>219</td><td>9</td><td>9</td><td>9</td><td>9</td><td>yes</td><td>9</td><td>9</td></tr><tr><td>nos4</td><td>100</td><td>247</td><td>10</td><td>10</td><td>10</td><td>10</td><td>yes</td><td>10</td><td>10</td></tr><tr><td>gent113</td><td>104</td><td>549</td><td>25</td><td>25</td><td>20</td><td>23</td><td>no</td><td>[20, 23]</td><td>23</td></tr><tr><td>bcsstk22</td><td>110</td><td>254</td><td>9</td><td>10</td><td>6</td><td>6</td><td>no</td><td>6</td><td>6</td></tr><tr><td>gre_115</td><td>115</td><td>267</td><td>20</td><td>22</td><td>20</td><td>23</td><td>yes*</td><td>[20, 23]</td><td>23</td></tr><tr><td>dwt_234</td><td>117</td><td>162</td><td>11</td><td>11</td><td>11</td><td>11</td><td>yes</td><td>11</td><td>11</td></tr><tr><td>bcspwr03</td><td>118</td><td>179</td><td>9</td><td>9</td><td>9</td><td>10</td><td>yes*</td><td>[9, 10]</td><td>10</td></tr><tr><td>lns_131</td><td>123</td><td>275</td><td>18</td><td>20</td><td>18</td><td>20</td><td>yes</td><td>[18, 20]</td><td>20</td></tr><tr><td>arc130</td><td>130</td><td>715</td><td>63</td><td>63</td><td>62</td><td>63</td><td>unknown</td><td>[62, 63]</td><td>63</td></tr><tr><td>bcsstk04</td><td>132</td><td>1758</td><td>36</td><td>37</td><td>33</td><td>37</td><td>unknown</td><td>[33, 37]</td><td>37</td></tr><tr><td>west0132</td><td>132</td><td>404</td><td>23</td><td>28</td><td>23</td><td>31</td><td>unknown</td><td>[23, 31]</td><td>31</td></tr><tr><td>impcol_c</td><td>137</td><td>352</td><td>23</td><td>27</td><td>23</td><td>24</td><td>unknown</td><td>[23, 24]</td><td>24</td></tr><tr><td>can_144</td><td>144</td><td>576</td><td>13</td><td>13</td><td>7</td><td>7</td><td>no</td><td>7</td><td>7</td></tr><tr><td>lund_a</td><td>147</td><td>1151</td><td>19</td><td>23</td><td>19</td><td>23</td><td>yes</td><td>[19, 23]</td><td>23</td></tr><tr><td>lund_b</td><td>147</td><td>1147</td><td>19</td><td>23</td><td>19</td><td>23</td><td>yes</td><td>[19, 23]</td><td>23</td></tr><tr><td>bcsstk05</td><td>153</td><td>1135</td><td>19</td><td>20</td><td>19</td><td>20</td><td>yes</td><td>[19, 20]</td><td>20</td></tr><tr><td>west0156</td><td>156</td><td>371</td><td>33</td><td>33</td><td>23</td><td>32</td><td>no</td><td>[23, 32]</td><td>–</td></tr><tr><td>nos1</td><td>158</td><td>312</td><td>3</td><td>3</td><td>3</td><td>3</td><td>yes</td><td>3</td><td>3</td></tr><tr><td>can_161</td><td>161</td><td>608</td><td>18</td><td>18</td><td>18</td><td>18</td><td>yes</td><td>18</td><td>18</td></tr><tr><td>west0167</td><td>167</td><td>489</td><td>31</td><td>34</td><td>28</td><td>34</td><td>unknown</td><td>[28, 34]</td><td>34</td></tr><tr><td>mcca</td><td>168</td><td>1662</td><td>32</td><td>32</td><td>32</td><td>37</td><td>yes</td><td>32</td><td>–</td></tr><tr><td>fs_183_1</td><td>183</td><td>701</td><td>52</td><td>58</td><td>52</td><td>58</td><td>unknown</td><td>[52, 58]</td><td>58</td></tr><tr><td>gre_185</td><td>185</td><td>650</td><td>17</td><td>19</td><td>17</td><td>21</td><td>yes*</td><td>[17, 21]</td><td>21</td></tr><tr><td>will199</td><td>199</td><td>660</td><td>55</td><td>65</td><td>34</td><td>50</td><td>no</td><td>[34, 50]</td><td>–</td></tr></tbody></table>

reduce the search interval. Indeed, we immediately conclude optimality for 28 of the 113 studied instances. Among the 85 remaining instances, the search interval is of length 2 (resp. 3) for 12 (resp. 9) instances.
<table><caption>Table 3. Results for 80 large Harwell-Boeing instances (part 1)</caption><thead><tr><th rowspan="2">Instance</th><th rowspan="2">vertices</th><th rowspan="2">edges</th><th colspan="4">Inputs</th><th colspan="2">Recycling algorithm</th><th rowspan="2">Opt. algorithm value</th></tr><tr><th>lb<sub>B</sub></th><th>ub<sub>B</sub></th><th>lb<sub>C</sub></th><th>ub<sub>C</sub></th><th>B<sup>*</sup><sub>c</sub> = B<sup>*</sup>?</th><th>value</th></tr></thead><tbody><tr><td>impcol_a</td><td>206</td><td>557</td><td>24</td><td>32</td><td>23</td><td>32</td><td>unknown</td><td>[23, 32]</td><td>-</td></tr><tr><td>dwt_209</td><td>209</td><td>767</td><td>20</td><td>23</td><td>20</td><td>23</td><td>yes</td><td>[20, 23]</td><td>23</td></tr><tr><td>gre_216a</td><td>216</td><td>660</td><td>17</td><td>21</td><td>17</td><td>21</td><td>yes</td><td>[17, 21]</td><td>21</td></tr><tr><td>dwt_221</td><td>221</td><td>704</td><td>11</td><td>13</td><td>11</td><td>13</td><td>yes</td><td>[11, 13]</td><td>13</td></tr><tr><td>impcol_e</td><td>225</td><td>1187</td><td>34</td><td>42</td><td>34</td><td>42</td><td>unknown</td><td>[34, 42]</td><td>-</td></tr><tr><td>saylri</td><td>238</td><td>445</td><td>12</td><td>14</td><td>12</td><td>14</td><td>yes</td><td>[12, 14]</td><td>14</td></tr><tr><td>steam1</td><td>240</td><td>1761</td><td>32</td><td>44</td><td>32</td><td>44</td><td>yes</td><td>[32, 44]</td><td>-</td></tr><tr><td>dwt_245</td><td>245</td><td>608</td><td>21</td><td>21</td><td>21</td><td>21</td><td>yes</td><td>21</td><td>21</td></tr><tr><td>nnc261</td><td>261</td><td>794</td><td>22</td><td>24</td><td>22</td><td>24</td><td>yes</td><td>[22, 24]</td><td>24</td></tr><tr><td>bcspwr04</td><td>274</td><td>669</td><td>23</td><td>24</td><td>23</td><td>24</td><td>yes</td><td>[23, 24]</td><td>-</td></tr><tr><td>ash292</td><td>292</td><td>958</td><td>16</td><td>19</td><td>16</td><td>19</td><td>yes</td><td>[16, 19]</td><td>-</td></tr><tr><td>can_292</td><td>292</td><td>1124</td><td>34</td><td>36</td><td>34</td><td>38</td><td>yes</td><td>[34, 36]</td><td>-</td></tr><tr><td>dwt_310</td><td>310</td><td>1069</td><td>11</td><td>12</td><td>11</td><td>12</td><td>yes</td><td>[11, 12]</td><td>12</td></tr><tr><td>gre_343</td><td>343</td><td>1092</td><td>23</td><td>28</td><td>23</td><td>28</td><td>yes</td><td>[23, 28]</td><td>-</td></tr><tr><td>dwt_361</td><td>361</td><td>1296</td><td>14</td><td>14</td><td>14</td><td>14</td><td>yes</td><td>14</td><td>14</td></tr><tr><td>plat362</td><td>362</td><td>2712</td><td>28</td><td>34</td><td>28</td><td>34</td><td>yes</td><td>[28, 34]</td><td>-</td></tr><tr><td>plskz362</td><td>362</td><td>880</td><td>14</td><td>18</td><td>14</td><td>18</td><td>yes</td><td>[14, 18]</td><td>-</td></tr><tr><td>str_0</td><td>363</td><td>2446</td><td>87</td><td>116</td><td>58</td><td>91</td><td>unknown</td><td>[58, 91]</td><td>-</td></tr><tr><td>str_200</td><td>363</td><td>3049</td><td>90</td><td>124</td><td>65</td><td>99</td><td>unknown</td><td>[65, 99]</td><td>-</td></tr><tr><td>str_600</td><td>363</td><td>3244</td><td>95</td><td>132</td><td>71</td><td>103</td><td>unknown</td><td>[71, 103]</td><td>-</td></tr><tr><td>west0381</td><td>381</td><td>2150</td><td>117</td><td>151</td><td>86</td><td>113</td><td>no</td><td>[86, 113]</td><td>-</td></tr><tr><td>dwt_419</td><td>419</td><td>1572</td><td>22</td><td>25</td><td>22</td><td>25</td><td>yes</td><td>[22, 25]</td><td>-</td></tr><tr><td>bcssstk06</td><td>420</td><td>3720</td><td>37</td><td>45</td><td>37</td><td>45</td><td>yes</td><td>[37, 45]</td><td>-</td></tr><tr><td>bcssstm07</td><td>420</td><td>3416</td><td>37</td><td>42</td><td>37</td><td>45</td><td>yes</td><td>[37, 42]</td><td>-</td></tr><tr><td>impcol_d</td><td>425</td><td>1267</td><td>36</td><td>40</td><td>24</td><td>35</td><td>no</td><td>[24, 35]</td><td>-</td></tr><tr><td>hor_131</td><td>434</td><td>2138</td><td>46</td><td>55</td><td>46</td><td>55</td><td>yes</td><td>[46, 55]</td><td>-</td></tr><tr><td>bcspwr05</td><td>443</td><td>590</td><td>25</td><td>27</td><td>25</td><td>27</td><td>yes</td><td>[25, 27]</td><td>26</td></tr><tr><td>can_445</td><td>445</td><td>1682</td><td>45</td><td>52</td><td>45</td><td>46</td><td>unknown</td><td>[45, 46]</td><td>-</td></tr><tr><td>pores_3</td><td>456</td><td>1769</td><td>13</td><td>13</td><td>13</td><td>13</td><td>yes</td><td>13</td><td>13</td></tr><tr><td>bcssstk20</td><td>467</td><td>1295</td><td>8</td><td>13</td><td>8</td><td>13</td><td>unknown</td><td>[8, 13]</td><td>-</td></tr><tr><td>nos5</td><td>468</td><td>2352</td><td>52</td><td>63</td><td>52</td><td>63</td><td>yes</td><td>[52, 63]</td><td>-</td></tr><tr><td>west0479</td><td>479</td><td>1889</td><td>81</td><td>118</td><td>80</td><td>105</td><td>unknown</td><td>[80, 105]</td><td>-</td></tr><tr><td>mbeacxc</td><td>487</td><td>41686</td><td>246</td><td>260</td><td>243</td><td>243</td><td>no</td><td>243</td><td>-</td></tr><tr><td>mbeaflw</td><td>487</td><td>41686</td><td>246</td><td>261</td><td>243</td><td>243</td><td>no</td><td>243</td><td>-</td></tr><tr><td>mbeause</td><td>492</td><td>36209</td><td>249</td><td>254</td><td>245</td><td>246</td><td>no</td><td>[245, 246]</td><td>-</td></tr><tr><td>494_bus</td><td>494</td><td>586</td><td>25</td><td>29</td><td>25</td><td>28</td><td>unknown</td><td>[25, 28]</td><td>-</td></tr><tr><td>west0497</td><td>497</td><td>1715</td><td>69</td><td>85</td><td>69</td><td>81</td><td>unknown</td><td>[69, 81]</td><td>-</td></tr><tr><td>dwt_503</td><td>503</td><td>2762</td><td>29</td><td>40</td><td>29</td><td>41</td><td>yes</td><td>[29, 40]</td><td>-</td></tr><tr><td>lns_511</td><td>503</td><td>1425</td><td>33</td><td>44</td><td>33</td><td>44</td><td>yes</td><td>[33, 44]</td><td>-</td></tr><tr><td>gre_512</td><td>512</td><td>1680</td><td>30</td><td>36</td><td>30</td><td>36</td><td>yes</td><td>[30, 36]</td><td>-</td></tr></tbody></table>
<table><caption>Table 4. Results for 80 large Harwell-Boeing instances (part 2)</caption><thead><tr><th rowspan="2">Instance</th><th rowspan="2">vertices</th><th rowspan="2">edges</th><th colspan="4">Inputs</th><th colspan="2">Recycling algorithm</th><th rowspan="2">Opt. algorithm value</th></tr><tr><th>lb<sub>B</sub></th><th>ub<sub>B</sub></th><th>lb<sub>C</sub></th><th>ub<sub>C</sub></th><th>B<sub>c</sub><sup>*</sup> = B<sup>*</sup>?</th><th>value</th></tr></thead><tbody><tr><td>fs_541_1</td><td>541</td><td>2466</td><td>270</td><td>270</td><td>270</td><td>270</td><td>unknown</td><td>270</td><td>–</td></tr><tr><td>sherman4</td><td>546</td><td>1341</td><td>21</td><td>27</td><td>21</td><td>27</td><td>yes</td><td>[21, 27]</td><td>–</td></tr><tr><td>dwt_592</td><td>592</td><td>2256</td><td>22</td><td>28</td><td>22</td><td>29</td><td>yes</td><td>[22, 28]</td><td>–</td></tr><tr><td>steam2</td><td>600</td><td>6580</td><td>54</td><td>63</td><td>54</td><td>63</td><td>yes</td><td>[54, 63]</td><td>–</td></tr><tr><td>nos2</td><td>638</td><td>1272</td><td>3</td><td>3</td><td>3</td><td>3</td><td>yes</td><td>3</td><td>3</td></tr><tr><td>west0655</td><td>655</td><td>2841</td><td>109</td><td>160</td><td>94</td><td>149</td><td>unknown</td><td>[94, 149]</td><td>–</td></tr><tr><td>662_bus</td><td>662</td><td>906</td><td>36</td><td>39</td><td>36</td><td>38</td><td>unknown</td><td>[36, 38]</td><td>–</td></tr><tr><td>shl_0</td><td>663</td><td>1682</td><td>211</td><td>226</td><td>211</td><td>212</td><td>unknown</td><td>[211, 212]</td><td>–</td></tr><tr><td>shl_200</td><td>663</td><td>1720</td><td>220</td><td>231</td><td>220</td><td>220</td><td>unknown</td><td>220</td><td>–</td></tr><tr><td>shl_400</td><td>663</td><td>1709</td><td>213</td><td>230</td><td>213</td><td>215</td><td>unknown</td><td>[213, 215]</td><td>–</td></tr><tr><td>nnc666</td><td>666</td><td>2148</td><td>33</td><td>40</td><td>33</td><td>41</td><td>yes</td><td>[33, 40]</td><td>–</td></tr><tr><td>nos6</td><td>675</td><td>1290</td><td>15</td><td>16</td><td>15</td><td>16</td><td>yes</td><td>[15, 16]</td><td>16</td></tr><tr><td>fs_680_1</td><td>680</td><td>1464</td><td>17</td><td>17</td><td>17</td><td>17</td><td>yes</td><td>17</td><td>17</td></tr><tr><td>saylr3</td><td>681</td><td>1373</td><td>35</td><td>47</td><td>35</td><td>46</td><td>yes</td><td>[35, 46]</td><td>–</td></tr><tr><td>sherman1</td><td>681</td><td>1373</td><td>35</td><td>47</td><td>35</td><td>46</td><td>yes</td><td>[35, 46]</td><td>–</td></tr><tr><td>685_bus</td><td>685</td><td>1282</td><td>30</td><td>32</td><td>30</td><td>32</td><td>yes</td><td>[30, 32]</td><td>–</td></tr><tr><td>can_715</td><td>715</td><td>2975</td><td>54</td><td>72</td><td>52</td><td>60</td><td>unknown</td><td>[52, 60]</td><td>–</td></tr><tr><td>nos7</td><td>729</td><td>1944</td><td>43</td><td>65</td><td>43</td><td>65</td><td>yes</td><td>[43, 65]</td><td>–</td></tr><tr><td>mcfe</td><td>731</td><td>15086</td><td>112</td><td>126</td><td>112</td><td>126</td><td>yes</td><td>[112, 126]</td><td>[125, 126]</td></tr><tr><td>fs_760_1</td><td>760</td><td>3518</td><td>36</td><td>38</td><td>36</td><td>38</td><td>yes</td><td>[36, 38]</td><td>–</td></tr><tr><td>bcssstk19</td><td>817</td><td>3018</td><td>13</td><td>14</td><td>13</td><td>14</td><td>yes</td><td>[13, 14]</td><td>–</td></tr><tr><td>bp_0</td><td>822</td><td>3260</td><td>174</td><td>236</td><td>174</td><td>207</td><td>unknown</td><td>[174, 207]</td><td>–</td></tr><tr><td>bp_200</td><td>822</td><td>3788</td><td>186</td><td>258</td><td>186</td><td>218</td><td>unknown</td><td>[186, 218]</td><td>–</td></tr><tr><td>bp_400</td><td>822</td><td>4015</td><td>188</td><td>268</td><td>188</td><td>220</td><td>unknown</td><td>[188, 220]</td><td>220</td></tr><tr><td>bp_600</td><td>822</td><td>4157</td><td>190</td><td>272</td><td>189</td><td>229</td><td>unknown</td><td>[189, 229]</td><td>229</td></tr><tr><td>bp_800</td><td>822</td><td>4518</td><td>197</td><td>278</td><td>190</td><td>239</td><td>unknown</td><td>[190, 239]</td><td>239</td></tr><tr><td>bp_1000</td><td>822</td><td>4635</td><td>197</td><td>287</td><td>191</td><td>241</td><td>unknown</td><td>[191, 241]</td><td>241</td></tr><tr><td>bp_1200</td><td>822</td><td>4698</td><td>197</td><td>291</td><td>193</td><td>241</td><td>unknown</td><td>[193, 241]</td><td>241</td></tr><tr><td>bp_1400</td><td>822</td><td>4760</td><td>199</td><td>290</td><td>193</td><td>242</td><td>unknown</td><td>[193, 242]</td><td>242</td></tr><tr><td>bp_1600</td><td>822</td><td>4809</td><td>199</td><td>293</td><td>192</td><td>241</td><td>unknown</td><td>[192, 241]</td><td>241</td></tr><tr><td>can_838</td><td>838</td><td>4586</td><td>75</td><td>86</td><td>57</td><td>58</td><td>no</td><td>[57, 58]</td><td>58</td></tr><tr><td>dwt_878</td><td>878</td><td>3285</td><td>23</td><td>25</td><td>23</td><td>24</td><td>yes</td><td>[23, 24]</td><td>24</td></tr><tr><td>orsirr_2</td><td>886</td><td>2542</td><td>62</td><td>84</td><td>62</td><td>85</td><td>yes</td><td>[62, 84]</td><td>–</td></tr><tr><td>gr_30_30</td><td>900</td><td>3422</td><td>31</td><td>31</td><td>31</td><td>32</td><td>yes</td><td>31</td><td>31</td></tr><tr><td>dwt_918</td><td>918</td><td>3233</td><td>27</td><td>32</td><td>27</td><td>32</td><td>yes</td><td>[27, 32]</td><td>–</td></tr><tr><td>jagmesh1</td><td>936</td><td>2664</td><td>24</td><td>27</td><td>20</td><td>20</td><td>no</td><td>20</td><td>20</td></tr><tr><td>nos3</td><td>960</td><td>7442</td><td>43</td><td>43</td><td>43</td><td>43</td><td>yes</td><td>43</td><td>43</td></tr><tr><td>jpwh_991</td><td>983</td><td>2678</td><td>82</td><td>90</td><td>82</td><td>88</td><td>yes</td><td>[82, 88]</td><td>–</td></tr><tr><td>west0989</td><td>989</td><td>3500</td><td>123</td><td>210</td><td>123</td><td>217</td><td>unknown</td><td>[123, 217]</td><td>–</td></tr><tr><td>dwt_992</td><td>992</td><td>7876</td><td>35</td><td>35</td><td>35</td><td>35</td><td>yes</td><td>35</td><td>35</td></tr></tbody></table>
Results obtained by our Recycling algorithm along with the Optimization function. Tightening the search interval through Algorithm 1 is obviously advantageous for our optimization() function (Algorithm 5), as it is based on dichotomy. As a matter of fact, the results we obtain through “Recycling + optimization”, prove very efficient. Indeed, among the 113 initial instances, Algorithm 5 determines the optimal $B_c^*$ value for half of them (56 cases), and the search interval is reduced in one case. Note also that, every time $B_c^* = B^*$, determining $B_c^*$ or tightening its search interval also improves knowledge on $B^*$. All experiments are run on a computer equipped with an Intel Xeon ES 2630, 2.66 GHz processor, and coded in Python using the PyCSP³ v2.2 library [24]. Each instance has up to 120 h to complete the optimization() function, which can lead to several calls to the CSP solver (same instance, different k values).

# 6 Conclusions and Future Work

This paper shows how the combination of pre-existing knowledge and some solving techniques can help to improve results for some hard combinatorial problems, such as the CYCLIC BANDWIDTH problem. In our case, we leverage the close relation between the BANDWIDTH MINIMIZATION and the CYCLIC BANDWIDTH problems to propose the Recycling algorithm. Our algorithm takes advantage of existing knowledge and uses it in a way that no solver is required to tighten bounds, prove optimization, or find the optimum at almost zero computational cost. For instances that require long computational runtimes, the bound tightening is a direct gain in the quest to find (or validate) optimums. In a second step, we propose an optimization function, based on constraint programming, to test the remaining values in the lower and upper bounds interval obtained in the first step. The experimental results validated the proposed approach by obtaining optimums for 56 (out of the 113) Harwell-Boeing instances and tightening bounds for another instance. We also found three instances presenting discrepancies between the Recycling algorithm and the optimization function; upon reviewing the data and running a CP-based bandwidth minimization function, it seems there may be errors in the reported values from Pop's article. Our next steps will involve: 1) a revision of bandwidth minimization values and, 2) the study of graph properties or different modeling approaches in CP to overcome the specificities of certain instances for which the solver could not find a solution.

# References

1. Apt, K.R., Monfroy, É.: Constraint programming viewed as rule-based programming. Theory Pract. Log. Program. 1(6), 713–750 (2001)

2. Chinn, P.Z., Chvátalová, J., Dewdney, A.K., Gibbs, N.E.: The bandwidth problem for graphs and matrices - a survey. J. Graph Theor. 6(3), 223–254 (1982)

3. Chung, F.R.: Labelings of graphs. Sel. Top. Graph Theor. 3, 151–168 (1988)

4. Déprés, H., Fertin, G., Monfroy, E.: Improved lower bounds for the cyclic bandwidth problem. In: Paszynski, M., Kranzlmüller, D., Krzhizhanovskaya, V.V., Dongarra, J.J., Sloot, P.M.A. (eds.) ICCS 2021. LNCS, vol. 12742, pp. 555–569. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77961-0_45
5. Harary, F., Manvel, B.: On the number of cycles in a graph. Matematický časopis **21**(1), 55–63 (1971)

6. Harper, L.H.: Optimal assignments of numbers to vertices. J. Soc. Ind. Appl. Math. **12**(1), 131–135 (1964)

7. van Hoeve, W.J.: The all different constraint: a survey. CoRR cs.PL/0105015 (2001). https://arxiv.org/abs/cs/0105015

8. Hromkovič, J., Müller, V., Sýkora, O., Vrťo, I.: On embedding interconnection networks into rings of processors. In: Etiemble, D., Syre, J.-C. (eds.) PARLE 1992. LNCS, vol. 605, pp. 51–62. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-55599-4_80

9. Lam, P.C.B., Shiu, W.C., Chan, W.H.: Characterization of graphs with equal bandwidth and cyclic bandwidth. Discret. Math. **242**(1–3), 283–289 (2002)

10. Lecoutre, C.: Optimization of simple tabular reduction for table constraints. In: Stuckey, P.J. (ed.) CP 2008. LNCS, vol. 5202, pp. 128–143. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85958-1_9

11. Leung, J.Y., Vornberger, O., Witthoff, J.D.: On some variants of the bandwidth minimization problem. SIAM J. Comput. **13**(3), 650–667 (1984)

12. Lin, Y.: A level structure approach on the bandwidth problem for special graphs. Ann. N. Y. Acad. Sci. **576**(1), 344–357 (1989)

13. Lin, Y.: The cyclic bandwidth problem. Syst. Sci. Math. Sci. **7** (1994)

14. Lin, Y.: Minimum bandwidth problem for embedding graphs in cycles. Networks **29**(3), 135–140 (1997)

15. Martí, R., Campos, V., Piñana, E.: A branch and bound algorithm for the matrix bandwidth minimization. Eur. J. Oper. Res. **186**, 513–528 (2008)

16. Martí, R., Laguna, M., Glover, F., Campos, V.: Reducing the bandwidth of a sparse matrix with tabu search. Eur. J. Oper. Res. **135**, 450–459 (2001)

17. Mladenovic, N., Urosevic, D., Pérez-Brito, D., García-González, C.: Variable neighbourhood search for bandwidth reduction. Eur. J. Oper. Res. **200**(1), 14–27 (2010)

18. Pop, P., Matei, O., Comes, C.A.: Reducing the bandwidth of a sparse matrix with a genetic algorithm. Optimization **63**(12), 1851–1876 (2014)

19. Ren, J., Hao, J., Rodriguez-Tello, E.: An iterated three-phase search approach for solving the cyclic bandwidth problem. IEEE Access **7**, 98436–98452 (2019)

20. Ren, J., Hao, J.K., Rodriguez-Tello, E., Li, L., He, K.: A new iterated local search algorithm for the cyclic bandwidth problem. Knowl.-Based Syst. **203**, 106136 (2020)

21. Rodriguez-Tello, E., Hao, J.K., Torres-Jimenez, J.: An improved simulated annealing algorithm for bandwidth minimization. Eur. J. Oper. Res. **185**(3), 1319–1335 (2008)

22. Rodriguez-Tello, E., Romero-Monsivais, H., Ramírez-Torres, G., Lardeux, F.: Tabu search for the cyclic bandwidth problem. Comput. Oper. Res. **57**, 17–32 (2015)

23. Rossi, F., van Beek, P., Walsh, T. (eds.): Handbook of Constraint Programming, Foundations of Artificial Intelligence, vol. 2. Elsevier (2006)

24. XCSP3 Team: PyCSP³ v2.2 (2023). https://www.pycsp.org/

25. Zhou, S.: Bounding the bandwidths for graphs. Theoret. Comput. Sci. **249**(2), 357–368 (2000)