Interesses de Pesquisa

Alexandre Salles da Cunha
Professor Titular

Otimização

Departamento de Ciência da Computação
Universidade Federal de Minas Gerais

Dezembro de 2024

O meu interesse principal de pesquisa é desenvolver novas classes de algoritmos e/ou aprimorar classes de algoritmos de otimização existentes para resolver problemas nos seguintes domínios da Programação Matemática:

  1. Programação Binária Quadrática

  2. Otimização em Dois Níveis

  3. Otimização Inteira e Combinatória

  4. Otimização Não Linear

  5. Otimização Não Linear Inteira Mista

  6. Programação Semidefinida

  7. Programação Estocástica

Além disso, me interesso por modelar, formular e resolver problemas de Otimização Combinatória, empregando as técnicas de cada um dos domínios da Programação Matemática acima citadas.

Alguns temas de pesquisa e Problemas de Otimização Combinatória de interesse são apresentados abaixo. Se você precisa de instâncias para algum destes problemas, se gostaria de saber mais sobre algum deles ou se deseja trabalhar em algum tema relacionado, entre em contato através do email: acunha [at] dcc [dot] ufmg [dot] br.

  1. Programação Binária Quadrática [37, 38, 39, 17, 34, 24, 23].

    1. Problema da Árvove Geradora de Custo Mínimo Quadrático.
      O objetivo neste problema consiste em encontrar uma árvore geradora de custo mínimo de um grafo não direcionado G = (V,E). Porém, a função objetivo não é linear, e sim quadrática. Sendo mais específico, o problema é definido por uma matriz simétrica de custos Q = (qef)e,f∈E ∈ ℝm×m,m = |E|. A endrada q ef representa o custo incorrido quando as arestas e,f são simultaneamente escolhidas para pertencer à árvore geradora. Desta forma, o objetivo do problema é encontrar uma árvore geradora (V,ET ) de G que minimize a função ∑ e∈ETqee + 1 2 ∑ e∈ET ∑ f∈ET\{e}qef. Para este problema, desenvolvemos algoritmos Branch-and-bound que empregam limitantes duais de diversas naturezas, por exemplo:

    2. Problema da Árvove Geradora de Custo Mínimo Quadrático entre Arestas Adjacentes.
      Este problema é similar ao problema acima apresentado. Entretanto, a componente quadrática de custo só ocorre quando duas arestas são adjacentes, isto é, quando compartilham uma extremidade. Ou seja, para duas arestas e = {p,q},f = {i,j} não adjacentes, {p,q}∩{i,j} = ∅, temos qef = qfe = 0. Este problema é melhor resolvido que o problema no qual os custos quadráticos são aplicáveis para todos os pares de arestas. Isto porque a estrutura de custos nos permite criar métodos de decomposição em Programação Matemática (decomposição de Dantzig-Wolfe, técnicas de Projeção) bastante eficazes. Explorando estas ideias desenvolvemos:

      1. Algoritmos Branch-and-cut e Branch-and-cut-and-price baseados em uma Reformulação Estrela,

      2. Um algoritmo baseado em decomposição de Dantzig-Wolfe Dinâmica, generalizando a ideia da reformulação estrela e

      3. Um estudo poliedral em conjunto com uma Relaxação Lagrangeana.

    3. Problema da K-Clusterização ou K-dispersão.

  2. Problemas de Geometria Computacional [25, 13, 12]. Foram dois os problemas com os quais trabalhei até o momento. Ambos possuem aplicações em redes de comunicação sem fio:

    1. O Problema da Árvore Geradora de Mínima Área. Este problema é definido em um grafo não direcionado G = (V,E), que representa pontos em um Espaço Euclideano Bidimensional (plano Euclideano). Para cada aresta e = {i,j} de E associe o ponto médio p(e) da aresta e o disco c(e) que tem p(e) como centro e raio exatamente igual à metade da distância d(i,j) Euclideana entre i e j. Dada uma árvore geradora de G = (V,ET ), a sua área corresponde à área do objeto geométrico correspondente à união dos discos associados às arestas da árvore. No Problema da Árvore Geradora de Mínima Área, desejamos encontrar uma árvore geradora de G que tem a mínima área. Veja os discos c(e),c(f) associados a duas arestas da árvore, e ∈ E e f ∈ E, podem ter interseção. Esta interseção conta apenas uma vez para a área da árvore. Não se sabe se a versão de decisão deste problema é NP-Completo.

    2. O Problema da Árvore Geradora de Custo Mínimo Com Restrição Angular [13, 12]. Este também é um Problema de Otimização Combinatória definido a partir de um grafo não direcionado G = (V,E) que representa pontos no plano Euclideano. Além do grafo G não direcionado e completo, o problema é definido a partir de um ângulo α e de distâncias d(i,j) Euclideanas, associadas às extremidades das arestas {i,j}∈ E. No problema, deseja-se encontrar uma árvore geradora de G de mínimo peso. Entretanto, as arestas incidentes a cada vértice devem satisfazer uma restrição angular. Esta restrição estabelece que todas as arestas incidentes a i ∈ V devem estar contidas em um setor circular de ângulo igual ou inferior a α, centrado em i. Pelo que conhecemos, a primeira formulação e algoritmo de resolução exata para o problema foram apresentados em nosso artigo publicado em Computers & Operations Research. Posteriormente, apresentamos uma reformulação que emprega desigualdades válidas para conjuntos estáveis e um novo algoritmo Branch-and-cut, resultado publicado em Journal of Combinatorial Optimization.

  3. Problemas de Otimização em Dois Níveis com aplicações em Jogos de Stackelberg [32].

    Veja o exemplo de um Problema de Otimização em Dois Níveis:

    min F(x,w(x))
    s.t. x ∈ Ω
    g(x,w(x)) ≤ 0
    w(x) = min{f(x,y) : h(x,y) ≤ 0,y ∈ Δ}

    Nesta classe de problemas de Programação Matemática, há dois problemas de Otimização (um interno e outro externo) relacionados de forma hierárquica. Observe que na formulação acima há um problema mais externo, cuja função objetivo é min F(x,w(x)), definido no vetor de variáveis de decisão x, do qual depende w(x). Por sua vez, dada uma escolha de x, w(x) deve pertencer ao conjunto de valores ótimos da função objetivo do nível mais interno, que depende de x e de um segundo vetor y de variáveis de decisão.

    Uma aplicação interessante desta classe de Problemas de Programação Matemática surge no contexto de Teoria dos Jogos, mais especificamente em Jogos de Stackelberg. Um dos problemas interessantes com os quais trabalhei neste domínio é o Stackelberg Minimum Spanning Tree Game.

    O problema é definido a partir de um grafo não direcionado G = (V,B ∪R), onde B e R (B ∩ R = ∅) são conjuntos de arestas vermelhas e azuis, respectivamente. Complementam a definição do problema custos {ce ≥ 0 : e ∈ R} definidos para as arestas vermelhas. Estes custos são fixos e conhecidos antes do início do jogo. No jogo, há dois participantes: o líder e o seguidor.

    O líder deve definir preços {pe : e ∈ B} para as arestas azuis. Uma vez que estes preços tenham sido definidos, o seguidor deve construir uma árvore geradora (V,ET ) de G de mínimo peso ∑ e∈B∩ETpe + ∑ e∈R∩ETce. Observe que, para isso, o seguidor pode empregar as arestas em B e em R, da forma mais econômica possível.

    O objetivo do líder é definir preços {pe : e ∈ B} que maximizem a parcela ∑ e∈B∩ETpe que recebe da árvore geradora escolhida pelo seguidor.

  4. O Problema da Mochila 0/1 [1]. Dado um conjunto de itens N, um valor b ∈ ℤ+, lucros {cj : j ∈ N} e volumes {aj ∈ ℤ+ : j ∈ N}, deseja-se encontrar um subconjunto N′ ⊆ N satisfazendo ∑ j∈N′aj ≤ b que maximize a quantidade ∑ j∈N′cj. Em particular, trabalhei com o Problema da Mochila 0/1 quando as instâncias do problema são definidas por valores de b muito grandes, da ordem de 1016, por exemplo. Para estes casos, a técnica usualmente empregada para se resolver o problema (Programação Dinâmica) não é bem sucedida.

  5. Problemas de Roteamento de Veículos (PRV). Foram várias as versões do PRV com as quais trabalhei [40, 42, 41, 18, 19, 9, 5, 10, 11, 33, 44, 7] e também foram diversas as abordagens de solução exatas propostas (algoritmos Branch-and-cut, Branch-and-price e Branch-and-cut-and-price). Os seguintes problemas são os mais interessantes:

    1. Truck-and-trailler routing problem. Este PRV possui vários aspectos de modelagem interessantes. O veículo é composto pelo caminhão com sua capacidade de carga e por uma carreta com capacidade de carga adicional. Ao longo da rota, há pontos onde o veículo pode estacionar e desacoplar a carreta, para poder visitar clientes onde o acesso é restrito. Depois de visitar alguns clientes, o veículo retorna e reacopla a carreta. Os tempos de desacoplamento, acoplamento e de carregamento da carga no veículo são considerados. Este problema tem aplicações na coleta de leite em propriedades rurais.

    2. Roteamento de Veículos Seletivo Min-Max [44, 7]. Este PRV possui aplicações no monitoramento e na operação de redes de sensores sem fio. O objetivo do problema consiste em definir um conjunto de rotas, uma para cada um dos veículos disponíveis na frota, de forma que cada cliente ou seja visitado por um veículo ou esteja suficientemente perto de algun cliente visitado. Entretanto, não se deseja minimizar a distância total percorrida pelo conjunto de veículos da frota. Deseja-se minimizar a mais longa das rotas.

    3. Two Echelon Capacitated Vehicle Routing Problem [42, 41] Foram dois trabalhos que fizemos para o problema. O primeiro foi publicado na revista Optimization Letters, enquanto que o segundo foi publicado em Transportation Science. Esta classe de PRVs é interessante pois não é permitido o suprimento de produtos diretamente dos depósitos aos clientes finais. Ao invés disso, a rede de distribuição é organizada em camadas (ou echelons) e o problema passa a envolver o roteamento de veículos apenas em uma mesma camada: de armazéns para armazéns intermediários e, apenas destes, para os clientes finais. Portanto, é necessário ocorrer a sincronização de cargas nos armazéns intermediários, antes de definir as rotas dos veículos da última camada.

    4. Problema de Coleta e Entrega com Cross-Docking. [40] Usualmente, as versões de VRP que lidam com a integração de cargas em armazéns do tipo Cross-Docking (armazéns destinados a produtos que não ficam muito tempo em estoque, tipicamente apenas algumas horas), requerem que os veículos parem no Cross-Docking para descarregar e fazer a composição de cargas. Nesta variante do VRP que introduzimos, permitimos que os veículos façam simultaneamene coleta e entrega, sem necessariamente fazerem paradas no Cross-Docking, reduzindo com isso custos e tempos de transporte.

    5. Covering Tour Problem [10]. Nesta variação de VRP, os clientes são particionados entre clientes terminais e não terminais. Os clientes terminais predisam ser visitados por alguma rota. Os não terminais podem não ser visitados, mas devem estar a uma distância não superior a um determinado valor previamente estabelecido de algum cliente que tenha sido visitado. Além disso, há restrições de capacidade que limitam o número de clientes visitados e a carga atribuída a cada veículo.

  6. Problemas de Identificação de Subgrafos Induzidos de Máxima Cardinalidade [36, 35]. Dado um grafo não direcionado G = (V,E) e um subconjunto S ⊆ V , o subgrafo de G induzido por S é G[S] = (S,E(S)) onde E(S) ⊆ E é o conjunto de arestas que possuem as duas extremidades em S. Dependendo do tipo de grafo G[S] desejado, diferentes problemas de subgrafos induzidos podem surgir. Um dos problemas interessantes nesta classe, com o qual trabalhei, é o Chordless Cycle Problem. Neste problema, deseja-se encontrar um conjunto S, de máxima cardinalidade, tal que G[S] = (S,E(S)) seja um ciclo elementar de G. Observe um ciclo induzido não pode conter cordas, por isso é chamado de Chordless Cycle Problem. Para este problema, apresentamos diversas classes de desigualdades válidas e algoritmos Branch-and-cut e assim como uma reformulação binária quadrática e limites de Programação Semidefinida.

  7. Problemas de Dominância em Grafos [31, 22, 43]. Dado um grafo G = (V,E), os vizinhos de v ∈ V são respresentados por N(v). Um conjunto D ⊆ V é dominante se e somente se ⋃ i∈DN(i) = V . Muitos problemas de Otimização Combinatória interessantes envolvem a definição de conjuntos dominantes de cardinalidade mínima, satisfazendo alguma restrição adicional, por exemplo, envolvendo conexidade entre os vértices do conjunto dominante escolhido. Este foi o assunto tratado nos dois problemas abaixo, que se diferenciam pelos requisitos de conexidade impostos ao conjunto dominante.

    1. Conjunto Dominante Conexo de Mínima Cardinalidade. Neste problema, se D é o conjunto dominante, é necessário que exista um caminho que conecte os vétices de D, empregando para isso apenas as arestas com ambas as extremidades em D.

    2. Ciclo Dominante de Mínima Cardinalidade. Neste problema, é necessário que haja um ciclo Hamiltoniano conectando os vértices do conjunto dominante D.

  8. Problemas de Árvores ou Florestas Ótimas em Grafos, com distintas restrições complicantes e funções objetivos [21, 20, 26, 14, 8, 27, 28, 29, 6, 2, 3, 15, 16, 4, 30].

    1. Degree Preserving Spanning Tree Problem [16, 4, 30]. Dado um grafo G = (V,E), seja di o grau de i em G, isto é, di é o número de arestas incidentes a i em G. Dada uma árvore geradora de G, (V,ET ), dizemos que i ∈ V possui grau completo (ou grau preservado) se o seu grau di em G e na árvore são os mesmos. No Degree Preserving Spanning Tree Problem, desejamos encontrar uma árvore geradora de G com o máximo número de vértices com grau completo. A aplicação principal deste problema é na identificação de possíveis vazamentos em redes de distribuição de água. Na verdade, pode ser aplicado para identificação (ou medição) de fluxos em qualquer rede onde se observe o princípio de conservação de Kirchoff. Para o problema, desenvolvemos Algoritmos Branch-and-cut e do tipo Benders Combinatorial assim como uma reformulação baseada em conjuntos estáveis.

    2. Árvore de peso mínimo com exatas K arestas [21, 20, 26]. O problema é definido por um número inteiro positivo K, um grafo não direcionado G = (V,E) com pesos {pi : i ∈ V } associados aos seus vértices e custos {ce : e ∈ E} associados às suas arestas. Uma árvore T = (V T ,ET ) é viável se |ET | = K, isto é, se possui exatamente K arestas. O peso de T corresponde à soma dos pesos de seus vértices mais os custos das arestas que os conectam: ∑ i∈V Tpi + ∑ e∈ETce. Deseja-se uma árvore com K arestas com o menor peso possível. Para este problema propusemos Formulações compactas e Heurísticas Lagrangeanas. e posteriormente um estudo poliedral e algoritmo Branch-and-cut.

    3. Árvore Geradora de Custo Mínimo com Restrição de Grau Mínimo [27, 28, 29]. Dado um grafo não direcionado G = (V,E), com pesos {ce : e ∈ E} associados às suas arestas e um número inteiro positivo d, deseja-se encontrar uma árvore geradora (V,ET ) de mínimo peso ∑ e∈ETce, tal que todo vértice seja ou uma folha na árvore (e portanto, possui grau unitário) ou, se for um vértice central (não folha), deve possuir grau igual ou maior que d. Além de algoritmos Branch-and-cut, também sugerimos uma implementação paralela de uma Relaxação Lagrangeana para se produzir limites duais de uma Reformulação de Interseção para o roblema.

    4. Floresta Geradora de Mínimo Custo Máximo [3, 15]. Neste problema, dispomos de um grafo G = (V,E), um valor inteiro K e pesos {ce : e ∈ E} associados às aresas de G. Desejamos encontrar uma floresta geradora de G, com exatamente K componentes conexas. O peso de um componente conexo da floresta corresponde à soma dos pesos de suas arestas. A floresta procurada deve minimizar o peso total da mais pesada das suas componentes.

    5. Problema de Steiner em Grafos Com Recolha de Prêmios [2] Dado um grafo não direcionado G = (V,E) com penalidades {di ≥ 0 : i ∈ V } associadas aos vértices de G e custos {ce : e ∈ E} associados às arestas de G, deseja-se encontrar um subgrafo acíclico (V T ,ET ) de G que minimize a quantidade ∑ i∈V \V Tdi + ∑ e∈ETce.

    6. Árvores Geradoras Com Restrição de Grau Máximo nos Vértices.
      Trabalhei com este problema tanto na versão multi-período, definida em um horizonte de tempo, na qual é necessário definir o sequenciamento da ativação dos vértices na árvore geradora, quanto nas versão clássica, em que todos os vértices devem ser conectados simultaneamente (isto é, não há uma noção temporal no problema). Para a versão clássica, desenvolvemos um algoritmo Relax-and-cut para avaliação de limites duais fortes e também algoritmos Branch-and-cut-and-price.

Referências

[1]   A. S. da Cunha, L. Bahiense, A. Lucena, C. C. de Souza. A New Lagrangian Based Branch and Bound Algorithm for the 0-1 Knapsack Problem. Electronic Notes in Discrete Mathematics, 36:623 – 630, 2010.

[2]   A.S. da Cunha, A. Lucena, N. Maculan, M.G.C. Resende. A Relax-and-cut algorithm for the Prize Collecting Steiner Problem in Graphs. Discrete Applied Mathematics, 157(6):1198–1217, 2009.

[3]   A.S. da Cunha, L. Simonetti, A. Lucena. Formulations and Branch-and-cut algorithm for the K rooted Mini-max Spanning Forest Problem. Lecture Notes in Computer Science, LNCS 6701:43–50, 2011. Network Optimization - Proceedings of the 5th International Network Optimization Conference, Hamburg.

[4]   B. Gendron, A. Lucena, A. S. da Cunha and L. Simonetti. The degree preserving spanning tree problem: Formulations and valid inequalities. In INOC 2013 - International Network Optimization Conference, volume 41 of Electronic Notes in Discrete Mathematics, pages 173–180. Elsevier, 2013.

[5]   C. Bechelane, A.S. Cunha, and G.R. Mateus. The Minimum Cost Hop-and-root constrained forest in Wireless Sensor Networks. Electronic Notes in Discrete Mathematics, 35:139–144, 2009.

[6]   Luís Henrique Bicalho, Alexandre Salles da Cunha, and Abilio Lucena. Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem. Computational Optimization and Applications, 63:755–792, 2016.

[7]   C. A. Valle, L. C. Martinez, A. S. da Cunha, G. R. Mateus. Heuristic and exact algorithms for a min–max selective vehicle routing problem. Computers and Operations Research, 38(7):1054–1065, 2011.

[8]   Chagas, R.J., Valle, C.A., and da Cunha, A.S. Exact solution approches for the Multi-period Degree Constrained Minimum Spanning Tree Problem. European Journal of Operational Research, 271(1):57–71, 2018.

[9]   D. L. Pereira, A. S. da Cunha, G. R. Mateus. Stronger column generation bounds for the minimum cost hop-and-root constrained forest problem. Electronic Notes in Discrete Mathematics, 37:315–320, 2011.

[10]   Henrique Favarini Alves da Cruz and Alexandre Salles da Cunha. The profitable single truck and trailer routing problem with time windows: Formulation, valid inequalities and branch-and-cut algorithms. Computers & Industrial Engineering, 180:109238, 2023.

[11]   Alexandre Salles da Cunha. Formulation and branch-and-cut algorithm for the minimum cardinality balanced and connected clustering problem. In Proceedings of the 9th International Network Optimization Conference, INOC 2019, volume 1, pages 25–30, Avignon, France, 2019.

[12]   Alexandre Salles da Cunha. Improved formulations and branch-and-cut algorithms for the angular constrained minimum spanning tree problem. Journal of Combinatorial Optimization, 44:379–413, 2022.

[13]   Alexandre Salles da Cunha and Abilio Lucena. Modeling and solving the angular constrained minimum spanning tree problem. Computers & Operations Research, 112, 2019.

[14]   Alexandre Salles da Cunha, Luidi Simonetti, and Abilio Lucena. A strong symmetric formulation for the min-degree constrained minimum spanning tree problem. Electronic Notes in Discrete Mathematics, 52:237–244, 2016. INOC 2015 - 7th International Network Optimization Conference.

[15]   da Cunha, A.S., Simonetti and L., Lucena, A. Optimality cuts and branch-and-cut algorithm for the mini-max spanning forest problem. European Journal of Operational Research, 246:392–399, 2015.

[16]   da Cunha, A.S., Simonetti, L., Lucena, A. and Gendron, B. Formulations and exact solution approaches for the degree preserving spanning tree problem. Networks, 65:329–343, 2015.

[17]   D.L. Pereira and A.S. da Cunha. Polyhedral results, branch-and-cut and Lagrangian relaxation algorithms for the adjacent only quadratic minimum spanning tree problem. Networks, 71:31–50, 2018.

[18]   F. A. Santos, G. R. Mateus, A. S. da Cunha. A Novel Column Generation Algorithm for the Vehicle Routing Problem with Cross-Docking. In Network Optimization, volume 6701 of Lecture Notes in Computer Science, pages 412–25. Springer, 2011.

[19]   F. A. Santos, G. R. Mateus, A. S. da Cunha. A branch-and-price algorithm for a vehicle routing problem with cross-docking. In LAGOS’11 - VI Latin-American Algorithms, Graphs and Optimization Symposium, volume 37 of Electronic Notes in Discrete Mathematics, pages 249–54. Elsevier, 2011.

[20]   F. P. Quintão, A. S. da Cunha, G. R. Mateus and A. Lucena. The k-Cardinality Tree Problem: Reformulations and Lagrangian Relaxation. Discrete Applied Mathematics, 158(12):1305 – 1314, 2010.

[21]   F. P. Quintão and A.S. Cunha and G. R. Mateus. Integer Programming Formulations for the k Cardinality Tree Problem. Eletronic Notes in Discrete Mathematics, pages 225–230, 2008.

[22]   Gendron, B., Lucena, A., da Cunha, A.S., Simonetti, L. Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem. INFORMS Journal on Computing, 26(4):645–657, 2014.

[23]   D. Guimarães, A. Salles da Cunha, and D. L. Pereira. Exploiting sdp bounds for the quadratic minimum spanning tree problem. In Proceedings of the EURO/ALIO International Conference 2018 on Applied Combinatorial Optimization, page 56, 2018.

[24]   Dilson Almeida Guimarães, Alexandre Salles da Cunha, and Dilson Lucas Pereira. Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem. European Journal of Operational Research, 280(1):46–58, 2020.

[25]   Dilson Almeida Guimarães and Alexandre Salles da Cunha. The minimum area spanning tree problem: Formulations, benders decomposition and branch-and-cut algorithms. Computational Geometry, 97:101771, 2021.

[26]   L. Simonetti, A.S. da Cunha, A. Lucena. Polyhedral Results and Branch-and-cut algorithm for the k-Cardinality Tree Problem. Mathematical Programming, 142:511–538, 2013.

[27]   L.C. Martinez, A.S. da Cunha . Finding Min-degree Constrained Spanning Trees faster with a Branch-and-cut algorithm. Electronic Notes in Discrete Mathematics, 36:311–318, 2010.

[28]   L.C. Martinez, A.S. da Cunha . A Parallel Lagrangian Relaxation Algorithm for the Min-Degree Constrained Minimum Spanning Tree Problem. In A.R. Mahjoub et al., editor, Lecture Notes in Computer Science, volume 7422, pages 237–248, 2nd International Symposium on Combinatorial Optimization - Athens, 2012.

[29]   L.C. Martinez, A.S. da Cunha . The Min-Degree Constrained Minimum Spanning Tree Problem: Formulations and Branch-and-cut algorithm. Discrete Applied Mathematics, 164:210–224, 2014.

[30]   Abilio Lucena and Alexandre Salles da Cunha. Stable set reformulations for the degree preserving spanning tree problem. European Journal of Operational Research, 319(1):50–61, 2024.

[31]   Lucena, A., da Cunha, A.S. and Simonetti, L. Formulating and solving the minimum dominating cycle problem. In LAGOS 2013 - Latin American Algorithms, Graphs and Optimization Symposium, volume 41 of Electronic Notes in Discrete Mathematics, pages 423–430. Elsevier, 2013.

[32]   Morais, V., da Cunha, A. S. and Mahey, P. A branch-and-cut-and-price algorithm for the stackelberg minimum spanning tree game. Electronic Notes on Discrete Mathematics, 52:309–316, 2016.

[33]   Dilson Lucas Pereira and Alexandre Salles da Cunha. Reformulations and branch-and-price algorithm for the minimum cost hop-and-root constrained forest problem. Computers & Operations Research, 98:38–55, 2018.

[34]   Dilson Lucas Pereira and Alexandre Salles da Cunha. Dynamic intersection of multiple implicit dantzig-wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem. European Journal of Operational Research, 284(2):413–426, 2020.

[35]   Dilson Lucas Pereira, Dilson Almeida Guimarães, Alexandre Salles da Cunha, and Abilio Lucena. Quadratically constrained reformulation, strong semidefinite programming bounds, and algorithms for the chordless cycle problem. In Amitabh Basu, Ali Ridha Mahjoub, and Juan José Salazar González, editors, Combinatorial Optimization - 8th International Symposium, ISCO 2024, La Laguna, Tenerife, Spain, May 22-24, 2024, Revised Selected Papers, volume 14594 of Lecture Notes in Computer Science, pages 30–42. Springer, 2024.

[36]   Dilson Lucas Pereira, Abilio Lucena, Alexandre Salles da Cunha, and Luidi Simonetti. Exact solution algorithms for the chordless cycle problem. INFORMS Journal on Computing, 34, 2022.

[37]   Pereira, D. L., Gendreau, M. and da Cunha, A.S. Stronger lower bounds for the quadratic minimum spanning tree problem with adjacency costs. Electronic Notes in Discrete Mathematics, 41:229–236, 2013.

[38]   Pereira, D. L., Gendreau, M. and da Cunha, A.S. Branch-and-cut and branch-and-cut-and-price algorithms for the adjacent only quadratic minimum spanning tree problem. Networks, 65:367–379, 2015.

[39]   Pereira, D. L., Gendreau, M. and da Cunha, A.S. Lower bounds and exact algorithms for the quadratic minimum spanning tree problem. Computers and Operations Research, 63:149–160, 2015.

[40]   F. A. Santos, G. R. Mateus, and A. S. da Cunha. The pickup and delivery problem with cross-docking. Computers & Operations Research, 40(4):1085–1093, 2013.

[41]   F. A. Santos, G. R. Mateus, and A. S. da Cunha. A Branch-and-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem. Transportation Science, 49:355–368, 2015.

[42]   Santos, F. A., da Cunha, A.S., and Mateus, G. R. A branch-and-price algorithm for the two-echelon capacitated vehicle routing problem. Optimization Letters, 7:1537–1547, 2013.

[43]   Simonetti L, da Cunha AS, Lucena A. The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and Branch-and-cut Algorithm. Lecture Notes in Computer Science, LNCS 6701:162–169, 2011. Network Optimization - Proceedings of the 5th International Network Optimization Conference, Hamburg.

[44]   C.A. Valle, A.S. Cunha, G.R. Mateus, and L.C. Martinez. Exact algorithms for a selective Vehicle Routing Problem where the longest route is minimized. Electronic Notes in Discrete Mathematics, 35:133–138, 2009.