# Tire noise optimization problem: a mixed integer linear programming approach

Matthias Becker, Nicolas Ginoux, Sébastien Martin, Zsuzsanna Róka

► To cite this version:

Matthias Becker, Nicolas Ginoux, Sébastien Martin, Zsuzsanna Róka. Tire noise optimization problem: a mixed integer linear programming approach. RAIRO - Operations Research, 2021, 55 (5), pp.3073-3085. 10.1051/ro/2021147. hal-03379132v2

HAL Id: hal-03379132

https://hal.science/hal-03379132v2

Submitted on 14 Oct 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# TIRE NOISE OPTIMIZATION PROBLEM: A MIXED INTEGER LINEAR PROGRAMMING APPROACH

MATTHIAS BECKER<fnref n="1" />, NICOLAS GINOUX<fnref n="2" /> ID, SÉBASTIEN MARTIN<fnref n="3" /> AND ZSUZSANNA RÓKA<fnref n="3" />,* ID

**Abstract.** We present a Mixed Integer Linear Programming (MILP) approach in order to model the non-linear problem of minimizing the tire noise function. In a recent work, we proposed an exact solution for the Tire Noise Optimization Problem, dealing with an APproximation of the noise (TNOP-AP). Here we study the original non-linear problem modeling the EXact- or real-noise (TNOP-EX) and propose a new scheme to obtain a solution for the TNOP-EX. Relying on the solution for the TNOP-AP, we use a Branch&Cut framework and develop an exact algorithm to solve the TNOP-EX. We also take more industrial constraints into account. Finally, we compare our experimental results with those obtained by other methods.

**Mathematics Subject Classification.** 49M, 65K05, 90C05, 90C10, 90C11, 90C57, 90C90.

Received February 10, 2020. Accepted September 18, 2021.

## 1. INTRODUCTION

The reduction of tire noise in the vehicle interior has been a major field of research in the tire industry for many years. After the tire engineers have determined every aspect of a new tire prototype concerning the driving and safety characteristics, the last degree of freedom is the final design of the so-called pitch sequence. In [16], T.A. Williams provides a historical overview of the approaches used by different companies, based on some U.S. Patent documents, from 1934 to 1994. First studies show that the noise optimization does not give good results when the number of pitch types is small (a mono-space sequence is the noisiest) and the tire mold is difficult when this number is large. A realistic tire size is a sequence of around 60-70 pitches, hence a complete search is not feasible because of an exponential computational time. First methods concerned patented single pitch sequences and a randomization of the sequence design. In the 1990's, some heuristic optimization algorithms were used in [9], based on genetic algorithms. In [11], the road surface is also taken into account when modeling the noise of certain pitch patterns. In [14], the authors explain the sound generation mechanisms of a tire as well as the mathematical noise model. Further works deal with application of intelligent heuristic optimization

<footnote>*Keywords*. Mixed integer linear programming, branch-and-cut, tire shape optimization.</footnote>

<footnote n="1">1 FG HCI, Appelstr. 9A, Universität Hannover, 30167 Hannover, Germany.</footnote>

<footnote n="2">2 Université de Lorraine, CNRS, IECL, Metz 57000, France.</footnote>

<footnote n="3">3 Laboratoire de Conception, Optimisation et Modélisation des Systèmes, LCOMS EA 7306, Université de Lorraine, Metz 57000, France.</footnote>

<footnote>*Corresponding author: zsuzsanna.roka@univ-lorraine.fr</footnote>
algorithms (such as genetic algorithms and algorithms based on neural networks) on problems with one pitch sequence, with multiple pitch sequences, and on tires with spikes (cf. [1,2] and references within those articles). An approach based on artificial immune systems combined with genetic algorithms is presented in [4] and [13]. In [10], a pitch sequence with five pitch types and 50 pitches is optimized using a genetic algorithm. There, by contrast with other approaches, the noise of the tire pattern is assessed *via* an image based algorithm. During the optimization procedure, the only free parameter is the pitch sequence. The quality of each sequence is assessed *via* a spectral analysis of the candidate sequences. The optimization of the pattern of a single pitch *via* particle swarm (PSO) is studied in [5].

The survey of the previous works shows that the first approaches tried to find good pitch sequences using random generation since a complete enumeration of all possibilities is too complex. In the following, more sophisticated methods from the field of heuristic optimization have been used, which are quite fast and deliver good results. However, it cannot be guaranteed that the globally best solution will be found. Thus, the motivation of our research work is to evaluate whether a Mixed Integer Linear Program (MILP) approach could efficiently tackle the problem. The MILP approach makes use of the problem-inherent constraints to decrease the size of the search space but still will find the optimal solution. We thereby would like to fill the gap between complete enumeration which would find the global optimum but cannot be applied to real-world problem sizes (about 60 pitches), and the heuristic algorithms which are quite fast but do not guarantee to find the global optimum. At best, the MILP would be fast enough to tackle real-world problem sizes and would also find the global optimum. In order to use the MILP approach for the optimization of tire noise, the optimization problem has to be formulated in a linearized way. This is the first research objective of our work. Indeed, the tire noise is approximated by a mathematical function, based on Fourier coefficients computed on a space of functions that is not a vector space and hence cannot be linearized in a natural way. Nevertheless, a pitch sequence has to satisfy several constraints (pitch length ratios, number of pitches, etc.), and hence a MILP approach can be considered once a convenient noise approximation is defined. Our second objective is then to implement the MILP for our problem and to check to which extent the algorithm is efficient enough so that real-world problems might be solved.

In a previous work [2], we proposed in a very first approach a linear approximation of the tire noise and a MILP solving the tire noise optimization problem: the noise value computed for a given sequence is only an approximation of the modeled real noise and the sequences we found are in general not the optimal ones. Nevertheless, the ratio between the computed value and the modeled real noise is bounded by $\sqrt{2}$.

In the present paper, we deepen our study and focus on the modeled real noise. The MILP defined in [2] only allows for an approximated solution. Here, for an easier understanding, we clarify the notations of [2] and present the mathematical model in more detail. In Section 3.1, we present a graph model of the problem, showing that the tire optimization problem can be interpreted as a path problem. In Section 3.2, we add some new constraints to the MILP. We then complete the MILP with a Branch-and-Cut algorithm to obtain the optimal solution (see Sect. 3.3). We conclude with some experimental results.

## 2. THE TIRE NOISE OPTIMIZATION PROBLEM

### 2.1. Brief description of the problem

The surface of a tire consists of different tracks, each track built out of a sequence of pitches of different sizes (see Fig. 1a). Since we are interested in the feasibility of the MILP approach, we focus our study on the least complex tires, i.e. those with only one track. In a previous work [3], it has been shown that multiple pitch tracks result in an enormous increase of problem complexity. For very complex problems, naively applied heuristic algorithms do not even find the next allowed solutions in the neighborhood of the search space.

A pitch is considered as the juxtaposition of an elevated part and a low part, called groove. The tire noise is produced by the grooves when coming into contact with the road surface. All pitches have the same height $h$ and the groove is a constant fractional part $q$ of the pitch length (Fig. 1b). Let $P := \{1, \dots, r\}$ be the finite set
<figure><img src="image_2.png" /><figcaption>FIGURE 1. (a) Tracks and pitches, (b) a pitch of size $\bar{l}_i$ and (c) a pitch sequence representing a tire track.</figcaption></figure>

of pitch types with lengths $\bar{l}_1 < \dots < \bar{l}_r$. Then, a pitch sequence can be modeled by an integer vector on $P$. For instance, for $|P| = 3$, the pitch sequence of Figure 1c is modeled by $(3, 2, 3, 1, \dots)$.

In this paper, we only study single track tires, thus the tire profile can be considered as a step function. The modeled exact tire noise is then defined as a scalar multiple of the largest Fourier coefficient in absolute value of that function (see Sect. 2.2.1 for a formal definition). From now on, we mean by tire noise the modeled exact tire noise.

The Tire Noise Optimization Problem for the EXact noise (TNOP-EX) consists in finding a pitch sequence producing the lowest noise, respecting given parameters provided by engineers. For the basic model, they are:

- the number of different pitch types,

- the length ratios of the different pitch types,

- the total number of pitches composing the tire.

Notice that the length of each type is not given as an absolute physical number in SI (Système International) units, but as a relative length ratio between the types. Note also that only the total number of pitches is fixed but not the number of pitches of each type, therefore the length of the pitch sequence, corresponding to the tire circumference, can vary. However, this circumference can always be normalized to some standard industrial tire size since the tire noise only depends on the relative pitch lengths.

To ensure stability in driving and wearing, we also consider other constraints such as:

**ctMinMaxOcc:** The minimal and maximal number of occurrences of each pitch type in a pitch sequence is bounded

**ctIncompatibility:** Pitches of given types cannot be neighbors in a sequence (e.g. the shortest and the longest ones)

**ctMaxSeq:** The length of a sub-sequence of pitches of the same type is bounded.

## 2.2. Definition of a discrete model

Here we describe a continuous mathematical model for the tire noise and its discretization. In particular, we define length units to transform the relative ratios into integral pitch length thus allowing for a MILP model. Notice that this MILP provides an approximated noise value. The Tire Noise Optimization Problem for this AP-approximated noise is denoted TNOP-AP.

### 2.2.1. The noise function

The model we study is based on the computation of the Fourier coefficients $a_n, b_n, c_n$ of a given function depending on the profile of the tire. Recall that, if $f$ is a $T$-periodic function of one real variable, then formally,
for all $n \in \mathbb{N}$,

$$a_n(f) := \frac{2}{T} \int_0^T f(x) \cos\left(\frac{2\pi n}{T}x\right) dx$$

$$b_n(f) := \frac{2}{T} \int_0^T f(x) \sin\left(\frac{2\pi n}{T}x\right) dx$$

$$c_n(f) := \frac{1}{T} \int_0^T f(x) e^{-\frac{2i\pi n}{T}x} dx = \frac{1}{2}(a_n(f) - ib_n(f)).$$

Originally (see e.g. [3]), the real noise produced by a tire with one track is proportional to

$$2 \max_{n \ge 1}(|c_n(f)|),$$

where $f$ is the profile function of the track.

Variable-rescaling does not change the value of the Fourier coefficients: if $f$ is a $T$-periodic function, then for any real positive number $\delta$, the function $f_{\delta}(x) := f(\delta x)$ is $\frac{T}{\delta}$-periodic and, for every $n \in \mathbb{N}$, we have $c_n(f_{\delta}) = c_n(f)$ (in particular $a_n(f_{\delta}) = a_n(f)$ as well as $b_n(f_{\delta}) = b_n(f)$). This property has the following important consequence: instead of fixing the circumference $T$ of the tire and let the pitch-lengths vary according to the number of pitches $N$ present on the track, we may fix the pitch-lengths once for all and let the total circumference vary in terms of $N$; the computed Fourier coefficients (and therefore the noise) will not change under that transformation.

Another important assumption deals with relative pitch length ratios that we assume to be rational, hence allowing the pitch lengths to be integers (see Sect. 2.2.3). When we denote a length by an integer, we implicitly assume it is expressed as an integer number of a fixed unit length that we do not need to make precise for the computations.

It is worth noticing that several models exist for the profile function. For instance, in [14], the profile function is described as a finite sum of Dirac functions (actually distributions) at positions $t_1 < \dots < t_N$, where $N$ is the number of pitches. In that case the modulus of the Fourier coefficient $c_n$ is given by

$$|c_n| = \frac{1}{T} \sqrt{\left(\sum_{i=1}^{N} \cos\left(\frac{2\pi n}{T} t_i\right)\right)^2 + \left(\sum_{i=1}^{N} \sin\left(\frac{2\pi n}{T} t_i\right)\right)^2}, \quad n \in \{1, \dots, 200\}.$$

Remark that, in real life, a tire track can be considered as a sequence of $N = 60$ pitches at most. As explained in Section 4, the estimated noise can be computed before the $n = 3.5N$th Fourier coefficient.

Trying to calculate the impact of exactly one pitch at a certain position $t_m$ ($1 \le m \le N$) we can write
$$|c_n| = \frac{1}{T} \sqrt{C^2 + S^2}, \text{ with}$$

$$C = \sum_{i=1}^{N} \cos \left( \frac{2\pi n}{T} t_i \right) = \sum_{i=1}^{m-1} \cos \left( \frac{2\pi n}{T} t_i \right) + \cos \left( \frac{2\pi n}{T} t_m \right) + \sum_{i=m+1}^{N} \cos \left( \frac{2\pi n}{T} t_i \right)$$

$$S = \sum_{i=1}^{N} \sin \left( \frac{2\pi n}{T} t_i \right) = \sum_{i=1}^{m-1} \sin \left( \frac{2\pi n}{T} t_i \right) + \sin \left( \frac{2\pi n}{T} t_m \right) + \sum_{i=m+1}^{N} \sin \left( \frac{2\pi n}{T} t_i \right),$$

where $m$ corresponds to the position of the pitch and $n$ to the measured frequency. We have emphasized the contribution of the pitch standing at position $t_m$. Because of the squares in the expression of $|c_n|$, the specific harmonic cannot be calculated up to a position $t_m$. This means we have to multiply e.g. the expression for $a_n$ out, when we can compute $\frac{a_n^2}{4}$ as

$$\frac{1}{T^2} \left( \sum_{i=1}^{m-1} \cos \left( \frac{2\pi n}{T} t_i \right) + \cos \left( \frac{2\pi n}{T} t_m \right) + \sum_{i=m+1}^{N} \cos \left( \frac{2\pi n}{T} t_i \right) \right)^2$$
which makes the contribution of each pitch dependent with that of every other (the part before position $t_m$ has to be multiplied with the part after $t_m$, with contribution at $t_m$ itself).

As mentioned in Section 1, several further models have been described in the literature. Here we are interested in the model that was proposed in [3] and [2]. The profile function $f$ is provided by the profile of the tire, i.e. the step function given by the pitch sequence. In that case, the Fourier coefficients of a given track may be explicitly computed in terms of the height $h$ and the lengths of the different pitches. From now on, we assume there are $N$ pitches on the given track. We denote by $l(1), \dots, l(N)$ the lengths of the successive pitches of a given pitch sequence. Then, for any $n \ge 1$,

$$a_n(f) = \frac{h}{n\pi} \cdot \sum_{j=1}^{N} \sin(M_{j,n}) - \sin(N_{j,n}) \qquad (2.1)$$

$$b_n(f) = -\frac{h}{n\pi} \cdot \sum_{j=1}^{N} \cos(M_{j,n}) - \cos(N_{j,n}), \qquad (2.2)$$

where

$$M_{j,n} := \frac{2n\pi}{T} \cdot \left( \sum_{p=1}^{j-1} l(p) + (1-q)l(j) \right) \quad \text{and}$$

$$N_{j,n} := \frac{2n\pi}{T} \cdot \sum_{p=1}^{j-1} l(j) = M_{j,n} - (1-q) \frac{2n\pi}{T} l(j).$$

The quantities $M_{j,n}$ and $N_{j,n}$ do not have any particular geometric meaning here. In particular,

$$c_n(f) = \frac{ih}{2n\pi} \cdot \sum_{j=1}^{N} e^{-iM_{j,n}} - e^{-iN_{j,n}}. \qquad (2.3)$$

It is important to notice a few symmetry properties of the Fourier coefficients.

- The modulus of each Fourier coefficient $c_n$ is invariant under translation, that is, applying a circular permutation to the pitches does not change the value of $|c_n|$. Note however that $|a_n|$ and $|b_n|$ change in general under such transformations. As a consequence, for the computation of the real noise involving $|c_n|$, we can assume that the first pitch in the sequence is of the first pitch type.

- Taking the mirror image of a given profile function keeps $a_n$ unchanged while turning each $b_n$ into $-b_n$, in particular it fixes $|a_n|$ and $|b_n|$ – and thus also $|c_n|$.

In order to handle the noise with Mixed Integer Linear Programming (MILP), the authors of [2] defined the approximated noise of a given one-tracked-tire to be proportional to

$$\max_{n \ge 1} (\max(|a_n(f)|, |b_n(f)|)),$$

where neither squares nor square-roots enter. Though a priori different, both formulae are roughly equivalent in the following sense: for any real numbers $a, b$,

$$\max(|a|, |b|) \le \sqrt{a^2 + b^2} \le \sqrt{2} \cdot \max(|a|, |b|). \qquad (2.4)$$

Therefore, the noises computed by both formulae cannot be too far from each other, the ratio between both lying in $[1, \sqrt{2}]$. Moreover, $\max(|a|, |b|) = \sqrt{a^2 + b^2}$ if and only if $a = 0$ or $b = 0$ and $\sqrt{a^2 + b^2} = \sqrt{2} \cdot \max(|a|, |b|)$ if and only if $|a| = |b|$.
### 2.2.2. Fourier precision

In theory, all Fourier coefficients must be computed in order to determine the noise produced by a one-tracked-tire. However, it is sufficient to compute the $c_n$ coefficients only for $n$ bounded in terms of $N$. A regular tire composed of $N$ pitches has a peak at the frequency of $N$ as well as at multiples of $N$, so called harmonics. Humans are able to hear only frequencies between 20 Hz and 20 kHz, so only the first harmonics of the tire signal are in the main human audible frequency range, and at most the second harmonics come close to the 20 kHz frequency border. Furthermore, the amplitude of higher frequencies of a regular signal decreases quickly, so there is no need to compute more than 1.5–3.0 times $N$ coefficients, around 200 ($=n$) in the case of a realistic tire pattern with $N = 60$ pitches.

Moreover, because of the very specific profile functions we deal with, it is an easy consequence of (2.3) that, for every $n \ge 1$,

$$|c_n(f)| \le \frac{Nh}{n\pi},$$

where $h > 0$ is the pitch height. In particular, if $N$ is fixed, then $|c_n|$ (as well as $|a_n|$ and $|b_n|$) is an $O(\frac{1}{n})$ and thus is small for large $n$.

### 2.2.3. Units and integer pitch lengths

Recall that the set of different pitch types $P = \{1, \dots, r\}$ is finite and $\bar{l}_1 < \dots < \bar{l}_r$ are the different pitch lengths. Recall that the ratio of any two pitch lengths is supposed to be rational and hence we can assume the existence of a largest length (called unit) dividing each pitch length into an integral number of units. Formally, let $\bar{l}_i = \frac{p_i}{q_i} \cdot \bar{l}_r$ with $p_i, q_i \in \mathbb{N}$ and $\gcd(p_i, q_i) = 1$ for all $1 \le i \le r$ (note that $p_r = q_r = 1$). We define the unit length by $u := \frac{\bar{l}_r}{\text{lcm}(q_1, \dots, q_r)}$, where $\text{lcm}(q_1, \dots, q_r)$ is the least common multiple of the integers $q_1, \dots, q_r$. From now on, we study tires with reduced pitch lengths $l_1 < \dots < l_r$, where $l_i := \frac{\bar{l}_i}{u} \in \mathbb{N}$ for all $i \in \{1, \dots, r\}$. We call $l_{\min} := N \cdot l_1 \in \mathbb{N}$ and $l_{\max} := N \cdot l_r \in \mathbb{N}$ the minimal and maximal tire-length, respectively. From the industrial perspective, the sequence of pitch lengths is given as a sequence of ratios with respect to the smallest pitch length. Most of the results presented in Section 4 concern ratios $\{1.0, 1.25, 1.5\}$ reduced to lengths $\{4, 5, 6\}$ in the MILP (here $u = 0.25$). Notice also that we do not study tires of a fixed length $T$ but tires with lengths varying from $l_{\min}$ to $l_{\max}$, while $N$ is fixed.

## 3. OPTIMIZATION MODELS

In the previous section, we described the tire noise optimization problem and the corresponding model for the approximated noise (TNOP-AP). In [2], we presented a preliminary version of a linear optimization model for the TNOP-AP. In Section 3.1, we propose a new approach and first highlight the link with scheduling, graph and mathematical programming. In Section 3.2, we correct and enhance the linear optimization model from [2]. In Section 3.3, we introduce a new method, using Branch-and-Cut, to solve the Tire Noise Optimization Problem for the real noise, that we call TNOP-EX.

### 3.1. Graph representation

In order to illustrate the model, we consider here tires of length $T = l_{\max}$. From Section 3.2 on, we let the tire length vary and solve the TNOP-AP for each tire size from $l_{\min}$ to $l_{\max}$. Recall that a tire track is a sequence of consecutive pitches of different sizes assumed to be integers. Then, on each position, a pitch can or cannot start. A sequence of pitches can be seen as a scheduling problem on a single machine where the pitches are the jobs and the criteria to minimize depends on the beginning of each pitch. This problem also can be modeled as a graph problem. Let $T$ denote the length of a tire expressed as an integral number of the above units and let $G = (V, A)$ be the oriented graph defined as follows:
<figure><img src="image_3.png" /><figcaption>FIGURE 2. Graph model for a tire of length 6.</figcaption></figure>

- $V = \{v_p^i | \forall i \in \{1, \dots, T\}; \forall p \in \{1, \dots, r\} \} \cup \{s, t\}$ where $i$ denotes a position on the tire and $p$ denotes a pitch type,

- $A = A_s \cup A_{\text{int}} \cup A_t$, where

$$ 
\begin{align*}
A_s &= \{(s, v_p^1) | p \in \{1, \dots, r\}\}, \\
A_{\text{int}} &= \{(v_p^i, v_{p'}^{i+\text{length}(p)}) | \quad \forall i \in \{1, \dots, T\}; \quad \forall p, p' \in \{1, \dots, r\}, \\
& \phantom{=} i + \text{length}(p) \le T\}, \\
A_t &= \{(v_p^{T-\text{length}(p)}, t) | p \in \{1, \dots, r\}\}.
\end{align*}
$$

An example for a tire of length 6 built of pitches of lengths 2, 3 and 4 is presented on Figure 2 (solid, dashed and dotted arrows, respectively). To each arc a starting at $v_p^i$ in A and each $k \in \mathbb{N}$, we associate a weight pair $(w_a^k(\mathbf{a}), w_b^k(\mathbf{a}))$, corresponding to the $a_k$- and $b_k$-contributions to the noise produced by a pitch of type $p$ starting at position $i$. Actually, $w_a^k(\mathbf{a}) = A_{k,0,i,p}$ and $w_b^k(\mathbf{a}) = B_{k,0,i,p}$, where $A_{k,0,i,p}$ (resp. $B_{k,0,i,p}$) denotes the contribution to the $k$th Fourier coefficient $a_k$ (resp. $b_k$) of the function having only one pitch of type $p$ starting on the $i$th unit (see Sect. 3.2 for the formal definitions).

Let P be the set of all paths of N pitches starting at $s$ and ending at $t$. Then, the TNOP-AP consists in finding a path $p \in P$ such that the maximum noise $\max_k\{|\sum_{\mathbf{a} \in P} w_a^k(\mathbf{a})|, |\sum_{\mathbf{a} \in P} w_b^k(\mathbf{a})|\}$ is minimal. In the example of Figure 2, the paths of p are highlighted by bold arrows. For

- $N=3: P = \{((s, v_1^1), (v_1^1, v_1^3), (v_1^3, v_1^5), (v_1^5, t))\}$

- $N=2: P = \{((s, v_1^1), (v_1^1, v_3^1), (v_3^1, t)), ((s, v_2^1), (v_2^1, v_2^4), (v_2^4, t)), ((s, v_3^1), (v_3^1, v_5^1), (v_5^1, t))\}$

We propose in the next section a mixed integer linear program based on the path problem defined above.

## 3.2. Mixed Integer Linear Program (MILP) solving TNOP-AP

We propose a MILP to solve the problem for a fixed tire length between $l_{\text{min}}$ and $l_{\text{max}}$, considering hence some empty unit slots at the end of the sequence. Recall that the noise we compute differs from the real noise by a factor at most $\sqrt{2}$, as described in Section 2.2.1.

We use the following notations which should be clearer than in [2].

- N is the number of pitches,
- $P = \{1, 2, \dots, r\}$ is the set of pitch types and $l_1 < l_2 < \dots < l_r$ are the reduced pitch lengths, supposed to be integers,

- $L = \{0, \dots, l_{\max} - l_{\min}\}$ denotes the set of possible numbers of empty unit slots at the end, where $l_{\max}$ and $l_{\min}$ denote respectively the maximal and minimal tire lengths, and $|L|$ is then the number of possible tire lengths,

- $L_p^j = \{1, \dots, l_{\max} - l_p - j\}$ denotes the set of positions at which a pitch of type $p \in P$ can start on a sequence with $j$ empty unit slots at the end,

- $T_j = l_{\max} - j$ denotes the length of a tire with $j$ empty unit slots at the end,

- $K = \{1, \dots, 3N\}$ where $3N$ denotes the Fourier coefficient precision (see Sect. 2.2.2),

- $A_{k,j,i,p}$ denotes the contribution to the $k$th Fourier coefficient $a_k$ of the function having only one pitch of type $p$ starting on the $i$th unit and such that the $j$ last units do not bear any pitch. Formally, they are computed as follows:

$$A_{0,j,i,p} = \frac{1}{T_j} \cdot h \cdot (1-q)l_p = \frac{(1-q) \cdot h \cdot l_p}{(l_{\max} - j)}$$

and for any $k \ge 1$,

$$A_{k,j,i,p} = \frac{h}{k\pi} \cdot \left( \sin \left( \frac{2k((i-1) + (1-q)l_p)\pi}{l_{\max} - j} \right) - \sin \left( \frac{2k(i-1)\pi}{l_{\max} - j} \right) \right).$$

These identities can be deduced from (2.1) described in Section 2.2.1.

- $B_{k,j,i,p}$ denotes the contribution to the Fourier coefficient $b_k$ under the same conditions as for $A_{k,j,i,p}$, and they are computed as follows:

$$B_{k,j,i,p} = -\frac{h}{k\pi} \cdot \left( \cos \left( \frac{2k((i-1) + (1-q)l_p)\pi}{l_{\max} - j} \right) - \cos \left( \frac{2k(i-1)\pi}{l_{\max} - j} \right) \right).$$

These identities can be deduced from (2.2) described in Section 2.2.1.

- $\minOcc_p$: the minimum number of pitches of type $p$ in a sequence;

- $\maxOcc_p$: the maximum number of pitches of type $p$ in a sequence;

- $\max_p$: the maximal length of a sub-sequence composed of pitches of a same type $p$.

Let us now introduce the binary variables

- $x_i^p \in \{0, 1\}$:

$$x_i^p = \begin{cases} 1 & \text{if a pitch of type } p \text{ starts at position } i \\ 0 & \text{otherwise} \end{cases}$$

for all $p \in P$ and $i \in L_p^0$

and the continuous variables

- $z^j \in \mathbb{R}_+$: the noise produced by a pitch sequence with $j$ empty units at the end, for all $j \in L$,

- $za_k^j \in \mathbb{R}$: the value of the $k$-th Fourier coefficient $a_k$ of a given pitch sequence with $j$ empty units at the end, for all $j \in L$ and $k \in K$,

- $zb_k^j \in \mathbb{R}$: the value of the $k$-th Fourier coefficient $b_k$ of a given pitch sequence with $j$ empty units at the end, for all $j \in L$ and $k \in K$.

Let us fix the number of empty units $j \in L$ at the end of the sequence and hence consider tires of length $T_j$. The MILP below solves the TNOP-AP for this fixed tire length.
The objective function $z^j$ represents actually the maximum of $|za_k^j|$ and $|zb_k^j|$ for all $k \in K$. Note that thanks to additivity of integration on intervals, the Fourier coefficients $za_k^j$ and $zb_k^j$ are the sums of the contribution of each pitch in the sequence.

Notice that, in order to solve the TNOP-AP, the MILP has to be solved for all $j \in L$.

Mixed Integer Linear Program (P):

$$ \min z^j \\ za_k^j \le z^j \quad \forall k \in K, \qquad (3.1) $$

$$ -za_k^j \le z^j \quad \forall k \in K, \qquad (3.2) $$

$$ zb_k^j \le z^j \quad \forall k \in K, \qquad (3.3) $$

$$ -zb_k^j \le z^j \quad \forall k \in K, \qquad (3.4) $$

$$ za_k^j = \sum_{p \in P} \sum_{i \in L_p^j} A_{k,j,i,p} x_i^p \quad \forall k \in K, \qquad (3.5) $$

$$ zb_k^j = \sum_{p \in P} \sum_{i \in L_p^j} B_{k,j,i,p} x_i^p \quad \forall k \in K, \qquad (3.6) $$

$$ \sum_{p \in P} x_i^p \le 1 \quad \forall i \in \{1, \dots, T_j\}, \qquad (3.7) $$

$$ \sum_{p \in P} \sum_{i \in L_p^j} l_p x_i^p = T_j, \qquad (3.8) $$

$$ \sum_{\substack{p=1 \\ i-l_p>0}}^{r} x_i^p = \sum_{p=1}^{r} x_i^p, \quad \forall i \in \{1, \dots, T_j\}, \qquad (3.9) $$

$$ \sum_{p \in P} \sum_{i \in L_p^j} x_i^p = N, \qquad (3.10) $$

$$ x_i^p \in \{0, 1\} \quad \forall p \in P, \forall i \in \{1, \dots, T_j - l_p + 1\}, \qquad (3.11) $$

$$ z^j \ge 0 \qquad (3.12) $$

$$ za_k^j, zb_k^j \in \mathbb{R}, \quad \forall k \in K \qquad (3.13) $$

The objective function and inequalities (3.1)–(3.4) ensure that $z^j$ is a maximum of the absolute value of $za_k^j$ and $zb_k^j$ for all $k \in K$. Equalities (3.5) and (3.6) compute the noise contribution of the sequence found by the MILP. The inequalities (3.7) ensures that at most one pitch can start at each position. The equality (3.8) ensures that the non-empty part is completely filled with pitches, that is, we take into account all possible combinations having a fixed tire length. The equalities (3.9) prevent a pitch from starting inside another pitch, i.e. there is no overlapping. They replace and simplify the former corresponding inequalities from [2]. The equality (3.10) ensures that exactly $N$ pitches compose the tire. Note that it had been forgotten in [2] as well as (3.13).

The above (P) is a model for the basic TNOP-AP problem. We can however easily add some more constraints such as those mentioned in Section 2.1:

$$ \sum_{i \in L_p^j} x_i^p \ge \min \mathrm{Occ}_p \quad \forall p \in P, \qquad (3.14) $$

$$ \sum_{i \in L_p^j} x_i^p \le \max \mathrm{Occ}_p \quad \forall p \in P, \qquad (3.15) $$
$$ \sum_{k=0}^{\max_p - 1} x_{i+kl_p}^p \le \max_p \quad \forall p \in P, \forall i \in \{1, \dots, T_j - l_p + 1\}, \qquad (3.16) $$

$$ x_i^1 + x_{i+l_1}^r \le 1, \quad \forall i \in \{1, \dots, T_j - l_r - l_1 + 1\}, \qquad (3.17) $$

$$ x_i^r + x_{i+l_r}^1 \le 1, \quad \forall i \in \{1, \dots, T_j - l_r - l_1 + 1\}, \qquad (3.18) $$

where

- inequalities (3.14) and (3.15) correspond to the constraint ctMinMaxOcc,

- inequalities (3.16) express ctMaxSeq,

- inequalities (3.17) and (3.18) translate ctIncompatibility for the incompatibility of the smallest and the largest pitch types.

### 3.3. Exact algorithm to solve TNOP-EX

Recall that the MILP (P) presented in the previous section allows to solve TNOP-AP. In this section, we propose an algorithm based on (P) allowing to find the optimal solution of the TNOP-EX regarding the real noise (see Sect. 2.2.1).

From the MILP (P) we use the Branch-and-Cut framework of ILP solvers to ensure that the solution is optimal for the TNOP-EX. Let $z_{ub}$ be an upper bound for the approximated noise. We initialize $z_{ub}$ by the heuristic algorithm described in [3]. During the execution of the Branch-and-Bound algorithm associated with the solving of (P), for each integral feasible solution $\tilde{x}$ found by the Branch-and-Bound, the real noise is computed and denoted by $noise_{c_n}(\tilde{x})$. If $noise_{c_n}(\tilde{x}) < z_{ub}$ then the solution found is better, so that we improve the upper bound by setting $z_{ub} = noise_{c_n}(\tilde{x})$. As $\tilde{x}$ is momentarily the best solution found, we save it in $x^*$ and we add the inequalities

$$ z^j \le z_{ub} \qquad (3.19) $$

and

$$ \sum_{p \in P} \sum_{i \in \{1, \dots, T_j\}} \tilde{x}_i^p x_i^p \le N - 1 \qquad (3.20) $$

to the current MILP. We then continue the Branch-and-Bound algorithm. The inequality (3.19) updates the upper bound of $z^j$. Adding the inequality (3.20) makes the solution $\tilde{x}$ unfeasible for the MILP.

This procedure can be easily done using specific callback in the ILP solver (e.g. lazy constraint callback for CPLEX). The idea of inequalities (3.19) is similar to the no-good cut inequalities but we also cut valid solutions in order to converge to the best solution (see e.g. [7]).

The algorithm stops when no solution exists and the best solution is $x^*$ with a noise $noise_{c_n}(x^*)$. As we consider the Branch-and-Bound on the MILP (P) allowing to solve TNOP-AP, the linear relaxation still provides a valid lower bound, and thus all solutions need not be enumerated.

As we saw in Section 2.2.1, the noise is invariant under circular permutations. Therefore, as $minOcc_p > 0$ for each $p \in P$, we can always assume that the first pitch is of type $p = 1$. Hence, we could add the constraint

$$ x_1^1 = 1 \qquad (3.21) $$

in order to break the symmetries and thus reduce the space of feasible solutions. It turns out that in practice the computational time is not shortened.
<table><caption>TABLE 1. Experimental results – exact solutions.</caption><thead><tr><th>Instance</th><th>Noise GA =<br>Noise MILP</th><th>Pitch sequence<br>GA</th><th>Time<br>GA</th><th>Pitch sequence<br>MILP with B&C</th><th>Time MILP<br>with B&C</th></tr></thead><tbody><tr><td>(10,1,8)</td><td>9.019</td><td>1311323331</td><td>5</td><td>1323331131</td><td>7</td></tr><tr><td>(10,2,6)</td><td>9.247</td><td>1231123333</td><td>3</td><td>1233331231</td><td>6</td></tr><tr><td>(10,2,4)</td><td>9.268</td><td>2213111333</td><td>3</td><td>1333221311</td><td>3</td></tr><tr><td>(10,3,4)</td><td>9.368</td><td>1233321123</td><td>3</td><td>1231233321</td><td>2</td></tr><tr><td>(15,1,13)</td><td>7.027</td><td>311113311133312</td><td>6</td><td>111333123111133</td><td>25:27</td></tr><tr><td>(15,2,11)</td><td>7.236</td><td>112131223333111</td><td>5</td><td>131223333111112</td><td>27:30</td></tr><tr><td>(15,4,7)</td><td>7.261</td><td>111222123333111</td><td>5</td><td>122212333311111</td><td>13:13</td></tr><tr><td>(15,4,6)</td><td>7.439</td><td>332112331112213</td><td>4</td><td>112331112213332</td><td>10:25</td></tr><tr><td>(20,6,8)</td><td>6.444</td><td>11123332312321132112</td><td>26</td><td>12321132112111233323</td><td>153:53:39</td></tr><tr><td>(60,1,58)</td><td>4.131 (noise GA)</td><td>21231123311232313111<br>21112311231111131332<br>13323323333331212131</td><td>02:21:34</td><td>-</td><td>-</td></tr><tr><td>(60,10,40)</td><td>3.899 (noise GA)</td><td>12311331212133312113<br>21131112223333311111<br>23311231333113331121</td><td>03:35:87</td><td>-</td><td>-</td></tr></tbody></table>

## 4. IMPLEMENTATION AND EXPERIMENTAL RESULTS

In order to compare experimental results produced by the different methods, the tests have been carried out using the same parameters as for the case of Genetic Algorithms (GA), studied in [1]:

- There are three different pitch types of length ratios 1, 1.25 and 1.5, respectively.

- The height of a pitch is $h = 100$.

- The groove is $q = 0.1$.

Notice that these parameters correspond to realistic values, the same pitch types have been studied in [6], for the Goodyear patent described in [12].

To solve the TNOP-EX with GA [1], JAVA is used for the implementation. The main parameters of the GA are: a maximal population size of 1500 and a crossover probability of 0.3. The crossover is performed randomly. The mutation probability is 0.15 and the mutation is also random. Roulette and Ranking selection has been used, with a selection pressure of 0.4. For performance reasons, the coding of the genes has been realized as final Byte Array instead of a binary encoding. The value semantics of the genes save memory usage and enable the use of the efficient `==` operator. A chromosome then is composed of genes.

To solve the TNOP-AP with the MILP ($P$) we used the CPLEX 12.7.1 solver. The iterative algorithm solving ($P$) for each tire length $T_j$ was implemented in JAVA. The exact algorithm to solve TNOP-EX presented in Section 3.3 was implemented in JAVA using CPLEX and the lazy constraint callback. The numerical tests have been carried out on an Intel Core i5 of 3.4 GHz in a Linux environment.

In Tables 1 and 2, an instance is considered as a triple $(N, \min Occ_p, \max Occ_p)$. According to the tests made with heuristic methods, we do not take into account the constraints (3.16), (3.17) and (3.18). The computational times are given in `sec`, `min:sec` and `hrs:min:sec`.

Table 1 presents some experimental results for the heuristic method (GA) and the MILP with B&C, the latter computing the exact noise. We can remark that the sequences found coincide up to circular permutation and hence we can also confirm that the solutions found by the heuristic method are also exact. The computational time remains small for GA but increases in a significant way for the MILP with B&C. Indeed, for 10 pitches, the computation times are very close for GA and B&C. For 15 pitches the computation time for B&C ranges from 10 to 28 minutes which still remains acceptable, but from 20 pitches on, it increases considerably. Notice
<table><caption>TABLE 2. Experimental results – approximated solutions.</caption><thead><tr><th>Instance</th><th>Pitch sequence</th><th>Time</th><th>Noise MILP</th><th>Real Noise</th><th>Optimal Noise</th><th>Gap (%)</th></tr></thead><tbody><tr><td>(10,1,8)</td><td>1121133231</td><td>4</td><td>7.100</td><td>9.540</td><td>9.019</td><td>5.5</td></tr><tr><td>(10,2,6)</td><td>1121133231</td><td>3</td><td>7.100</td><td>9.540</td><td>9.247</td><td>3</td></tr><tr><td>(10,2,4)</td><td>1223331113</td><td>1</td><td>7.177</td><td>9.638</td><td>9.268</td><td>3.8</td></tr><tr><td>(10,3,4)</td><td>1332311212</td><td>1</td><td>7.397</td><td>9.921</td><td>9.367</td><td>5.9</td></tr><tr><td>(15,1,13)</td><td>223333121111131</td><td>1:12</td><td>5.613</td><td>7.852</td><td>7.027</td><td>10.5</td></tr><tr><td>(15,2,11)</td><td>13122333111112</td><td>1:11</td><td>5.613</td><td>7.852</td><td>7.236</td><td>7</td></tr><tr><td>(15,4,7)</td><td>123333131222111</td><td>52</td><td>5.949</td><td>8.362</td><td>7.260</td><td>13.2</td></tr><tr><td>(15,4,6)</td><td>123333131222111</td><td>37</td><td>5.949</td><td>8.362</td><td>7.439</td><td>11</td></tr><tr><td>(20,6,8)</td><td>2232333311322122111</td><td>24:13</td><td>5.094</td><td>6.931</td><td>6.444</td><td>7</td></tr></tbody></table>

that the genetic algorithm cannot ensure to find the optimal solution, e.g. the noise found for the instance (60, 10, 40) is 3.899 and the one for the instance (60, 1, 58) is 4.132, whereas the noise of the latter should be smaller since its space of feasible solutions is larger than that of the former.

Table 2 shows the results found for the computation of the approximated noise, based on the same instances. The presented values are the following: *noise MILP* is the approximated noise, *real noise* is the exact noise of the sequence found by the MILP and the *optimal noise* is the noise of the optimal sequence, presented in Table 1. The gap is computed between the *real noise* and the *optimal noise*, with respect to the latter. Notice that, for each of the sequences found, the real noise is an upper bound for the optimal noise. We can also remark that, from 15 pitches on, the solution found is not optimal but the computational time is significantly shorter than that of the exact algorithm (MILP with B&C) and the gap might be considered as reasonable. Moreover, although the theoretical gap between the real and the optimal noises is bounded by 42%, we notice that for our instances the gap computed is much lower, ranging from 3 to 13.2%.

## 5. CONCLUSION

We had started in [2] with a new approach using a MILP for the Tire Noise Optimization Problem. Indeed, the tire shape has to satisfy several constraints a priori allowing for linear programming. However, the objective function depends a very non-linear way on the data. In [2], we proposed an approximated tire noise model allowing for its linearization. The approximated noise is guaranteed to differ from the optimal noise by a ratio of at most 42%. In the present paper, we take some more constraints into account and provide an exact method to minimize the noise thanks to a Branch&Cut algorithm. We have tested all proposed algorithms and compared their performances. The MILP approach always finds a solution in reasonable time, up to a ratio of 14%, which is much lower than the theoretical 42% one. The first results on Branch&Cut algorithm show that our algorithm can provide an exact solution for at most 20 pitches.

Concerning the research objectives of our study, as stated in the Introduction, we could on one hand show, that the highly nonlinear problem of tire noise optimization can be linearized and handled by a MILP. We showed how to find the optimal pitch sequence for the exact noise. On the other hand, the implementation of the model turns out not to be efficient enough to solve complex real-world problems yet. We expect that in future work, it will be improved and experiments on highly parallel hardware will solve the efficiency problem.

As an extension, it would be interesting to enhance the optimization part to be able to compute the noise for realistic instances, e.g. by developing a dedicated algorithm or by adding valid inequalities to strengthen the linear relaxation. This opens a new research field on the tire noise problem.
*Acknowledgements.* We are very grateful to the anonymous referees and the editors for their comments and suggestions which helped improving our paper.

## REFERENCES

[1] M. Becker, Genetic algorithms for noise reduction in tire design. In: *IEEE International Conference on Systems, Man and Cybernetics, 2006 (SMC'06)*, Vol. 6. IEEE (2006) 5304–5308.

[2] M. Becker, N. Ginoux, S. Martin and Zs. Róka, Optimization of tire noise by solving an integer linear program (ILP). In: *2016 IEEE International Conference on Systems, Man, and Cybernetics (SMC)*. IEEE (2016) 001591–001596.

[3] M. Becker, S. Jaschke and H. Szczerbicka, Tread profile optimization for tires with multiple pitch tracks. In: *INES'09 Proceedings of the IEEE 13th International Conference on Intelligent Engineering Systems* (2009).

[4] X. Chen, L. Chen, Y. Chen and W. Xiao. Adaptive immune genetic algorithm for tire tread pattern pitch parameters optimization. In: *Third International Symposium on Intelligent Information Technology Application, 2009 (IITA 2009)*, Vol. 1. IEEE (2009) 52–55.

[5] J. Chiu and F. Tu, Application of a pattern recognition technique to the prediction of tire noise. *J. Sound Vibration* **350** (2015) 30–40.

[6] J.T. Chiu, W.C. Weng and C.F. Hung, Optimization of pitch sequencing for pneumatic tire by tabu search method. *Jpn. J. Ind. Appl. Math.* **19** (2002) 399–414.

[7] M. Fischetti, I. Ljubic, M. Monaci and M. Sinnl, Intersection Cuts for Bilevel Optimization. In: *Integer Programming and Combinatorial Optimization: Proceedings of 18th International Conference, IPCO 2016, Liège, Belgium, June 1–3, 2016* (2016) 77–88.

[8] A. Ghoniem and H.D. Sherali, Defeating symmetry in combinatorial optimization via objective perturbations and hierarchical constraints. *IIE Trans.* **43** (2011) 575–588.

[9] K. Hoffmeister and J. Bernard, Tread pitch arrangement optimization through the use of a genetic algorithm. *Tire Sci. Technol.* **26** (1998) 2–22.

[10] E. Kim, S. Hwang and S. Lee, Image-based approach to optimize the tyre pitch sequence for a reduction in the air-pumping noise based on a genetic algorithm. *Proc. Inst. Mech. Eng. D: J. Automob. Eng.* **226** (2012) 1171–1184.

[11] S. Kim, W. Jeong, Y. Park and S. Lee, Prediction method for tire air-pumping noise using a hybrid technique. *J. Acoust. Soc. Am.* **119** (2006) 3799–3812.

[12] S.P. Landers, Spreading noise generated by load supporting elements. *United State Patent Document Number 4327792*. The Goodyear Tire and Rubber Company (1982) 5.

[13] X. Li, B. Guo and H. Yang, *Application of Tread Patterns Noise-Reduction Based on Fuzzy Genetic Algorithm*. Springer Berlin Heidelberg, Berlin, Heidelberg (2009) 1141–1148.

[14] Y. Nakajima and A. Abe, Application of genetic algorithms for optimization of tire pitch sequences. *Jpn. J. Ind. App. Math.* **17** (2000) 403–426.

[15] H.D. Sherali and J.C. Smith, Improving discrete model representations via symmetry considerations. *Manage. Sci.* **47** (2001) 1396.

[16] T.A. Williams, Tire tread pattern noise reduction through the application of pitch sequencing. In: *SAE Technical Paper*. SAE International (1995) 05.

Subscribe to Open (S2O)
A fair and sustainable open access model

This journal is currently published in open access under a **Subscribe-to-Open model (S2O)**. S2O is a transformative model that aims to move subscription journals to open access. Open access is the free, immediate, online availability of research articles combined with the rights to use these articles fully in the digital environment. We are thankful to our subscribers and sponsors for making it possible to publish this journal in open access, free of charge for authors.

**Please help to maintain this journal in open access!**

Check that your library subscribes to the journal, or make a personal donation to the S2O programme, by contacting
**subscribers@edpsciences.org**

More information, including a list of sponsors and a financial transparency report, available at: [https://www.edpsciences.org/en/maths-s2o-programme](https://www.edpsciences.org/en/maths-s2o-programme)