O problema da subsequência comum máxima sem repetições

Prévia do material em texto

O problema da subsequência comum
máxima sem repetições
Christian Tjandraatmadja
Dissertação apresentada
ao
Instituto de Matemática e Estatística
da
Universidade de São Paulo
para
obtenção do título
de
Mestre em Ciências
Programa: Ciência da Computação
Orientador: Prof. Dr. Carlos Eduardo Ferreira
Durante o desenvolvimento deste trabalho o autor recebeu auxílio financeiro da FAPESP através do
processo 07/57149-5
São Paulo, julho de 2010
O problema da subsequência comum
máxima sem repetições
Esta versão definitiva da dissertação
contém as correções e alterações sugeridas pela
Comissão Julgadora durante a defesa realizada
por Christian Tjandraatmadja em 26/7/2010.
Comissão Julgadora:
• Prof. Dr. Carlos Eduardo Ferreira (orientador) - IME-USP
• Prof.a Dr.a Yoshiko Wakabayashi - IME-USP
• Prof.a Dr.a Marie-France Sagot - UCBL-FRANÇA
Agradecimentos
Agradeço à minha família, em especial meus pais, pelo sempre presente apoio e pelo extensivo
esforço em me ajudarem a chegar onde estou.
Agradeço a todos os meus amigos, pela companhia, apoio, diversão e amizade em geral que me
trouxeram todos esses anos. Tenho muita sorte por conhecer os amigos que conheço. Em particular,
agradeço ao Jan M. P. G. e ao Stefan T., dois grandes amigos de inúmeras qualidades que muito me
influenciaram de forma positiva nestes últimos anos. Aprecio também as interessantes discussões de
programação inteira que tive com o Alexandre da S. F. durante o mestrado.
Agradeço aos meus professores, em particular,
• ao prof. Carlos Eduardo Ferreira, excelente orientador e professor, sempre disposto, com
bastante interesse e entusiasmo, a me oferecer ótimos conselhos e ideias e a me guiar na
superação dos desafios que surgiram neste trabalho; aprecio também seu esforço para tornar
possíveis viagens para conferências e cursos que certamente contribuíram para minha formação;
• à prof.a Yoshiko Wakabayashi, uma professora excelente pela qual tenho muito respeito
particularmente devido à sua notável atenção e esforço em dar impulso à aprendizagem de
seus alunos; sou grato pelo seu interesse em minha formação, pela sua participação em ambas
as minhas bancas e pelos valiosos conselhos e sugestões dados quanto a este trabalho;
• à prof.a Cristina Gomes Fernandes, que sempre mostrou interesse e teve uma grande parte no
desenvolvimento deste trabalho particularmente perto de seu início, oferecendo interessantes
comentários e sugestões sempre com o entusiasmo de explorar possíveis caminhos;
• ao prof. Paulo Feofiloff, pelo qual tenho grande respeito por suas notáveis qualidades como
professor; particularmente por, no curso de graduação, ter me feito enxergar a elegância em
algoritmos, graças à sua habilidade em elaborar e dar aulas que têm precisão e “encaixam”;
• ao prof. José Coelho de Pina, que participou em minha banca de qualificação e trouxe
comentários detalhados e ótimas sugestões para este trabalho;
• ao prof. Roberto Hirata Jr., por sempre demonstrar interesse mesmo sendo de uma área
diferente; e
• à prof.a Marie-France Sagot, pela participação em minha banca e seus interessantes comentários
sobre este trabalho.
Enfim, fico feliz por ter conhecido e aprendido com todos estes professores, que certamente foram
importantes para minha formação.
Resumo
Exploramos o seguinte problema: dadas duas sequências X e Y sobre um alfabeto finito, encontre
uma subsequência comum máxima de X e Y sem símbolos repetidos. Estudamos a estrutura deste
problema, particularmente do ponto de vista de grafos e de combinatória poliédrica. Desenvolvemos
algoritmos de aproximação e heurísticas para este problema. O enfoque deste trabalho está na
construção de um algoritmo baseado na técnica branch-and-cut, aproveitando-nos de um algoritmo
de separação eficiente e de heurísticas e técnicas para encontrarmos uma solução ótima mais cedo.
Também estudamos um problema mais fácil no qual este problema é baseado: dadas duas
sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y .
Exploramos este problema do ponto de vista de combinatória poliédrica e descrevemos vários
algoritmos conhecidos para resolvê-lo.
Palavras-chave: Subsequência comum máxima sem repetições, subsequência comum máxima,
programação inteira, combinatória poliédrica, branch-and-cut, algoritmos de aproximação, heurísti-
cas.
Abstract
We explore the following problem: given two sequences X and Y over a finite alphabet, find a
longest common subsequence of X and Y without repeated symbols. We study the structure of
this problem, particularly from the point of view of graphs and polyhedral combinatorics. We
develop approximation algorithms and heuristics for this problem. The focus of this work is in
the construction of an algorithm based on the branch-and-cut technique, taking advantage of an
efficient separation algorithm and of heuristics and techniques to find an optimal solution earlier.
We also study an easier problem on which this problem is based: given two sequences X and Y
over a finite alphabet, find a longest common subsequence of X and Y . We explore this problem
from the point of view of polyhedral combinatorics and describe several known algorithms to solve it.
Keywords: Repetition-free longest common subsequence, longest common subsequence, integer
programming, polyhedral combinatorics, branch-and-cut, approximation algorithms, heuristics.
Sumário
1 Introdução 13
1.1 Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.1 Problema do LCS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.2 Problema do RFLCS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2 Organização do texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3 Informações sobre os resultados computacionais . . . . . . . . . . . . . . . . . . . . . 16
2 Os problemas e suas estruturas 17
2.1 Descrição dos problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Conceitos estruturais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Grafos de cruzamento e de conflito . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 Formulações e poliedros 21
3.1 Preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Formulações para LCS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 Formulações para RFLCS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.1 Formulação por estrelas estendidas . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.2 Formulação por símbolos distintos . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4 Limitantes e gap de integralidade para RFLCS . . . . . . . . . . . . . . . . . . . . . 39
4 Aproximabilidade e heurísticas para RFLCS 41
4.1 Preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2 Algoritmos de aproximação baseados em remoção de repetições . . . . . . . . . . . . 42
4.2.1 LCS e remove repetições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2.2 Remove repetições e LCS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.3 Heurísticas gulosas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3.1 Escolha simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3.2 Menor número de conflitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3.3 Maior limitante de casamento . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4 Resultados computacionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.5 Inaproximabilidade do RFLCS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.5.1 Preliminares. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.5.2 Uma L-redução de MAX 2,3-SAT para uma versão restrita do RFLCS . . . . 49
9
5 Algoritmo branch-and-cut para RFLCS 55
5.1 A técnica branch-and-cut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.2 Algoritmo de separação para estrelas estendidas maximais . . . . . . . . . . . . . . . 56
5.2.1 Algoritmo de separação baseado em programação dinâmica . . . . . . . . . . 57
5.2.2 Algoritmo de separação baseado em limiares . . . . . . . . . . . . . . . . . . . 62
5.2.3 Comparação entre os dois algoritmos de separação . . . . . . . . . . . . . . . 69
5.3 Heurísticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.4 Limitante de casamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.5 Pré-processamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.6 Resultados computacionais gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
6 Algoritmos de enumeração para RFLCS 81
6.1 Decomposição em subproblemas fáceis . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.2 Decomposição em subproblemas fáceis com branch-and-bound . . . . . . . . . . . . . 82
6.3 Programação dinâmica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.4 Conjunto independente no grafo de conflito . . . . . . . . . . . . . . . . . . . . . . . 88
7 Algoritmos para LCS 89
7.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.2 Algoritmo de programação dinâmica . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.3 Visualização da estrutura do LCS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.4 Algoritmo por limiares de Hunt e Szymanski . . . . . . . . . . . . . . . . . . . . . . 95
7.4.1 Modificação por Kuo e Cross . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.5 Algoritmo por contornos de Hirschberg . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.6 Modificações dos algoritmos de Hirschberg e de Hunt-Szymanski por Apostolico e
Guerra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
7.6.1 Modificação do algoritmo de Hirschberg . . . . . . . . . . . . . . . . . . . . . 107
7.6.2 Modificação do algoritmo de Hunt-Szymanski . . . . . . . . . . . . . . . . . . 110
7.7 Algoritmo por preenchimento de diagonais de Nakatsu, Kambayashi e Yajima . . . . 111
7.8 Algoritmo de divisão e conquista de Hirschberg em espaço linear . . . . . . . . . . . 115
7.9 Algoritmo de subdivisão de matriz de Masek e Paterson . . . . . . . . . . . . . . . . 118
7.10 Algoritmo por limiares e saltos para casamentos . . . . . . . . . . . . . . . . . . . . . 120
7.11 Resultados computacionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
7.12 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
8 Conclusão 127
A Técnicas não usadas no algoritmo branch-and-cut 129
A.1 Algoritmo de separação para circuito ímpar . . . . . . . . . . . . . . . . . . . . . . . 129
A.2 Pool de inequações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
A.3 Atualização da matriz de programação dinâmica no algoritmo de separação . . . . . 131
B Comparação entre resultados computacionais usando CPLEX e GLPK 133
10
C Dados numéricos dos resultados computacionais 135
C.1 Algoritmos de aproximação e heurísticas . . . . . . . . . . . . . . . . . . . . . . . . . 135
C.2 Algoritmos de separação de estrela estendida . . . . . . . . . . . . . . . . . . . . . . 138
C.3 Heurísticas no branch-and-cut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
C.4 Variáveis fixadas através de limitantes de casamento . . . . . . . . . . . . . . . . . . 140
C.5 Resultados gerais do algoritmo branch-and-cut . . . . . . . . . . . . . . . . . . . . . 140
C.6 Formulação por símbolos distintos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
C.7 Formulação por cruzamentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
C.8 Algoritmos de decomposição em subproblemas . . . . . . . . . . . . . . . . . . . . . 142
C.9 Algoritmo de programação dinâmica . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
C.10 Algoritmos de conjunto independente . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
C.11 Algoritmos para o LCS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
Créditos 147
Referências Bibliográficas 149
11
12
Capítulo 1
Introdução
O objetivo deste trabalho é explorar a fundo um problema de otimização combinatória denominado
problema da subsequência comum máxima sem repetições e desenvolver um algoritmo exato eficiente
para o problema. No decorrer deste trabalho estudamos também o problema do qual ele é derivado,
o problema da subsequência comum máxima.
O problema de comparar duas sequências surge em diversas aplicações. Um critério comum para
comparar duas sequências consiste em olhar para a mais longa sequência da qual podemos obter
cada uma das duas apenas adicionando símbolos a ela (nesse sentido, é uma espécie de ancestral).
Se for possível obter uma sequência desse tipo que é longa, então as duas sequências são similares.
O problema de encontrar a sequência mais longa desse tipo é o problema da subsequência comum
máxima, ou LCS (longest common subsequence).
O problema estudado neste trabalho é uma variante do problema do LCS: o problema da sub-
sequência comum máxima sem repetições, ou RFLCS (repetition-free longest common subsequence).
Ele é um problema pouco estudado, mas, assim como o problema do LCS, pode ser usado para
determinar a similaridade entre duas sequências. No entanto, o critério usado tem uma condição
adicional: a sequência usada como critério pode ter no máximo uma ocorrência de cada símbolo do
alfabeto. Este critério é útil para comparar genomas em que hajam famílias de genes, como veremos
na seção seguinte.
Os problemas serão definidos formalmente e exemplos serão dados no capítulo seguinte.
1.1 Aplicações
1.1.1 Problema do LCS
O problema do LCS é um problema bem conhecido e estudado em computação. Uma aplicação
relativamente recente do problema do LCS e de bastante interesse é a comparação de segmentos de
DNA e de proteínas. Podemos estar interessados em saber o grau de similaridade de dois segmentos,
que pode ser um indicativo de que têm um ancestral comum parecido com os dois. Com a evolução,
nucleotídeos ou aminoácidos podem ter sido inseridos, removidos ou alterados, e o comprimento de
um LCS dos segmentos é uma medida que considera bem isso. Atualmente existem outras variantes
do LCS para compará-los mais precisamente, pois existem outras transformações que podem ocorrer
com esses segmentos conforme a evolução, mas o problema do LCS não deixa de ter um papel muito
importante nas comparações.
13
Capítulo 1. Introdução
Uma outra aplicação é comparar arquivos, como no programa Unix diff. Queremos comparar
dois arquivos e saber quais linhas foram inseridas ou removidas. Se considerarmos um arquivo como
uma sequência de linhas, um LCS nos dá o “núcleo” que pertence a ambos os arquivos, e para saber
quais linhas foram inseridas ou removidas, basta observar a diferença entre esse “núcleo” e algum
dos arquivos. A comparação de arquivos também é útil para sistemas de controle de versão.
Mais uma aplicação é corrigir erros ortográficos – podemos procurar palavras dentro de um
dicionário que tenha um LCS de comprimento alto entre ela e a palavra incorreta. Também existem
aplicações em compressão de dados, reconhecimento de voz, atualização de tela em monitores CRT,
entre outras. Algumas dessas aplicações e outras são descritas em [42].
1.1.2 Problema do RFLCS
Devido a característicasde sequências, diversas variantes do problema do LCS surgiram. O problema
do RFLCS é uma delas, e sua aplicação vem da comparação entre genomas, levando em conta a
teoria de rearranjo de genomas. Nessa abordagem, representamos cada gene como um símbolo,
sem se preocupar com sua estrutura interna, e consideramos a evolução de genomas baseada em
processos de rearranjo.
Durante esses processos, duplicatas de genes podem surgir de diversas maneiras. Uma suposição
comum feita para comparar rearranjos de genomas é que cada gene é homólogo a no máximo um
gene de outro genoma. Em outras palavras, dadas duas sequências X e Y de genomas, essa suposição
diz que, dado um símbolo em X, só pode ter no máximo uma ocorrência desse símbolo em Y . Essa
suposição tem fundamento para alguns genomas pequenos, como os de vírus ou de mitocôndrias, e
torna o problema mais fácil, já que o comprimento de um LCS é uma medida boa para esse caso.
No entanto, para genomas maiores, ela é problemática devido ao número de duplicatas de genes.
No genoma humano, aproximadamente 15% dos genes de proteína são duplicatas [31]. Ainda mais,
a situação é complicada pelo processo de divergência de sequência, no qual as duplicatas podem se
tornar estruturalmente e funcionalmente diferentes até o ponto de deixarem de ser duplicatas, mas
continuam sendo da mesma família de genes, que são homólogas e funcionalmente similares.
Com esse conceito de família de genes, em vez de considerar cada gene separadamente, podemos
considerar um representante de cada família, chamado de exemplar. Usando essa ideia, Sankoff [39]
propõe uma medida de comparação de genes, denominado de distância exemplar. Ademais, com
base nessa medida, Bonizzoni et al. [6] estuda variantes do LCS chamados de subsequência comum
máxima exemplar (exemplar longest common subsequence, ELCS), que consideram um conjunto de
símbolos obrigatórios na subsequência. Uma dessas variantes limita em 1 o número de ocorrências
de cada símbolo opcional e, assim, é uma generalização do RFLCS. Outra generalização do problema
do RFLCS também é considerada em [7], em que os autores juntam o problema do RFLCS com o
problema do CLCS (constrained longest common subsequence).
O comprimento de um RFLCS é uma outra medida que leva em consideração a noção de exemplar.
Ele pode ser visto como uma medida de similaridade entre dois genomas na qual, para cada família
de genes, desconsideramos todos os genes exceto um representante da família, o exemplar.
Uma noção melhor sobre rearranjo de genomas e duplicação de genes pode ser obtida em [41, 40].
Em particular, a variante do problema do RFLCS que permite reversões de sequências é
uma medida boa para evidenciar uma conjectura que afirma que o cromossomo Y é derivado do
cromossomo X a partir de cinco grandes reversões [30, 44]. Nessas referências, observa-se que o
cromossomo X é dividido em quatro ou cinco trechos (estratos) que são comparáveis com partes do
cromossomo Y em termos da distância entre eles.
14
Capítulo 1. Introdução
1.2 Organização do texto
Os capítulos seguintes são organizados como abaixo.
Capítulo 2: Os problemas e suas estruturas. Iniciamos descrevendo alguns conceitos impor-
tantes para resolver os problemas do LCS e do RFLCS e apresentamos uma visão dos problemas
sob o ponto de vista de grafos.
Capítulo 3: Formulações e poliedros. Prosseguimos com formulações de programação inteira
para os problemas do LCS e do RFLCS e provamos que as inequações das formulações são
“fortes” do ponto de vista de poliedros. Além disso, mostramos que o poliedro da formulação
para o problema do LCS descreve por completo o poliedro associado ao problema. Na última
seção desse capítulo, descrevemos limitantes para o comprimento de um RFLCS. Esse capítulo
contém a maior parte dos resultados teóricos desta dissertação.
Capítulo 4: Aproximabilidade e heurísticas para RFLCS. Nesse capítulo, descrevemos al-
goritmos de aproximação e heurísticas para o problema do RFLCS e mostramos o resultado de
dificuldade sobre a aproximabilidade do problema desenvolvido por Adi et al. [1]. Apresentamos
alguns resultados computacionais dos algoritmos.
Capítulo 5: Algoritmo branch-and-cut para RFLCS. Os dois capítulos anteriores formam
a base para esse capítulo, que descreve a implementação de um algoritmo baseado na técnica
branch-and-cut para o problema do RFLCS. Ele é baseado em uma formulação do Capítulo 3
e usa heurísticas inspiradas nos algoritmos de aproximação e heurísticas do Capítulo 4, além
de usar técnicas para permitir que uma solução ótima seja encontrada mais cedo. Mostramos
resultados computacionais do algoritmo.
Capítulo 6: Algoritmos de enumeração para RFLCS. Esse curto capítulo descreve mais al-
guns algoritmos exatos para o problema do RFLCS que se aproveitam da estrutura do
problema para enumerar soluções e encontrar uma solução ótima no processo. Apresentamos
dois algoritmos que enumeram subproblemas computacionalmente mais fáceis de se resolver e
um algoritmo de programação dinâmica eficiente para alfabetos muito pequenos. Também
mostramos resultados computacionais desses algoritmos. Além disso, comparamos o consumo
de tempo do algoritmo branch-and-cut com os de dois algoritmos de conjunto independente
no grafo relacionado ao problema.
Capítulo 7: Algoritmos para LCS. Estudamos e implementamos alguns algoritmos para o
problema do LCS. Em particular, a Seção 7.10 apresenta um algoritmo para o problema do
LCS que não encontramos na literatura.
Para o leitor que não conhece nenhum algoritmo para resolver o problema do LCS, pode
valer a pena pelo menos conhecer o algoritmo de programação dinâmica lendo a Seção
7.2. Mais adiante, descreveremos um algoritmo que faz parte do algoritmo branch-and-cut
(algoritmo de separação) que usa como base os algoritmos de programação dinâmica e de Hunt
e Szymanski, da Seção 7.4. O restante dos algoritmos descritos no Capítulo 7 não são usados
em nenhum outro capítulo desta dissertação, com exceção de uma técnica por Apostolico e
Guerra (Seção 7.6.1) usada no algoritmo de programação dinâmica (Seção 6.3). Apresentamos
resultados computacionais das implementações.
15
Capítulo 1. Introdução
O Capítulo 7 é uma resenha auto-contida e o leitor que deseja apenas estudar algoritmos para
o problema do LCS pode pular diretamente para esse capítulo.
Finalmente, o Capítulo 8 resume os principais resultados obtidos nesta dissertação de mestrado
e sugere alguns trabalhos futuros que podem ser realizados.
Além dos capítulos, esta dissertação contém três apêndices. O primeiro apêndice comenta
algumas técnicas que foram implementadas mas não usadas no algoritmo branch-and-cut por
não contruibuírem ao algoritmo. O segundo compara a implementação do algoritmo, que usa a
biblioteca GLPK, com uma mesma implementação que usa a biblioteca comercial CPLEX. O terceiro
documenta os valores numéricos dos resultados computacionais dos gráficos apresentados nesta
dissertação (recomendamos ao leitor interessado que observe os valores numéricos junto com os
gráficos).
Este trabalho foi desenvolvido com contribuições técnicas diretas de algumas pessoas. A seção
de Créditos no final desta dissertação menciona as contribuições, especificando que partes o autor e
essas pessoas tiveram neste trabalho.
1.3 Informações sobre os resultados computacionais
Todas as instâncias usadas para os testes foram sequências geradas de forma aleatória e uniforme de
acordo com o alfabeto. Isto é, para cada posição na sequência, escolhemos um símbolo aleatório do
alfabeto. Ambas as sequências geradas para cada teste são do mesmo comprimento.
Em todos os testes que envolveram programação linear, foi usada a biblioteca de código aberto
GLPK 4.41 [14], que cuida da resolução de programas lineares e organiza a estrutura do algoritmo
branch-and-cut (com exceção da formulação por cruzamentos, para o qual foi usada a versão 4.31
pela razãoexplicada no Apêndice C.7).
Todos os resultados computacionais neste texto foram obtidos a partir da média de 10 execuções.
A máquina utilizada para realizar os testes roda Linux, é 64-bit e tem dois processadores Intel R©
Xeon R© E5440 (quad-core), com velocidade de clock 2.83GHz, e 32GB de RAM. Cada execução foi
sequencial (usou apenas uma thread).
Para facilitar a identificação das curvas nos gráficos, as legendas dos gráficos estão ordenadas na
mesma ordem em que os valores estão na margem direita do gráfico (ou, se a curva não atingir a
margem direita, o valor que a atingiria se a curva crescesse na mesma taxa).
16
Capítulo 2
Os problemas e suas estruturas
Neste capítulo, descrevemos os problemas do LCS e do RFLCS e exploramos suas características
estruturais. Tal investigação é especialmente importante para o desenvolvimento do algoritmo exato
para o problema do RFLCS do Capítulo 5.
2.1 Descrição dos problemas
Defina um alfabeto como um conjunto finito cujos elementos são chamados de símbolos. Por
exemplo, o conjunto de letras Σ = {a,b, c, . . . , z} é um alfabeto. Uma sequência é uma lista
ordenada de símbolos de algum alfabeto. Por exemplo, uma palavra como projeto é uma sequência
sobre o alfabeto Σ do exemplo anterior.
Dada uma sequência qualquer Z, denote por zi o seu i-ésimo símbolo, por |Z| o seu comprimento,
e por Z[r..s] a subsequência zrzr+1 . . . zs.
Dada uma sequência X sobre algum alfabeto (por exemplo, X = mestrado), Z é uma sub-
sequência de X se podemos obter Z removendo zero ou mais símbolos de X (por exemplo, Z pode
ser etrdo). Vale ressaltar que os símbolos de Z não precisam estar em ordem contígua em X e, além
disso, Z pode ser vazio ou ser igual a X. Formalmente, Z é uma subsequência de X se existe uma
sequência estritamente crescente i1i2 . . . ik de índices de X tal que zj = xij para todo j = 1, . . . , |Z|.
Uma subsequência comum de duas sequências X e Y é uma sequência que é tanto sub-
sequência de X como de Y (por exemplo, se X = mestrado e Y = matrizes, ela pode ser ma).
Uma subsequência comum máxima ou LCS (longest common subsequence) de X e Y é uma
subsequência comum de comprimento máximo entre todas as subsequências comuns de X e Y (no
exemplo anterior, ela pode ser mtr ou mes). O problema do LCS é encontrar um LCS de duas
sequências.
Dizemos que uma sequência é sem repetições se não contém dois símbolos que são iguais no
alfabeto (por exemplo, a sequência abcd é sem repetições enquanto abca tem repetições). Assim, uma
subsequência comum máxima sem repetições ou RFLCS (repetition-free longest common
subsequence) de X e Y é uma subsequência comum sem repetições de comprimento máximo entre
todas as subsequências comuns sem repetições de X e Y . O problema do RFLCS é encontrar
um RFLCS de duas sequências.
Nesta dissertação, as sequências X e Y estão implícitas (a menos que definidas explicitamente).
Assim, quando nos referirmos a uma subsequência comum, LCS, ou RFLCS, estamos nos referindo
a uma subsequência comum, LCS, ou RFLCS das duas sequências X e Y para as quais queremos
17
Capítulo 2. Os problemas e suas estruturas
resolver o problema do LCS ou do RFLCS, dependendo do contexto. O alfabeto Σ também está
implícito nesta dissertação como o alfabeto que contém os símbolos de X e Y .
Observe que nem sempre podemos obter um RFLCS removendo os símbolos repetidos de um
LCS. Por exemplo, se X = aaabc e Y = bcaaa, então o único LCS de X e Y é aaa, mas o único
RFLCS de X e Y é bc.
LCS
c a a d b d
a b a c d a d
a a d d
c a a d b d
a b a c d a d
c a dRFLCS
O problema do LCS pode ser resolvido usando programação dinâmica em tempo O(mn), onde m
e n são os comprimentos das duas sequências para as quais se quer encontrar um LCS (Seção 7.2). Já
o problema do RFLCS é APX-difícil [1]. Em outras palavras, adicionar essa restrição aparentemente
simples não só torna o problema NP-difícil como também faz com que seja impossível encontrar, a
menos que P = NP, um esquema de aproximação polinomial para o problema (descrito na Seção
4.1).
2.2 Conceitos estruturais
Defina um casamento como um par ordenado de índices (i, j) para o qual xi = yj , isto é, o i-ésimo
símbolo de X é igual ao j-ésimo símbolo de Y . Cada casamento (i, j) está associado a um símbolo
xi (= yj). Seja C o conjunto de casamentos associados a X e Y . Dizemos que dois casamentos
(i, j) ∈ C e (k, l) ∈ C se cruzam se i ≥ k e j ≤ l, ou i ≤ k e j ≥ l (representando os casamentos
graficamente como abaixo, eles se cruzam se e só se eles se intersectam graficamente). Dizemos
também que um casamento conflita com outro se eles se cruzam ou seus símbolos são iguais.
a b c e c d a e
e c a b d a c c
a b c e c d a e
e c a b d a c c
a b c e c d a e
e c a b d a c c
casamentos
a b c e c d a e
e c a b d a c c
casamentos que se cruzam
casamentos que conflitam um com o outro
Dizemos que (i, j) precede (k, l) (ou (k, l) sucede (i, j)) se i < k e j < l, e denotamos isso por
(i, j) ≺ (k, l). Isto é, (i, j) não cruza com (k, l) e está à esquerda de (k, l) na representação gráfica.
É fácil ver que, dado um conjunto de casamentos C = {(i1, j1), (i2, j2), . . . , (ik, jk)}, seus
elementos não se cruzam dois a dois se e só se eles podem ser ordenados de forma que (il1 , jl1) ≺
(il2 , jl2) ≺ . . . ≺ (ilk , jlk), onde (l1, l2, . . . , lk) é uma permutação de {1, 2, . . . , k}. Assim, dizemos
que um conjunto de casamentos C = {(i1, j1), (i2, j2), . . . , (ik, jk)} com seus elementos ordenados
de tal maneira é uma representação da subsequência comum S = xi1xi2 . . . xik = yj1yj2 . . . yjk .
Note que, embora toda representação esteja associada a uma subsequência comum, uma mesma
subsequência comum pode ter mais de uma representação, como ilustrado na figura seguinte.
18
Capítulo 2. Os problemas e suas estruturas
a b c e c d a e
e c a b d a c c
c d a
a b c e c d a e
e c a b d a c c
c d a
i1 i2 i3 i4 ik
...
...
j1 j2 j3 j4 jk...
1 2 3 4 k
duas representações distintas 
da subsequência comum cda
σ σ σ σ σ
A relação entre esses conceitos e os problemas estudados é clara: é de interesse buscar uma
representação de cardinalidade máxima, livre ou não de repetições dependendo do problema, pois
dela obtemos um RFLCS ou um LCS. É importante observar que, se o conjunto de casamentos
não conflitam entre si dois a dois, então ele representa uma subsequência comum sem repetições.
Todos os algoritmos exatos para o problema do LCS e do RFLCS comentados neste texto primeiro
encontram uma representação, implicitamente ou explicitamente, e dela se constrói um LCS ou um
RFLCS.
2.3 Grafos de cruzamento e de conflito
É interessante observar os conceitos anteriores sob o ponto de vista de grafos. Um grafo é um par
(V,E), onde V é um conjunto finito cujos elementos são chamados de vértices, e E é uma família
de pares não-ordenados de V chamados de arestas.
Defina Gcr = (Vcr, Ecr) como o grafo de cruzamento de X e Y , onde Vcr é o conjunto
de casamentos de X e Y e uma aresta (u, v) ∈ Ecr se e só se os casamentos u e v se cruzam.
Analogamente, defina o grafo de conflito Gc da mesma forma, mas a aresta (u, v) pertence ao
grafo se e só se u conflita com v.
Sejam occX(σ) e occY (σ) o número de ocorrências do símbolo σ ∈ Σ em X e Y respectivamente
e seja Σ′ ⊆ Σ o conjunto de símbolos σ tal que occX(σ) > 1 e occY (σ) > 1. Então o grafo de conflito
tem exatamente ∑σ∈Σ′ (occX(σ)2 )(occY (σ)2 ) arestas a mais que o grafo de cruzamento. No exemplo
abaixo, as quatro arestas destacadas no grafo de conflito são a única diferença entre os dois grafos.
Grafo de cruzamento Grafo de conflito
a b c e c d a e
e
c
a
b
d
a
c
c
a b c e c d a e
e
c
a
b
d
a
c
c
19
Capítulo 2. Os problemas e suas estruturas
Para resolver o problema do LCS ou do RFLCS, buscamos um conjunto de casamentos que,
dois a dois, não se cruzamou não conflitam um com o outro respectivamente. Portanto, é o
mesmo que procurar um conjunto independente máximo para o grafo de cruzamento ou de conflito
respectivamente (um conjunto independente máximo é um conjunto de vértices dois a dois não
adjacentes de cardinalidade máxima).
Grafo de cruzamento Grafo de conflito
a b c e c d a e
e
c
a
b
d
a
c
c
a b c e c d a e
e
c
a
b
d
a
c
c
a b c e c d a e
e c a b d a c c
a d ab
RFLCSLCS
a b c e c d a e
e c a b d a c c
c d ae
Seja ≺c uma ordem parcial tal que (i, j) ≺c (k, l) se i ≤ k e j ≥ l (ela é uma ordem parcial pois
é reflexiva, antissimétrica e transitiva). Com isso, podemos reescrever a definição de cruzamento da
seguinte forma: (i, j) e (k, l) se cruzam se (i, j) ≺c (k, l) e (k, l) ≺c (i, j). Portanto, por definição,
o grafo de cruzamento pertence à classe dos grafos de comparabilidade. Sabe-se que o problema
do conjunto independente para grafos de comparabilidade é computacionalmente fácil, o que é
consistente com o fato que o problema do LCS é também um problema fácil.
Tome o complemento de Gc, Gc. Dois casamentos são adjacentes em Gc se e só se eles não se
cruzam. Como ≺ é uma ordem parcial estrita (ela é irreflexiva, antissimétrica e transitiva), Gc
também é um grafo de comparabilidade. Nesse caso, o problema do LCS é equivalente ao problema
do clique máximo em Gc, que é equivalente ao problema do caminho mínimo na orientação transitiva
em Gc, por ser um grafo de comparabilidade.
Já o grafo de conflito não tem essa propriedade. Em particular, o grafo de conflito não pertence
à classe dos grafos perfeitos (que contém a classe dos grafos de comparabilidade), pois se pertencesse,
o problema do RFLCS seria polinomialmente tratável, já que o problema do conjunto independente
máximo também o é em grafos perfeitos. (As relações entre grafos de comparabilidade, grafos
perfeitos, e o problema do conjunto independente máximo podem ser encontradas em [15]. Voltaremos
a falar sobre grafos de comparabilidade e grafos perfeitos na segunda prova do Teorema 3.2.3.)
20
Capítulo 3
Formulações e poliedros
Neste capítulo, investigamos possíveis formulações para os problemas do LCS e do RFLCS, e
exploramos características dos poliedros associados a essas formulações.
3.1 Preliminares
Descrevemos brevemente alguns conceitos básicos de programação linear, programação inteira e
combinatória poliédrica necessários para o entendimento deste capítulo. Esta seção é baseada no
livro de Wolsey [46].
Um programa linear é, de uma forma geral, um problema de maximizar ou minimizar uma
função linear sobre um poliedro, dado por um sistema de inequações lineares. Trataremos apenas
de problemas de maximização nesta seção; o de minimização é análogo.
Mais formalmente, um programa linear é um problema do tipo
maximize cx (função objetivo)
sujeito a Ax ≤ b (sistema de inequações lineares)
x ≥ 0
onde x é um vetor coluna de variáveis de dimensão n, e o restante são dados: A é uma matriz m
por n, c é um vetor linha de dimensão n, e b é um vetor coluna de dimensão m (0 denota o vetor
zero neste caso). Em outras palavras, queremos encontrar um vetor x que maximiza cx e satisfaz as
restrições Ax ≤ b e x ≥ 0.
Exemplo 3.1.1. Se o problema é de maximização, e n = 2, m = 3, x = (x1, x2) ∈ R2, c = (1, 2),
A =
 1 12 −1
−1 1
 e b =
 56
2
, então temos o programa linear: maximize x1 + 2x2
sujeito a x1 + x2 ≤ 5
2x1 − x2 ≤ 6
−x1 + x2 ≤ 2
x1 ≥ 0
x2 ≥ 0
21
Capítulo 3. Formulações e poliedros
Uma solução viável é um vetor x que satisfaz as restrições do programa linear. Uma solução
ótima é uma solução viável que maximiza a função objetivo, isto é, é uma solução propriamente
dita do problema.
Um poliedro é um conjunto {x ∈ Rn | Ax ≤ b} para alguma matriz A ∈ Rm×n e vetor b ∈ Rm.
O poliedro associado à formulação linear anterior ao exemplo é
P := {x ∈ Rn | Ax ≤ b, x ≥ 0}.
Exemplo 3.1.2. O poliedro do exemplo anterior é o conjunto P := {(x1, x2) ∈ R2 | x1 + x2 ≤ 5,
2x1 − x2 ≤ 6, − x1 + x2 ≤ 2, x1 ≥ 0, x2 ≥ 0}, ilustrado pela região sombreada delimitada pelas
retas abaixo.
x1
x2
2x1 – x2 ≤ 6
x1 + x2 ≤ 5
–x1 + x2 ≤ 2
0 1 2 3 4 5
1
2
3
4
5
P
Programas lineares podem ser resolvidos usando o método simplex, desenvolvido por Dantzig
em 1947 [10]. A ideia do método, em termos gerais, é encontrar um vértice do poliedro e andar
de vértice em vértice adjacente sempre aumentando o valor da função objetivo até não ser mais
possível. O método simplex funciona bem na prática e é bastante usado, embora não se saiba até
agora um limitante superior polinomial para seu consumo de tempo. A figura seguinte ilustra, em
linhas gerais, a ideia do método simplex.
x1
x2
0 1 2 3
1
2
3
x1
x2
0 1 2 3
1
2
3
x1
x2
0 1 2 3
1
2
3
solução
ótima
solução 
viável inicial
direção da
função obj.
Em 1979 e 1984, Khachiyan [26] e Karmarkar [24] desenvolveram dois outros métodos para
resolver programas lineares: o método do elipsoide e o método dos pontos interiores, respectivamente.
Ambos os métodos consomem tempo polinomial, apesar do primeiro não ser rápido o suficiente para
aplicações práticas. Já o segundo é comparável com o método simplex na prática.
22
Capítulo 3. Formulações e poliedros
Um programa linear inteiro (ou apenas programa inteiro) é um programa linear no qual
adicionamos a restrição de que as variáveis são inteiras, como a seguir.
max cx
s. a Ax ≤ b
x ∈ Zn+
Os métodos mencionados para resolver um programa linear não resolvem um programa inteiro,
especialmente pelo fato de que as soluções viáveis do problema não formam um conjunto convexo.
Ainda mais, o problema geral de resolver um programa inteiro é NP-difícil. Veremos como resolver
um programa inteiro (particularmente, um relacionado ao problema do RFLCS) no Capítulo 5.
O casco convexo de um conjunto de pontos P , denotado por conv(P ), é o conjunto convexo
minimal que contém P . Mais formalmente, se P = {x1, . . . , xk}, então conv(P ) = {λ1x1+. . .+λkxk |
λ1 + . . .+ λk = 1, λ1, . . . , λk ≥ 0}. O casco convexo de um conjunto finito de pontos é um poliedro
limitado.
O poliedro associado à formulação inteira anterior é
PI := conv{x ∈ Zn+ | Ax ≤ b}.
Se A e b têm valores racionais, então conv(PI) é um poliedro racional [33].
Exemplo 3.1.3. Os pontos em preto da figura ao lado são as soluções
da formulação inteira dada pelo exemplo anterior adicionando a restri-
ção de integralidade. A região sombreada, definida pelos traços cheios,
definem o casco convexo dessas soluções, e, portanto, definem PI (as
linhas pontilhadas são do poliedro original P ).
x1
x2
0 1 2 3 4
1
2
3
4
PI
A relaxação linear de um programa inteiro é o programa linear obtido ao remover a restrição
de integralidade do programa inteiro. Por exemplo, a relaxação linear do programa inteiro anterior
é max{cx | Ax ≤ b, x ≥ 0}, e o poliedro associado a ele é {x ∈ Rn | Ax ≤ b, x ≥ 0}. Idealmente,
gostaríamos de ter o poliedro associado à formulação inteira, mas, se o problema for NP-difícil e
NP 6= co-NP, não é possível obter uma descrição completa dele de forma que exista uma “prova
curta” para toda inequação linear que o define de que ela é necessária para o poliedro [25]. Então,
trabalhamos, em geral, com o poliedro associado à relaxação linear, que podemos obter diretamente
da formulação.
Uma inequação é válida para um poliedro P se ela é satisfeita por todos os pontos de P . Uma
inequação válida pix ≤ pi0 domina uma outra inequação válida µx ≤ µ0 se existe u > 0 tal que
pi ≥ uµ e pi0 ≤ uµ0.1 Note que se pix ≤ pi0 domina µx ≤ µ0, então toda solução x não-negativa que
satisfaz a primeira inequação também satisfaz a segunda.
Os pontos x1, x2, . . . , xk são linearmente independentes se, quando
∑k
i=1 αixi = 0, onde
αi ∈ R,temos que α1 = α2 = . . . = αk = 0. Os pontos x1, x2, . . . , xk são afim-independentes se os
1A definição usual inclui a condição de que (pi, pi0) 6= (uµ, uµ0). Neste texto, desconsideraremos essa condição por
conveniência.
23
Capítulo 3. Formulações e poliedros
k−1 pontos x2−x1, . . . , xk−x1 são linearmente independentes, ou os k pontos (x1, 1), . . . , (xk, 1) são
linearmente independentes. Afim-independência é análogo a independência linear desconsiderando a
origem (todo conjunto de pontos linearmente independentes são também afim-independentes).
A dimensão de um poliedro P é o número máximo de pontos afim-independentes em P menos
um. Um poliedro P ⊆ Rn tem dimensão plena se sua dimensão é n. Isso implica que não existe
equação ax = b satisfeita por todos os pontos de P , onde a ∈ Rn e b ∈ R. Pode-se provar que se um
poliedro tem dimensão plena, então ele tem uma descrição minimal única (cujas inequações são
únicas a menos de um múltiplo positivo).
Uma face de um poliedro P é um conjunto F = {x ∈ P | pix = pi0} para alguma inequação
válida pix ≤ pi0. Dizemos que essa inequação define a face. Uma face é uma faceta se sua dimensão
é a dimensão do poliedro menos um.
Exemplo 3.1.4. Ainda considerando as inequações e os
poliedros dos exemplos anteriores, as inequações x1 +x2 ≤ 5,
−x1 + x2 ≤ 2, x1 ≥ 0 e x2 ≥ 0 definem facetas de PI . A
única inequação das anteriores que não define uma faceta
é 2x1 − x2 ≤ 6, pois existe apenas um ponto x do poliedro
tal que 2x1 − x2 = 6. Note que as inequações x1 ≤ 3 e
x2 ≤ 3, não presentes nas inequações anteriores, definem
facetas de PI . Com essas inequações, temos uma descrição
completa de PI . x1
x2
0 1 2 3
1
2
3
PI
2x1 – x2 ≤ 6 define
uma face de dim. 0
–x1 + x2 ≤ 2 define
uma faceta (dim. 1)
O foco deste capítulo é descrever formulações e provar que algumas inequações definem facetas
de poliedros associados aos problemas do LCS e do RFLCS. A importância disso é que, se um
poliedro P tem dimensão plena, então uma inequação válida de P define faceta se e só se ela é
necessária na descrição de P (isto é, não existe outra inequação válida além de um múltiplo dela
que a domina).
3.2 Formulações para LCS
Como vimos no capítulo anterior, resolver o problema do LCS é equivalente a escolher um conjunto
de casamentos de cardinalidade máxima em que não haja dois casamentos que se cruzam. Em outras
palavras, para cada dois casamentos que se cruzam, podemos apenas escolher um deles. Usando
isso, construiremos, a seguir, uma formulação de programação inteira que é válida para o problema
do LCS.
Para todo casamento (i, j) em C, seja zij uma variável que é 1 se o casamento (i, j) está na
representação da subsequência comum associada a z, ou é 0 em caso contrário.
max
∑
(i,j)∈C
zij (formulação por cruzamentos)
s. a zij + zkl ≤ 1 para todo (i, j) e (k, l) em C que se cruzam,
zij ∈ {0, 1} para todo (i, j) em C.
24
Capítulo 3. Formulações e poliedros
O poliedro associado à relaxação linear da formulação é
PC := {z ∈ RC | zij + zkl ≤ 1 para todo (i, j) e (k, l) em C que se cruzam, e
0 ≤ zij ≤ 1 para todo (i, j) em C}.
Sobre PC , apenas faremos a observação de que PC pode ter vértices fracionários (isto é, não-
inteiros). De fato, tome o caso em que as sequências de entrada são X = abc e Y = cba, ou seja,
existem apenas três casamentos (1, 3), (2, 2) e (3, 1) que se cruzam dois a dois. Então as inequações
de cruzamento são z13 + z22 ≤ 1, z13 + z31 ≤ 1 e z22 + z31 ≤ 1. O ponto fracionário (12 , 12 , 12) é um
vértice do poliedro, pois pertence ao poliedro e satisfaz d = 3 inequações com igualdade, onde d é a
dimensão do poliedro.
O ideal seria o poliedro não ter vértices fracionários, pois otimizar sobre tal poliedro nos daria
sempre um ponto inteiro, que é o que queremos. Observe que, se substituirmos essas 3 inequações
pela inequação z13 + z22 + z31 ≤ 1, o ponto fracionário (12 , 12 , 12) deixa de ser um vértice do poliedro
pois ele viola a inequação, e a formulação inteira original continua sendo válida sob este poliedro
pois a nova inequação não elimina nenhum ponto inteiro do poliedro.
( , , )1
2
1
2
1
2
x3
x2 + x3 ≤ 1
(0,1,0)
(1,0,0)
(0,0,1)
x1 + x2 ≤ 1
x1
x2
x1 + x3 ≤ 1
(0,1,0)
(1,0,0)
(0,0,1)
x1 + x2 + x3 ≤ 1
x3
x1
x2
A seguir, construiremos uma outra formulação mais forte com inequações como a última do
exemplo acima e, mais adiante, mostraremos que o poliedro dado por esse tipo de inequações tem
apenas vértices inteiros.
Uma estrela é um conjunto de casamentos que se cruzam dois a dois (ilustrada na página
seguinte), ou seja, é um clique no grafo de cruzamento definido na Seção 2.3 (um clique de um
grafo é um conjunto de vértices dois a dois adjacentes). Dizemos que uma estrela S é maximal
se não existe nenhum casamento que pode ser acrescentado a S de forma a se obter uma estrela
maior. Note que, para qualquer estrela maximal S, podemos escolher no máximo um casamento de
S para estar em uma representação de uma subsequência comum. Construiremos, a seguir, uma
formulação baseada nesse fato.
Seja z ∈ {0, 1}C uma variável como na formulação anterior, isto é, zij = 1 se e só se (i, j) pertence
à representação dada por z.
max
∑
(i,j)∈C
zij (formulação por estrelas)
s. a
∑
(i,j)∈S
zij ≤ 1 para toda estrela maximal S ⊆ C,
zij ∈ {0, 1} para todo (i, j) em C.
25
Capítulo 3. Formulações e poliedros
a b c e c d a e
e
c
a
b
d
a
c
c
a b c e c d a e
e c a b d a c c
estrela maximal
Uma relaxação linear da formulação pode ser obtida trocando zij ∈ {0, 1} por zij ≥ 0 (não são
necessárias as inequações zij ≤ 1 pois as inequações de estrela as dominam).
Vale comentar que a formulação é a formulação por cliques para o problema do conjunto
independente máximo, mas restrito a grafos de cruzamento (ela aparece no contexto de conjunto
independente máximo, por exemplo, na referência [16]). As inequações ∑v∈K zv ≤ 1 para todo
clique maximal K são chamadas de inequações de clique e são válidas para o problema do conjunto
independente máximo. As inequações baseadas em estrelas maximais são uma adaptação das
inequações de clique, uma vez que uma estrela é um clique no grafo de cruzamento.
Como todo par de casamentos que se cruzam está contido em alguma estrela maximal, as
restrições baseadas em cruzamento são dominadas pelas restrições baseadas em estrelas maximais.
Logo, o poliedro associado à formulação por cruzamentos está contido no poliedro associado à
formulação por estrelas. Ainda mais, podemos provar um resultado mais forte: o poliedro associado
à formulação por estrelas é o melhor poliedro possível (o mais justo) em termos de representações
de subsequências comuns.
Defina o poliedro do problema do LCS como
Plcs := conv{z ∈ {0, 1}C | z representa uma subsequência comum de X e Y }.
Observe primeiro que o poliedro Plcs tem dimensão |C|, isto é, tem dimensão plena. De fato, o
vetor zero e os |C| vetores unitários eij para todo (i, j) ∈ C estão em Plcs e são afim-independentes
(um vetor unitário ek tem valor 1 na posição k e 0 nas restantes).
Provaremos a seguir que as inequações da relaxação linear da formulação por estrelas,∑
(i,j)∈S
zij ≤ 1 para toda estrela maximal S ⊆ C, e (inequação de estrela)
zij ≥ 0 para todo (i, j) em C, (inequação de não-negatividade)
definem facetas de Plcs.
Proposição 3.2.1. Para todo (i, j) em C, a inequação de não-negatividade zij ≥ 0 define uma
faceta de Plcs.
Prova. Considere um casamento (i, j) ∈ C. O vetor zero e os vetores unitários ekl para todo
(k, l) 6= (i, j) estão contidos na face {z ∈ Plcs | zij = 0} e são afim-independentes. Portanto, zij ≥ 0
define uma faceta.
26
Capítulo 3. Formulações e poliedros
Lema 3.2.2. Considere uma estrela S ⊆ C. Então a inequação de estrela ∑(i,j)∈S zij ≤ 1 define
uma faceta de Plcs se e só se S é maximal.Prova. Mostraremos primeiro que a inequação de estrela define uma faceta quando S é maximal.
Seja F a face definida em Plcs pela inequação de estrela, isto é, F := {z ∈ Plcs |∑(i,j)∈S zij = 1}.
Suponha que S é maximal. Então, para cada casamento (k, l) em C r S, existe um casamento
(i, j) em S que não cruza com (k, l). Tome os |C| − |S| vetores ekl + eij para todo par de casamentos
(k, l) e (i, j) dessa forma. Como eles representam uma subsequência comum e satisfazem a igualdade∑
(i,j)∈S zij = 1, eles pertencem à face F . Além disso, os |S| vetores eij para todo (i, j) em S
também pertencem a F . Esses |C| vetores são afim-independentes e, assim, F é uma faceta de Plcs.
Agora, suponha que F é uma faceta de Plcs. Se S não é maximal, então existe uma estrela
maximal S′ que contém S, e ∑(i,j)∈S zij ≤ 1 pode ser escrito como uma soma da inequação∑
(i′,j′)∈S′ zi′j′ ≤ 1 com as inequações −zkl ≤ 0 para todo (k, l) em S′ r S, o que é uma contradição.
Considere o poliedro associado à relaxação linear da formulação por estrelas, isto é, dado pelas
inequações de estrela e de não-negatividade:
PS := {z ∈ RC |
∑
(i,j)∈S
zij ≤ 1 para toda estrela maximal S ⊆ C, e
zij ≥ 0 para todo (i, j) ∈ C}.
Provaremos que as inequações de estrela e de não-negatividade definem o poliedro do problema
do LCS por completo, isto é:
Teorema 3.2.3. Plcs = PS.
Apresentaremos duas provas do teorema acima, ambas por Fernandes et al. [12]. A primeira
prova mostra diretamente que toda inequação que define faceta de Plcs é uma inequação de estrela
ou de não-negatividade. A segunda prova usa um teorema de Chvátal relacionando grafos perfeitos
e poliedros de clique.
Antes de apresentarmos as demonstrações, uma primeira tentativa para provar o teorema seria
verificar se a matriz de restrições A da relaxação linear da formulação por estrelas é totalmente
unimodular. Uma matriz é totalmente unimodular se o determinante de toda submatriz quadrada
dela é 1, 0 ou −1. Pode-se provar que se a matriz de restrições de um programa linear for totalmente
unimodular e o lado direito das inequações tiver apenas valores inteiros, então os vértices do poliedro
associado a esse programa são inteiros [46], o que provaria o teorema. No entanto, no caso do LCS,
nem sempre a matriz de restrições de estrela é totalmente unimodular, como no exemplo em que
X = abcdef e Y = efcdab, cuja matriz de restrições possui um subdeterminante −2.
Prova 1. (Teorema 3.2.3) Seja az ≤ α uma inequação que define uma faceta F de Plcs. Isto é,
F := {z ∈ Plcs | az = α}.
27
Capítulo 3. Formulações e poliedros
Sejam F1(i, j) e F2(S) as facetas definidas pelas inequações de não-negatividade para (i, j) e de
estrela para S respectivamente. Isto é,
F1(i, j) := {z ∈ RC | zij = 0}, e
F2(S) := {z ∈ RC |
∑
(i,j)∈S
zij = 1}.
Como F é faceta, é suficiente provarmos que F ⊆ F1(i, j) para algum (i, j) em C, ou F ⊆ F2(S)
para alguma estrela maximal S ⊆ C.
Denote por F -representação um conjunto de casamentos que representa uma subsequência
comum cujo vetor de incidência z pertence a F (um vetor de incidência z de um conjunto S é aquele
em que zs = 1 se s ∈ S, ou zs = 0 caso contrário). Como os vértices de Plcs são inteiros, é suficiente
considerar apenas vetores z em Plcs que são vetores de incidência de alguma F -representação.
Primeiro, suponha que existe (i, j) em C tal que aij < 0. Qualquer F -representação R satisfaz
zij = 0, pois, caso contrário (se zij = 1), Rr {(i, j)} também representa uma subsequência comum,
mas a(z − eij) = az − aij > α, isto é, z − eij não pertence a Plcs, o que é um absurdo. Portanto,
F ⊆ F1(i, j).
Podemos supor então que aij ≥ 0 para todo (i, j) em C.
Seja T o vetor suporte para az ≤ α, isto é, T := {(i, j) ∈ C | aij > 0}. Como a inequação define
faceta, podemos supor que T 6= ∅.
Seja R uma F -representação e z seu vetor de incidência. Se zij = 0 para qualquer (i, j) em T ,
então ∑(i,j)∈T aijzij = 0, e, logo, α = 0. Então, como aij ≥ 0 para todo (i, j) em C e a 6= 0, existe
um (i′, j′) em C tal que zi′j′ = 0 para qualquer vetor de incidência z de uma F -representação e,
portanto, F ⊆ F1(i′, j′).
Assim, podemos supor que, para qualquer F -representação, existe (i, j) em T tal que zij = 1.
Definiremos agora uma ordem lexicográfica entre conjuntos de casamentos. Considere dois
subconjuntos S1 e S2 de C ordenados de forma que (i, j) vem antes de (k, l) se i < k ou (i = k e
j < l). Dizemos que S1 é lexicograficamente menor ou igual a S2 se, sob a ordem acima, ou S1 é
prefixo de S2, ou, para o primeiro índice p tal que o p-ésimo casamento (i1, j1) de S1 é diferente
do p-ésimo casamento (i2, j2) de S2, (i1, j1) vem antes de (i2, j2) na ordem acima (se existir tal p).
Esta ordem lexicográfica é uma ordem total.
Seja S1 a primeira estrela maximal em T em ordem lexicográfica. Provaremos que F ⊆ F2(S1).
Para isso, temos que mostrar que sempre vale ∑(i,j)∈S1 zij = 1 para qualquer vetor de incidência z
de uma F -representação.
Suponha, por contradição, que existe uma F -representação R com vetor de incidência z tal que
zij = 0 para todo casamento em S1. Como existe (i, j) em T tal que zij = 1, R ∩ (T r S1) 6= ∅.
Então cada casamento (i, j) em S1 cruza com algum casamento em R∩ (T rS1), pois, caso contrário,
R ∪ {(i, j)} representaria uma subsequência comum e a(z + eij) = az + aij > α, isto é, z + eij não
pertenceria a Plcs, o que é um absurdo.
Mostraremos agora que existe um par de casamentos distintos (i, j) e (k, l) em R∩(TrS1) tal que
todo casamento em S1 cruza com (i, j) ou com (k, l). De fato, suponha que tal par não existe. Então,
para qualquer par de casamentos distintos em R ∩ (T r S1), existe um casamento em S1 que não
cruza com nenhum dos dois. Lembremos da definição de precedência entre casamentos: (i, j) precede
(k, l), ou (i, j) ≺ (k, l), se i < k e j < l. Considere dois casamentos (i1, j1) e (i2, j2) em R∩ (T r S1)
tal que (i1, j1) precede imediatamente (i2, j2), e seja (k, l) um casamento em S1 que não cruza
28
Capítulo 3. Formulações e poliedros
com nenhum dos dois. Se (i1, j1) ≺ (k, l) ≺ (i2, j2), então (k, l) não cruza com nenhum casamento
em R ∩ (T r S1), uma contradição. Caso contrário, para todo par desse tipo, (k, l) ≺ (i1, j1) ou
(i2, j2) ≺ (k, l). Em ordem de precedência, tome o primeiro par de casamentos (i1, j1) e (i2, j2) de
R∩ (T rS1), com (i1, j1) precedendo imediatamente (i2, j2), tal que (k, l) ≺ (i1, j1), onde (k, l) é um
casamento em S1 que não cruza com (i1, j1) ou (i2, j2). Se (i1, j1) for o primeiro casamento ou se tal
par não existir (ou seja, (i2, j2) ≺ (k, l) para o último casamento (i2, j2) em R∩ (T rS1)), então, em
ambos os casos, (k, l) não cruza com nenhum casamento de R ∩ (T r S1), o que é uma contradição.
Assim, existe um casamento (i0, j0) em R ∩ (T r S1) que precede imediatamente (i1, j1), e vale que
(i1, j1) ≺ (k′, l′) para algum (k′, l′) em S1 que não cruza com (i0, j0) ou (i1, j1), já que (i1, j1) e
(i2, j2) são o primeiro par tal que (k, l) ≺ (i1, j1). Mas então (k, l) ≺ (k′, l′), ou seja, existem dois
casamentos de S1 que não se cruzam, o que é uma contradição.
Considere tal par (i, j) e (k, l) e suponha, sem perda de generalidade, que (i, j) ≺ (k, l). Como
S1 é a primeira estrela maximal em ordem lexicográfica, existe um casamento (i1, j1) em S1 que
não cruza com (i, j) e é tal que i1 < i ou (i1 = i e j1 < j). De fato, caso contrário, ou S1
não seria maximal, ou todo casamento que não cruza com (i, j) vem depois de (i, j) (na ordem
definida anteriormente), o que implicaria que o conjunto S1 ∪ {(i, j)}r {(k, l) ∈ S1 | (k, l) não cruza
com (i, j)} seria uma estrela que vem antes de S1 em ordem lexicográfica, o que é um absurdo.
Logo, vale que (i1, j1) ≺ (i, j) ≺ (k, l). Assim, (i1, j1) não cruza nem com (i, j), nem com (k, l), o
que é uma contradição.
Logo, F ⊆ F2(S1).
Finalmente, note que F2(S′) ⊆ F2(S) para qualquer estrela S′ e qualquer estrelamaximal S que
contém S′. De fato, para todo z ∈ RC tal que ∑(i,j)∈S′ zij = 1, vale que ∑(i,j)∈S zij ≥ 1. Como S é
uma estrela, ∑(i,j)∈S zij = 1.
Assim, F ⊆ F2(S) para alguma estrela maximal S que contém S1.
A segunda prova requer que olhemos para o problema sob o ponto de vista de grafos novamente.
A prova se baseia essencialmente no teorema de Chvátal a seguir. Lembremos que um clique é
um conjunto de vértices dois a dois adjacentes e um conjunto independente é um conjunto de vértices
dois a dois não-adjacentes. Dizemos que G é um grafo perfeito se, para cada subgrafo induzido G′
de G, o tamanho de um clique máximo de G′ é igual ao número mínimo de cores necessárias para
colorir os vértices de G′ de forma que dois vértices adjacentes não tenham a mesma cor.
Teorema 3.2.4 (Chvátal [9]). Seja G = (V,E) um grafo. Considere o poliedro
P := {z ∈ RV |
∑
v∈S
zv ≤ 1 para todo conjunto independente maximal S ⊆ V , e
zv ≥ 0 para todo v ∈ V }.
Então P é o casco convexo dos cliques de G se e somente se G é perfeito.
Uma prova do teorema acima pode ser encontrada nas referências [15, 43].
Prova 2. (Teorema 3.2.3) Usando-se o teorema de Chvátal acima, a prova é simples. Considere
o complemento do grafo de cruzamento Gc definido na Seção 2.3: Gc = (C, E) é o grafo onde os
vértices são os casamentos e dois casamentos são adjacentes se e só se eles não se cruzam. Lembremos
também da relação da precedência entre casamentos: (i, j) ≺ (k, l) se i < k e j < l. A relação ≺ é
29
Capítulo 3. Formulações e poliedros
uma ordem parcial estrita, pois ela é irreflexiva ((i, j) 6≺ (i, j)), antissimétrica (se (i1, j1) ≺ (i2, j2) e
(i2, j2) ≺ (i1, j1), então (i1, j1) = (i2, j2)) e transitiva (se (i1, j1) ≺ (i2, j2) e (i2, j2) ≺ (i3, j3), então
(i1, j1) ≺ (i3, j3)). Como dois casamentos (i, j) e (k, l) são adjacentes em Gc se e só se (i, j) ≺ (k, l)
ou (k, l) ≺ (i, j), Gc pertence à classe dos grafos de comparabilidade, por definição.
Veremos agora que todo grafo de comparabilidade é perfeito [11, 15]. De fato, sejam G um grafo
de comparabilidade e F sua orientação transitiva. Tome uma coloração c tal que c(v) = 0 se v
não tem arcos de saída em F , e c(v) = 1 + max{c(w) | vw ∈ F} caso contrário. É fácil ver que a
coloração c é própria em G (isto é, dois vértices adjacentes não têm a mesma cor) e o número de
cores usadas é o comprimento de um caminho máximo em F . Além disso, como F é transitiva, os
vértices de um caminho em F correspondem a um clique em G. Portanto, temos uma coloração
própria do tamanho de um clique máximo. Além disso, como todo subgrafo induzido de um grafo
de comparabilidade também é de comparabilidade, a mesma propriedade vale para os subgrafos
induzidos de G. Logo, G é um grafo perfeito.
Seja P o poliedro enunciado no teorema de Chvátal para Gc. Um conjunto independente, no
contexto de Gc, é um conjunto de casamentos que se cruzam dois a dois, que é exatamente a
definição de estrela. Portanto, podemos enunciar P da seguinte forma:
P = {z ∈ RC |
∑
(i,j)∈C
zij ≤ 1 para toda estrela maximal S ⊆ C, e
zij ≥ 0 para todo (i, j) ∈ C}.
Vemos que P = PS . Pelo teorema de Chvátal, P = PS é o casco convexo dos cliques de Gc. Um
clique em Gc é um conjunto de casamentos que não se cruzam dois a dois, ou seja, uma representação.
Portanto, PS é o casco convexo dos conjuntos de casamentos que representam uma subsequência
comum, isto é, PS = Plcs.
Nesta seção, descrevemos de forma completa e minimal o poliedro do problema do LCS através
de inequações lineares. Assim, qualquer solução básica ótima z∗ da relaxação linear da formulação
por estrelas (isto é, uma solução ótima que corresponde a um vértice do poliedro) é inteira e, logo,
representa um LCS. Portanto, podemos resolver o problema do LCS apenas resolvendo um programa
linear. Isso é apenas interessante em teoria, pois, na prática, já temos algoritmos que resolvem o
problema do LCS de forma muito mais eficiente que um algoritmo que usa a formulação por estrelas.
Como o problema de otimização sobre um poliedro e o problema de separação de suas inequações
são computacionalmente equivalentes [16], e conhecemos um algoritmo polinomial para separar
as inequações (uma versão mais simples do algoritmo de separação para o problema do RFLCS
descrito na Seção 5.2), então sabemos que é possível otimizar sobre o poliedro do problema do LCS
em tempo polinomial. Isso é consistente com o fato do problema do LCS ser resolvível em tempo
polinomial usando programação dinâmica.
Esta seção, porém, se reflete indiretamente na prática ao servir de apoio para a seção seguinte,
na qual desenvolvemos a base teórica para um algoritmo que resolve a variante sem repetições do
problema do LCS.
30
Capítulo 3. Formulações e poliedros
3.3 Formulações para RFLCS
Veremos nesta seção algumas características dos poliedros do problema do RFLCS e de um outro
problema equivalente. O algoritmo baseado em branch-and-cut implementado, que descreveremos
no Capítulo 5, é relacionado à formulação principal da subseção seguinte.
3.3.1 Formulação por estrelas estendidas
Uma primeira formulação para o problema do RFLCS é simplesmente adicionar à formulação do
problema do LCS a restrição de que queremos no máximo uma ocorrência de cada símbolo do
alfabeto na subsequência comum obtida. A seguir, estendemos tanto a formulação baseada em
cruzamento como a baseada em estrelas, e ambas as formulações são válidas para o problema do
RFLCS.
Para todo casamento (i, j) em C, seja zij uma variável que é 1 se o casamento (i, j) está na
representação da subsequência comum associada a z, ou é 0 caso contrário. Seja C(σ) o conjunto
dos casamentos em C que são do símbolo σ.
max
∑
(i,j)∈C
zij
s. a
∑
(i,j)∈C(σ)
zij ≤ 1 para todo σ em Σ,
zij + zkl ≤ 1 para todo (i, j) e (k, l) em C que se cruzam,
zij ∈ {0, 1} para todo (i, j) em C.
A formulação seguinte é baseada na formulação por estrelas do problema do LCS.
max
∑
(i,j)∈C
zij
s. a
∑
(i,j)∈C(σ)
zij ≤ 1 para todo σ em Σ,∑
(i,j)∈S
zij ≤ 1 para toda estrela maximal S ⊆ C,
zij ∈ {0, 1} para todo (i, j) em C.
Do ponto de vista de poliedros, a segunda formulação é mais forte que a primeira pelo mesmo
motivo que no problema do LCS (as inequações de estrela dominam as de cruzamento). Porém,
ainda vale tentar obter uma formulação mais forte ainda.
Lembremos que um casamento conflita com outro se eles se cruzam ou são do mesmo símbolo, e
que encontrar um RFLCS de duas sequências é equivalente a encontrar um conjunto de casamentos
que dois a dois não conflitam entre si. É natural então a formulação seguinte.
max
∑
(i,j)∈C
zij (formulação por conflitos)
s. a zij + zkl ≤ 1 para todo (i, j) e (k, l) em C que conflitam entre si,
zij ∈ {0, 1} para todo (i, j) em C.
A formulação acima nos lembra da formulação por cruzamentos para o problema do LCS. De
31
Capítulo 3. Formulações e poliedros
forma análoga à que fizemos com estrelas na seção anterior, estenderemos o conceito de conflito para
considerar conjuntos de casamentos em vez de pares. Defina uma estrela estendida como um
conjunto de casamentos que dois a dois conflitam entre si (ou seja, é um clique no grafo de conflito).
É verdade que, para toda estrela estendida maximal, podemos escolher apenas um casamento dela
para estar em uma representação de uma subsequência comum sem repetições.
a b c e c d a e
e
c
a
b
d
a
c
c
a b c e c d a e
e c a b d a c c
estrela estendida maximal
Seja zij uma variável como na formulação anterior: é 1 se o casamento (i, j) está na representação
da subsequência comum sem repetições associada a z, ou é 0 em caso contrário. A seguinte formulação
é válida para o problema do RFLCS.
max
∑
(i,j)∈C
zij (formulação por estrelas estendidas)
s. a
∑
(i,j)∈S
zij ≤ 1 para toda estrela estendida maximal S ⊆ C,
zij ∈ {0, 1} para todo (i, j) em C.
A formulaçãoacima é a base do algoritmo exato do Capítulo 5. Não é difícil ver que as inequações
da formulação acima dominam as inequações de todas as formulações anteriores. De fato, qualquer
par de casamentos que se cruzam ou que conflitam entre si, qualquer conjunto de todos os casamentos
de um mesmo símbolo, ou qualquer estrela maximal está contido em alguma estrela estendida
maximal.
Defina o poliedro do problema do RFLCS como
Prflcs := conv{z ∈ {0, 1}C | z representa uma subsequência comum sem repetições de X e Y }.
O poliedro Prflcs tem dimensão plena pois o vetor zero e os |C| vetores unitários eij para todo
(i, j) ∈ C estão em Prflcs e são afim-independentes.
As inequações da relaxação linear da formulação por estrelas estendidas,∑
(i,j)∈S
zij ≤ 1 para toda estrela estendida maximal S ⊆ C, e (inequação de estrela estendida)
zij ≥ 0 para todo (i, j) em C, (inequação de não-negatividade)
definem facetas de Prflcs.
32
Capítulo 3. Formulações e poliedros
Proposição 3.3.1. Para todo (i, j) em C, a inequação de não-negatividade zij ≥ 0 define uma
faceta de Prflcs.
Prova. Análoga à prova da Proposição 3.2.1, onde isso foi provado para Plcs.
Lema 3.3.2. Considere uma estrela estendida S ⊆ C. Então a inequação de estrela estendida∑
(i,j)∈S zij ≤ 1 define uma faceta de Prflcs se e só se S é maximal.
Prova. Análoga à prova da Proposição 3.2.2, onde foi provado que a inequação de estrela define
faceta para Plcs.
O poliedro associado à formulação não tem todos os vértices inteiros, pois o problema do RFLCS
é NP-difícil e, como já mencionado na primeira seção deste capítulo, não se espera ter uma descrição
explícita e completa do poliedro inteiro associado a um problema NP-difícil [25] (além disso, o
poliedro contém pontos fracionários que violam as inequações de buraco ímpar mais adiante).
Usaremos, no Capítulo 5, um método para adicionar as inequações de estrela estendida conforme
elas são necessárias. Essencialmente, otimizamos sobre um poliedro relaxado, procuramos uma
inequação de estrela estendida que é violada pela solução ótima do poliedro relaxado se existir,
adicionamos a inequação violada ao programa linear relaxado, e repetimos o processo até nenhuma
inequação de estrela estendida ser violada pela solução ótima de um poliedro relaxado. O problema
de encontrar tal inequação é chamado de problema da separação.
De acordo com as formulações que discutimos, o poliedro associado ao problema do RFLCS é
equivalente ao poliedro associado ao problema do conjunto independente máximo no correspondente
grafo de conflito. Assim, as inequações válidas para o poliedro do conjunto independente também
são válidas para o poliedro do RFLCS. Por exemplo, as seguintes inequações são válidas para o
problema do RFLCS, considerando o grafo de conflito:
∑
(i,j)∈B
zij ≤ |B| − 12 para todo buraco ímpar (odd hole) B ⊆ C, e∑
(i,j)∈A
zij ≤ 2 para todo anti-buraco ímpar (odd antihole) A ⊆ C.
a c b a d
b a d c a
buraco ímpar de
comprimento 5
a c b a d
b
a
d
c
a
anti-buraco ímpar
de comprimento 7
a b c a d c e
d c e a c b a
a b c a d c e
d
c
e
a
c
b
a
33
Capítulo 3. Formulações e poliedros
Um buraco ímpar é um circuito induzido de comprimento ímpar maior ou igual a 5, e um
anti-buraco ímpar é o complemento de um buraco ímpar. As duas inequações anteriores definem
facetas se o buraco ou anti-buraco ímpar for todo o conjunto de vértices do grafo de conflito [37].
Observe que essas inequações podem deixar o poliedro mais justo: no exemplo do buraco ímpar
dado, uma solução em que todos os casamentos destacados têm valor 12 (e os outros dois zero) é uma
solução fracionária válida para as inequações de estrela estendida que viola inequações de buraco
ímpar. O mesmo pode ser dito para o exemplo do anti-buraco ímpar dado, com uma solução em
que os casamentos destacados têm valor 13 e os outros zero.
Existem outras restrições que podem ser herdadas do problema do conjunto independente
máximo, mas elas costumam ser difíceis de se lidar. Discutiremos mais sobre a restrição de buraco
ímpar na Seção A.1 (apêndice).
3.3.2 Formulação por símbolos distintos
Descreveremos nesta seção uma formulação de programação inteira para um problema equivalente
ao problema do RFLCS.
Denotaremos uma subsequência comum com número máximo de símbolos (do alfabeto) distintos
por MSCS (maximum-symbol common subsequence). Dadas duas sequências X e Y , o problema
do MSCS é encontrar um MSCS de X e Y .
O problema do RFLCS e o problema do MSCS são equivalentes a menos de uma transformação
simples. Mais especificamente,
• Todo RFLCS de X e Y é um MSCS de X e Y .
• Para todo MSCS de X e Y , existe pelo menos um RFLCS de X e Y que é subsequência desse
MSCS (podendo ser ele próprio). Tal RFLCS pode ser obtido removendo símbolos repetidos
desse MSCS de forma a manter apenas uma ocorrência de cada símbolo.
Como consequência, o comprimento de um RFLCS é igual ao número de símbolos distintos de
um MSCS. Isto é, o valor ótimo de ambos os problemas são iguais. Note também que as soluções
viáveis do problema do MSCS contém as soluções viáveis do problema do RFLCS.
Exemplo 3.3.3. A figura ao lado mostra duas
sequências e todos os seus RFLCSs e MSCSs. Note
que todo RFLCS é um MSCS.
a b a c b
c b a a b
RFLCS
MSCS
subseq. comuns
a b c
ab ba cb aa bb
aab bab
Dado que conhecemos a formulação por estrelas para o problema do LCS, a seguinte formulação
é natural para o problema do MSCS.
Para todo (i, j) em C, seja zij uma variável binária como nas formulações anteriores: é 1 se
o casamento (i, j) está na representação da subsequência comum associada a z, ou é 0 em caso
contrário. Para todo σ em Σ, seja xσ uma variável binária igual a 1 se o símbolo σ ocorre na
solução, ou 0 caso contrário (na formulação seguinte, isso vale para uma solução ótima, mas não
necessariamente para qualquer solução viável; explicaremos isso melhor mais adiante). Seja C(σ) o
conjunto de casamentos em C que são do símbolo σ.
34
Capítulo 3. Formulações e poliedros
max
∑
σ∈Σ
xσ
s. a
∑
(i,j)∈S
zij ≤ 1 para toda estrela maximal S ⊆ C,
xσ ≤
∑
(i,j)∈C(σ)
zij para todo σ em Σ,
zij ∈ {0, 1} para todo (i, j) em C,
xσ ∈ {0, 1} para todo σ em Σ.
Obtemos, ao otimizar esse programa inteiro, um conjunto de casamentos que representa um
MSCS, e, se removermos casamentos de símbolos repetidos, o conjunto resultante representa um
RFLCS. De fato, na formulação, a primeira classe de inequações garante que z esteja associada a
uma representação de uma subsequência comum, e a segunda classe de inequações garante que xσ
seja 0 se não houver casamentos de símbolo σ na solução dada por z. Não é necessário forçar que a
variável xσ seja 1 se σ ocorre na solução, pois, ao maximizarmos a soma de todas essas variáveis,
isso sempre valerá já que xσ é limitado superiormente por 1. O poliedro mais adiante leva isso em
consideração.
Além disso, para todo σ em Σ, como zij é binária para todo (i, j) em C, e com a restrição xσ ≤ 1
implícita, xσ é limitado superiormente por um valor inteiro (0 ou 1). Logo, dado que o problema
é de maximização, xσ é binária na solução ótima mesmo sem forçar explicitamente que ela seja
binária. Portanto, para todo σ em Σ, a restrição xσ ∈ {0, 1} pode ser relaxada para as restrições
xσ ∈ R e xσ ≤ 1.
Considere o poliedro associado à formulação acima,
Pmscs := conv{(z, x) ∈ {0, 1}C × {0, 1}Σ | z representa uma subsequência comum de X e Y , e
xσ = 0 se σ não ocorre em z
(podendo ser 0 ou 1 caso contrário)}.
O resultado seguinte nos dá uma noção da força das inequações usadas na formulação anterior.
Lema 3.3.4. As seguintes restrições definem facetas de Pmscs:
(a) zij ≥ 0 para todo (i, j) em C tal que (i, j) não é o único casamento em C de seu símbolo;
(b)
∑
(i,j)∈S
zij ≤ 1 para toda estrela maximal S ⊆ C;
(c) xσ ≥ 0 para todo σ emΣ;
(d) xσ ≤
∑
(i,j)∈C(σ)
zij para todo σ em Σ.
Prova. Para provar que as restrições acima definem facetas, para cada caso, enumeraremos |C|+ |Σ|
vetores afim-independentes em Pmscs que satisfazem as inequações com igualdade. Supomos que
existe pelo menos um casamento em C de cada símbolo em Σ.
Denotamos por eij o vetor unitário para o casamento (i, j) e eσ o vetor unitário para o símbolo σ.
35
Capítulo 3. Formulações e poliedros
(a) zij ≥ 0 para todo (i, j) em C tal que (i, j) não é o único casamento em C de seu símbolo.
• vetor zero (1 vetor);
• vetores ekl para todo (k, l) em C, com (k, l) 6= (i, j) (|C| − 1 vetores);
• vetores eσ + ekl para todo σ em Σ, onde (k, l) é um casamento de símbolo σ diferente
de (i, j) (|Σ| vetores).
Um dos vetores deste último item não existe sem a suposição sobre (i, j) acima. Entretanto,
observe que se (i, j) é o único casamento de seu símbolo σ, a inequação zij ≥ xσ domina
zij ≥ 0 (dado que xσ ≥ 0) e também define faceta por ser uma inequação do tipo (d) (provado
mais adiante).
(b)
∑
(i,j)∈S
zij ≤ 1 para toda estrela maximal S ⊆ C.
• vetores eij para todo (i, j) em S (|S| vetores);
• vetores eij + ekl para todo (i, j) fora de S, onde (k, l) é um casamento de S que não cruza
com (i, j) ((k, l) existe pois S é maximal) (|C| − |S| vetores);
• vetores eσ + eij para todo σ em Σ tal que existe um casamento (i, j) de símbolo σ em S
(|Σ′| vetores para algum Σ′ ⊆ Σ);
• vetores eσ + eij + ekl para todo σ em Σ tal que não existe casamento de símbolo σ em S,
onde (i, j) é um casamento de símbolo σ fora de S e (k, l) é um casamento em S que não
cruza com (i, j) ((k, l) existe pois S é maximal) (|Σ| − |Σ′| vetores).
(c) xσ ≥ 0 para todo σ em Σ.
• vetor zero (1 vetor);
• vetores eij para todo (i, j) em C (|C| vetores);
• vetores eσ′ + eij para todo σ′ 6= σ em Σ, onde (i, j) é um casamento de símbolo σ′ (|Σ|−1
vetores).
(d) xσ ≤
∑
(i,j)∈C(σ)
zij para todo σ em Σ.
• vetor zero (1 vetor);
• vetores eij + eσ para todo (i, j) em C de símbolo σ (|C(σ)| vetores);
• vetores eij para todo (i, j) em C de símbolo diferente de σ (|C| − |C(σ)| vetores);
• vetores eσ′ + eij para todo σ′ 6= σ em Σ, onde (i, j) é um casamento de símbolo σ′ (|Σ|−1
vetores).
Para todos os casos acima, não é difícil ver que os vetores listados são afim-independentes. Nos
casos (a), (c) e (d), subtraímos o vetor zero dos outros vetores, e a matriz formada pelos vetores
como linhas na ordem dada, desconsiderando as colunas de zij , xσ e xσ respectivamente, é uma
matriz triangular com diagonal formada por 1s, o que significa que os vetores são linearmente
independentes. Já no caso (b), isso já vale sem precisar subtrair nenhum vetor de outros. Portanto,
em todos os casos, os vetores são afim-independentes.
36
Capítulo 3. Formulações e poliedros
A seguinte classe de inequações também é válida para Pmscs e define facetas.
Denote por estrela estendida especial (ou simplesmente estrela especial) um conjunto de
casamentos Sˆ de C tal que, para cada (i, j) e (k, l) em Sˆ, ou (i, j) e (k, l) se cruzam, ou (i, j) e (k, l)
não se cruzam mas são do mesmo símbolo σ e todo casamento de símbolo σ pertence a Sˆ (isto é,
C(σ) ⊆ Sˆ). Uma estrela especial maximal é um conjunto maximal desse tipo. Note que uma estrela
especial é uma estrela estendida.
Seja simb(Sˆ) o conjunto de símbolos σ tal que todo casamento de símbolo σ está em Sˆ e
existem pelo menos dois casamentos desse símbolo que não se cruzam. Seja rest(Sˆ) os casamentos
restantes, isto é, rest(Sˆ) = Sˆ r ∪σ∈simb(Sˆ)C(σ). Note que uma estrela é um caso particular de uma
estrela especial em que simb(Sˆ) = ∅ e rest(Sˆ) = Sˆ, e a classe de inequações abaixo inclui todas as
inequações de estrela.
A seguinte inequação é válida para Pmscs:∑
σ∈simb(Sˆ)
xσ +
∑
(i,j)∈rest(Sˆ)
zij ≤ 1 para toda estrela especial maximal Sˆ ⊆ C.
Denominamos a inequação acima de inequação de estrela especial.
É fácil ver que a inequação acima é válida. De fato, se escolhermos um casamento de Sˆ
de símbolo σ, não podemos escolher nenhum casamento em rest(Sˆ) ou de símbolo σ′ 6= σ em
simb(Sˆ) pois eles se cruzam (posso escolher outro casamento de símbolo σ que não cruza com ele se
σ ∈ simb(Sˆ), mas xσ ainda é limitado por 1).
Lema 3.3.5. Para qualquer estrela especial maximal Sˆ, a inequação de estrela especial Sˆ define
faceta de Pmscs.
Prova. Mostraremos |C| + |Σ| vetores afim-independentes em Pmscs que satisfazem a inequação
com igualdade.
Para todo (i, j) em Sˆ, seja
y1(i, j) =
{
eij se (i, j) está em rest(Sˆ), ou
eij + eσ caso contrário, onde σ é o símbolo de (i, j).
Para todo (i, j) em C r Sˆ, seja
y2(i, j) = eij + y1(k, l) tal que (k, l) é um casamento de Sˆ que não cruza com (i, j)
((k, l) existe pois Sˆ é maximal).
Para todo σ em Σr simb(Sˆ), seja
y3(σ) =
{
eij se existe casamento (i, j) de símbolo σ em Sˆ, ou
y2(i, j) caso contrário, onde (i, j) é um casamento de símbolo σ (fora de Sˆ).
Os vetores são os seguintes:
• vetores y1(i, j) para todo (i, j) em Sˆ (|Sˆ| vetores);
• vetores y2(i, j) para todo (i, j) em C r Sˆ (|C| − |Sˆ| vetores);
37
Capítulo 3. Formulações e poliedros
• vetores eσ + y3(σ) para todo σ em Σr simb(Sˆ) (|Σ| − |simb(Sˆ)| vetores);
• vetores eσ + eij + ekl para todo σ em simb(Sˆ), onde (i, j) e (k, l) são dois casamentos de
símbolo σ de Sˆ que não se cruzam ((i, j) e (k, l) existem pela definição de simb(Sˆ)) (|simb(Sˆ)|
vetores).
Provaremos indiretamente que os vetores listados são afim-independentes. Considere um hiper-
plano genérico ∑(i,j)∈C µijzij +∑σ∈Σ µσxσ = µ0. Se, colocando os vetores listados nesse hiperplano,
obtivermos uma única solução µ tal que µij = µ0 para todo casamento (i, j) em rest(Sˆ), µσ = µ0
para todo σ em simb(Sˆ) e µij = µσ = 0 para o restante dos casamentos (i, j) e símbolos σ, então o
único vetor de coeficientes (µ, µ0) possível é um múltiplo do vetor de coeficientes da inequação de
estrela especial, o que significa que os vetores são afim-independentes. Mostraremos que isso vale.
Pelo primeiro grupo de vetores, para todo (i, j) em rest(Sˆ), µij = µ0, e, para todo (i, j) em
Sˆ r rest(Sˆ), µij + µσ = µ0, onde σ é o símbolo de (i, j).
Pelo quarto grupo de vetores, para todo σ em simb(Sˆ), µσ + µij + µkl = µ0, onde (i, j) e (k, l)
são dois casamentos de símbolo σ que não se cruzam. Observe que (i, j) e (k, l) pertencem então
a Sˆ r rest(Sˆ). Logo, reescrevendo a segunda equação do primeiro grupo, µij = µkl = µ0 − µσ.
Aplicando isso na equação, temos que µσ + 2µ0 − 2µσ = µ0, isto é, µσ = µ0.
Voltando ao primeiro grupo de vetores, para todo (i, j) em Sˆ r rest(Sˆ), µij + µ0 = µ0, isto é,
µij = 0, pelo fato do símbolo de (i, j) estar em simb(Sˆ), junto com o fato anterior. Então,
µy1(i, j) = µ0 para todo (i, j) em Sˆ.
Pelo segundo grupo de vetores, para todo (i, j) em C r Sˆ, µij + µy1(k, l) = µ0, onde (k, l) é um
casamento em Sˆ que não cruza com (i, j). Logo, µij + µ0 = µ0, ou seja, µij = 0 para todo (i, j) em
C r Sˆ. Além disso, também obtemos que µy2(i, j) = µ0 para todo (i, j) em C r Sˆ.
Pelo terceiro grupo de vetores, para todo σ em Σr simb(Sˆ), µσ + µij = µ0 se existe casamento
(i, j) de símbolo σ em Sˆ, ou µσ + µy2(i, j) = µ0 caso contrário, para algum (i, j) em C r Sˆ de
símbolo σ. No primeiro caso, como σ /∈ simb(Sˆ), qualquer casamento de símbolo σ em Sˆ deve
estar em rest(Sˆ). Logo, nesse caso, µij = µ0, e, portanto, µσ = 0. No segundo caso, temos que
µσ + µ0 = µ0, isto é, µσ = 0.
Em resumo, temos que, para todo (i, j) em rest(Sˆ), µij = µ0, e, para todo σ em simb(Sˆ), µσ = µ0.
Para qualquer casamento (i, j) e símbolo σ no restante dos casos, µij = µσ = 0. Logo, os vetores
são afim-independentes.
Vale observar que, para qualquer σ em Σ, a inequação xσ ≤ 1 é dominada diretamente por uma
inequação de estrela especial se existir uma estrela especial maximal Sˆ tal que σ está em simb(Sˆ).
Se não existir, todos