Biased Random-Key Genetic Algorithms for the Minimum Broadcast Time Problem
Aluno: Alfredo Lima Moura Silva Orientador: Prof. Dr. Rian Gabriel Santos Pinheiro
Masters_Thesis___Alfredo_4 (1).pdf
Documento PDF (1.2MB)
Documento PDF (1.2MB)
Master’s Thesis
Biased Random-Key Genetic Algorithms for the
Minimum Broadcast Time Problem
Alfredo Lima Moura Silva
alfredolms@ic.ufal.br
Advisers:
Dr. Rian Gabriel Santos Pinheiro
Dr. Bruno Costa e Silva Nogueira
Maceió
November 12, 2021
Alfredo Lima Moura Silva
Biased Random-Key Genetic Algorithms for the
Minimum Broadcast Time Problem
A thesis submitted by Alfredo Lima Moura Silva in partial fulfillment of the requirements for the degree of
Master of Science in Informatics at the Federal University of Alagoas, Computing Institute.
Advisers:
Dr. Rian Gabriel Santos Pinheiro
Dr. Bruno Costa e Silva Nogueira
Maceió
November 12, 2021
A thesis submitted by Alfredo Lima Moura Silva in partial fulfillment of the requirements for
the degree of Master of Science in Informatics at the Federal University of Alagoas, Computing
Institute, approved by the examination committee which signs bellow.
Dr. Rian Gabriel Santos Pinheiro - Adviser
Computing Institute
Federal University of Alagoas
Dr. Bruno Costa e Silva Nogueira - Adviser
Computing Institute
Federal University of Alagoas
Dr. André Luiz Lins de Aquino - Examiner
Computing Institute
Federal University of Alagoas
Dr. Fábio Protti - Examiner
Computing Institute
Fluminense Federal University
Maceió
November 12, 2021
Catalogação na Fonte
Universidade Federal de Alagoas
Biblioteca Central
Divisão de Tratamento Técnico
Bibliotecário: Marcelino de Carvalho Freitas Neto – CRB-4 - 1767
S586b
Silva, Alfredo Lima Moura.
Biased random-key genetic algorithms for the minimum broadcast
time problem / Alfredo Lima Moura Silva. – 2021.
61 f. : il.
Orientador: Rian Gabriel Santos Pinheiro.
Coorientador: Bruno Costa e Silva Nogueira.
Dissertação (mestrado em Informática) - Universidade Federal de
Alagoas. Instituto de Computação. Maceió, 2021.
Bibliografia: f. 53-58.
Apêndices: f. 59-61.
1. Otimização combinatória. 2. Tempo mínimo de transmissão. 3.
Metaheurística. 4. Chaves aleatórias enviesadas (Algoritmos genéticos). I.
Título.
CDU: 004.421
UNIVERSIDADE FEDERAL DE ALAGOAS/UFAL
Programa de Pós-Graduação em Informática – PPGI
Instituto de Computação/UFAL
Campus A. C. Simões BR 104-Norte Km 14 BL 12 Tabuleiro do Martins
Maceió/AL - Brasil CEP: 57.072-970 | Telefone: (082) 3214-1401
Folha de Aprovação
ALFREDO LIMA MOURA SILVA
BIASED RANDOM-KEY GENETIC ALGORITHMS FOR THE MINIMUM BROADCAST
TIME PROBLEM
Dissertação submetida ao corpo docente do Programa
de Pós-Graduação em Informática da Universidade
Federal de Alagoas e aprovada em 12 de novembro de
2021.
Banca Examinadora:
________________________________________
Prof. Dr. RIAN GABRIEL SANTOS PINHEIRO
UFAL – Instituto de Computação
Orientador
__________________________________________
Prof. Dr. BRUNO COSTA E SILVA NOGUEIRA
UFAL – Instituto de Computação
Coorientador
________________________________________
Prof. Dr. ANDRE LUIZ LINS DE AQUINO
UFAL – Instituto de Computação
Examinador Interno
________________________________________
Prof. Dr. FÁBIO PROTTI
UFF- Universidade Federal Fluminense
Examinador Externo
Acknowledgement
I thank God for all the gifts and graces that I had received.
I would like to special acknowledge my advisors Rian Pinheiro and Bruno Nogueira. My
mother Neide, stepfather Helder Fernando and grandmother Maria José (in memoriam) for all
the support.
I thank for the new friends I made during this time. To Professors who are members of the
examining board. Prof. Dr. Fábio Protti and Prof. Dr. André Luiz for their time dedicated to
reading and contributing to making this work better. To the Federal University of Alagoas (Ufal),
OptLab, and EDGE - Innovation Center for every opportunity, they were essential pieces in my
academic background.
The power of compound interest the most powerful force in the universe.
– Einstein, A.
iii
Resumo
O problema T EMPO M ÍNIMO DE T RANSMISSÃO (TMT) é um problema conhecido de disseminação de dados, com o objetivo é encontrar um esquema de transmissão que minimize o número
de passos necessários para executar a operação de transmissão.
O T EMPO M ÍNIMO DE T RANSMISSÃO COM P ESO (TMTP) é uma generalização do TMT, de
forma que cada operação tem um custo. Ambos os problemas têm diversas aplicações em
sistemas distribuídos, por exemplo, o processo de atualização de dispositivos em uma rede
ponto-a-ponto.
Este trabalho propõe Algoritmos Genéticos de Chave-Aleatória Enviesados (AGCAE) para
o TMT e o TMTP. Um algoritmo híbrido (AGCAE + Programação Linear Inteira) para o TMT.
Algoritmos para calcular um limite inferior para o TMT e o TMTP. Uma abordagem de refinamento, e métodos para criar instâncias com ótimos conhecidos para TMT e TMTP. Além disso,
um método para diminuir os grafos para o TMTP.
Foi realizado experimentos com o AGCAE em instâncias comumente utilizadas na literatura
e também em instâncias sintéticas massivas (até 1000 vértices), o que permite cobrir muitas
possibilidades de topologias reais da indústria.
A proposta comparou métodos exatos e heurísticas do estado-da-arte dos problemas. Os
algoritmos superaram as heurísticas mais conhecidas para TMT e TMTP.
Os experimentos demonstraram que estes algoritmos são uma boa alternativa quando métodos exatos não podem ser aplicados. Para todas as instâncias do TMT com valor ótimo
conhecido, os algoritmos alcançaram o valor ótimo ou no máximo uma unidade para encontrar
o tempo mínimo de transmissão. Para todas as instâncias do TMTP, as abordagens alcançaram
ou melhoraram os resultados da literatura.
Keywords: Otimização combinatória, Tempo Mínimo de Transmissão, Metaheurísticas, Algoritmos Genéticos de Chave Aleatória Enviesados.
iv
Abstract
The M INIMUM B ROADCAST T IME (MBT) is a well-known data dissemination problem whose goal
is to find a broadcast scheme that minimizes the number of steps needed to execute the broadcast operation. The W EIGHTED M INIMUM B ROADCAST T IME (WMBT) is a generalization of the
MBT, such that each operation has a cost. Both problems have many applications in distributed
systems, e.g., the devices update process in a peer-to-peer network.
This work proposes Biased Random-Key Genetic Algorithms (BRKGA) for the MBT and
WMBT. A hybrid algorithm (BRKGA + Integer Linear Programming) for the MBT. Algorithms to
calculate a lower bound for the MBT and WMBT. A refinement approach and methods to create
instances with known optima for the MBT and WMBT. Moreover, reducing rules for the WMBT.
We carry out experiments with our BRKGA on instances commonly used in the literature
and also on massive synthetic instances (up to 1000 vertices), allowing us to cover many possibilities of real industry topologies. Our proposal compared state-of-the-art exact methods and
heuristics. Our algorithms outperformed the best-known heuristics for the MBT and WMBT. The
experiments demonstrated they are a very good alternative when exact methods cannot be applied. For all instances for the MBT with known optima value, our approaches either attained the
optimal value or missed it by at most one broadcast step. For all instances for the WMBT, our
approaches attained or improved the results of literature.
Keywords: Combinatorial Optimization, Minimum Broadcast Time, Metaheuristics, Biased
Random-Key Genetic Algorithms.
v
Contents
Figure List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Table List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Algorithm List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
viii
ix
x
1
Introduction
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Message-passing systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.1 Exact algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.2 Approximate algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.3 Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.4 Matheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
2
3
5
5
5
6
8
8
9
2
Minimum Broadcast Time
2.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Algorithmic approaches for the MBT . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Synthetic instances for the MBT . . . . . . . . . . . . . . . . . . . . . .
2.2.2 Lower bound algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.3 BRKGA decoders for the MBT . . . . . . . . . . . . . . . . . . . . . . .
2.2.4 Proposed matheuristic . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Computacional results of the MBT . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.2 Parameter settings and experimental protocol . . . . . . . . . . . . . . .
2.3.3 Experiments on Harary Graphs . . . . . . . . . . . . . . . . . . . . . . .
2.3.4 Experiments on others instances from literature . . . . . . . . . . . . . .
2.3.5 Experiments on Small-World and synthetic instances . . . . . . . . . . .
2.3.6 Experiments with SCHA decoding and the proposed matheuristic . . . . .
11
12
13
13
14
16
19
23
23
24
25
27
27
30
3
Weighted Minimum Broadcast Time
3.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Algorithmic approaches for the WMBT . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Mathematical models for WMBT . . . . . . . . . . . . . . . . . . . . . .
3.2.2 Lower bound algorithm for the WMBT . . . . . . . . . . . . . . . . . . .
3.2.3 Exact greedy algorithm for the WMBT for forest . . . . . . . . . . . . . .
3.2.4 Greedy algorithm for the WMBT for general instances . . . . . . . . . . .
3.2.5 Reducing rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.6 BRKGA for the WMBT . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
35
36
36
39
39
40
40
43
vi
CONTENTS
4
vii
3.3 Computacional results of the WMBT . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2 Parameter settings and experimental protocol . . . . . . . . . . . . . . .
3.3.3 Comparing the deterministic algorithms . . . . . . . . . . . . . . . . . .
3.3.4 Validating the reducing rules . . . . . . . . . . . . . . . . . . . . . . . .
3.3.5 Comparing the metaheuristics . . . . . . . . . . . . . . . . . . . . . . .
44
46
46
47
48
49
Final Considerations
4.1 Future works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Scientific production . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
52
52
References
53
A Detailed instances
A.1 Instances for the MBT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.2 Instances for the WMBT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
59
61
List of Figures
1.1
1.2
1.3
1.4
1.5
1.6
1.7
2.1
2.2
2.3
2.4
2.5
2.6
2.7
3.1
3.2
3.3
Example scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Feasible broadcast solution. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Optimal broadcast solution. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Network with connection time and transmission time . . . . . . . . . . . . . . .
Telephone and postal models . . . . . . . . . . . . . . . . . . . . . . . . . . .
BRKGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Overview of this work. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Examples of binomial trees. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Building a synthetic instance. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Building a synthetic instance with 2 sources. . . . . . . . . . . . . . . . . . . .
Input graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
FRFS decoding procedure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
FRFS-SCHA decoding procedure. . . . . . . . . . . . . . . . . . . . . . . . . .
Proposed matheristic: pool of solutions merging and solving process. . . . . . .
Example of weighted-vertex model. . . . . . . . . . . . . . . . . . . . . . . . .
Example of weighted-edge model. . . . . . . . . . . . . . . . . . . . . . . . . .
Example of weighted-edge-and-vertex model. . . . . . . . . . . . . . . . . . . .
viii
1
2
2
4
4
8
10
13
14
14
17
18
19
21
33
34
34
List of Tables
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
3.1
3.2
3.3
3.4
3.5
3.6
3.7
List of articles about MBT in the literature. . . . . . . . . . . . . . . . . . . . . .
Chromosomes of input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Range considered by IRACE and best parameter settings obtained. . . . . . . .
Comparative results of ACS, Treeblock and BRKGA_FRFS. . . . . . . . . . . . .
Comparative results of BRKGA_FRFS and ILPs. . . . . . . . . . . . . . . . . .
Comparative results of NEWH, NTBA, ILP, ACS and BRKGA . . . . . . . . . . .
Comparative results of ACS, ILP and BRKGA_FRFS . . . . . . . . . . . . . . .
Comparative results of BRKGAs and hybrids . . . . . . . . . . . . . . . . . . .
List of articles about WMBT in the literature. . . . . . . . . . . . . . . . . . . . .
Range considered by IRACE and best parameter settings obtained. . . . . . . .
Comparative results of deterministic algorithms. . . . . . . . . . . . . . . . . . .
Comparative results of BRKGA-DJs with and without RR . . . . . . . . . . . . .
Comparative results of BRKGA-MSFs with and without RR . . . . . . . . . . . .
Comparative results of BRKGAs with and without RR . . . . . . . . . . . . . . .
Comparative results of ACS, BRKGAs and HARUTYUNYAN-WSCHA . . . . . .
12
17
24
25
26
27
28
30
35
46
48
49
49
49
49
A.1 Description of the test instances. . . . . . . . . . . . . . . . . . . . . . . . . . .
A.2 Description of the test instances. . . . . . . . . . . . . . . . . . . . . . . . . . .
59
61
ix
List of Algorithms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Lower bound algorithm for the MBT. . . . . . . . . . . . . . . . . . . . . . . . . .
FRFS decoder. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
SCHA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
FRFS-SCHA decoder. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Proposed matheuristic for the MBT. . . . . . . . . . . . . . . . . . . . . . . . . .
Greedy algorithm for Weighted-Vertex-MBT . . . . . . . . . . . . . . . . . . . . .
Lower bound algorithm for WMBT. . . . . . . . . . . . . . . . . . . . . . . . . .
WMBT for forest instances. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exact greedy algorithm for WMBT . . . . . . . . . . . . . . . . . . . . . . . . . .
Algorithm to remove edges of graph . . . . . . . . . . . . . . . . . . . . . . . . .
BRKGA for the WMBT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
DJ decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
MSF decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Create a random weighted graph with optima known. . . . . . . . . . . . . . . . .
x
15
16
18
19
22
36
40
41
42
42
43
44
45
47
1
Introduction
Broadcasting is the distribution of data in a network. According to Hedetniemi et al. (1988), it
has been studied since the early 1950s with Bavelas (1950). He studied the effectiveness of
different communication patterns in helping small groups solve common tasks. He considered
measures such as the time required to perform an information transmission task and several
problems, e.g., the gossiping problem. In the 1970s, the broadcasting problem became more
and more popular among researchers.
The M INIMUM B ROADCAST T IME (MBT) problem (Farley et al., 1979) consists of finding the
shortest sequence of messages that allows the data to reach every node in the network. At each
time step, every node can transmit the message to at most a single neighbor. The goal is to
find a broadcast scheme that minimizes the number of steps needed to execute the broadcast
operation.
Figures 1.1-1.3 show a simple example of the MBT, where a dashed vertex indicates that
the vertex did not receive the message, and an arrow indicates a message sent at time t . In
this example, V0 = {g1 } model a set of network gateways, whereas D = {d1 , d2 , d3 } a set of
common network devices. A simple (feasible) solution for the presented problem is depicted in
Figure 1.2 and suggests a three-step broadcast. However, Figure 1.3 shows an optimal solution
that requires only two steps to broadcast the data throughout the network.
g1
d2
d1
d3
Figure 1.1: Example scenario
1
INTRODUCTION
g1
d2
d1
2
g1
d2
d1
g1
d2
g1
d2
d1
d3
d1
d3
Figure 1.2: Feasible broadcast solution.
g1
d2
d1
g1
d2
g1
d2
d1
d3
d1
d3
Figure 1.3: Optimal broadcast solution.
1.1
Motivation
The MBT and its generalization, the W EIGHTED M INIMUM B ROADCAST T IME (WMBT), have
many applications in distributed systems, such as the Internet of Things (IoT) and Wireless
Sensor Networks (WSNs) (Shang et al., 2010). These applications rely mainly on large-scale
machine communications. Hence, they need data dissemination techniques that combine high
reliability with low communication latency.
Besides distributed systems, the MBT has many other applications, including communication
among telephone networks (Ivanova, 2019), surveillance and reconnaissance (Dekker, 2002),
and Direct Memory Access (DMA) (Lazard, 1992). Next, we present applications in robotics,
satellite networks and an industrial with Bluetooth.
In the context of swarm robotics, the MBT can be used for solving the Freeze-Tag Problem
(Bucantanschi et al., 2007; Keshavarz et al., 2011). The problem is to devise a schedule to
activate all robots in the minimum amount of time. Activation of robots, other than the initial
robot, only occurs if an active robot physically moves to the location of an inactive robot.
Chu and Chen (2018) described a practical application on satellite networks. Antennas transmit data over a long distance in a directed way. Each vertex represents a satellite or a base
station, and transmissions only occur one at a time. Each satellite has a transmission and setup
time, such that the first considers the time to transmit the data and the second considers the time
to redirect the antenna.
The original motivation for our work on the MBT was a network problem from an industrial
partner, which asked us to optimize their device update process. In their network, devices used
Bluetooth for intranet communication. Some of these devices (gateways) had a GPRS board for
INTRODUCTION
3
external communication. In preliminary experiments, they tested the update process considering
that the gateways had a firmware image of 200KB to broadcast. Two broadcasting techniques
were tested: peer-to-peer and Bluetooth mesh. In peer-to-peer, the nodes work in a MBT style
such that only one transmission occurs at a time per device, whereas in mesh this restriction
does not exist and a device can update more than one neighbor at the same time. The experiments have shown that in peer-to-peer the update process took 2 minutes, and in Bluetooth
mesh, it took 4.5 hours. The main reason for this difference is that the mesh technique demanded more bandwidth, which in turn resulted in more network congestion and packet loss.
This observation was formally demonstrated in Robledo et al. (2020).
1.2
Message-passing systems
According to Tsou et al. (2013), the two most common models for studying message-passing
systems are the telephone model (Slater et al., 1981; Su et al., 2010) and the postal model (BarNoy and Kipnis, 1994). In both models, the communication is made via calls between adjacent
vertices, by transmitting a single message from one sender to one receiver. In the telephone
model, each call takes one unit of time, and each vertex can only participate in one call at
any time. The postal model incorporates a communication setup phase and latency time. It is
introduced as the most appropriate for the message-passing system, which employs additional
parameters α ≥ 0 and β ≥ 0, called the setup phase and latency time, respectively.
In this model, each call consists of a setup phase, which takes α units times. Furthermore,
a sender can start a new call to another receiver when the transmission phase of its last call
finishes. For example, suppose that a vertex u wants to transmit a message first to v1 and then
to v2 at time 0. In its first call, u sets up the connection to v1 and after α units time sends the
message to v1 . Thus, the call from u to v1 will be completed after α units of time, but v1 received
message in α + β units of time. Since the setup phase of the first call is finishes at time α, the
call from u to v2 must be completed after 2 · α units of time, but v2 receives the message in
2 · α + β units of time.
Rico-Gallego et al. (2019) present these models generics, considering a setup phase or
connection time α and transmission time β. Where α is assumed to be a constant and β varies
from edge to edge. Hence, the transmission time between the sender v and receiver u is βv,u .
The telephone model considers that the device must be set up only once and then can
transmit. That is, if the sender v transmits to u1 , u2 , . . . and un , thus broadcast time is defined
as:
i
b(v) = α +
max
(( ∑ βv,u j ) + b(ui )).
i∈{1,2,...,n}
j=1
On the other hand, the postal model considers that the device must be set up for each
connection, and then it can transmit. That is, if the sender v transmits to u1 , u2 , . . . and un , thus
INTRODUCTION
4
broadcast time is defined as:
b(v) =
max
(i · α + βv,ui + b(ui )).
i∈{1,2,...,n}
Figure 1.4 shows an example instance of the MBT. Figures 1.5.a and 1.5.b show the broadcast scheme for the telephone model and postal model with αg1 = 2, αd1 = αd2 = αd3 = 0,
βg1 ,v1 = 1, βg1 ,v2 = 2, and βg1 ,v3 = 3. The ordering of transmissions is arbitrary. In Figure 1.5.a,
the vertex g1 transmits to v1 , v2 and v3 . Note that g1 has only one setup phase before the first
sending. The remaining transmissions do not have this phase. On the other hand, in Figure
1.5.b (that illustrated the postal model), the vertex g1 transmits to v1 , v3 and v2 . Note that, before
each transmission, there is a setup phase.
g1
2
1
v1
0
3
2
v3
0
v2
0
Figure 1.4: Network with connection time and transmission time
t =0
t =0
t =1
t =1
t =2
t =2
t =3
t =3
t =4
t =4
t =5
t =5
t =6
t =6
t =7
t =7
t =8
t =8
g1
v1
v2
(a) Telephone model
v3
g1
v1
v2
(b) Postal model
Figure 1.5: Telephone and postal models
v3
INTRODUCTION
1.3
5
Optimization
Gomez et al. (2004) define optimization as “doing the most with the least” and Lockhart and
Johnson (2000) define optimization as “the process of finding the most effective or favorable
value or condition”. Optimization is the act of finding the input parameters or arguments to a
function that result in the minimum or maximum output of the function. Classical optimization
models are mathematical programming, combinatorial optimization, constraint satisfaction, and
nonanalytic. Mathematical programming can be divided into continuous, integer, and mixed for
linear or nonlinear models (Talbi, 2009).
Combinatorial problems can be identified in the most diverse real applications such as planning, production, coordination, investment, transportation, communication, among others. Combinatorial problems can be identified in the most diverse real applications such as planning,
production, coordination, investment, transportation, communication, and others. Furthermore,
they can be examined, formulated and solved, using techniques from different areas of knowledge such as engineering, biology, economics and computer science. To solve one of these
problems, you must maximize/minimize a given function with one or several variables, so that all
constraints are satisfied. Those constraints are modeled in the form of equations or inequalities.
However, solving some problems might be hard, since they can belong to the N P -hard complexity class. In these cases, their resolution through exact methods is ineffective in instances
of high dimensions. They need memory and processor time, so maybe it is not suitable practical to use them. But, approximate or heuristic methods can generate high-quality solutions in
acceptable time for practical use, but there is no guarantee of finding a globally optimal solution.
1.3.1
Exact algorithms
Exact methods obtain optimal solutions and guarantee their optimality. For N P -hard problems,
we do not know a polynomial-time algorithm to solve them. We include some classical algorithms
as dynamic programming, and branch-and-X family of algorithms (branch-and-bound, branchand-cut, branch-and-price) (Padberg and Rinaldi, 1987; Barnhart et al., 1998).. Both methods
perform the search by subdividing it into smaller problems of the same kind. Another exact
approach is to transform combinatorial problems into linear programming (LP) and integer linear
programming problems and then solve them using a mathematical programming solver.
1.3.2
Approximate algorithms
Approximate methods generate high-quality solutions in a reasonable time for practical use,
but there is no guarantee of finding a globally optimal solution. In the class of approximate
methods, two subclasses of algorithms may be distinguished: approximation algorithms and
heuristic algorithms (Talbi, 2009).
INTRODUCTION
6
Heuristics find “good” solutions on large-size problem instances. They allow obtaining acceptable performance at acceptable costs in a wide range of problems. In general, heuristics do
not have an approximation guarantee on the obtained solutions. Specific heuristics are tailored
and designed to solve a specific problem and/or instance. Greedy or constructive algorithms
start from scratch (empty solution) and construct a solution by assigning values to one decision
variable at a time, until a complete solution is generated (Gendreau and Potvin, 2010).
Approximation algorithms are similar to heuristics algorithms, but they ensure that the bound
of the obtained solution is from the global optimum. An k-approximation algorithm generates an
approximate solution not less than a factor k times the optimum solution (Vazirani, 2001).
1.3.3
Metaheuristics
Unlike heuristics that are designed to solve a specific problem, metaheuristics are generalpurpose algorithms that can be applied to solve almost any optimization problem. They may
be viewed as upper-level general methodologies that can be used as a guiding strategy in
designing underlying heuristics to solve specific optimization problems. Metaheuristics allow
tackling large-size problem instances by delivering satisfactory solutions in a reasonable time.
There is no guarantee to find globally optimal solutions or even bounded solutions. Their use in
many applications shows their efficiency and effectiveness to solve large and complex problems
(Sorensen et al., 2017).
In designing a metaheuristic, two contradictory criteria must be taken into account: (i) the
exploration of the search space (diversification) and (ii) the exploitation of the best solutions
found (intensification). We can determine if a region is promising by the quality of its solutions.
In intensification, a promising area is explored more deeply in the hope of finding better solutions.
In diversification, unexplored areas should be visited to make sure that all regions of the search
space are explored evenly and that the search is not limited to just a small number of regions.
Talbi (2009) classifies metaheuristics into two groups: single-solution-based and populationbased metaheuristics. For single-solution-based metaheuristics, the main idea is to find highquality solutions interactively. The initial solution is the first solution. It can be entirely random,
greedy, or a combination of both. The neighborhood of a solution s is a set of similar solutions,
which can be generated from s by applying predefined “small” perturbations. The algorithm
can accept a quality improvement or move to worst solution. These features may vary for each
metaheuristic.
The population-based metaheuristics approach maintains and improves multiple candidate
solutions, often using population characteristics to guide the search. The candidates have a
cooperative relationship, where this relationship designs from a kind of metaheuristic. There
are such as ACO (ant colonies optimization), GA (genetic algorithms), GRASP (greedy adaptive
search procedure), ILS (iterated local search), PSO (particle swarm optimization), SA (simulated
annealing), TS (tabu search), and VNS (variable neighborhood search). Now, we will show an
INTRODUCTION
7
overview of GA and detail the biased random-key genetic algorithm.
Genetic algorithms (GA) is a population-based metaheuristic that relies on the principles of
natural selection. It can be viewed as an iterative improvement in a population of solutions. A
GA usually has seven steps (Holland, 1975): (i) Initial population, (ii) Evaluation, (iii) Selection,
(iv) Recombination, (v) Mutation, (vi) Replacement, and (vii) Repeat (ii)—(vi). First, the
population is initialized and evaluated. Then, a new population of solutions is generated using
some selection, followed by recombination and mutation procedures. Finally, this new population
is integrated into the current one.
In a GA, each individual is referred as a chromosome, which encodes a candidate solution. A
chromosome consists of a string of genes whose values are called alleles. An objective function
associates a fitness value with each individual indicating its fitting to the problem. In the evolving
process, individuals are selected to reproduce, and a crossover operator is used on the selected
individuals to produce new offspring that make up the next generation. In addition, mutation
operators are involved in this process. Finally, a replacement step is applied to determine which
individuals of the population (parents and offspring) will survive.
The proposed GA is not similar to classical Genetic Algorithms (Holland, 1975), where individuals are represented using a binary array and modified by some mutation operator. Our
algorithm is based on more recent implementations using random-keys encodings. In randomkey genetic algorithms (RKGA), developed by Bean (1994), the chromosomes consist of vectors
of real numbers generated randomly in the range [0, 1). Besides, a deterministic algorithm called
decoder processes the vector to calculate the fitness of the solution. RKGA does not make use
of the standard mutation operator, where some alleles are changed with a given probability. Instead, new (mutant) solutions are randomly generated and introduced in the current population
in each generation, in the same way as the initial population is created.
A biased random-key genetic algorithm (BRKGA) (Gonçalves and Resende, 2011) differs
from an RKGA in the way parents are selected for crossover. As shown in Fig. 1.6, at each
generation, the population is partitioned into two parts: elite and non-elite. The elite part contains
the best solutions in the total population and is simply copied to the next population generation.
The remaining elements are created by crossover or randomly generated (mutants). In the
recombination phase, each new individual is generated by combining one individual selected
from the elite set and another individual selected from the non-elite population. The elite parent
has a higher probability of passing its genes to the offspring generation, i.e., a biased selection
via the parameterized uniform crossover operator proposed by Spears and Jong (1991). This
process is illustrated in Fig. 1.6, where ρe = 0.7 (70%) is the probability that the offspring will
inherit each of its alleles from the best fit of the two parents. Gonçalves et al. (2014) made
an empirical comparison of biased and unbiased random-keys genetic algorithms in four types
of covering problems and has shown that the biased variant is faster than the original Bean’s
algorithm.
INTRODUCTION
8
K
K+1
Copy individuals
Elite
Elite
Select one
parent
Select one
parent
Non-Elite
X
Offspring
Crossover
0.21
0.75
0.53
0.42
0.67
0.88
0.59
0.71
0.32
0.45
0.34
0.71
0.10
0.89
0.04
0.91
C2
0.42
X
0.42
0.59
0.99
0.45
0.32
0.94
C1
0.34
Random
individuals
< 0.7?
Random numbers
Figure 1.6: BRKGA
1.3.4
Matheuristics
Matheuristics are optimization methods that integrate mathematical programming techniques
into a heuristic framework (Boschetti et al., 2009). A matheuristic combines a metaheuristic with
exact methods, such as algorithms from mathematical programming and constraint programming. Both components of a hybrid metaheuristic may run concurrently and exchange information to guide the search. Coupling metaheuristics and exact methods is a promising alternative in
solving many combinatorial optimization problems. The interest in hybrid approaches has rapidly
grown especially due to several inspiring results obtained by the union of these two methods.
1.4
Objectives
Our work is centralized in solving the MBT and the WMBT using a Biased Random-Key Genetic
Algorithm (BRKGA). We focus on large and sparse networks since they are the hardest instances
to find the optimal solution (Hasson and Sipper, 2004). Finally, our proposal can be summarized
as follows (see Figure 1.7):
INTRODUCTION
9
• For MBT:
(i) An algorithm to calculate a lower bound;
(ii) A BRKGA metaheuristics;
(iii) A BRKGA metaheuristics coupled with a refinement approach;
(iv) A hybrid algorithm (BRKGA + ILP);
(v) A method to create instances with known optima;
• For WMBT:
(i) Three exact models (one for each variant of the WMBT);
(ii) An algorithm to calculate a lower bound;
(iii) A polynomial algorithm to calculate the WMBT of trees;
(iv) Two BRKGA metaheuristics coupled with a refinement approach;
(v) A method to create instances with known optima.
1.5
Structure of the Thesis
This work is structured as follows: Chapter 2 is the outcome of an article in revision in the
International Transactions in Operational Research (ITOR). It presents the definition, related
work of the MBT, and our proposals for the MBT. Chapter 3 introduces the definition, related
work of the WMBT, and our contributions to the WMBT. Finally, Chapter 4 includes our final
considerations.
1.5. STRUCTURE OF THE THESIS
10
Hybrid
(ILP+BRKGA)
Algorithms
MBT
BRKGA
Lower
Bound
BRKGA
Algorithms
Integer Linear
Programming
WMBT
Lower
Bound
Reduce
Rules
Figure 1.7: Overview of this work.
2
Minimum Broadcast Time
The M INIMUM B ROADCAST T IME is a classical N P -hard problem (Garey and Johnson, 1979,
problem ND49). The problem can be formally defined as the following. Let G = (V, E) be
an undirected connected graph and V0 ⊆ V a subset of vertices (message originators) which,
initially, contain a given message. Let Vt be the set of vertices that receive the message at time
t or earlier, with 1 ≤ t ≤ T , where T is an upper bound for the broadcast time. From these
definitions, the MBT asks to find a sequence V0 , E1 ,V1 , E2 , . . . , Ek ,Vk that minimizes k, such
that Vk = V . In addition, for each t ∈ {1, . . . , k}, the following constraints hold: (i) each edge
in Et has exactly one endpoint in Vt−1 , (ii) no two edges in Et share a common endpoint, and
(iii) Vt = Vt−1 ∪ {v : (u, v) ∈ Et }.
Here, we have some terminology that will be used throughout this work.
Definition 1. The broadcast scheme, denoted as BS , is a sequence of vertices and edges V0 ,
E1 , V1 , . . . , VT that describes a solution.
Definition 2. Broadcast tree BT is a directed spanning tree that describes a solution.
Definition 3. Broadcast time of vertex v0 in G, denoted as b(G, v0 ), is minimum number of steps
to v0 broadcast the message for all vertices in V .
Definition 4. Broadcast time of graph G is defined by b(G) = min (b(G, v0 )).
v0 ∈V
Definition 5. Broadcast center of graph G is defined as BC(G) = {v0 ∈ V | b(v0 ) = b(G)}.
Definition 6. A graph G is called broadcast graph if max(b(G, v0 )) = dlog2 |V |e.
v0 ∈V
Definition 7. A minimum broadcast graph (MBG) is a broadcast graph with a minimum number
of edges.
11
Minimum Broadcast Time
2.1
12
Related Work
This section introduces the related work on the MBT. Given its potential for modeling many
real-world applications, the MBT has attracted considerable research interest, and several exact
(de Sousa et al., 2018; Ivanova, 2019), approximation (Elkin and Kortsarz, 2003; Kortsarz and
Peleg, 1992), and heuristics (Scheuermann and Wu, 1984; Hoelting et al., 1996; de Sousa et al.,
2018; Hasson and Sipper, 2004) algorithms have been proposed.
In some special situations, for instance, when |V0 | = 1 and the graph is a tree (Koh and
Tcha, 1991; Su et al., 2010) or a complete grid (Wojciechowska and Scoy, 1999), the MBT can
be optimally solved in polynomial time. For arbitrary graphs, the exact approaches include a
dynamic programming algorithm (Scheuermann and Wu, 1984) and the ILP models presented
by de Sousa et al. (2018) and Ivanova (2019). Currently, the ILP model suggested by de Sousa
et al. (2018) is the best exact method. However, this model is able to solve in reasonable times
only instances of up to approximately 50 vertices, which is an insufficient number for real-world
industrial applications (this model is presented in Section 2.2.4).
Other works proposed approximation algorithms, constructive-based heuristics and metaheuristics. Approximation algorithms for MBT are studied in Kortsarz and Peleg (1992), where
√
the authors introduce an O ( n)-additive approximation algorithm for broadcasting in general
graphs with n vertices. This work also proposes several approximation algorithms for graph
classes with small separators, with anapproximation
ratio proportional to the separator size
log n
times log n. Another algorithm with O log log n -approximation ratio is presented in Elkin and
Kortsarz (2003).
Scheuermann and Wu (1984) were the first to propose heuristics for the problem, with two
constructive-based heuristic algorithms: Least Weight Maximum Matchings (LWMM) and Approximate Matching (AM). The AM presented better results. Next, Hoelting et al. (1996) proposed a genetic algorithm (GA), the first metaheuristic for the MBT. They compared their GA
with AM, and the experimental results indicated that the GA produces better broadcast time values. Hasson and Sipper (2004) proposed an ant colony system (ACS) algorithm and compared
it with LWMM, AM and GA. The ACS presented the best results in comparison with the other
heuristics.
We present a summarized the literature’s approaches. Table 2.1 lists the main articles about
MBT in the literature.
Table 2.1: List of articles about MBT in the literature.
Article
Approach
Observation
Scheuermann and Wu (1984)
Exact and heuristic algorithms
-
de Sousa et al. (2018)
ILP model and heuristic algorithm
-
Ivanova (2019)
ILP model and lower bound
-
Hoelting et al. (1996)
Metaheuristic algorithm
-
Hasson and Sipper (2004)
Metaheuristic algorithm
Continued on next page
Minimum Broadcast Time
13
Table 2.1 – continued from previous page
Article
Approach
Slater et al. (1981)
Polynomial time algorithm
Koh and Tcha (1991)
Polynomial time algorithm
For MBT, when graph is a tree and |V0 | = 1. With
Su et al. (2010)
Polynomial time algorithm
For MBT, when graph is a tree and |V0 | = 1. With
Wojciechowska and Scoy (1999)
Polynomial time algorithm
For MBT, when graph is a complete grid and |V0 | = 1.
2.2
Observation
For broadcast center problem, when graph is a tree
and |V0 | = 1.
complexity O(|E| log(|E|)).
complexity O(|E|).
Algorithmic approaches for the MBT
This section introduces our proposals for the classical MBT. Section 2.2.1 proposes synthetic
instances for the MBT. Section 2.2.2 describes a lower bound algorithm for the MBT. Section
2.2.3 presentes some decoders for the MBT. Finally, Section 2.2.4 shows a matheuristic for the
MBT.
2.2.1
Synthetic instances for the MBT
Given that the optimal solution for large MBT instances is often unknown, we generated a new
benchmark with known optimal solutions using the following procedure.
Let the instance G = (V, E) be defined by the union of a binomial tree Bk = (VB , EB ) and
a random graph Gr = (Vr , Er ), where V = VB = Vr and E = EB ∪ Er . The binomial tree Bk is
an ordered tree defined recursively as follows: (i) B0 is a trivial graph, (ii) Bk is constructed from
two binomial trees Bk−1 by attaching one of them as the rightmost (can be leftmost) child of the
root of the other. Figure 2.1 shows the binomial trees B0 through B3 . Note that the MBT of a
binomial tree Bk is equal to k if the root of Bk is in V0 . The random graph Gr is based on the
G(n, p) model, also known as the binomial model (Gilbert, 1959). Each graph Gr = (V, Er ) is
generated with n vertices and each potential edge in Er is created with probability p. In Figure
2.2, we apply a union of graphs B3 and Gr and we obtain a synthetic graph G with 8 vertices.
1
8
1
4
1
1
(a) B0
2
2
3
(b) B1
(c) B2
6
2
7
5
Figure 2.1: Examples of binomial trees.
3
4
(d) B3
Minimum Broadcast Time
14
1
8
1
6
2
7
5
8
3
1
6
2
7
5
4
8
3
6
2
7
5
4
(a) B3
3
4
(c) G = B3 ∪ Gr
(b) Gr
Figure 2.2: Building a synthetic instance.
This methodology can be applied to create synthetic instances with multiple sources (|V0 | >
1). The idea is simple, we will build |V0 | binomial trees and connect them with a random graph.
In Figure 2.3 we created a synthetic instance with V0 = {1, 5}.
5
1
4
2
8
6
4
7
3
5
1
2
8
3
(a) B2 + B2
5
1
6
7
(b) Gr
4
8
2
6
7
3
(c) G
Figure 2.3: Building a synthetic instance with 2 sources.
2.2.2
Lower bound algorithm
In many practical applications, bounds on the optimal solutions are sufficient. Bounds can also
help solvers to prove the optimally of a solution. Clearly, |V | − |V0 | is an upper bound for the
optimal broadcast time. Furthermore, the value
|V |
T LB(G,V0 ) = log2
|V0 |
(2.1)
defines a theoretical l
lower bound
m for the MBT (Ivanova, 2019). It is easy to see that a complete
|V |
graph needs exactly log2 |V | steps to broadcast.
0
A good estimate of the planning horizon length is very important for the performance of
a mathematical formulation. A tighter lower bound can reduce the number of columns in the
coefficient matrix and, thus, reduce the computational demand and the total amount of used
memory. Moreover, a lower bound can be used by a heuristic algorithm to prove the optimality
of a feasible solution, i.e., if a heuristic finds a solution whose value meets the lower bound, then
this solution is proved optimal.
Minimum Broadcast Time
15
Algorithm 1 presents the pseudo-code for the proposed lower bound calculation. The proposed lower bound, called LBB-BFS, is based on a multisource breadth-first search (BFS), starting at every vertex of V0 . Its main objective is to find the maximum shortest path between a target
vertex and its nearest source. Note a straightforward implementation of LBB-BFS, i.e., applying
a breadth-first search on each v ∈ V0 , would require O(|V0 | · |E|). This issue can be addressed
by labeling every vertex in V0 as discovered, and placing them at the beginning of the known
vertices queue Q0 (see lines 4–7). Overall, the worst-case running time of the LBB-BFS function
is O(|E|). A similar approach based on BFS has also been used by de Sousa et al. (2018) to
reduce the number of variables in their proposed ILP formulation.
Algorithm 1: Lower bound algorithm for the MBT.
Input : Undirected graph: G = (V, E),
Source set: V0
Output: Lower bound to broadcast: lowerBound
LBB-BFS(G,V0 )
for each v ∈ V do
3
dist[v] ← ∞
1
2
4
5
6
7
8
9
10
11
12
13
14
Q ← InitQueue()
for each v0 ∈ V0 do
dist[v0 ] ← 0
Q ← Enqueue(Q, v0 )
// Set distance to infinity
// Let Q be an empty queue
// Set distance to zero
// Enqueue v0 in Q
while not isEmpty(Q) do
v ← Dequeue(Q)
for each u ∈ G.ad j[v] do
if dist[u] > dist[v] + 1 then
dist[u] ← dist[v] + 1
Q ← Enqueue(Q, u)
lowerBound ←max (dist[v])
// Dequeue v of Q
// Check the distance
// Update distance of u
// Enqueue v0 in Q
// Get higher distance
v∈V
15
return lowerBound
Theorem 8. Algorithm 1 returns a lower bound for the optimum of the MBT with input graph
G = (V, E) and source set V0 .
Proof. Let b∗ be the optimum of MBT for an instance (G,V0 ) and z be the value returned by
the LBB-BFS algorithm. Let v ∈ V0 be the closest vertex of V0 to a vertex ` ∈ V , such that the
distance between them is exactly z. We need at least z steps to reach ` from any vertex in V0 .
Therefore, z ≤ b∗ , i.e., z is a lower bound for the optimum MBT value.
The lower bound is given by
LB(G,V0 ) = max(T LB(G,V0 ), LBB-BFS(G,V0 )),
(2.2)
Minimum Broadcast Time
16
where TLB(G,V0 ) is defined in Eq. (2.1) and LBB-BFS(G,V0 ) is calculated by Algorithm 1.
Hence, if the best fitness in the current population is equal to LB(G,V0 ), the algorithm proves
that it is an optimal solution.
2.2.3
BRKGA decoders for the MBT
The only problem-specific part of BRKGA is the decoder, i.e., the procedure that converts randomkeys (chromosomes vector) into a solution for the problem. The following subsections present
the two proposed decoders for the MBT.
2.2.3.1
First receive first send decoder
Algorithm 2 describes our first decoder, called FRFS, which is based on the priority decoder of
Hoelting et al. (1996). The algorithm receives as input a graph G(V, E), source set V0 , and
chromosomes vector Cr. It returns as output the MBT for the encoded candidate solution. In
this decoder, the chromosomes vector Cr has size |V |. Each allele Cr[v] represents the priority
of vertex v to receive a message. The lower the allele value, the higher the priority.
Algorithm 2: FRFS decoder.
Input : Undirected graph: G = (V, E), Source set: V0 , Chromosomes vector: Cr
Output: Total step time to broadcast: time
FRFS(G,V0 ,Cr)
time ← 0
// Init time
3
Transmitters ← V0
// Set the initial Transmitters
4
Ranking ← InitList()
// Init Ranking list
5
for each v ∈ Sort(V0 ,Cr) do
// Ordering in ascending order of allele value
6
Ranking ← AppendItem(Ranking,v)
1
2
7
8
9
10
while Transmitters 6= V do
NewTransmitters ← InitList()
for each v ∈ Ranking do
u←
argmin(Cr[u])
// Set the new transmitters
// Get the best vertex
u∈N(v)\{Transmitters∪NewTransmitters}
11
12
13
14
15
16
17
if u 6= 0/ then
NewTransmitters ← AppendItem(NewTransmitters, u)
vertex in NewTransmitters
for each v ∈ NewTransmitters do
Transmitters ← Transmitters ∪ {v}
Ranking ← AppendItem(Ranking,v)
time ← time + 1
// Add the best
// Update Transmitters
// Update Ranking
// Increment time
return time
The algorithm starts by setting the variables time = 0 and Transmitters = V0 (lines 2–4),
where time represents the current time step, set Transmitters the vertices that have the mes-
Minimum Broadcast Time
17
sage, and list Ranking the order of each transmitter. Next, it appends at list Ranking the vertex
v for each vertex v ∈ V0 , in ascending order of allele value (lines 4–6). In the main loop (lines
7–16), the variable NewTransmitters indicates the list of vertices that receive the message in
step time. This loop is executed until all vertices are in set Transmitters. The main loop starts
by scanning, in order, each vertex v from list Ranking and selects the neighbor u of v that has
not yet received the message, ties are broken according to the allele value Cr[u]. The selected
vertex u is then added to the list NewTransmitters (line 12). In lines 13–15, the vertices in
NewTransmitters are added in Transmitters and appended at the end of the list Ranking. Finally, variable time is incremented (line 16). Overall, the worst-case running time of this decoder
is O(|V | · |E|).
The graph in Figure 2.4 (with only one source) and chromosomes vector in Table 2.2 show
an input example for the decoding procedure. We now describe the FRFS decoding procedure
for this example. Initially, vertex v1 is designated as the unique transmitter (Figure 2.5-a). Among
the neighbors of v1 , vertex v3 has the highest priority value (according to its chromosome value),
hence vertex v1 sends the message to v3 (Figure 2.5-b). In time 2, only vertices v1 and v3 have
received the message. Because of the ordering in the Ranking list of the FRFS algorithm, v1 will
transmit first to vertex v4 (its second highest priority neighbor), and v3 transmits to v8 (Figure
2.5-c). Next, in time 3, v1 transmits to v2 , and v4 transmits to v7 (Figure 2.5-d). Finally, in time
4, the other vertices receive the messages in the following order: v4 → v6 and v7 → v5 (Figure
2.5-e).
Figure 2.4: Input graph
v2
v6
v1
v3
2.2.3.2
v5
Vertices
Value(Cr )
v4
v8
Table 2.2: Chromosomes of input
v1
v2
v3
v4
v5
v6
v7
v8
0.5
0.4
0.1
0.2
0.8
0.7
0.6
0.3
v7
First Receive First Send with SCHA improvement
Preliminary experiments with the FRFS decoder have shown that this decoder has a poor performance in sparse graphs. This motivated us to devise a new decoder, called FRFS-SCHA. This
new decoder combines FRFS with a greedy method, called SCHA, that is able to find in polynomial
time the optimal MBT on forest graphs. More specifically, in FRFS-SCHA, we use an adaptation
of the FRFS decoder to produce a forest that is then used as input to the SCHA algorithm. In the
following, we give more details about FRFS-SCHA.
Algorithm 3 introduces SCHA. This algorithm receives as input a forest graph F(V, E) and
source set V0 . It returns as output the optimal MBT for the forest. SCHA iteratively calls function
MBT-Tree (line 5), which is an algorithm proposed by Su et al. (2010); Koh and Tcha (1991) for
Minimum Broadcast Time
18
v2
v2
v1
v2
v4
v1
v6
v4
v1
1
v3
v8
v3
v6
v5
v2
v6
v5
4
3
v1
2
1
v4
v1
v8
2
1
3
2
v7
v7
(c) t = 2
3
v3
v8
2
(b) t = 1
v2
v4
1
v3
(a) t = 0
2
v3
(d) t = 3
v4
4
3
2
v8
v7
(e) t = 4
Figure 2.5: FRFS decoding procedure.
finding the MBT on tree graphs. Hence, SCHA finds the optimal MBT by calculating the MBT of
each tree in the forest, and then returning the greatest MBT among these trees. Given that the
asymptotic complexity of MBT-Tree is O(|V | · log2 (|V |)), SCHA is O(|V | · log2 (|V |)).
Algorithm 3: SCHA.
Input : Forest undirected: F = (V, E), Source set: V0
Output: Total step time to broadcast: time
SCHA(F,V0 )
time ← 0
3
for each v0 ∈ V0 do
4
T ← GetTree(F ,v0 )
5
time ← max(time, MBT-Tree(T ,v0 ))
1
2
6
// Init time
// Get the tree with root v0
// MBT of tree T from source v0
return time
Our new decoder FRFS-SCHA is depicted in Algorithm 4. In lines 2–16, FRFS was adapted to
produce a forest. In line 17, this forest is used as input to SCHA, which calculates the resulting
MBT. Because of the complexity of FRFS is O(|V | · |E|) and SCHA is O(|V | · log2 |V |), the worst-
case running time of this decoder is O(|V | · |E|).
Figure 2.6-b shows the resulting forest for the input example in Figure 2.4 and Table 2.2. The
solution obtained after the SCHA procedure is applied to this forest is depicted in Fig 2.6-a. Note
this solution is better than the solution previously obtained with the original FRFS (Figure 2.5-e).
Minimum Broadcast Time
19
Algorithm 4: FRFS-SCHA decoder.
Input : Undirected graph: G = (V, E), Source set: V0 , Chromosomes vector: Cr
Output: Total step time to broadcast: time
FRFS-SCHA(G,V0 ,Cr)
2
EF ← 0/
// Init the set of edges from the forrest graph
3
Transmitters ← V0
// Set the initial Transmitters
4
Ranking ← InitList()
// Init Ranking list
5
for each v ∈ Sort(V0 ,Cr) do
// Ordering in ascending order of allele value
6
Ranking ← AppendItem(Ranking,v)
1
while Transmitters 6= V do
7
NewTransmitters ← InitList()
for each v ∈ Ranking do
u←
argmin(Cr[u])
8
9
10
// Set the new transmitters
// Get the best vertex
u∈N(v)\{Transmitters∪NewTransmitters}
if u 6= 0/ then
11
NewTransmitters ← AppendItem(NewTransmitters, u) // Add the best
vertex in NewTransmitters
EF ← EF ∪ {(v, u)}
// Add the edge in EF
12
13
for each v ∈ NewTransmitters do
14
Transmitters ← Transmitters ∪ {v}
Ranking ← AppendItem(Ranking,v)
15
16
return SCHA((V, EF ),V0 )
17
v2
// Update Transmitters
// Update Ranking
// Compute MBT of forest with SCHA
v6
v5
v2
v6
v5
3
3
v1
v4
v1
1
2
v3
v8
(a) t = 0
v7
v3
v4
3
2
3
v8
v7
(b) t = 1
Figure 2.6: FRFS-SCHA decoding procedure.
2.2.4
Proposed matheuristic
This section describes the proposed matheuristic, which combines an extension of the ILP model
of de Sousa et al. (2018) and our BRKGA. To the best of our knowledge, this is the first work to
propose a matheuristic for the MBT.
This is a small extension for the ILP model of de Sousa et al. (2018). Different from
the original model, ILP extension considers graphs with multi-source (i.e., |V0 | > 1).
Let
V = {0, 1, · · · , n − 1} be the set of vertices, V0 the set of sources, E the set of connections
between two vertices, and N(i) the set of neighboring vertices of vertex i. In the model, Ki is a
binary constant indicating whether or not vertex i is in V0 , and Tmax a constant that represents
Minimum Broadcast Time
20
an upper limit on the time in which a vertex receives the message (e.g., Tmax = |V | − |V0 | is the
trivial limit). Finally, define T as a decision variable that represents the minimum broadcast time,
and xti j as a binary variable that has value 1 if the vertex i sends the message to the vertex j in
time t and 0, otherwise. Based on these elements, the ILP model is as follows:
min T
(2.3)
Tmax
s. t
∑ ∑ xtji = 1
(2.4)
j∈N(i) t=1
∀i ∈ V
∑ xti j ≤ 1
∀i ∈ V, ∀t ∈ [1, Tmax ]
(2.5)
∀(i, j) ∈ E, ∀t ∈ [1, Tmax ]
(2.6)
∀(i, j) ∈ E
(2.7)
Ki +
j∈N(i)
t−1
xti j ≤ Ki + ∑
∑
τ
xki
τ=1 k∈N(i)\{ j}
Tmax
∑ t · xti j ≤ T
t=1
T ∈N
xti j ∈ B
(2.8)
∀(i, j) ∈ E, ∀t ∈ [1, Tmax ]
(2.9)
Equation (2.3) is the objective function. Constraints (2.4) limit each vertex to receive only
one message at a time or to start with it. Constraints (2.5) require that each vertex sends at
most one message to a neighbor in each t . Constraints (2.6) establish that each vertex can
only transmit if it has already received the message. Constraints (2.7) state that the value of T
must be greater than or equal to the time of any transmission. Finally, Constraints (2.8) and (2.9)
define the domain of the decision variables.
Figure 2.7 illustrates the main ideas of the proposed matheuristic. First, given a problem
instance, the matheuristic uses BRKGA to generate and maintain a pool of candidate solutions.
After some BRKGA iterations without improvement in this pool, the matheuristic combines the
solutions in the pool through a merging process. The merging process generates a subgraph
that contains the original instance vertices and some edges from the solutions in the pool. Next,
the matheuristic uses the ILP model to solve the problem instance induced by this subgraph.
Note that solving the induced problem instance is far easier than solving the original instance.
The solution obtained through the ILP model is then added to the pool of solutions, and some
other solution is removed from the pool. The process in Figure 2.7 is then repeated until a stop
criterion is met.
Algorithm 5 details the proposed matheuristic. It starts with an initial pool of candidate solutions P generated through BRKGA (line 3). In the main loop (lines 5–28), the algorithm uses
BRKGA to evolve the current pool of solutions, and then it checks if this pool has improved. If
Minimum Broadcast Time
21
Population PK
Graph
16
3
9
14
v2
v6
v5
17
2
15
v1
v4
4
1
8
6
v3
v8
11
13
v7
5
7
Solution 1
v2
4
Solution 2
v6
v5
v2
3
1
v4
2
v3
3
2
3
v8
v5
v2
4
v1
3
Solution n
v6
2
v1
12
10
3
v4
4
v3
v5
3
v1
···
1
v7
v6
2
v4
4
1
2
v8
v7
3
v3
v8
2
3
v7
Subgraph (Merge of Solutions)
v2
v6
v5
v2
v6
3
v1
ILP
v4
3
v1
1
2
v3
v8
v7
v3
v5
v4
3
2
3
v8
v7
Figure 2.7: Proposed matheristic: pool of solutions merging and solving process.
no improvement is achieved after maxIt iterations, the merging process begins. In the merging
process, the subgraph GS (V, ES ) is created by adding the edges from the best solutions in the
pool until the edge density of the subgraph is greater than or equal to d (lines 15–22). After
the subgraph is created, the algorithm uses the lower bound given in Eq. (2.2) to check if a
better solution than the best current one S∗ can be found. Note this checking is useful to avoid
unnecessary ILP model solving, which can be quite costly. If the subgraph passes this filter, the
algorithm solves the ILP model using a standard model solver. The model solver is invoked with
S∗ as the initial solution and a time limit of tILP . If the ILP solution returned by the model solver
SILP is better than S∗ , then we remove S∗ from P, add SILP in P, and update S∗ with SILP (lines
25–28).
Minimum Broadcast Time
22
Algorithm 5: Proposed matheuristic for the MBT.
Input : Undirected graph: G = (V, E), Source set: V0 , Time limit for each running of ILP: tILP ,
Minimal density of subgraph: d ,
Maximum number of generations without improvement: maxIt
Output: Schedule Broadcast: S
BRKGA+ILP(G,V0 ,tILP , d, maxIt)
2
P ← BRKGA_Init(G, V0 )
3
S∗ ← GetBestIndividual(P)
4
noImprovement ← 0
1
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
while stopping criterion not met do
P ← BRKGA_Evolve(P)
// Evolve population
S ← GetBestIndividual(P)
// Get the best individual of the
population
if Fitness(S) < Fitness(S∗ ) then // Check if the population has improved
S∗ ← S
// Update S∗
noImprovement ← 0
else
noImprovement ← noImprovement + 1
if noImprovement = maxIt then
// If no improvement after I generations
noImprovement ← 0
ES ← GetEdges(S∗ )
EP ← InitList()
// Let EP a empty list
for each S in Sort(P \ S∗ ) do
// For each solution S in P (in fitness
order)
EP ←AppendItems(GetEdges(S))
// Append the edges of S in EP
for each e in EP do
if Density((V, ES )) ≥ d then
ES ← ES ∪ {e}
if LB((V, ES ), V0 ) < Fitness(S∗ ) then
// Add the edge e in ES
// Check if a better solution can
be found
SILP ← ILP-MBT((V, ES ), V0 , S∗ , tILP )
if Fitness(SILP ) < Fitness(S∗ ) then
P ← P \ {S∗ }
P ← P ∪ {SILP }
S∗ ← SILP
24
25
26
27
28
29
// For each edge e in EP
break
22
23
// Inicialize the first BRKGA population
// Get the best individual of the population
return S∗
// Run ILP
// Check if SILP is better
// Remove solution S∗ on P
// Add solution SILP in P
// Update S∗
Minimum Broadcast Time
2.3
23
Computacional results of the MBT
This section presents the computational experiments conducted to evaluate the effectiveness
of our proposed BRKGA and matheuristic. The proposed algorithms are compared with the
following state-of-the-art approaches: (i) the Ant Colony metaheuristic (ACS) from Hasson and
Sipper (2004); (ii) the ILP model from de Sousa et al. (2018); and (iii) the constructive heuristic
TreeBlock from de Sousa et al. (2018).
Since we could not obtain the source code of ACS, we implemented our own version of this
algorithm based on its original definitions. We did not implement the GA approach of (Hoelting
et al., 1996) because the results reported in Hasson and Sipper (2004) are enough to conclude
that ACS outperforms it.
To test the effectiveness of the SCHA decoding approach, we developed two versions of our
BRKGA: one without SCHA (Algorithm 2), called BRKGA_FRFS, and one with SCHA (Algorithm 4),
called BRKGA. The effectiveness of SCHA was also tested on the proposed matheuristic, hence
two versions of the matheuristic were devised: one without SCHA, called BRKGA_FRFS+ILP, and
one with SCHA, called BRKGA+ILP.
All experiments in this section were conducted on an Intel Core i7-6700 with 3.40 GHz, 32
GB of RAM, running Ubuntu 18.04.5. The heuristic algorithms were coded in C++ and compiled
with g++ 7.5 and ‘-O3’ flag. The BRKGA C++ framework developed by Toso and Resende (2015)
has been used to implement our BRKGA. Moreover, IBM Cplex 12.9 has been adopted to solve
the ILP models.
2.3.1
Instances
The algorithms were tested on a total of 142 instances, which include:
• Harary graphs (16 instances): These are the same instances used in the work of
de Sousa et al. (2018). A Harary graph, denoted by Hk,n , is a k-connected graph with
n vertices having the smallest possible number of edges.
• Others graphs (25 instances): We also included the instances we were able to repro-
duce from the works of Harutyunyan and Wang (2010); Harutyunyan and Jimborean
(2014). These instances are hypercube (6 instances), shuffle exchange (7 instances),
cube-connected cycles graphs (5 instances), and deBruijn (7 instances).
• Network Data Repository1 (59 instances): Because the MBT instances used in previous
works (Scheuermann and Wu, 1984; Hoelting et al., 1996; Hasson and Sipper, 2004) are
no longer available, we have chosen some instances from well-established benchmarks of
complex network problems. To cover different industry scenarios, we consider instances
based on connected small-world networks with 100 or 1000 vertices (Freitas et al., 2019).
1
http://www.networkrepository.com
Minimum Broadcast Time
24
We have chosen the small-world model because it is commonly used to represent communication networks in industrial scenarios, as suggested in (Guidoni et al., 2010; Cabral
et al., 2013).
• Large synthetic instances based on Binomial Tree (42 instances): Given that the op-
timal solution for large MBT instances is often unknown, we generated a new benchmark
with known optimal solutions using the following procedure. Let the instance G = (V, E) be
defined by the union of a binomial tree Bk = (VB , EB ) and a random graph Gr = (Vr , Er ),
where V = VB = Vr and E = EB ∪ Er . The binomial tree Bk is an ordered tree defined
recursively as follows: (i) B0 is a trivial graph, (ii) Bk is constructed from two binomial trees
Bk−1 by attaching one of them as the rightmost (can be leftmost) child of the root of the
other. Figure 2.1 shows the binomial trees B0 through B3 . Note that the MBT of a binomial tree Bk is equal to k if the root of Bk is in V0 . The random graph Gr is based on the
G(n, p) model, also known as binomial model (Gilbert, 1959). Each graph Gr = (V, Er )
is generated with n vertices and each potential edge in Er is created with probability p.
In Figure 2.2-b, we apply an union of graphs B3 and Gr , obtaining a synthetic instance G
with 8 vertices.
For much more detail of instances, see Appendix A.1.
2.3.2
Parameter settings and experimental protocol
In our experiments with the ACS algorithm, we adopted the same parameter settings indicated
by its authors. Moreover, we have used the irace tunning tool (López-Ibáñez et al., 2016) to
configure the parameters of our algorithms and their variations. The best parameter settings
identified by the tuning experiment are reported in Table 2.3. In this table, BRKGA parameters p,
pe , pm , ρe , and K represent, respectively, number of individuals in each population, percentage
of elite individuals into each population, percentage of mutants introduced at each generation
into the population, probability that an offspring inherits the allele of its elite parent, and the
number of independent populations. Parameters d and tILP are used only in the matheuristic
and represent, respectively, density of subgraph GS (V, ES ) and time limit for the ILP model
solver. The matheuristic has an additional parameter maxIt (maximum number of generations
without improvement),
l m which was experimentally set to a linear function that depends on |V |:
maxIt = 550 −
|V |
10 , where 20 ≤ maxIt ≤ 500.
Table 2.3: Range considered by IRACE and best parameter settings obtained.
Parameter
p
pe
pm
Value ranges
BRKGA_FRFS
BRKGA
BRKGA_FRFS+ILP
BRKGA+ILP
-
|V |
0.16
0.11
|V |
0.11
0.19
|V |
0.16
0.11
|V |
0.11
0.19
0.10, 0.11, . . ., 0.25
0.10, 0.11, . . ., 0.30
Continued on next page
Minimum Broadcast Time
25
Table 2.3 – continued from previous page
Parameter
ρe
K
d
tILP
Value ranges
BRKGA_FRFS
BRKGA
BRKGA_FRFS+ILP
BRKGA+ILP
0.50, 0.51, . . ., 0.80
0.69
1
0.53
1
-
-
-
-
0.69
1
0.85
13.31
0.53
1
0.30
18.01
-
0.10, 0.11, . . ., 1.00
5.00, 5.01, . . ., 25.00
We have set a time limit of 3600 s (1 h) to Cplex for solving the ILP models from de Sousa
et al. (2018). To assess the average performance of the heuristic algorithms (BRGKAs and ACS),
we have performed 10 runs in each benchmark instance with different random seeds for each
run. A time limit of 60 s has been used for these runs.
2.3.3
Experiments on Harary Graphs
Table 2.4 compares BRKGA_FRFS with the heuristic approaches ACS and TreeBlock in Harary
instances. The methods are compared using the following criteria: the best, the average, the
worst solution obtained (columns ‘Best’, ‘Avg.’ and ‘Worst’, respectively), as well as the average
CPU time to find the best solution (column ‘t (s)’). An asterisk means that the method has
been able to prove the optimality of a given result. If in a run the heuristic fails to attain the
best solution, its CPU time to find the best in this run is considered to be the cutoff time of
60 seconds. The bottom of Table 2.4 shows a summary that includes: number of instances in
which the method found the best broadcast time, number of instances in which the algorithm
determined the best average broadcast time, and the average of the average CPU time values
to find the best solution. The results of TreeBlock are reproduced from its original paper.
Table 2.4: Comparative results of ACS, Treeblock and BRKGA_FRFS.
ACS
Instance
H10,30
H11,50
H20,50
H21,50
H2,100
H2,17
H2,30
H2,50
H3,17
H3,30
H3,50
H5,17
H6,17
H7,17
H8,30
H9,30
# Best
Treeblock
Best
Avg.
Worst
5*
5.00
6*
6.00
6*
6.00
6
6*
6.00
6
50*
50.00
50
t (s)
Best
Best
Avg.
Worst
t (s)
5
0.10
6
5*
5.00
5
6
7
6*
6.00
6
8
6*
6.00
6
7
6*
6.00
6
50
50*
50.00
50
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
9*
9.00
9
15*
15.00
15
25*
25.00
25
5*
5.00
5
9*
9.00
9
14*
14.00
14
5*
5.00
5
5*
5.00
5
5*
5.00
5
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
6
6.00
6
5*
5.00
5
15
BRKGA_FRFS
9
9*
9.00
9
15
15*
15.00
15
25
25*
25.00
25
5
5*
5.00
5
9
9*
9.00
9
14
14*
14.00
14
5
5*
5.00
5
5
5*
5.00
5
5
5*
5.00
5
60.00
6
5*
5.00
5
0.02
< 0.01
6
5*
5.00
5
< 0.01
10
16
Continued on next page
Minimum Broadcast Time
26
Table 2.4 – continued from previous page
ACS
Instance
Best
Avg.
Treeblock
Worst
t (s)
BRKGA_FRFS
Best
Best
Avg.
Worst
# Best Avg.
15
-
16
Avg. t (s)
3.76
-
0.01
t (s)
The results in Table 2.4 show that our BRKGA version without SCHA outperforms both ACS
and TreeBlock. In particular, BRKGA_FRFS was able to prove the optimal solution for all Harary
graph instances in milliseconds.
Next, we compare in Table 2.5 our BRKGA_FRFS with the ILP from de Sousa et al. (2018).
Five variants of this model were considered: (i) the original model without bounds, (ii) the model
with the lower bound defined in Eq. (2.1), (iii) the model with the lower bound defined in Eq.
(2.2), (iv) the model with an upper bound determined by our BRKGA_FRFS, and (v) the model
with upper and lower bounds.
It is possible to observe in the results of Table 2.5 that the utilization of bounds in the ILP
model effectively reduced the computational time. Without the upper bounds provided by our
BRKGA_FRFS, instances H11,50 , H20,50 , and H21,50 could not be optimally solved by the ILP
model. In instances H2,100 , H2,30 and H3,50 , the ILP model with the proposed lower bound
outperformed the model with the theoretical lower bound defined in Eq. (2.1). Indeed, for these
three instances, LBB–BFS(G,V0 ) > T LB(G,V0 ) (Table A.1). Additionally, BRKGA_FRFS used
less CPU time to prove the optimal solution than all ILP model variants.
Table 2.5: Comparative results of BRKGA_FRFS and ILPs.
de Sousa et al’s ILP
Instance
H10,30
H11,50
H20,50
H21,50
H2,100
H2,17
H2,30
H2,50
H3,17
H3,30
H3,50
H5,17
H6,17
H7,17
H8,30
H9,30
BRKGA_FRFS
No Bounds
Lower Bound - Eq. (2.1) Lower Bound - Eq. (2.2) Upper Bound Both Bounds
Best
t (s)
Best
5*
8.91
6
3600
6*
6
t (s)
Best
t (s)
Best
5*
44.01
6*
2431.80
890.20
6*
3600
6*
50*
9.71
t (s)
Best
t (s)
Best
Avg.
t(s)
5*
43.63
6*
2472.72
5*
1.71
5*
0.11
5*
5.00
6
3600
6*
0.17
6*
6.00
0.07
6
3600
6*
0.01
6*
6.00
0.07
6
3600
6*
0.01
6*
6.00
0.13
50*
0.76
50*
0.76
50*
50.00
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
0.07
6*
0.07
6*
50*
7.71
50*
9*
0.02
9*
0.02
9*
0.02
9*
0.01
9*
0.01
9*
9.00
15*
0.08
15*
0.08
15*
< 0.01
15*
0.02
15*
0.02
15*
15.00
25*
1.06
25*
0.82
25*
0.01
25*
0.09
25*
0.09
25*
25.00
5*
0.09
5*
0.03
5*
0.03
5*
0.01
5*
< 0.01
5*
5.00
9*
0.72
9*
0.61
9*
0.36
9*
0.03
9*
0.03
9*
9.00
14*
3.23
14*
2.33
14*
0.64
14*
0.09
14*
0.09
14*
14.00
5*
0.61
5*
0.52
5*
5.00
5*
0.36
5*
5*
5.00
5*
61.49
5*
5*
5*
134.06
5*
< 0.01
< 0.01
< 0.01
5*
5*
< 0.01
< 0.01
< 0.01
5*
0.61
< 0.01
< 0.01
< 0.01
5*
5*
5*
5.00
5*
3.78
5*
1.42
5*
1.42
5*
0.20
5*
0.10
5*
5.00
0.02
5*
14.72
5*
29.79
5*
29.73
5*
8.43
5*
0.08
5*
5.00
< 0.01
5*
# Best
16
16
16
16
16
16
Avg. t (s)
512.19
157.42
159.30
684.12
0.09
0.01
Minimum Broadcast Time
2.3.4
27
Experiments on others instances from literature
Table 2.6 compares the methods on the instances we were able to reproduce from the works of
Harutyunyan and Wang (2010); Harutyunyan and Jimborean (2014). In the experiments shown
in this table, we use the BRKGA version with SCHA decoding. The results for NTBA and NEWH
were reproduced from their original papers (Harutyunyan and Wang, 2010; Harutyunyan and
Jimborean, 2014). A hyphen in Table 2.6 indicates we do not have the method result for an
instance or the method could not produce a feasible solution. Once again, the results show that
BRKGA is competitive in terms of both solution quality and computational efficiency relative the
best performing methods in the literature.
Table 2.6: Comparative results of NEWH, NTBA, ILP, ACS and BRKGA
Instance
HC5
HC6
HC7
HC8
HC9
HC10
CCC3
CCC4
CCC5
CCC6
CCC7
DB4
DB5
DB6
DB7
DB8
DB9
DB10
SE4
SE5
SE6
SE7
SE8
SE9
SE10
Treeblock
NTBA
NEWH
Best
Best
Best
5
5
6
7
ILP (Both bounds)
ACS
BRKGA
Best (GAP)
t (s)
Best
Avg.
t (s)
Best
Avg.
t (s)
5
5*
5.00
5.00
6*
6.00
< 0.01
< 0.01
5*
6*
< 0.01
< 0.01
5*
6
6*
6.00
< 0.01
< 0.01
7
9
7
7*
0.02
7*
7.00
0.01
7*
7.00
0.16
8
11
8
8*
0.07
8*
8.00
0.01
9
9.00
60.00
60.00
9
14
9
9*
0.39
9*
9.00
0.02
10
10.00
10
15
10
10*
2.02
10*
10.00
0.23
11
11.00
60.00
-
6
7
6*
0.04
6*
6.00
0.04
6*
6.00
-
9
9
9*
0.14
9*
9.00
0.01
9*
9.00
-
11
12
11*
0.57
12
12.00
60.00
11*
11.00
< 0.01
< 0.01
< 0.01
-
14
14
13*
4.82
14
14.90
60.00
13*
13.90
55.83
-
16
17
-
3600.00
17
17.80
60.00
16
16.00
1.37
4
5
5
-
3600.00
5
5.00
60.00
5
5.00
60.00
< 0.01
< 0.01
7
7
7
-
3600.00
6*
6.00
1.27
6*
6.00
8
8
8
-
3600.00
8
8.00
0.03
8
8.00
12
10
10
-
3600.00
10
10.00
60.00
9
9.00
0.60
12
12
12
-
3600.00
12
12.00
60.00
11
11.00
< 0.01
< 0.01
14
13
13
-
3600.00
14
14.00
60.00
13
13.00
15
15
15
-
3600.00
16
16.00
60.00
14
14.20
21.48
-
7
7
7*
0.02
7
7.00
< 0.01
7
7.00
< 0.01
< 0.01
< 0.01
< 0.01
-
9
9
9*
0.02
9*
9.00
0.01
9*
9.00
-
11
11
11*
0.05
11*
11.00
0.01
11*
11.00
-
13
13
13*
0.25
13*
13.00
0.01
13*
13.00
-
15
15
15*
1.21
15*
15.00
0.04
15*
15.00
0.34
-
18
18
17*
12.65
17*
17.00
0.04
18
18.00
60.00
-
20
20
-
3600.00
19*
19.00
0.07
20
20.00
60.00
# Best
8/13
13/25
15/25
16/25
17/25
19/25
# Best Avg.
8/13
13/25
15/25
16/25
17/25
18/25
Avg. t (s)
-
-
-
1296.89
19.27
17.59
2.3.5
Experiments on Small-World and synthetic instances
Table 2.7 compares BRKGA_FRFS with ACS and the ILP model with both bounds in the SmallWorld and synthetic instances. In this table, we have added a GAP information for instances in
which the ILP model did not prove the optimal solution.
Minimum Broadcast Time
28
Table 2.7: Comparative results of ACS, ILP and BRKGA_FRFS
ACS
Instance
B4
B5
B6
B7
B8
B9
B5 ∪ G(32, 5%)
B5 ∪ G(32, 7.5%)
B5 ∪ G(32, 10%)
B5 ∪ G(32, 15%)
B5 ∪ G(32, 20%)
B5 ∪ G(32, 25%)
B6 ∪ G(64, 5%)
B6 ∪ G(64, 7.5%)
B6 ∪ G(64, 10%)
B6 ∪ G(64, 15%)
B6 ∪ G(64, 20%)
B6 ∪ G(64, 25%)
B7 ∪ G(128, 5%)
B7 ∪ G(128, 7.5%)
B7 ∪ G(128, 10%)
B7 ∪ G(128, 15%)
B7 ∪ G(128, 20%)
B7 ∪ G(128, 25%)
B8 ∪ G(256, 5%)
B8 ∪ G(256, 7.5%)
B8 ∪ G(256, 10%)
B8 ∪ G(256, 15%)
B8 ∪ G(256, 20%)
B8 ∪ G(256, 25%)
B9 ∪ G(512, 5%)
B9 ∪ G(512, 7.5%)
B9 ∪ G(512, 10%)
B9 ∪ G(512, 15%)
B9 ∪ G(512, 20%)
B9 ∪ G(512, 25%)
B10 ∪ G(1024, 5%)
B10 ∪ G(1024, 7.5%)
B10 ∪ G(1024, 10%)
B10 ∪ G(1024, 15%)
B10 ∪ G(1024, 20%)
B10 ∪ G(1024, 25%)
ILP (Both bounds)
BRKGA_FRFS
Best
Avg.
t (s)
Best (GAP)
t (s)
Best
Avg.
t (s)
4*
4.00
4.00
< 0.01
5*
5.00
2.03
6*
6.00
< 0.01
< 0.01
< 0.01
4*
5.00
6*
6.80
55.04
7*
7.00
< 0.01
< 0.01
< 0.01
< 0.01
4*
5*
7*
0.01
8
8.80
60.00
8*
8.00
0.01
8*
0.06
10
10.60
60.00
9*
9.00
0.08
9*
0.35
12
12.30
60.00
6
6.00
60.00
5*
0.01
5*
5.90
58.45
6
6.00
60.00
5*
0.06
5*
5.10
15.21
5*
5.00
2.28
5*
0.02
5*
5.00
0.15
5*
5.00
2.25
5*
0.02
5*
5.00
0.02
5*
5.00
0.03
5*
0.11
5*
5.00
5*
5.00
0.05
5*
0.15
5*
5.00
< 0.01
< 0.01
7
7.00
60.00
6*
1.02
7
7.00
60.00
7
7.00
60.00
6*
2.34
7
7.00
60.00
7
7.00
60.00
6*
0.49
6*
6.00
3.65
6*
6.00
5.57
6*
1.17
6*
6.00
0.02
6*
6.00
0.68
6*
1.78
6*
6.00
6*
6.00
0.32
6*
2.16
6*
6.00
< 0.01
< 0.01
8
8.00
60.00
7*
65.50
8
8.00
60.00
8
8.00
60.00
7*
81.61
8
8.00
60.00
8
8.00
60.00
7*
45.78
7*
7.00
2.06
8
8.00
60.00
7*
1643.97
7*
7.00
0.04
7*
7.00
2.09
7*
204.40
7*
7.00
0.01
7*
7.00
1.41
7*
239.89
7*
7.00
9
9.00
< 0.01
9(11.11%)
3600
9
9.00
< 0.01
< 0.01
9
9.00
60.00
-
3600
8*
8.90
56.79
9
9.00
60.00
-
3600
8*
8.00
16.23
9
9.00
60.00
-
3600
8*
8.00
0.07
9
9.00
60.00
-
3600
8*
8.00
0.03
8*
8.00
2.23
-
3600
8*
8.00
0.01
10
10.00
0.01
10(10.00%)
3600
10
10.00
10
10.00
0.03
10(10.00%)
3600
10
10.00
< 0.01
< 0.01
10
10.00
60.00
-
3600
9*
9.30
35.79
10
10.00
60.00
-
3600
9*
9.00
0.53
10
10.00
60.00
-
3600
9*
9.00
0.07
10
10.00
60.00
-
3600
9*
9.00
0.02
11
11.00
0.11
-
3600
11
11.00
0.01
11
11.00
0.22
-
3600
11
11.00
0.01
11
11.00
60.00
-
3600
10*
10.50
41.54
5*
6*
11
11.00
60.00
-
3600
10*
10.00
3.64
10*
10.00
2.58
-
3600
10*
10.00
0.27
11
11.00
60.00
-
3600
10*
10.00
0.08
SW-100-3-0d1-trial1
61*
61.00
0.09
61*
0.70
61*
61.00
0.01
SW-100-3-0d2-trial1
31*
31.00
0.02
31*
0.33
31*
31.00
SW-100-3-0d2-trial3
31*
31.00
0.04
31*
0.33
31*
31.00
< 0.01
< 0.01
SW-100-4-0d1-trial1
10
10.00
60.00
9*
0.84
9*
9.00
0.24
SW-100-4-0d1-trial2
9
9.00
60.00
8*
0.79
8*
8.70
45.89
SW-100-4-0d1-trial3
11
11.00
60.00
10*
0.77
10*
10.00
0.07
SW-100-4-0d2-trial1
9
9.00
60.00
8*
1.28
8*
8.90
57.91
SW-100-4-0d2-trial2
9
9.00
60.00
8*
3.78
9
9.00
60.00
SW-100-4-0d2-trial3
9*
9.00
1.41
9*
1.88
9*
9.00
< 0.01
SW-100-4-0d3-trial1
9
9.00
60.00
8*
1.20
8*
8.00
1.43
Continued on next page
Minimum Broadcast Time
29
Table 2.7 – continued from previous page
ACS
Instance
Best
Avg.
ILP (Both bounds)
BRKGA_FRFS
t (s)
Best (GAP)
t (s)
Best
Avg.
t (s)
SW-100-4-0d3-trial2
8*
8.00
0.90
8*
16.23
8*
8.00
0.01
SW-100-4-0d3-trial3
9
9.00
60.00
8*
0.56
8*
8.00
10.86
SW-100-5-0d1-trial1
10
10.00
60.00
9*
0.56
9*
9.00
5.00
SW-100-5-0d1-trial2
11
11.00
60.00
10*
0.73
10*
10.00
0.05
SW-100-5-0d1-trial3
13
13.00
60.00
12*
0.32
12*
12.00
0.05
SW-100-5-0d2-trial1
10
10.00
60.00
9*
1.59
10
10.00
60.00
SW-100-5-0d2-trial2
10
10.00
60.00
9*
0.42
10
10.00
60.00
SW-100-5-0d2-trial3
9
9.00
60.00
8*
2.62
9
9.00
60.00
SW-100-5-0d3-trial1
9
9.00
60.00
8*
3.22
8*
8.00
0.12
SW-100-5-0d3-trial2
8
8.00
0.36
8(12.50%)
3600
8
8.00
SW-100-5-0d3-trial3
8*
8.00
4.29
8*
11.25
8*
8.00
< 0.01
< 0.01
SW-100-6-0d1-trial1
8
8.00
60.00
7*
4.35
8
8.00
60.00
SW-100-6-0d1-trial2
9
9.00
60.00
8*
870.41
8*
8.00
0.02
SW-100-6-0d1-trial3
9
9.00
60.00
7*
2.94
8
8.00
60.00
SW-100-6-0d2-trial1
8
8.00
60.00
7*
1.64
7*
7.10
17.88
SW-100-6-0d2-trial2
8
8.00
60.00
7*
0.11
7*
7.00
0.81
SW-100-6-0d2-trial3
8
8.00
60.00
7*
1.65
7*
7.00
6.58
SW-100-6-0d3-trial1
8
8.00
60.00
7*
1.53
7*
7.00
1.31
SW-100-6-0d3-trial2
8
8.00
60.00
7*
1.28
7*
7.00
0.56
SW-100-6-0d3-trial3
8
8.00
60.00
7*
0.86
7*
7.00
0.11
SW-1000-3-0d2-trial1
96
96.00
60.00
-
3600
89*
89.00
14.42
SW-1000-3-0d2-trial2
94
94.00
60.00
-
3600
88*
88.00
9.26
SW-1000-3-0d3-trial2
96
96.00
60.00
-
3600
87*
87.00
9.39
SW-1000-4-0d1-trial1
19
19.00
60.00
-
3600
17
17.00
5.68
SW-1000-4-0d1-trial2
20
20.00
60.00
-
3600
17
17.90
55.04
SW-1000-4-0d1-trial3
20
20.00
60.00
-
3600
18
18.00
5.07
SW-1000-4-0d2-trial1
15
15.00
60.00
-
3600
14
14.30
41.90
SW-1000-4-0d2-trial2
16
16.00
60.00
-
3600
14
14.80
49.96
SW-1000-4-0d2-trial3
16
16.00
60.00
-
3600
15
15.20
28.21
SW-1000-4-0d3-trial1
14
14.00
60.00
12(16.67%)
3600
13
13.00
60.00
SW-1000-4-0d3-trial3
14
14.00
60.00
13(23.08%)
3600
13
13.00
0.37
SW-1000-5-0d1-trial1
20
20.00
60.00
-
3600
17
17.10
15.22
SW-1000-5-0d1-trial2
20
20.00
60.00
-
3600
17
17.00
13.70
SW-1000-5-0d1-trial3
18
18.00
60.00
15(24.38%)
3600
16
16.00
60.00
SW-1000-5-0d2-trial1
16
16.00
60.00
-
3600
15
15.00
0.10
SW-1000-5-0d2-trial2
16
16.00
60.00
-
3600
14
14.90
54.75
SW-1000-5-0d2-trial3
15
15.00
60.00
-
3600
14
14.00
1.25
SW-1000-5-0d3-trial1
14
14.00
60.00
12(16.67%)
3600
13
13.90
60.00
SW-1000-5-0d3-trial2
14
14.00
60.00
-
3600
13
13.20
26.52
SW-1000-5-0d3-trial3
14
14.00
17.22
-
3600
14
14.00
0.04
SW-1000-6-0d1-trial1
16
16.00
60.00
-
3600
14
14.00
16.05
SW-1000-6-0d1-trial2
15
15.00
60.00
-
3600
13
13.90
57.65
SW-1000-6-0d1-trial3
14
14.00
60.00
-
3600
13
13.00
6.31
SW-1000-6-0d2-trial1
13
13.00
60.00
-
3600
12
12.00
0.13
SW-1000-6-0d2-trial2
14
14.00
60.00
-
3600
13
13.00
0.01
SW-1000-6-0d2-trial3
13
13.00
60.00
-
3600
12
12.00
0.24
SW-1000-6-0d3-trial1
12
12.00
0.12
-
3600
12
12.00
0.01
SW-1000-6-0d3-trial2
12
12.00
5.33
-
3600
12
12.00
0.01
SW-1000-6-0d3-trial3
12
12.00
3.99
-
3600
12
12.00
0.01
Avg. t (s)
40.93
1742.87
17.94
# Best
33
61
85
# Best Avg.
33
61
79
Minimum Broadcast Time
30
The results in Table 2.7 confirm the robustness of BRKGA_FRFS and its superiority over ACS
and the ILP model. Even with an upper bound set by BRKGA_FRFS, the ILP model could not
produce any feasible results for instances with 256 vertices. BRKGA_FRFS proved the optimal
solution in 56 instances, whereas this number was 53 for the ILP model. Moreover, our algorithm
outperformed ACS in terms of both solution quality and CPU time. It attained the best solution in
85 out of the 101 instances. It is worthwhile mentioning that the synthetic instances proposed
in this paper are indeed very challenging, as the ILP model could only solve a small portion
of them. Hence, we think the proposed benchmark with known optima is a very good one to
evaluate future new exact methods.
2.3.6
Experiments with SCHA decoding and the proposed matheuristic
As shown in the previous results, our basic BRKGA_FRFS algorithm outperforms the bestperforming algorithms in the literature. In this subsection, we show that BRKGA_FRFS results
can be improved using SCHA decoding and our matheuristic. Table 2.8 compares: (i) BRKGA
without SCHA (BRKGA_FRFS), (ii) BRKGA with SCHA, (iii) proposed matheuristic without SCHA
(BRKGA_FRFS+ILP), and (iv) proposed matheuristic with SCHA (BRKGA+ILP).
Table 2.8: Comparative results of BRKGAs and hybrids
BRKGA_FRFS
Instance
B4
B5
B6
B7
B8
B9
B5 ∪ G(32, 5%)
B5 ∪ G(32, 7.5%)
B5 ∪ G(32, 10%)
B5 ∪ G(32, 15%)
B5 ∪ G(32, 20%)
B5 ∪ G(32, 25%)
B6 ∪ G(64, 5%)
B6 ∪ G(64, 7.5%)
B6 ∪ G(64, 10%)
B6 ∪ G(64, 15%)
B6 ∪ G(64, 20%)
B6 ∪ G(64, 25%)
B7 ∪ G(128, 5%)
B7 ∪ G(128, 7.5%)
B7 ∪ G(128, 10%)
B7 ∪ G(128, 15%)
B7 ∪ G(128, 20%)
B7 ∪ G(128, 25%)
B8 ∪ G(256, 5%)
B8 ∪ G(256, 7.5%)
BRKGA
Best
Avg.
t (s)
Best
4*
4.00
< 0.01
5*
5.00
2.03
BRKGA_FRFS+ILP
BRKGA+ILP
Avg.
t (s)
Best
Avg.
t (s)
Best
Avg.
t (s)
4*
4.00
4*
4.00
< 0.01
4*
4.00
5*
5.00*
5*
5.00
0.05
5*
5.00
6*
6.10
6.25
6*
6.00
7*
7.20
7.15
7*
7.00
8*
8.00
6.02
8*
8.00
9*
9.30
40.91
9*
6*
6.80
55.04
6*
6.00
8
8.80
60.00
7*
7.00
10
10.60
60.00
8*
8.00
12
12.30
60.00
9*
9.00
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
9.00
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
5*
5.90
58.45
5*
5.10
19.41
5*
5.00
0.12
5*
5.00
0.17
5*
5.10
15.21
5*
5.00
3.45
5*
5.00
0.25
5*
5.00
0.22
5*
5.00
0.15
5*
5.00
0.04
5*
5.00
0.14
5*
5.00
0.04
5*
5.00
0.02
5*
5.00
0.06
5*
5.00
0.05
5*
5.00
0.09
5*
5.00
5*
5.00
5.00
5.00
5*
5.00
5*
5.00
< 0.01
< 0.01
5*
5.00
< 0.01
< 0.01
5*
5*
< 0.01
< 0.01
5*
5.00
< 0.01
< 0.01
7
7.00
60.00
7
7.00
60.00
6*
6.10
9.96
6*
6.00
5.47
7
7.00
60.00
7
7.00
60.00
6*
6.00
6.77
6*
6.00
11.97
6*
6.00
3.65
6*
6.00
4.58
6*
6.00
3.87
6*
6.00
3.69
6*
6.00
0.02
6*
6.00
0.03
6*
6.00
0.02
6*
6.00
0.03
6*
6.00
6*
6.00
6.00
6.00
6.00
6*
6.00
6*
6.00
6*
6.00
8.00
8
8.00
8
8.00
< 0.01
< 0.01
< 0.01
6*
8
< 0.01
< 0.01
< 0.01
6*
6*
< 0.01
< 0.01
< 0.01
8
8.00
< 0.01
< 0.01
< 0.01
8
8.00
60.00
7*
7.80
52.93
8
8.00
60.00
8
8.00
60.00
7*
7.00
2.06
7*
7.00
6.25
7*
7.00
23.98
7*
7.40
33.13
7*
7.00
0.04
7*
7.00
0.07
7*
7.00
0.05
7*
7.00
0.08
7*
7.00
0.01
7*
7.00
0.01
7*
7.00
0.01
7*
7.00
0.01
7*
7.00
7*
7.00
7*
7.00
7.00
9.00
9
9.00
< 0.01
< 0.01
7*
9
< 0.01
< 0.01
9
9.00
< 0.01
< 0.01
8*
8.90
55.27
9
9.00
60.00
8*
8.90
57.20
9
9.00
< 0.01
< 0.01
8*
8.90
56.79
Continued on next page
Minimum Broadcast Time
31
Table 2.8 – continued from previous page
BRKGA_FRFS
Instance
BRKGA
BRKGA_FRFS+ILP
BRKGA+ILP
Best
Avg.
t (s)
Best
Avg.
t (s)
Best
Avg.
t (s)
Best
Avg.
t (s)
8*
8.00
16.23
8*
8.30
34.42
8*
8.40
38.81
8*
8.60
42.42
8*
8.00
0.07
8*
8.00
0.29
8*
8.00
0.08
8*
8.00
0.30
8*
8.00
0.03
8*
8.00
0.04
8*
8.00
0.04
8*
8.00
0.05
8*
8.00
0.01
8*
8.00
0.01
8*
8.00
0.01
8*
8.00
0.01
10
10.00
10
10.00
10.00
10.00
10
10.00
10
10.00
< 0.01
< 0.01
10
10.00
< 0.01
< 0.01
10
10
< 0.01
< 0.01
10
10.00
< 0.01
< 0.01
9*
9.30
35.79
9*
9.70
50.77
9*
9.50
38.45
9*
9.70
51.38
9*
9.00
0.53
9*
9.00
1.05
9*
9.00
0.62
9
9.00
1.18
9*
9.00
0.07
9*
9.00
0.09
9*
9.00
0.08
9*
9.00
0.10
9*
9.00
0.02
9*
9.00
0.03
9*
9.00
0.03
9*
9.00
0.03
11
11.00
0.01
11
11.00
0.01
11
11.00
0.01
11
11.00
0.02
11
11.00
0.01
11
11.00
0.01
11
11.00
0.02
11
11.00
0.01
10*
10.50
41.54
11
11.00
60.00
10*
10.50
42.99
11
11.00
60.00
10*
10.00
3.64
10*
10.00
4.58
10*
10.00
4.14
10*
10.00
5.09
10*
10.00
0.27
10*
10.00
0.31
10*
10.00
0.31
10*
10.00
0.36
10*
10.00
0.08
10*
10.00
0.09
10*
10.00
0.09
10*
10.00
0.10
SW-100-3-0d1-trial1
61*
61.00
0.01
61*
61.00
61*
61.00
0.01
61*
61.00
SW-100-3-0d2-trial1
31*
31.00
31.00
31*
31.00
31.00
31.00
31*
31.00
31
31.00
< 0.01
< 0.01
31*
31*
< 0.01
< 0.01
31*
SW-100-3-0d2-trial3
31*
31.00
< 0.01
< 0.01
< 0.01
SW-100-4-0d1-trial1
9*
9.00
0.24
9*
9.00
< 0.01
< 0.01
< 0.01
< 0.01
9*
9.00
0.28
9*
9.00
0.01
SW-100-4-0d1-trial2
8*
8.70
45.89
8*
8.00
3.10
8*
8.00
1.44
8*
8.00
1.42
SW-100-4-0d1-trial3
10*
10.00
0.07
10*
10.00
0.01
10*
10.00
0.07
10*
10.00
0.02
SW-100-4-0d2-trial1
8*
8.90
57.91
8*
8.50
43.80
8*
8.00
1.62
8*
8.00
3.18
SW-100-4-0d2-trial2
9
9.00
60.00
9
9.00
60.00
8*
8.00
6.14
8*
8.00
7.48
SW-100-4-0d2-trial3
9*
9.00
< 0.01
9*
9.00
< 0.01
9*
9.00
< 0.01
9*
9.00
< 0.01
B8 ∪ G(256, 10%)
B8 ∪ G(256, 15%)
B8 ∪ G(256, 20%)
B8 ∪ G(256, 25%)
B9 ∪ G(512, 5%)
B9 ∪ G(512, 7.5%)
B9 ∪ G(512, 10%)
B9 ∪ G(512, 15%)
B9 ∪ G(512, 20%)
B9 ∪ G(512, 25%)
B10 ∪ G(1024, 5%)
B10 ∪ G(1024, 7.5%)
B10 ∪ G(1024, 10%)
B10 ∪ G(1024, 15%)
B10 ∪ G(1024, 20%)
B10 ∪ G(1024, 25%)
SW-100-4-0d3-trial1
8*
8.00
1.43
8*
8.00
1.00
8*
8.00
1.01
8*
8.00
0.76
SW-100-4-0d3-trial2
8*
8.00
0.01
8*
8.00
< 0.01
8*
8.00
0.01
8*
8.00
< 0.01
SW-100-4-0d3-trial3
8*
8.00
10.86
8*
8.00
1.44
8*
8.00
1.33
8*
8.00
0.76
SW-100-5-0d1-trial1
9*
9.00
5.00
9*
9.00
0.08
9*
9.00
0.83
9*
9.00
0.10
SW-100-5-0d1-trial2
10*
10.00
0.05
10*
10.00
10.00
0.05
10*
10.00
12*
12.00
0.05
12*
12.00
< 0.01
< 0.01
10*
SW-100-5-0d1-trial3
12*
12.00
0.05
12*
12.00
< 0.01
< 0.01
SW-100-5-0d2-trial1
10
10.00
60.00
10
10.00
60.00
9*
9.00
2.08
9*
9.00
3.34
SW-100-5-0d2-trial2
10
10.00
60.00
10
10.00
60.00
9*
9.00
1.50
9*
9.00
2.45
SW-100-5-0d2-trial3
9
9.00
60.00
9
9.00
60.00
8*
8.00
3.72
8*
8.00
6.96
SW-100-5-0d3-trial1
8*
8.00
0.12
8*
8.00
0.03
8*
8.00
0.13
8*
8.00
0.02
8
8.00
8.00
8.00
8*
8.00
< 0.01
< 0.01
8
8.00
< 0.01
< 0.01
8
8*
8*
8.00
< 0.01
< 0.01
SW-100-5-0d3-trial2
8
8.00
SW-100-5-0d3-trial3
8*
8.00
< 0.01
< 0.01
SW-100-6-0d1-trial1
8
8.00
60.00
8
8.00
60.00
7*
7.50
48.87
7*
7.50
44.86
SW-100-6-0d1-trial2
8*
8.00
0.02
8*
8.00
< 0.01
8*
8.00
0.03
8*
8.00
< 0.01
15.28
SW-100-6-0d1-trial3
8
8.00
60.00
8
8.00
60.00
7*
7.00
13.55
7*
7.00
SW-100-6-0d2-trial1
7*
7.10
17.88
7*
7.20
36.35
7*
7.00
7.39
7*
7.00
8.02
SW-100-6-0d2-trial2
7*
7.00
0.81
7*
7.00
0.35
7*
7.00
5.87
7*
7.00
0.44
SW-100-6-0d2-trial3
7*
7.00
6.58
7*
7.00
8.53
7*
7.00
10.50
7*
7.00
6.92
SW-100-6-0d3-trial1
7*
7.00
1.31
7*
7.00
0.89
7*
7.00
9.88
7*
7.00
5.60
SW-100-6-0d3-trial2
7*
7.00
0.56
7*
7.00
0.40
7*
7.00
4.91
7*
7.00
0.45
SW-100-6-0d3-trial3
7*
7.00
0.11
7*
7.00
0.06
7*
7.00
0.76
7*
7.00
0.08
SW-1000-3-0d2-trial1
89*
89.00
14.42
89*
89.00
0.01
89*
89.00
14.81
89*
89.00
0.02
SW-1000-3-0d2-trial2
88*
88.00
9.26
88*
88.00
0.01
88*
88.00
9.34
88*
88.00
0.01
SW-1000-3-0d3-trial2
87*
87.00
9.39
87*
87.00
0.01
87*
87.00
9.43
87*
87.00
0.02
SW-1000-4-0d1-trial1
17
17.00
60.00
16
16.60
46.05
17
17.00
60.00
16
16.60
44.75
SW-1000-4-0d1-trial2
17
17.90
55.04
17
17.00
0.42
17
17.90
55.05
17
17.00
0.67
SW-1000-4-0d1-trial3
18
18.00
60.00
17
17.80
53.42
18
18.00
60.00
17
17.70
53.47
SW-1000-4-0d2-trial1
14
14.30
41.90
14
14.00
0.02
14
14.30
42.26
14
14.00
0.02
Continued on next page
Minimum Broadcast Time
32
Table 2.8 – continued from previous page
BRKGA_FRFS
Instance
BRKGA
BRKGA_FRFS+ILP
BRKGA+ILP
Best
Avg.
t (s)
Best
Avg.
t (s)
Best
Avg.
t (s)
Best
Avg.
t (s)
SW-1000-4-0d2-trial2
14
14.80
49.96
14
14.00
0.17
14
14.80
49.98
14
14.00
0.17
SW-1000-4-0d2-trial3
15
15.20
28.21
15
15.00
0.01
15
15.20
28.29
15
15.00
0.02
SW-1000-4-0d3-trial1
13
13.00
0.60
13
13.00
0.02
13
13.00
0.60
13
13.00
0.01
SW-1000-4-0d3-trial3
13
13.00
0.37
13
13.00
0.02
13
13.00
0.37
13
13.00
0.02
SW-1000-5-0d1-trial1
17
17.10
15.22
17
17.00
0.05
17
17.10
15.36
17
17.00
0.06
SW-1000-5-0d1-trial2
17
17.00
13.70
17
17.00
0.14
17
17.00
14.96
17
17.00
0.15
SW-1000-5-0d1-trial3
16
16.00
60.00
15
15.00
0.65
16
16.00
60.00
15
15.00
1.09
SW-1000-5-0d2-trial1
15
15.00
60.00
14
14.00
2.39
15
15.00
60.00
14
14.00
2.58
SW-1000-5-0d2-trial2
14
14.90
54.75
14
14.00
0.07
14
14.90
54.77
14
14.00
0.07
SW-1000-5-0d2-trial3
14
14.00
1.25
14
14.00
0.01
14
14.00
1.26
14
14.00
0.02
SW-1000-5-0d3-trial1
13
13.90
55.65
13
13.00
0.05
13
13.90
55.67
13
13.00
0.05
SW-1000-5-0d3-trial2
13
13.20
26.52
13
13.00
0.03
13
13.20
26.64
13
13.00
0.03
SW-1000-5-0d3-trial3
14
14.00
60.00
13
13.00
5.81
14
14.00
60.00
13
13.00
3.22
SW-1000-6-0d1-trial1
14
14.00
16.05
14
14.00
0.39
14
14.10
18.35
14
14.00
0.61
SW-1000-6-0d1-trial2
13
13.90
57.65
13
13.20
28.66
13
13.90
58.20
13
13.00
26.01
SW-1000-6-0d1-trial3
13
13.00
6.31
13
13.00
0.08
13
13.00
7.24
13
13.00
0.08
SW-1000-6-0d2-trial1
12
12.00
0.13
12
12.00
0.02
12
12.00
0.14
12
12.00
0.02
SW-1000-6-0d2-trial2
13
13.00
0.01
13
13.00
0.01
13
13.00
0.01
13
13.00
0.01
SW-1000-6-0d2-trial3
12
12.00
0.24
12
12.00
0.03
12
12.00
0.24
12
12.00
0.03
SW-1000-6-0d3-trial1
12
12.00
0.01
12
12.00
0.01
12
12.00
0.01
12
12.00
0.01
SW-1000-6-0d3-trial2
12
12.00
0.01
12
12.00
0.01
12
12.00
0.01
12
12.00
0.01
SW-1000-6-0d3-trial3
12
12.00
0.01
12
12.00
0.01
12
12.00
0.01
12
12.00
0.01
99
# Best
84
92
94
# Best Avg.
69
85
78
96
Avg. t (s)
18.98
9.98
12.24
5.69
The results in Table 2.8 show that the SCHA decoding positively impacts the search since the
algorithms with SCHA performed better than their counterparts without SCHA. The SCHA refinement gives more accuracy to the BRKGA decoding. Moreover, the results reveal that BRKGA+ILP
compares favorably with BRKGA in both features, solution quality and CPU time. Note that in the
cases BRKGA+ILP missed the best solution, the solution determined by BRKGA+ILP is at most
one unit time longer than the best one. Adding ILP features to the BRKGA has shown a very
feasible approach.
3
Weighted Minimum Broadcast Time
The Weighted Minimum Broadcast Time (WMBT) is a generalization of the MBT with weight in
vertices or/and edges. The WMBT model is more realistic than the MBT. Because the WMBT
can represent transmission delay rates as explained in Section 1.2. We remark that our work
focuses on the telephone model.
There are four variations of the WMBT: (i) classic model (α = 0 and β = 1 for all edges),
(ii) weighted-vertex model (Harutyunyan and Kamali, 2008) (α ≥ 0 and β = 1 for all edges),
(iii) weighted-edge model (Su et al., 2010) (α = 0 and β ≥ 1 for all edges), and (iv) weight-
ed-vertex-and-edge (general) model (α ≥ 0 and β ≥ 1 for all edges). The α and β were defined
in Section 1.2. The first model was presented in Section 2.2. In this chapter, we will propose
solutions for the remaining models.
Figures 3.1–3.3 illustrate an example for each variant of the WMBT. Figure 3.1-a shows a
network with weighted-vertex, such that each vertex has a label and setup phase. Figure 3.1-b
shows an optimal solution of example of the previous example. The values in edges represent
the time that vertex received information.
g1
0
d1
3
d2
1
g1
0
d3
0
(a) Example network with
weighted-vertex
2
d2
1
1
4
d1
3
d3
0
(b) Optimal broadcast solution.
Figure 3.1: Example of weighted-vertex model.
Figure 3.2-a shows a network with a weighted-edge graph. Each edge is associated with a
value representing the transmission time of connection. Similarly, Figure 3.1-b shows optimal
33
Weighted Minimum Broadcast Time
34
solution of the previous example. The values in edges represent the time that each vertex
received information.
g1
3
d2
g1
1
1
1
1
d3
d1
d1
(a) Example network with
weighted-edge
d2
2
3
d3
(b) Optimal broadcast solution.
Figure 3.2: Example of weighted-edge model.
Figure 3.3-a shows an example of a weighted-edge-and-vertex variant. Edges are associated with a transmission time, whereas vertices are associated with a setup time. Figure 3.1-b
shows optimal solution of the previous example.
g1
0
3
d2
1
g1
0
1
1
1
1
6
d3
0
d1
3
d3
0
d1
3
(a) Example network with
weighted-edge-and-vertex
4
d2
1
(b) Optimal broadcast solution.
Figure 3.3: Example of weighted-edge-and-vertex model.
Theorem 9. The weighted-edge, weighted-vertex and weighted-edge-and-vertex Minimum
Broadcast Problems are N P -Complete.
Proof. Restrict each WMTB variant to classical MBT by allowing only instances having we = 1
for all e ∈ E(G) and wv = 0 for all v ∈ V (G).
We remark that the classical MBT can be viewed as telephone or postal models when α = 0
and β = 1 for all edges. Harutyunyan and Kamali (2008) introduced a generalization of the
telephone model with the weighted-vertex model, where each vertex has a different α value.
In both, telephone and postal models, only one transmission can be performed at a time.
Because of this, these models are labeled as 1-broadcast or 1-port. In addition, a model in
which a maximum of k transmission can be performed at a time, it called k-broadcast or k-port
Weighted Minimum Broadcast Time
35
(König and Lazard, 1994). This work aims to study the telephone model as a message-passing
system for the MBT.
We remark that Definitions 1–7 are related to the MBT when |V0 | = 1. However, similar
considerations can be applied, mutatis mutandis, for the WMBT or/and when |V0 | > 1.
3.1
Related Work
Harutyunyan and Kamali (2008); Koh and Tcha (1991) introduced generalizations of the Telephone model. Koh and Tcha (1991) show a polynomial algorithm that optimally solves the
weighted-edge model for the tree graphs. Harutyunyan and Kamali (2008) presented a greedy
algorithm and an evolutionary algorithm for the general graphs with setup phase (weightedvertex). The greedy algorithm outperformed the evolutionary algorithm. Averbuch et al. (2000)
propose polynomial algorithms for weighted-vertex and weighted-edge trees, but the cost function is computed differently than Garey and Johnson (1979); Harutyunyan and Kamali (2008);
Koh and Tcha (1991). To the best of the authors’ knowledge, there are no exact algorithms
for any generalization of the WMBT. Also, there are no heuristic or metaheuristic algorithms for
general graphs with transmission time and setup phase (weighted-vertex-and-edge).
Harutyunyan and Kamali (2008) introduce a greedy algorithm for the weighted-vertex model,
which we will show in Algorithm 6. This algorithm is an adaptation of Dijkstra’s algorithm for
Weighted-Vertex MBT. It starts setting the cost of all vertices to infinity, creates sets to informed
and uninformed vertices, and sets the cost of source v0 (lines 2-6). Next, the procedure may be
repeated if there is any uninformed vertex, choosing an edge with the least weight that does not
cycle in the solution (lines 7-12). Finally, broadcastTime gets the biggest cost of vertices (line
13). Overall, the worst-case running time of this algorithm is O(|V | · |E|).
Harutyunyan and Kamali (2008) described that even if it finds the optimal broadcast tree, the
algorithm does not guarantee that the WMBT schedule will be the optimum. In Section 3.2.4, we
describe an exact algorithm for the WMBT for trees.
We present a summarized comparison of the literature’s approaches. Table 3.1 lists the main
articles about WMBT in the literature.
Table 3.1: List of articles about WMBT in the literature.
Article
Approach
Bar-Noy et al. (2000)
Description of message-passing systems
Harutyunyan and Kamali (2008)
Heuristic and metaheuristic algorithm
Su et al. (2016)
Polynomial time algorithm
Observation
For weighted-vertex.
For edge-vertex, when graph is a tree and |V0 | = 1.
Weighted Minimum Broadcast Time
36
Algorithm 6: Greedy algorithm for Weighted-Vertex-MBT
Input : Weighted Vertex Undirected graph: G = (V, E,Wv ),
Source vertex: v0
Output: Broadcast time: broadcastTime
GreedyAlgorithm(G, v0 )
for v ∈ V do
3
cost[v] ← ∞
1
2
4
5
6
7
8
I ← {v0 }
U ← V \ {v0 }
cost[v0 ] ← Wv [v0 ]
while U 6= 0/ do
vα , vβ ← argmin(c(vi ) + w(v j ))
// let I be a set
// let U be a set
i∈I, j∈U,(i, j)∈E
9
10
11
12
13
cost(vβ ) ← cost(vα ) + w(vβ ) + 1
cost(vα ) ← cost(vα ) + 1
I ← I ∪ {vβ }
U ← U \ {vβ }
broadcastTime ←max (cost[v])
// Get higher cost
v∈V
14
15
return broadcastTime
3.2
Algorithmic approaches for the WMBT
In this Section, we will show our contributions. First, we will explain about our mathematical
models for WMBTs in Section 3.2.1. Section 3.2.2 describes a lower bound algorithm for the
WMBT. Section 3.2.3 shows an exact greedy algorithm for the WMBT for forests. Section 3.2.4
presents a greedy algorithm for the WMBT for general instances. Section 3.2.5 describes a
reduce rule for the WBMT. Finally, Section 3.2.6 some decoders for BRKGA for the WMBT.
3.2.1
Mathematical models for WMBT
To the best of the author’s knowledge, there is no mathematical model for WMBTs. In this
section, we proposed a mathematical model for each variant of the WMBT: (i) weighted-vertex model, (ii) weighted-edge model, and (iii) general model. These mathematical models are
extensions of the model proposed by de Sousa et al. (2018) for the MBT.
3.2.1.1
Weighted-vertex model
Let G = (V, E) be a simple graph, N(i) the set of neighboring vertices of vertex i ∈ V , and Wv
the list of weights for each vertex of G. In our model, Ki is a binary constant indicating whether
or not vertex i is in V0 , and Tmax a constant that represents an upper bound on the time in which
a vertex receives the message (e.g., Tmax = ( ∑ Wv (v)) + |V | − |V0 | is the trivial bound). Finally,
v∈V
Weighted Minimum Broadcast Time
37
define T as a decision variable that represents the minimum broadcast time, and xti j as a binary
variable that has value 1 if the vertex i starts transmission of the message to the vertex j in time
t and 0, otherwise. Based on these elements, our ILP model is defined as follows:
min T
(3.1)
Tmax
s. t Ki +
∑ ∑ xtji = 1
j∈N(i) t=0
∑ xti j = 0
j∈N(i)
∑ xti j ≤ 1
j∈N(i)
∀i ∈ V
(3.2)
∀i ∈ V0 , ∀t ∈ [0,Wv (i))
(3.3)
∀i ∈ V, ∀t ∈ [0, Tmax ]
(3.4)
∀(i, j) ∈ E, ∀t ∈ [0, Tmax ]
(3.5)
∀(i, j) ∈ E
(3.6)
t−1−Wv (i)
xti j ≤ Ki +
∑
∑
k∈N(i)\{ j}
τ=0
τ
xki
Tmax
∑ (t + 1 +Wv( j)) · xti j ≤ T
t=0
T ∈N
xti j ∈ B
(3.7)
∀(i, j) ∈ E, ∀t ∈ [0, Tmax ]
(3.8)
The objective function (3.1) minimizes the weighted broadcast time. Constraints (3.2) limit
each vertex to receive only one message or start with its. Constraints (3.3) imply that each
source sends the message after its setup phase. Constraints (3.4) require that each vertex
sends at most one message to a neighbor at each time t . Constraints (3.5) establish that each
vertex can only transmit if it has already received the message. Constraints (3.6) state that the
value of T must be greater than or equal to the time of any transmission. Finally, Constraints
(3.7) and (3.8) define the domain of the decision variables.
3.2.1.2
Weighted-edge model
In the weighted-edge variation, there is a list We with weights for each edge of the graph. The
ILP model for this variation is as follows:
min T
(3.9)
Tmax
s. t
∑ ∑ xtji = 1
∀i ∈ V
(3.10)
j∈N(i) t=1
∑ xti j ≤ 1
∀i ∈ V, ∀t ∈ [0, Tmax ]
(3.11)
Ki +
j∈N(i)
Weighted Minimum Broadcast Time
38
t−We ((k,i))
xti j ≤ Ki +
τ
xki
(3.12)
τ=0
∀(i, j) ∈ E, ∀t ∈ [0, Tmax ]
∑ (t +We((i, j))) · xti j ≤ T
∀(i, j) ∈ E
(3.13)
∀(i, j) ∈ E, ∀t ∈ [0, Tmax ], ∀k ∈ N(i), ∀τ ∈ [t + 1,t +We (i, j)]
(3.14)
∑
∑
k∈N(i)\{ j}
Tmax
t=0
τ
≤ 1 − xti j
xik
T ∈N
(3.15)
xti j ∈ B
∀(i, j) ∈ E, ∀t ∈ [0, Tmax ]
(3.16)
The objective function (3.9) minimizes the weighted broadcast time. Constraints (3.10) limit
each vertex to receive only one message or start with its, where Tmax = ∑ We (e) is the trivial
e∈E
upper bound. Constraints (3.11) require that each vertex sends at most one message to a
neighbor at each time t . Constraints (3.12) establish that each vertex can only transmit if it has
already received the message. Constraints (3.13) state that the value of T must be greater than
or equal to the time of any transmission. Constraints (3.14) mean each vertex wait We (i, j) units
of time for a new transmission. Finally, Constraints (3.15) and (3.16) define the domain of the
decision variables.
3.2.1.3
General model
The general model is based on the previous ones and combines them as follows:
min T
(3.17)
Tmax
s. t
Ki +
∑ ∑ xtji = 1
∀i ∈ V (3.18)
j∈N(i) t=1
∑ xti j = 0
∀i ∈ V0 , ∀t ∈ [0,Wv (i)) (3.19)
j∈N(i)
∑ xti j ≤ 1
∀i ∈ V, ∀t ∈ [0, Tmax ] (3.20)
j∈N(i)
t−We ((k,i))−Wv (i)
xti j ≤ Ki +
τ
xki
∀(i, j) ∈ E, ∀t ∈ [0, Tmax ] (3.21)
∑ (t +We((i, j)) +Wv(( j))) · xti j ≤ T
∀(i, j) ∈ E (3.22)
∑
∑
k∈N(i)\{ j}
τ=0
Tmax
t=0
τ
xik
≤ 1 − xti j
T ∈N
xti j ∈ B
∀(i, j) ∈ E, ∀t ∈ [0, Tmax ], ∀k ∈ N(i), ∀τ ∈ [t + 1,t +We ((i, j))] (3.23)
(3.24)
∀(i, j) ∈ E, ∀t ∈ [0, Tmax ] (3.25)
Weighted Minimum Broadcast Time
39
The objective function (3.17) minimizes the weighted broadcast time. Constraints (3.18) limit
each vertex to receive only one message or start with its, where Tmax = ∑ We (e) + ∑ Wv (v) is
e∈E
v∈V
the trivial bound. Constraints (3.19) imply that each source sends the message after its setup
phase. Constraints (3.20) require that each vertex sends at most one message to a neighbor
at each time t . Constraints (3.21) establish that each vertex can only transmit if it has already
received the message. Constraints (3.22) state that the value of T must be greater than or equal
to the time of any transmission. Constraints (3.23) mean each vertex wait We (i, j) units of time
for a new transmission. Finally, Constraints (3.24) and (3.25) define the domain of the decision
variables.
For the remainder of this work, we will consider only the general model as the WMBT.
3.2.2
Lower bound algorithm for the WMBT
We have already commented on the importance of bounds in Section 2.2.2. Harutyunyan and
Kamali (2008) proposed a lower bound given by d + (d + 1) · wmin , where d is the maximum distance of sources to other vertices and wmin is min(Wv (v)). To the best of the author’s knowledge,
v∈V
there are no works about bounds for weighted-edge and weighted-edge-and-vertex models.
Clearly, ∑ We (e) + ∑ Wv (v) is an upper bound for the optimal broadcast time. However,
e∈E
v∈V
this upper bound value is not tight, because, this sum can be a very high value. Consequently,
for exact models, a large upper bound makes the solver require a lot of memory to solve the
problem exactly.
Algorithm 7 calculates an upper bound for the WMBT. Its main objective is to find the maximum shortest path between a target vertex and its nearest source. Note that a straightforward
implementation of LBB-Dijkstra, i.e., applying a Dijkstra’s algorithm on each v ∈ V0 , would
require O(|V0 | · (|V | + |E| · log(|V |))). But, the worst-case running time of LBB-Dijkstra is
O(|V | + |E| · log(|V |).
Theorem 10. Algorithm 7 returns a lower bound for the optimum of the MBT with input graph
G = (V, E), positive edge weights We , non-negative vertex weights Wv and source set V0 .
Proof. Let b∗ be the optimum an instance G(V, E,We ,Wv ), V0 and z be the value returned by the
LBB-Dijkstra algorithm. Consider that v ∈ V0 is the closest vertex of V0 to a vertex ` ∈ V , such
that the distance between them is exactly z. We need at least z distance to reach ` from any
vertex in V0 . Therefore, z ≤ b∗ , i.e., z is a lower bound for the optimum MBT value.
3.2.3
Exact greedy algorithm for the WMBT for forest
In this section, we extend the algorithm proposed by Su et al. (2016). The original algorithm
solves the weighted-vertex MBT for trees. In our extension, both vertices and edges have
Weighted Minimum Broadcast Time
40
Algorithm 7: Lower bound algorithm for WMBT.
Input : Undirected graph: G = (V, E),
Positive edge weights: We ,
Non-negative vertex weights: Wv ,
Source set: V0
Output: Lower bound to broadcast: lowerBound
LBB-Dijkstra(G,Wv ,We ,V0 )
2
for v ∈ V do
3
dist[v] ← ∞
1
4
5
6
7
8
9
S ← 0/
// let S be an set
for v ∈ V0 do
dist[v] ← 0 +Wv [v]
S ← S ∪ {v}
while S 6= 0/ do
v ← argmin(dist[u])
// Get the vertex with lower distance
u∈S
10
11
12
S ← S \ {v}
for all (v, u) ∈ E do
if dist[u] > dist[v] + We [(v, u)] +Wv [u] then
13
dist[u] ← dist[v] + We [(v, u)] +Wv [u]
14
S ← S ∪ {u}
15
lowerBound ←max (dist[v])
// Get higher distance
v∈V
16
return lowerBound
weights. Our contribution is illustrated in Algorithm 8 with an underline. For the remainder of
this work, we will label Algorithm 8 as Weighted-SCHA.
3.2.4
Greedy algorithm for the WMBT for general instances
In this section, we propose an extension for the algorithm of Harutyunyan and Kamali (2008)
(Algorithm 6). We improve this algorithm by considering multi-source graphs and also by allowing
weights on both vertices and edges. The differences from the original algorithm are highlighted
with rectangles in Algorithm 9. Note that our algorithm refines the greedy solution by applying the
Weighted-SCHA algorithm (line 17). Moreover, our algorithm ensures the optimal solution if the
input graph is a tree. Overall, the worst-case running time of the algorithm remains O(|E| · |V |).
3.2.5
Reducing rules
In this section, we propose a reducing rule to improve the performance of heuristics for WMBT.
The idea is to reduce the search space by removing edges that do not belong to any optimal
solution. Consequently, the probability of finding an optimal solution increases. The proposed
Weighted Minimum Broadcast Time
41
Algorithm 8: WMBT for forest instances.
Input : Weighted forest: F = (V, E, S,Wv ,We )
Output: Total step time to broadcast: broadcastTime
WMBT-Forest(F)
2
broadcastTime ← 0
3
for each v ∈ V do
4
vstd[v] ← f alse
1
5
6
7
8
for each r ∈ R do
Tr ← GetTree(F ,r)
broadcastTime ← max(broadcastTime, WMBT-Tree(Tr , r, vstd))
return broadcastTime
WMBT-Tree(T, v, vstd)
vstd[v] ← true
11
broadcastTime ← 0
12
time ← 0
13
PQ ← InitPQ()
// let PQ be an priority queue
14
for each u ∈ N(v) do
15
if vstd[u] = f alse then
16
PQ ←PushPQ(PQ,( WMBT-Tree(T ,u,vstd) + We ((v, u)), We ((v, u)), u))
9
10
17
18
19
20
21
22
while not IsEmpty(PQ) do
p, w, u ← PopPQ(PQ)
broadcastTime ← max(broadcastTime, p + time)
time ← time + w
broadcastTime ← broadcastTime +Wv (v)
return broadcastTime
reduce algorithm uses Algorithm 7 to compute WMBT lowers bounds for each vertex. The main
idea of the algorithm is to check if the lower bound of a vertex plus its transmission cost is greater
than the best WMBT found. If so, we can delete some of this edges.
Definition 11. Given an instance G(V, E, S,We ,Wv ), for a vertex v ∈ V , there is a lower bound
on the time required to v receive any message from S, denoted by lb[v], which is computed by
the LBB-Dijkstra algorithm.
Definition 12. Let e = (v, u) ∈ E an edge with weight we = We (e) for an instance G(V, E, S,We ,Wv ).
The cost of edge cost(e) is computed as min(lb[v] +Wv [u], lb[u] +Wv [v]) + we .
Theorem 13. Let b be the WMBT of a primal solution for an instance G(V, E, S,We ,Wv ) and
e ∈ E an edge of G. If cost(e) > b, then not exists an optimal solution B, which has a lower
WMBT than the b such that e belong to B.
Proof. Let B0 be a solution of G(V, E, S,We ,Wv ) with WMBT b0 ≤ b such that e ∈ S0 . The edge e
can be used in the broadcast to transmit from u to v or from v to u. The vertex v can receive the
message (sent by u) at time lb[u] +Wv [v] + we . Similarly, the vertex u can receive the message
Weighted Minimum Broadcast Time
42
Algorithm 9: Exact greedy algorithm for WMBT
Input : Weighted Undirected graph: G = (V, E,Wv ,We ),
Source set: V0
Output: Broadcast time: broadcastTime
ImprovedGreedyAlgorithm(G,V0 )
for v ∈ V do
3
cost[v] ← ∞
1
2
4
5
6
7
8
9
10
11
I ← 0/
for v0 ∈ V0 do
cost[v0 ] ← Wv [v0 ]
I ← I ∪ {v0 }
// let I be a set
Eb ← 0/
U ← V \ {v0 }
while U 6= 0/ do
vα , vβ ← argmin(cost[vi ] +Wv [v j ] + We [(vi , v j )] )
// let Eb be a set
// let U be a set
i∈I, j∈U,(i, j)∈E
12
cost[vβ ] ← cost[vα ] +Wv [vβ ] + We [(vi , v j )]
13
cost[vα ] ← cost[vα ] + We [(vi , v j )]
14
I ← I ∪ {vβ }
U ← U \ {vβ }
Eb ← Eb ∪ {(vα , vβ )}
15
16
17
18
broadcastTime ← WSCHA((V, Eb ,V0 ,Wv ,We ))
return broadcastTime
Algorithm 10: Algorithm to remove edges of graph
Input : Weighted graph: G = (V, E, S,Wv ,We ), Lower bounds: lbs,
Broadcast time: broadcastTime
Output: Weighted graph: Gc
ReduceRules(G, lbs, broadcastTime)
2
Ec ← 0/
3
Wec ← 0/
4
for each e ∈ E do
5
cost ←min(lbs[ev ] +Wv [eu ],lbs[eu ] +Wv [ev ]) +ew
6
if cost ≤ broadcastTime then
7
Ec ← Ec ∪ {e}
8
Wec [e] ← We [e]
1
9
10
Gc = (V, Ec , S,Wv ,We )
return Gc
(sent by v) at time lb[v] + Wv [u] + we . Therefore, S0 (and any solution that uses the edge e)
must have a WMBT of at least min(lb[v] +Wv [u], lb[u] +Wv [v]) + we = cost(e), contradicting our
assumption that b0 ≤ b.
Weighted Minimum Broadcast Time
43
Rules 14. Given instance G(V, E, S,We ,Wv ), a solution S of G with b an edge e such that
cost(e) > b, then delete e from G.
3.2.6
BRKGA for the WMBT
In this section, we propose two BRKGA decoders for the WMBT: (i) Dijkstra-based with Weighted-SCHA, (ii) Minimum Spanning Forest-based with Weighted-SCHA refinement. Both decoders
start by generating a forest to be used as input for Weighted-SCHA. We do not apply the same
ideas in Chapter 2 since the decoders of MBT can not represent all solutions of WMBT in the
search space. Figure 3.2 shows an example of an instance such that the FRFS decoder can not
construct the optimal solution. In this example, any subgraph generated by the FRFS decoder
will have the edge (g1 , d2 ), but this edge does not belong to the optima.
In preliminary tests, we realize that an initial population with a single greedy solution produced good results. Thus, Algorithm 11 starts by computing the greedy solution using Algorithm
9 and the lower bound for each vertex in V . After that, in the multi-start loop (lines 2–3), it is applied the ReduceRule and population are initialized (including the greedy solution). In the main
loop (lines 4–15), we evolve the population and evaluate it using a decoder method (line 10),
which will be presented in the following sections. Finally, we finish the main loop after maxIt
attempts without improvement, and then we reset the population (lines 11–14).
Algorithm 11: BRKGA for the WMBT.
Input : Weighted graph: G = (V, E,Wv ,We ),
Source set: V0 , Maximum number of generations without improvement: maxIt
Output: Schedule Broadcast: S
BRKGA(G,V0 , maxIt)
2
S∗ ← ImprovedGreedyAlgorithm((V, E,V0 ,Wv ,We ))
3
Lb ← LB(G, V0 )
1
4
5
6
7
8
9
10
11
12
13
14
15
16
while stopping criterion not met do
G ← {ReduceRules(G, Lb, Fitness(S∗ ))}
P ← {EncodeSolution(S∗ )}
P ← P ∪ InitPopulation(G, V0 ) // Inicialize the first BRKGA population
noImprovement ← 0
while stopping criterion not met or does not improve the solution do
P ← BRKGA_Evolve(P)
noImprovement ← noImprovement + 1
if noImprovement = maxIt then
generations
noImprovement ← 0
P ← ResetPopulation(P)
S∗ ← GetBestIndividual(P)
population
return S∗
// Evolve population
// If no improvement after maxIt
// Reset the BRKGA population
// Get the best individual of the
Weighted Minimum Broadcast Time
3.2.6.1
44
Dijkstra-based decoder (DJ)
The Dijkstra-based decoder describes a solution by a set of |E| random keys (allele). Each
random key represents the priority of an edge to be added on the broadcast forest, i.e., the edge
with the lowest allele has the highest priority, and so on. We use the forest of Dijkstra as input to
Weighted-SCHA for computing the WMBT. Overall, the worst-case running time of the decoder
function is O(|E| · log |V |).
Algorithm 12: DJ decoder
Input : Weighted graph: G = (V, E, S,Wv ,We ),
Chromosomes vector: Cr
Output: Total step time to broadcast: broadcastTime
DJ(G,Cr)
2
for v ∈ V do
3
cost[v] ← ∞
1
4
5
6
7
8
9
10
11
I←S
Eb ← 0/
for v ∈ V do
cost[v] ← ∞
// let I be a set
// let Eb be a set
U ←V \S
cost[v0 ] ← 0
while U 6= 0/ do
vα , vβ ← argmin(cost[vi ] +Cr[(vi , v j )])
// let U be a set
i∈I, j∈U,(i, j)∈E
12
13
14
15
16
3.2.6.2
I ← I ∪ {vβ }
U ← U \ {vβ }
Eb ← Eb ∪ {(vα , vβ )}
broadcastTime ← WSCHA((V, Eb , S,Wv ,We ))
return broadcastTime
Minimum Spanning Forest-based decoder (MSF)
In this section, we describe a Minimum Spanning Forest-based decoder (MSF). In this approach,
each random key is associated with an edge. Each allele indicates the weight of this edge. Next,
we compute the minimum spanning forest using Kruskal Algorithm (Kruskal, 1956), . Finally, we
compute the WMBT over this forest using the Weighted-SCHA. Overall, the worst-case running
time of the decoder function is O(|E| · log |E|).
3.3
Computacional results of the WMBT
This section presents the computational experiments conducted to evaluate the effectiveness of
our proposed ILP and BRKGAs. The proposed algorithms are compared with the following stateof-the-art approaches: (i) an adaptation of Ant Colony metaheuristic (ACS) from Hasson and
Weighted Minimum Broadcast Time
45
Algorithm 13: MSF decoder
Input : Weighted graph: G = (V, E, S,Wv ,We ),
Chromosomes vector: Cr
Output: Total step time to broadcast: broadcastTime
Root(v, parent)
if parent[v] < 0 then
3
return v
1
2
parent[v] ← Root(parent[v], parent)
4
return parent[v]
5
Merge(u, v, parent)
u ← Root(u, parent)
8
v ← Root(v, parent)
9
parent[v] ← parent[u]
6
7
10
11
12
MSF(G,Cr)
Eb ← 0/
for each v ∈ V do
parent[v] ← −1
13
r ← ∀v0 ∈ S
for each v0 ∈ V0 do
Merge(r, v0 )
14
15
16
Ranking ← 0/
for each e ∈ E do
Ranking ← Ranking ∪ {(Cr[e], ev , eu )}
17
18
19
while |Eb | + |S| 6= |V | do
20
e ←ExtractMin(Ranking)
Ranking ← Ranking \ {e}
if Root(ev , parent) 6= Root(eu , parent) then
Eb ← Eb ∪ {(ev , eu )}
Merge(ev , eu )
21
22
23
24
25
broadcastTime ← WSCHA((V, Eb , S,Wv ,We ))
26
return broadcastTime
27
Sipper (2004); and (ii) an adaption of constructive heuristic from Harutyunyan and Kamali (2008).
For the ACS algorithm, we use the Weighted-SCHA algorithm to refine the partial solutions. We
adapt the constructive heuristic from Harutyunyan and Kamali (2008) by adding weights in the
edges.
All experiments in this section were conducted on an Intel Core i7-6700 with 3.40 GHz, 32
GB of RAM, running Ubuntu 18.04.5. The heuristic algorithms were coded in C++ and compiled
with g++ 7.5 and ‘-O3’ flag. The BRKGA C++ framework developed by Toso and Resende (2015)
has been used to implement our BRKGA. Moreover, IBM Cplex 12.9 has been adopted to solve
the ILP models.
Weighted Minimum Broadcast Time
3.3.1
46
Instances
We tested our algorithms on a total of 40 instances, which include:
• Random graph (20 instances): The random graph Gr is based on the G(n, p) model,
also known as binomial model (Gilbert, 1959). Each graph Gr = (V, Er ) is generated with
n vertices and each potential edge in Er is created with probability p. The vertices and
edges weights have been created using a uniform distribution.
• Large synthetic instances based on random tree (20 instances): Given that the optimal
solution for large the WMBT instances is often unknown, we generated a new benchmark
with known optimal solutions using the following procedure.
Algorithm 14 creates a random instance G = (V, E,Wv ,We ) by applying the union of a
weighted-vertex-and-edge random tree T = (VT , ET ,WvT ,WeT ) and a weighted-edge random
graph Gr = (Vr , Er ,Wr ), where V = VT = Vr , E = ET ∪ Er , Wv = WvT and We = WeT ∪Wr . First,
we calculate the optimal broadcast time of T by using the Algorithm 8 (WMBT-T REE). After that,
we created a random graph Gr to merge with T into G. Finally, for each new edge in Gr , we
assigned a weight value preserving the optimal solution found previously.
Appendix A.2 gives more information regarding the adopted instances, such as the number
of vertices and edges.
3.3.2
Parameter settings and experimental protocol
In our experiments with the ACS algorithm, we adopted the same parameter settings indicated by
its authors. Moreover, we have used the irace tunning tool (López-Ibáñez et al., 2016) to configure the parameters of our algorithms and their variations. The best parameter settings identified
by the tuning experiment are reported in Table 3.2. In this table, BRKGA parameters p, pe ,
pm , ρe , and K represent, respectively, the number of individuals in each population, percentage
of elite individuals into each population, percentage of mutants introduced at each generation
into the population, the probability that an offspring inherits the allele of its elite parent, and the
number of independent populations.
Table 3.2: Range considered by IRACE and best parameter settings obtained.
Parameter
p
pe
pm
ρe
K
Value ranges
BRKGA-DJ
BRKGA-MSF
-
|V |
0.24
0.23
0.59
1
|V |
0.25
0.22
0.52
1
0.10, 0.11, . . ., 0.25
0.10, 0.11, . . ., 0.30
0.50, 0.51, . . ., 0.80
-
We have set a time limit of 3600 s (1 h) to Cplex for solving our ILP model. To assess the
Weighted Minimum Broadcast Time
47
Algorithm 14: Create a random weighted graph with optima known.
Input : Number of vertices: n,
density: d
Output: Weighted-vertex-and-edge graph: G(VG , EG , S,Wv ,We ),
minimum broadcast time of graph G: wmbt
GenerateWeightedGraph(n, d)
T ← RandomTree(n)
3
root ← Random(0,n)
4
for each v ∈ V (T ) do
5
WvT [v] ← Random(0,∞)
1
2
for each e ∈ E(T ) do
6
WeT [e] ← Random(1,∞)
7
S ← WMBT-Tree((V (T ),V (E),WvT ,WeT ), root)
times ← GetTimes(S)
Gr ← RandomGraph(n,d)
VG ← V (T )
Wv ← WvT
EG ← E(T )
We ← WeT
for each e ∈ E(Gr ) \ E(T ) do
EG ← EG ∪ {e}
di f f erentTime ← abs(times[e.v] − times[e.u])
We [e] ← di f f erentTime+ Random(1,∞)
8
9
10
11
12
13
14
15
16
17
18
19
wmbt ←max (times[v])
20
G ← (VG , EG , {root},Wv ,We )
return G, wmbt
v∈V
21
average performance of the heuristic algorithms (BRGKAs and ACS), we have performed 10
runs in each benchmark instance with different random seeds for each run. A time limit of 300 s
has been used for these runs.
3.3.3
Comparing the deterministic algorithms
Table 3.3 compares the algorithm of Harutyunyan and Kamali (2008) (Algorithm 6), our improvement in this algorithm (Algorithm 9), and the ILP model in all instances. The methods are compared using only the following criteria: the WMBT, and the CPU time to find the best solution
(column ‘t (s)’). An asterisk means that the method has been able to prove the optimality of a
given result. Since the algorithms are deterministic, we run them only one time.
Note that Harutyunyan-WSCHA attains or improves the quality of the solutions obtained by
Harutyunyan on all instances. In the ILP model, we set the lower bound using Algorithm 7. We
also used the WMBT value of Harutyunyan-WSCHA as the upper bound to reduce the computational demand and the total amount of used memory. The ILP model does not produce feasible
solutions for instances with more than 512 vertices. But in graphs with up to 256 vertices, the
Weighted Minimum Broadcast Time
48
model showed a significant result.
Table 3.3: Comparative results of deterministic algorithms.
Instance
3.3.4
Lower Bound
HARUTYUNYAN
HARUTYUNYAN-WSCHA
ILP
WMBT
t (s)
WMBT
t (s)
WMBT
t (s)
R1024-G1-D10-1
13
20
0.19
19
0.19
-
3600.00
R1024-G1-D15-1
15
22
0.30
21
0.30
-
3600.00
R1024-G1-D20-1
9
17
0.40
16
0.39
-
3600.00
R1024-G1-D25-1
9
17
0.48
16
0.47
-
3600.00
R128-G1-D10-1
20
29
27
3575.57
20
28
23
3603.59
R128-G1-D20-1
18
26
24
3605.44
R128-G1-D25-1
15
22
18
3606.34
R256-G1-D10-1
15
24
-
3600.00
R256-G1-D15-1
16
22
21
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
23
R128-G1-D15-1
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
-
3600.00
R256-G1-D20-1
10
18
0.01
16
0.01
-
3600.00
R256-G1-D25-1
12
17
0.01
16
0.01
-
3600.00
R512-G1-D10-1
13
21
0.03
21
0.02
-
3600.00
27
25
20
23
R512-G1-D15-1
16
23
0.04
22
0.04
-
3600.00
R512-G1-D20-1
10
18
0.05
17
0.05
-
3600.00
R512-G1-D25-1
13
19
0.06
18
0.06
-
3600.00
R64-G1-D10-1
22
28
27
23
36.45
R64-G1-D15-1
20
25
R64-G1-D20-1
20
30
R64-G1-D25-1
16
21
< 0.01
< 0.01
< 0.01
< 0.01
21
< 0.01
< 0.01
< 0.01
< 0.01
18
51.16
RO1024-G1-D10-1
440
492
0.19
490
0.19
-
3600.00
RO1024-G1-D15-1
550
609
0.30
603
0.30
-
3600.00
RO1024-G1-D20-1
479
536
0.40
532
0.39
-
3600.00
RO1024-G1-D25-1
353
393
0.48
393
0.47
-
3600.00
RO128-G1-D10-1
117
139
124
3600.00
186
214
-
3600.00
RO128-G1-D20-1
167
202
-
3600.00
RO128-G1-D25-1
122
149
-
3600.00
RO256-G1-D10-1
250
282
-
3600.00
RO256-G1-D15-1
208
239
237
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
-
RO128-G1-D15-1
-
3600.00
RO256-G1-D20-1
169
202
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
197
0.01
-
3600.00
RO256-G1-D25-1
211
243
0.01
241
0.01
-
3600.00
RO512-G1-D10-1
288
335
0.03
331
0.02
-
3600.00
RO512-G1-D15-1
409
479
0.04
476
0.04
-
3600.00
RO512-G1-D20-1
297
333
0.05
332
0.05
-
3600.00
RO512-G1-D25-1
320
362
0.06
356
0.06
-
3600.00
RO64-G1-D10-1
74
95
74*
15.23
108
128
109
52.02
RO64-G1-D20-1
87
99
RO64-G1-D25-1
140
168
< 0.01
< 0.01
< 0.01
< 0.01
74*
RO64-G1-D15-1
< 0.01
< 0.01
< 0.01
< 0.01
24
29
186
197
149
279
128
88
168
22
42.99
25
3600.64
88
57.86
-
3600.00
# Best
4
31
11
Avg. t (s)
0.08
0.08
3066.18
Validating the reducing rules
This section shows the benefits of using the proposed reducing rules (RR). Tables 3.4, 3.5 and
3.6 compare the decoder with and without the RR. We considered instances with a density of
Weighted Minimum Broadcast Time
49
25%, a time limit of 600 seconds, and 5 runs with different random seeds for each run. Moreover,
we behold that the RR can reduce the density by 5–95%. Consequently, the BRKGA gets faster.
Table 3.4: Comparative results of BRKGA-DJs with and without RR
Method
BRKGA-DJ
BRKGA-DJ
without RR
with RR
10
# Best
9
# Best Avg.
8
10
Avg. t (s)
129.66
55.68
Table 3.5: Comparative results of BRKGA-MSFs with and without RR
Method
BRKGA-MSF
BRKGA-MSF
without RR
with RR
10
# Best
8
# Best Avg.
8
9
Avg. t (s)
140.93
113.39
Table 3.6: Comparative results of BRKGAs with and without RR
Method
3.3.5
BRKGA-DJ
BRKGA-MSF
BRKGA-DJ
BRKGA-MSF
without RR
without RR
with RR
with RR
10
# Best
8
8
9
# Best Avg.
7
8
8
8
Avg. t (s)
189.65
140.93
115.68
113.39
Comparing the metaheuristics
Table 3.7 compares the heuristics ACS-WSCHA, Harutyunyan-WSCHA and BRKGAs in all instances for the WMBT. The results show that BRKGAs outperform both heuristics from the literature in solution quality and CPU time. The BRKGA-MSF found 38 best solutions, whereas this
number was 36 for the BRKGA-DJ. Both decodes have similar computational times.
The BRKGAs initialize the initial population with an element based on a solution of
Harutyunyan-WSCHA, so it is prospective that the BRKGA would be better than its.
Table 3.7: Comparative results of ACS, BRKGAs and HARUTYUNYAN-WSCHA
BRKGA-DJ
Instance
Best
Avg.
BRKGA-MSF
t (s)
Best
Avg.
t (s)
HARUTYUNYAN-WSCHA
Best
t (s)
ACS-WSCHA
Best
Avg.
t (s)
R1024-G1-D10-1
19
19.00
0.24
19
19.00
0.24
19
0.24
391
391.00
300.00
R1024-G1-D15-1
21
21.00
0.36
21
21.00
0.36
21
0.38
512
512.00
300.00
R1024-G1-D20-1
16
16.00
0.46
16
16.00
0.46
16
0.49
735
735.00
300.00
R1024-G1-D25-1
16
16.00
0.57
16
16.00
0.57
16
0.59
843
843.00
300.00
R128-G1-D10-1
26
26.80
256.73
26
26.80
273.74
27
< 0.01
58
58.00
300.00
Continued on next page
Weighted Minimum Broadcast Time
50
Table 3.7 – continued from previous page
BRKGA-DJ
Instance
BRKGA-MSF
Best
Avg.
t (s)
Best
Avg.
R128-G1-D15-1
26
26.80
275.70
26
R128-G1-D20-1
24
24.90
299.05
25
R128-G1-D25-1
20
20.00
20
20.00
R256-G1-D10-1
23
23.00
< 0.01
< 0.01
23
R256-G1-D15-1
21
21.00
0.01
21
R256-G1-D20-1
16
16.00
0.01
R256-G1-D25-1
16
16.00
0.01
R512-G1-D10-1
21
21.00
R512-G1-D15-1
22
R512-G1-D20-1
HARUTYUNYAN-WSCHA
ACS-WSCHA
t (s)
Best
t (s)
Best
Avg.
t (s)
26.70
257.74
27
70.00
300.00
300.00
25
93
93.00
300.00
20
130
130.00
300.00
23.00
< 0.01
< 0.01
23
< 0.01
< 0.01
< 0.01
< 0.01
70
25.00
97
97.00
300.00
21.00
0.01
21
0.01
135
135.00
300.00
16
16.00
0.01
16
0.01
158
158.00
300.00
16
16.00
0.01
16
0.01
197
197.00
300.00
0.03
21
21.00
0.03
21
0.03
194
194.00
300.00
22.00
0.04
22
22.00
0.04
22
0.05
297
297.00
300.00
17
17.00
0.06
17
17.00
0.06
17
0.06
340
340.00
300.00
R512-G1-D25-1
18
18.00
0.07
18
18.00
0.07
18
0.08
407
407.00
300.00
R64-G1-D10-1
25
25.30
146.31
25
25.60
201.67
27
38
38.00
300.00
R64-G1-D15-1
23
23.80
277.72
23
23.70
226.22
24
52
52.00
300.00
R64-G1-D20-1
28
28.00
300.00
27
27.90
278.18
29
72
72.00
300.00
R64-G1-D25-1
19
19.40
142.70
19
19.50
195.32
21
< 0.01
< 0.01
< 0.01
< 0.01
56
56.00
300.00
RO1024-G1-D10-1
490
490.00
0.23
490
490.00
0.23
490
0.24
43309
43309.00
300.00
RO1024-G1-D15-1
603
603.00
0.35
603
603.00
0.35
603
0.37
73373
73373.00
300.00
RO1024-G1-D20-1
532
532.00
0.45
532
532.00
0.45
532
0.48
106708
106708.00
300.00
RO1024-G1-D25-1
393
393.00
0.56
393
393.00
0.56
393
0.59
91319
91319.00
300.00
RO128-G1-D10-1
124
124.00
124
124.00
1568.10
300.00
186.00
186
186.00
3655
3655.00
300.00
RO128-G1-D20-1
182
192.90
300.00
167
191.40
287.96
197
3829
3829.00
300.00
RO128-G1-D25-1
122
140.90
245.69
122
138.70
268.81
149
3720
3720.00
300.00
RO256-G1-D10-1
277
278.80
271.21
277
278.80
285.83
279
< 0.01
< 0.01
< 0.01
< 0.01
< 0.01
1567
186
< 0.01
< 0.01
124
RO128-G1-D15-1
< 0.01
< 0.01
5878
5882.30
300.00
RO256-G1-D15-1
232
235.50
300.00
209
234.10
281.18
237
0.01
8603
8603.00
300.00
186
RO256-G1-D20-1
197
197.00
300.00
189
195.10
277.43
197
0.01
8056
8056.00
300.00
RO256-G1-D25-1
238
240.30
249.51
241
241.00
300.00
241
0.01
10637
11548.90
300.00
RO512-G1-D10-1
331
331.00
0.03
331
331.00
0.03
331
0.03
14470
14640.60
300.00
RO512-G1-D15-1
476
476.00
0.04
476
476.00
0.04
476
0.05
31088
31088.00
300.00
RO512-G1-D20-1
332
332.00
0.06
332
332.00
0.06
332
0.06
30598
30598.00
300.00
RO512-G1-D25-1
356
356.00
0.07
356
356.00
0.07
356
0.08
36776
36776.00
300.00
< 0.01
< 0.01
< 0.01
< 0.01
485
485.00
300.00
914
916.00
300.00
1044
1044.00
300.00
2636
2636.00
300.00
RO64-G1-D10-1
74
74.00
< 0.01
74
74.00
< 0.01
74
RO64-G1-D15-1
109
109.00
5.81
109
109.00
65.92
128
RO64-G1-D20-1
88
88.00
< 0.01
88
88.00
< 0.01
88
RO64-G1-D25-1
140
142.80
71.03
140
140.00
37.46
168
Avg. t (s)
86.13
88.53
0.1
300
# Best
36
38
25
0
# Best Avg.
32
36
25
0
4
Final Considerations
In this work, we proposed some algorithms for the M INIMUM B ROADCAST T IME problem and its
weighted version (WMBT). For the MBT, we have described a new lower bound procedure for the
problem based on vertex distances in the input graph. This procedure can reduce computational
resources and heuristic algorithms used to prove the optimality. The experimental results reveal
that our approach increased several lower bounds and helped the Integer Linear Programming
(ILP) model and our BRKGA prove several previously unknown optima.
We proposed two BRKGA metaheuristics and a matheuristic using BRKGA and ILP, our approaches outperformed ACS (Hasson and Sipper, 2004) and ILP (de Sousa et al., 2018) in both
solution quality and CPU time. In our best approaches, we used the idea described in Koh and
Tcha (1991); Su et al. (2010) to improve solution quality. For all instances for the MBT with
known optima value, our approaches either attained the optimal value or missed it by at most
one broadcast step. Moreover, we described a method to create instances with known optima.
To the best of our knowledge, this is the first time that major efforts were made to study, generate,
and solve hard instances for the MBT.
The WMBT is even harder to handle than the MBT because the broadcast scheme does not
follow a standard pattern. There are a smaller amount of articles. To the best of our knowledge, we proposed the first mathematical model for the WMBT. Thus, we formulated three ILP
models (one for each variant of the WMBT). Moreover, we adapted our lower bound of MBT algorithm to WMBT. We adopted a similar refinement of MBT to improve solution quality, which the
experimental computational showed a significant improvement. We proposed two BRKGA metaheuristics, which outperformed the algorithms in the literature. Finally, we proposed a reducing
rule.
51
FINAL CONSIDERATIONS
4.1
52
Future works
We also plan to extend the proposed algorithm to solve related problems, such as the following
MBT or WMBT:
(i) with at most k transmissions (k-broadcast) (Lazard, 1992; Harutyunyan and Liestman,
2001),
(ii) proposal an algorithm distributed for problems, and
(iii) apply our algorithms for solving real problems, such as swarm robotics (Al-Sarawi et al.,
2017).
4.2
Scientific production
This master’s degree resulted in the following scientific production:
(i) An article published in the Simpósio Brasileiro de Pesquisa Operacional (SBPO) (Lima
et al., 2020) composed by part of Chapter 2;
(ii) An article in revision in the International Transactions in Operational Research (ITOR)
composed by Chapter 2.
(iii) An article published in IEEE Systems, Man, and Cybernetics Society (SMC) (Lima et al.,
2021), in cooperation with others researches;
Finally, we are writing a new article composed by the results of Chapter 3.
References
S. Al-Sarawi, M. Anbar, K. Alieyan, and M. Alzubaidi. Internet of things (iot) communication
protocols: Review. In 2017 8th International Conference on Information Technology (ICIT),
pages 685–690, May 2017. DOI 10.1109/ICITECH.2017.8079928.
A Averbuch, Y Roditty, and B Shoham. Computation of broadcasting multiple messages in a
positive weighted tree. Journal of Combinatorial Mathematics and Combinatorial Computing,
35:161–184, 2000.
Amotz Bar-Noy and Shlomo Kipnis. Designing broadcasting algorithms in the postal model for
message-passing systems. Mathematical systems theory, 27(5):431–452, 1994.
Amotz Bar-Noy, Sudipto Guha, Joseph Naor, and Baruch Schieber. Message multicasting in
heterogeneous networks. SIAM Journal on Computing, 30(2):347–358, 2000.
Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser, Martin W. P. Savelsbergh, and
Pamela H. Vance. Branch-and-price: Column generation for solving huge integer programs.
Operations Research, 46(3):316–329, 1998. DOI 10.1287/opre.46.3.316.
Alex Bavelas. Communication patterns in task-oriented groups. The journal of the acoustical
society of America, 22(6):725–730, 1950.
James C. Bean. Genetic algorithms and random keys for sequencing and optimization.
INFORMS Journal on Computing, 6(2):154–160, 1994. URL
https://EconPapers.repec.org/RePEc:inm:orijoc:v:6:y:1994:i:2:p:154-160.
Marco A. Boschetti, Vittorio Maniezzo, Matteo Roffilli, and Antonio Bolufé Röhler. Matheuristics:
Optimization, simulation and control. In María J. Blesa, Christian Blum, Luca Di Gaspero,
Andrea Roli, Michael Sampels, and Andrea Schaerf, editors, Hybrid Metaheuristics, pages
171–177, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. ISBN 978-3-642-04918-7.
Dan Bucantanschi, Blaine Hoffmann, Kevin R Hutson, and R Matthew Kretchmar. A
neighborhood search technique for the freeze tag problem. In Extending the Horizons:
Advances in Computing, Optimization, and Decision Technologies, pages 97–113. Springer,
2007.
53
REFERENCES
54
Raquel Silva Cabral, Andre Aquino, Alejandro Frery, Osvaldo Rosso, and Jaime Ramírez.
Structural changes in data communication in wireless sensor networks. Open Physics, 11
(12):1645–1652, 2013.
Xiaogeng Chu and Yuning Chen. Time division inter-satellite link topology generation problem:
Modeling and solution. International Journal of Satellite Communications and Networking, 36
(2):194–206, 2018.
Amaro de Sousa, Gabriela Gallo, Santiago Gutierrez, Franco Robledo, Pablo Rodríguez-Bocca,
and Pablo Romero. Heuristics for the minimum broadcast time. Electronic Notes in Discrete
Mathematics, 69:165–172, aug 2018. DOI 10.1016/j.endm.2018.07.022. URL
https://doi.org/10.1016%2Fj.endm.2018.07.022.
Anthony Dekker. Applying social network analysis concepts to military c4isr architectures.
Connections, 24(3):93–103, 2002.
Michael Elkin and Guy Kortsarz. Sublogarithmic approximation for telephone multicast: Path
out of jungle. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms,
pages 76–85, 01 2003. DOI 10.1145/644108.644120.
Arthur Farley, Stephen Hedetniemi, Sandra Mitchell, and Andrzej Proskurowski. Minimum
broadcast graphs. Discrete Mathematics, 25(2):189 – 193, 1979. ISSN 0012-365X.
DOI https://doi.org/10.1016/0012-365X(79)90022-0. URL
http://www.sciencedirect.com/science/article/pii/0012365X79900220.
Cristopher G. S. Freitas, Andre L. L. Aquino, Heitor S. Ramos, Alejandro C. Frery, and
Osvaldo A. Rosso. A detailed characterization of complex networks using information theory.
Scientific Reports, 9(1):16689, 2019.
Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory
of NP-Completeness. W. H. Freeman & Co., USA, 1979. ISBN 0716710447.
Michel Gendreau and Jean-Yves Potvin. Handbook of metaheuristics, volume 2. Springer,
2010.
E. N. Gilbert. Random graphs. Ann. Math. Statist., 30(4):1141–1144, 12 1959.
DOI 10.1214/aoms/1177706098. URL https://doi.org/10.1214/aoms/1177706098.
Alan G Gomez, William C Oakes, and Les L Leone. Engineering your future: A project-based
introduction to engineering. Great Lakes Press, 2004.
José Fernando Gonçalves, Mauricio GC Resende, and Rodrigo F Toso. An experimental
comparison of biased and unbiased random-key genetic algorithms. Pesquisa Operacional,
34(2):143–164, 2014.
REFERENCES
55
José Gonçalves and Mauricio Resende. Biased random-key genetic algorithms for
combinatorial optimization. J. Heuristics, 17:487–525, 10 2011.
DOI 10.1007/s10732-010-9143-1.
Daniel L Guidoni, Raquel AF Mini, and Antonio AF Loureiro. On the design of resilient
heterogeneous wireless sensor networks based on small world concepts. Computer
Networks, 54(8):1266–1281, 2010.
H. A. Harutyunyan and S. Kamali. Efficient broadcasting in networks with weighted nodes. In
2008 14th IEEE International Conference on Parallel and Distributed Systems, pages
879–884, 2008.
Hovhannes A Harutyunyan and Cosmin Jimborean. New heuristic for message broadcasting in
networks. In 2014 IEEE 28th International Conference on Advanced Information Networking
and Applications, pages 517–524. IEEE, 2014.
Hovhannes A. Harutyunyan and Arthur L. Liestman. Improved upper and lower bounds for
k-broadcasting. Networks, 37(2):94–101, 2001.
DOI 10.1002/1097-0037(200103)37:2<94::AID-NET4>3.0.CO;2-6. URL
https://onlinelibrary.wiley.com/doi/abs/10.1002/1097-0037%28200103%2937%
3A2%3C94%3A%3AAID-NET4%3E3.0.CO%3B2-6.
Hovhannes A. Harutyunyan and Wei Wang. Broadcasting algorithm via shortest paths. In 2010
IEEE 16th International Conference on Parallel and Distributed Systems, pages 299–305,
2010. DOI 10.1109/ICPADS.2010.110.
Yehudit Hasson and Moshe Sipper. A novel ant algorithm for solving the minimum broadcast
time problem. In Xin Yao, Edmund K. Burke, José A. Lozano, Jim Smith, Juan Julián
Merelo-Guervós, John A. Bullinaria, Jonathan E. Rowe, Peter Tiňo, Ata Kabán, and
Hans-Paul Schwefel, editors, Parallel Problem Solving from Nature - PPSN VIII, pages
501–510, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. ISBN 978-3-540-30217-9.
Sandra M. Hedetniemi, Stephen T. Hedetniemi, and Arthur L. Liestman. A survey of gossiping
and broadcasting in communication networks. Networks, 18(4):319–349, 1988.
DOI 10.1002/net.3230180406. URL
https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230180406.
Cory J. Hoelting, Dale A. Schoenefeld, and Roger L. Wainwright. A genetic algorithm for the
minimum broadcast time problem using a global precedence vector. In Proceedings of the
1996 ACM Symposium on Applied Computing, SAC ’96, page 258–262, New York, NY, USA,
1996. Association for Computing Machinery. ISBN 0897918207.
DOI 10.1145/331119.331187. URL https://doi.org/10.1145/331119.331187.
REFERENCES
56
John H. Holland. Adaptation in Natural and Artificial Systems: An Introductory Analysis with
Applications to Biology, Control and Artificial Intelligence. University of Michigan Press, Ann
Arbor, MI, 1975.
Marika Ivanova. Optimization problems in communication networks and multi-agent path
finding. Bergen Open Research Archive, 2019.
H. Keshavarz, A. Bagheri, K. Layeghi, and Seyed Iman Mahdavi. A simulated annealing
approach for the freeze-tag problem. In 2011 International Conference on Recent Trends in
Information Systems, pages 94–98, 2011. DOI 10.1109/ReTIS.2011.6146847.
J. Koh and D. Tcha. Information dissemination in trees with nonuniform edge transmission
times. IEEE Transactions on Computers, 40(10):1174–1177, 1991. DOI 10.1109/12.93751.
J-C König and Emmanuel Lazard. Minimum k-broadcast graphs. Discrete Applied
Mathematics, 53(1-3):199–209, 1994.
Guy Kortsarz and David Peleg. Approximation algorithms for minimum time broadcast. In
D. Dolev, Z. Galil, and M. Rodeh, editors, Theory of Computing and Systems, pages 67–78,
Berlin, Heidelberg, 1992. Springer Berlin Heidelberg. ISBN 978-3-540-47214-8.
J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem.
Proc. the American Mathematical Soc., 7(1):48–48, 1956.
DOI 10.1090/s0002-9939-1956-0078686-7.
E. Lazard. Broadcasting in dma-bound bounded degree graphs. Discrete Applied Mathematics,
37-38:387 – 400, 1992. ISSN 0166-218X.
DOI https://doi.org/10.1016/0166-218X(92)90147-3. URL
http://www.sciencedirect.com/science/article/pii/0166218X92901473.
A. Lima, M. Santos, A. Lima, B. Nogueira, and R. G. S. Pinheiro. A multi-population brkga for
the automatic clustering problem. In 2021 IEEE International Conference on Systems, Man
and Cybernetics (SMC), pages 1–6. IEEE, 2021.
Alfredo Lima, Rian Pinheiro, Bruno Nogueira, and Rodrigo Peixoto. Algoritmo genético de
chaves aleatórias viciadas para o problema do tempo de transmissão mínimo, Oct 2020.
URL https://proceedings.science/sbpo-2020/papers/
algoritmo-genetico-de-chaves-aleatorias-viciadas-para-o-problema-do-tempo-de-tran
Shawna D Lockhart and Cindy M Johnson. Engineering design communication: conveying
design through graphics. Addison-Wesley, 2000.
Manuel López-Ibáñez, Jérémie Dubois-Lacoste, Leslie Pérez Cáceres, Mauro Birattari, and
Thomas Stützle. The irace package: Iterated racing for automatic algorithm configuration.
REFERENCES
57
Operations Research Perspectives, 3:43–58, 2016. ISSN 2214-7160.
DOI https://doi.org/10.1016/j.orp.2016.09.002. URL
http://www.sciencedirect.com/science/article/pii/S2214716015300270.
M. Padberg and G. Rinaldi. Optimization of a 532-city symmetric traveling salesman problem by
branch and cut. Operations Research Letters, 6(1):1–7, 1987. ISSN 0167-6377.
DOI 10.1016/0167-6377(87)90002-2. URL
http://www.sciencedirect.com/science/article/pii/0167637787900022.
Juan A Rico-Gallego, Juan C Díaz-Martín, Ravi Reddy Manumachu, and Alexey L Lastovetsky.
A survey of communication performance models for high-performance computing. ACM
Computing Surveys (CSUR), 51(6):1–36, 2019.
Franco Robledo, Pablo Rodríguez-Bocca, and Pablo Romero. Optimal broadcast strategy in
homogeneous point-to-point networks. In Giuseppe Nicosia, Varun Ojha, Emanuele
La Malfa, Giorgio Jansen, Vincenzo Sciacca, Panos Pardalos, Giovanni Giuffrida, and
Renato Umeton, editors, Machine Learning, Optimization, and Data Science, pages
448–457, Cham, 2020. Springer International Publishing. ISBN 978-3-030-64583-0.
Scheuermann and Wu. Heuristic algorithms for broadcasting in point-to-point computer
networks. IEEE Transactions on Computers, C-33(9):804–811, Sep. 1984. ISSN 2326-3814.
DOI 10.1109/TC.1984.1676496.
Weiping Shang, Pengjun Wan, and Xiaodong Hu. Approximation algorithms for minimum
broadcast schedule problem in wireless sensor networks. Frontiers of Mathematics in China,
5(1):75–87, 2010.
P. J. Slater, E. J. Cockayne, and S. T. Hedetniemi. Information dissemination in trees. SIAM
Journal on Computing, 10(4):692–701, 1981. DOI 10.1137/0210052. URL
https://doi.org/10.1137/0210052.
Kenneth Sorensen, Marc Sevaux, and Fred Glover. A history of metaheuristics. arXiv preprint
arXiv:1704.00853, 2017.
Villiam M. Spears and Kenneth A. De Jong. On the virtues of parameterized uniform crossover.
In In Proceedings of the Fourth International Conference on Genetic Algorithms, pages
230–236, 1991.
Yu-Hsuan Su, Ching-Chi Lin, and DT Lee. Broadcasting in heterogeneous tree networks. In
International Computing and Combinatorics Conference, pages 368–377. Springer, 2010.
Yu-Hsuan Su, Ching-Chi Lin, and D.T. Lee. Broadcasting in weighted trees under the postal
model. Theoretical Computer Science, 621:73 – 81, 2016. ISSN 0304-3975.
REFERENCES
58
DOI https://doi.org/10.1016/j.tcs.2016.01.031. URL
http://www.sciencedirect.com/science/article/pii/S0304397516000554.
El-Ghazali Talbi. Metaheuristics: From Design to Implementation. Wiley Publishing, 2009.
ISBN 0470278587.
Rodrigo F Toso and Mauricio GC Resende. A c++ application programming interface for biased
random-key genetic algorithms. Optimization Methods and Software, 30(1):81–93, 2015.
Cheng-Hsiao Tsou, Gen-Huey Chen, Hung-I Yu, and Ching-Chi Lin. The broadcast median
problem in heterogeneous postal model. Journal of Combinatorial Optimization, 25(4):
602–616, 2013.
Vijay V Vazirani. Approximation algorithms, volume 1. Springer, 2001.
Iwona Wojciechowska and Frances L. Scoy. Broadcasting in Grid Graphs. PhD thesis, West
Virginia University, USA, 1999. AAI9967246.
Appendix A
Detailed instances
A.1
Instances for the MBT.
For each instance, Table A.1 gives the name (column ‘Instance’), the number of vertices (column
‘|V |’), the number of edges (column ‘|E|’), the initial source vertex (column ‘V0 ’), the theoretical
lower bound (column ‘TLB’, see Eq. (2.1)), the lower bound found by the proposed Algorithm 1
(column ‘LBB’), and the edge density (column ‘density’).
Table A.1: Description of the test instances.
Instance
|V |
|E|
V0 T LB LBB density Instance
|V |
|E|
V0 T LB LBB density
Harary Graphs
H10,30
H20,50
H2,100
H2,30
H3,17
H3,50
H6,17
H8,30
30
150
{30}
5
3
0.3448 H11,50
50
275
{50}
6
3
0.2245
50
500
{50}
6
3
0.4082 H21,50
50
525
{50}
6
2
0.4286
100
100
{100}
7
50 0.0202 H2,17
17
17
{17}
4
8
0.125
30
30
{30}
5
15
0.069 H2,50
50
50
{50}
6
25 0.0408
17
26
{6}
4
4
0.1912 H3,30
30
45
{30}
5
8
0.1034
50
75
{50}
6
13 0.0612 H5,17
17
43
{17}
4
3
0.3162
17
51
{17}
4
3
0.375 H7,17
17
60
{17}
4
2
0.4412
30
120
{30}
5
4
0.2759 H9,30
30
135
{30}
5
3
0.3103
Hypercube Graphs
HC5
HC7
HC9
32
80
{1}
5
5
0.1613 HC6
64
192
{1}
6
6
0.0952
128
448
{1}
7
7
0.0551 HC8
256
1024
{1}
8
8
0.0314
512
2304
{1}
9
9
0.0176 HC10
1024 5120
{1}
10
10 0.0098
Cube-Connected Cycles Graphs
CCC3
CCC5
CCC7
24
36
{1}
5
6
0.1304 CCC4
64
96
{1}
6
8
160
240
{1}
8
10 0.0189 CCC6
384
576
{1}
9
13 0.0078
896
1344
{1}
10
15 0.0034
0.0476
deBruijn Graphs
DB4
DB6
DB8
DB10
16
32
{1}
4
4
0.2583 DB5
32
64
{1}
5
5
64
128
{1}
6
6
0.0630 DB7
128
256
{1}
7
7
0.0314
256
512
{1}
8
8
0.0157 DB9
512
1024
{1}
9
9
0.0078
1024 2048
{1}
10
10 0.0039
0.1270
Continued on next page
59
Detailed instances
60
Table A.1 – continued from previous page
Instance
|V |
|E|
V0 T LB LBB density Instance
|V |
|E|
V0 T LB LBB density
Shuffle Exchange Graphs
SE4
SE6
SE8
SE10
16
21
{1}
4
7
0.1750 SE5
32
46
{1}
5
9
64
93
{1}
6
11 0.0461 SE7
128
190
{1}
7
13 0.0234
256
381
{1}
8
15 0.0117 SE9
512
766
{1}
9
17 0.0059
1024 1533
{1}
10
19 0.0029
0.0927
Network Repository
SW-100-3-0d1-trial1
100
100
{1}
7
61 0.0202 SW-100-3-0d2-trial1
100
100
{1}
7
31 0.0202
SW-100-3-0d2-trial3
100
100
{1}
7
31 0.0202 SW-100-4-0d1-trial1
100
200
{1}
7
7
0.0404
SW-100-4-0d1-trial2
100
200
{1}
7
7
0.0404 SW-100-4-0d1-trial3
100
200
{1}
7
9
0.0404
SW-100-4-0d2-trial1
100
200
{1}
7
7
0.0404 SW-100-4-0d2-trial2
100
200
{1}
7
7
0.0404
SW-100-4-0d2-trial3
100
200
{1}
7
7
0.0404 SW-100-4-0d3-trial1
100
200
{1}
7
6
0.0404
SW-100-4-0d3-trial2
100
200
{1}
7
6
0.0404 SW-100-4-0d3-trial3
100
200
{1}
7
7
0.0404
SW-100-5-0d1-trial1
100
200
{1}
7
8
0.0404 SW-100-5-0d1-trial2
100
200
{1}
7
9
0.0404
SW-100-5-0d1-trial3
100
200
{1}
7
11 0.0404 SW-100-5-0d2-trial1
100
200
{1}
7
8
0.0404
SW-100-5-0d2-trial2
100
200
{1}
7
9
0.0404 SW-100-5-0d2-trial3
100
200
{1}
7
7
0.0404
SW-100-5-0d3-trial1
100
200
{1}
7
6
0.0404 SW-100-5-0d3-trial2
100
200
{1}
7
6
0.0404
SW-100-5-0d3-trial3
100
200
{1}
7
6
0.0404 SW-100-6-0d1-trial1
100
300
{1}
7
5
0.0606
SW-100-6-0d1-trial2
100
300
{1}
7
6
0.0606 SW-100-6-0d1-trial3
100
300
{1}
7
6
0.0606
SW-100-6-0d2-trial1
100
300
{1}
7
6
0.0606 SW-100-6-0d2-trial2
100
300
{1}
7
4
0.0606
SW-100-6-0d2-trial3
100
300
{1}
7
4
0.0606 SW-100-6-0d3-trial1
100
300
{1}
7
4
0.0606
SW-100-6-0d3-trial2
100
300
{1}
7
5
0.0606 SW-100-6-0d3-trial3
100
300
{1}
7
5
0.0606
SW-1000-3-0d2-trial1 1000 1000
{1}
10
89
0.002 SW-1000-3-0d2-trial2 1000 1000
{1}
10
88
0.002
SW-1000-3-0d3-trial2 1000 1000
{1}
10
87
0.002 SW-1000-4-0d1-trial1 1000 2000
{1}
10
14
0.004
SW-1000-4-0d1-trial2 1000 2000
{1}
10
15
0.004 SW-1000-4-0d1-trial3 1000 2000
{1}
10
15
0.004
SW-1000-4-0d2-trial1 1000 2000
{1}
10
10
0.004 SW-1000-4-0d2-trial2 1000 2000
{1}
10
10
0.004
SW-1000-4-0d2-trial3 1000 2000
{1}
10
11
0.004 SW-1000-4-0d3-trial1 1000 2000
{1}
10
9
0.004
SW-1000-4-0d3-trial3 1000 2000
{1}
10
8
0.004 SW-1000-5-0d1-trial1 1000 2000
{1}
10
14
0.004
SW-1000-5-0d1-trial2 1000 2000
{1}
10
15
0.004 SW-1000-5-0d1-trial3 1000 2000
{1}
10
12
0.004
SW-1000-5-0d2-trial1 1000 2000
{1}
10
11
0.004 SW-1000-5-0d2-trial2 1000 2000
{1}
10
10
0.004
SW-1000-5-0d2-trial3 1000 2000
{1}
10
10
0.004 SW-1000-5-0d3-trial1 1000 2000
{1}
10
9
0.004
SW-1000-5-0d3-trial2 1000 2000
{1}
10
9
0.004 SW-1000-5-0d3-trial3 1000 2000
{1}
10
10
0.004
SW-1000-6-0d1-trial1 1000 3000
{1}
10
10
0.006 SW-1000-6-0d1-trial2 1000 3000
{1}
10
9
0.006
SW-1000-6-0d1-trial3 1000 3000
{1}
10
8
0.006 SW-1000-6-0d2-trial1 1000 3000
{1}
10
8
0.006
SW-1000-6-0d2-trial2 1000 3000
{1}
10
8
0.006 SW-1000-6-0d2-trial3 1000 3000
{1}
10
7
0.006
SW-1000-6-0d3-trial1 1000 3000
{1}
10
6
0.006 SW-1000-6-0d3-trial2 1000 3000
{1}
10
6
0.006
SW-1000-6-0d3-trial3 1000 3000
{1}
10
7
0.006
Synthetic instances
B5 ∪ RG32,0.05
B5 ∪ RG32,0.1
B5 ∪ RG32,0.2
B6 ∪ RG64,0.05
B6 ∪ RG64,0.1
B6 ∪ RG64,0.2
B7 ∪ RG128,0.05
B7 ∪ RG128,0.1
B7 ∪ RG128,0.2
B8 ∪ RG256,0.05
B8 ∪ RG256,0.1
B8 ∪ RG256,0.2
B9 ∪ RG512,0.05
B9 ∪ RG512,0.1
B9 ∪ RG512,0.2
32
48
{1}
5
5
32
83
{1}
5
3
32
142
{1}
5
2
64
159
{1}
6
3
64
243
{1}
6
3
64
461
{1}
6
2
128
560
{1}
7
3
128
923
{1}
7
3
128
1742
{1}
7
2
256
1863
{1}
8
3
256
3450
{1}
8
2
256
6691
{1}
8
2
512
6881
{1}
9
3
512 13444
{1}
9
2
512 27012
{1}
9
2
0.0968 B5 ∪ RG32,0.075
32
64
{1}
5
4
0.129
0.1673 B5 ∪ RG32,0.15
32
89
{1}
5
3
0.1794
0.2863 B5 ∪ RG32,0.25
32
156
{1}
5
2
0.3145
0.0789 B6 ∪ RG64,0.075
64
184
{1}
6
3
0.0913
0.1205 B6 ∪ RG64,0.15
64
349
{1}
6
2
0.1731
0.2287 B6 ∪ RG64,0.25
64
558
{1}
6
2
0.2768
0.0689 B7 ∪ RG128,0.075
128
716
{1}
7
3
0.0881
0.1136 B7 ∪ RG128,0.15
128
1313
{1}
7
3
0.1615
0.2143 B7 ∪ RG128,0.25
128
2140
{1}
7
2
0.2633
0.0571 B8 ∪ RG256,0.075
256
2657
{1}
8
3
0.0814
0.1057 B8 ∪ RG256,0.15
256
5168
{1}
8
2
0.1583
0.205 B8 ∪ RG256,0.25
256
8307
{1}
8
2
0.2545
0.0526 B9 ∪ RG512,0.075
512 10304 {1}
9
3
0.0788
0.1028 B9 ∪ RG512,0.15
512 20009 {1}
9
2
0.153
0.2065 B9 ∪ RG512,0.25
512 33313 {1}
9
2
0.2547
Continued on next page
Detailed instances
61
Table A.1 – continued from previous page
A.2
Instance
|V |
|E|
B10 ∪ RG1024,0.05
B10 ∪ RG1024,0.1
B10 ∪ RG1024,0.2
1024 27259
{1}
10
3
1024 53480
{1}
10
2
1024 105448 {1}
10
2
|V |
V0 T LB LBB density Instance
|E|
V0 T LB LBB density
0.052 B10 ∪ RG1024,0.075
1024 40222 {1}
10
3
1024 79574 {1}
10
2
0.1519
0.2013 B10 ∪ RG1024,0.25
1024 131643 {1}
10
2
0.2513
0.1021 B10 ∪ RG1024,0.15
0.0768
Instances for the WMBT.
For each instance, Table A.2 gives the name (column ‘Instance’), the number of vertices (column
‘|V |’), the number of edges (column ‘|E|’), the initial source vertex (column ‘V0 ’), the lower bound
found by the proposed Algorithm 7 (column ‘LBB’), and the edge density (column ‘density’).
Table A.2: Description of the test instances.
Instance
|V |
|E|
V0 T LB LBB density Instance
|V |
|E|
V0 T LB LBB density
Random graph
RG64,10,1
RG64,20,1
RG128,10,1
RG128,20,1
RG256,10,1
RG256,20,1
RG512,10,1
RG512,20,1
RG1024,10,1
RG1024,20,1
64
274
{7}
6
3
0.1359 RG64,15,1
64
352
{34}
6
3
0.1746
64
456
{31}
6
3
0.2262 RG64,25,1
64
549
{30}
6
2
0.2723
128
917
{82}
7
20 0.1128 RG128,15,1
128
1313 {104}
7
20 0.1615
128
1753
{5}
7
18 0.2157 RG128,25,1
128
2209
{57}
7
15 0.2718
256
3493
{20}
8
15
0.107 RG256,15,1
256
5069 {235}
8
16 0.1553
256
6743 {190}
8
10 0.2066 RG256,25,1
256
8404 {116}
8
12 0.2575
512 13500 {408}
9
13 0.1032 RG512,15,1
512 20081 {384}
9
16 0.1535
512 26446 {267}
9
10 0.2022 RG512,25,1
512 33103 {326}
9
13 0.2531
1024 53315 {553} 10
13 0.1018 RG1024,15,1
1024 79258 {829} 10
15 0.1513
1024 105629 {246} 10
9
0.2017 RG1024,25,1
1024 131816 {881} 10
9
0.2517
Random graph with optima know
RGO64,10,1
64
267
{48} 6
74 0.1324 RGO64,15,1
64
354
{50} 6 108 0.1756
RGO64,20,1
64
456
{32} 6
87 0.2262 RGO64,25,1
64
548
{38} 6 140 0.2718
RGO128,10,1 128 932 {30} 7 117 0.1147 RGO128,15,1 128 1325 {42} 7 186 0.163
RGO128,20,1 128 1705 {17} 7 167 0.2098 RGO128,25,1 128 2090 {65} 7 122 0.2571
RGO256,10,1 256 3461 {119} 8 250 0.106 RGO256,15,1 256 5119 {124} 8 208 0.1568
RGO256,20,1 256 6925 {163} 8 169 0.2122 RGO256,25,1 256 8353 {1}
8 211 0.2559
RGO512,10,1 512 13460 {272} 9 288 0.1029 RGO512,15,1 512 20347 {337} 9 409 0.1555
RGO512,20,1 512 26371 {300} 9 297 0.2016 RGO512,25,1 512 32891 {317} 9 320 0.2514
RGO1024,10,1 1024 53634 {778} 10 440 0.1024 RGO1024,15,1 1024 79458 {51} 10 550 0.1517
RGO1024,20,1 1024 105615 {871} 10 479 0.2016 RGO1024,25,1 1024 131157 {421} 10 353 0.2504