Universidade Federal do ABC Centro de Matemática, Computaç˜ao

Universidade Federal do ABC
Centro de Matemática, Computação e Cognição (CMCC)
Pós-Graduação em Ciência da Computação
Omar Latorre Vilca
MÉTODOS PARA PROBLEMAS DE SELEÇÃO DE CADEIAS DE CARACTERES
Dissertação de Mestrado
Santo André - SP
2013
Omar Latorre Vilca
MÉTODOS PARA PROBLEMAS DE SELEÇÃO DE CADEIAS DE CARACTERES
Dissertação de Mestrado
Dissertação de Mestrado apresentada ao Curso de Pós-Graduação da Universidade
Federal do ABC como requisito parcial para obtenção do grau de Mestre em Ciência da
Computação
Orientador: Prof. Dr. Cláudio Nogueira de Meneses
Santo André - SP
2013
Ficha Catalográfica
Vilca, Omar Latorre.
Métodos para Problemas de Seleção de Cadeias de Caracteres /
Omar Latorre Vilca.
Santo André, SP: UFABC, 2013.
31 p.
Omar Latorre Vilca
MÉTODOS PARA PROBLEMAS DE SELEÇÃO DE CADEIAS DE CARACTERES
Essa Dissertação de Mestrado foi julgada e aprovada para a obtenção do grau
de Mestre em Ciência da Computação no curso de Pós-Graduação em Ciência da
Computação da Universidade Federal do ABC.
Santo André - SP - 2013
Prof. Dr. Ronaldo Cristiano Prati
Coordenador do Curso
BANCA EXAMINADORA
Prof. Dr. Cláudio Nogueira de Meneses
Profa. Dra. Maristela Oliveira dos Santos
Prof. Dr. João Paulo Gois
Prof. Dr. Ronaldo Cristiano Prati
AGRADECIMENTOS
À DEUS, por ter me dado condições de lutar e alcançar os objetivos pretendidos.
Ao Prof. Dr. Ronaldo Cristiano Prati, coordenador do Programa de Pós-Graduação
em Ciência da Computação, pelo esforço e dedicação e por estar sempre presente e sempre
disposto a resolver os problemas com os quais tivemos que vivenciar.
Ao Prof. Dr. Claudio Nogueira de Meneses, ogrigado pela oportunidade, pela orientação, pelos ensinamentos, ajuda e colaboração com o meu trabalho e pelas conversas e
conselhos ao longo do perı́odo do mestrado.
Ao Centro de Matemática, Computação e Cognição (CMCC) da Universidade Federal
do ABC (UFABC), pelo apoio na realização deste trabalho.
Agradeço a CAPES e UFABC pelos financiamentos, em bolsas, para o desenvolvimento
desta pesquisa.
E por fim, agradeço a todos que um dia acreditaram em mim.
Este trabalho contou com o auxı́lio financeiro das seguintes entidades:
• Universidade Federal do ABC - UFABC (bolsa de mestrado, institucional), de fevereiro/2011 a outubro/2011;
• Coordenação de Aperfeiçoamento de Pessoal de Nı́vel Superior - CAPES (bolsa de
mestrado, demanda social), de novembro/2011 a fevereiro/2013.
Resumo
Nesta pesquisa propomos métodos para resolver um problema de seleção de cadeias de
caracteres (strings) que surge na área de bioinformática. Este problema é conhecido pelo
nome Closest String Problem (CSP) e pode ser definido assim: dado um conjunto finito
S = {s1 , s2 , · · · , sn } com n strings, todas de mesmo tamanho m, sobre um alfabeto A,
deseja-se encontrar uma string x, de tamanho m, sobre A que minimiza o valor de d tal
que para cada string si ∈ S tem-se dH (x, si ) ≤ d. Por dH (x, s) queremos dizer a distância
de Hamming entre as strings x e s e ela é calculada tendo em conta o número de posições
em que as duas strings diferem. Por exemplo, se x = AT T e s = AT C, então dH (x, s) = 1,
pois x e s diferem apenas na última posição. O CSP pertence a classe de complexidade
computacional NP-difı́cil e são conhecidos algoritmos de aproximação e métodos exatos
para resolver esse problema. Como objetivo principal da pesquisa, desejamos desenvolver
métodos exatos baseados em programação linear inteira.
Palavras-chave: seleção de cadeias de caracteres, programação linear inteira, branchand-cut
1
Abstract
In this work we design methods to solve a string selection problem that arises in bioinformatics. This problem is called Closest String Problem (CSP) and is defined as: given
a finite set S = {s1 , · · · , sn } with n strings, every string of size m, over an alphabet A,
we want to find a string x, of size m, over A that minimizes the value d such that for
each string si ∈ S we have dH (x, si ) ≤ d. By dH (x, s) we mean the Hamming distance
between the strings x and s and it represents the number of positions the two strings differ.
For example, if x = AT T and s = AT C then dH (x, s) = 1, since x and s differ at the
last position. The CSP is NP-hard and several methods have been proposed to solve the
problem. Our main goal in this work is to design exact methods based on integer linear
programming.
Keywords: string selection, integer linear programming, branch-and-cut
2
Sumário
1 Introdução
4
2 Definições e Conceitos Básicos
6
2.1
Problemas de Seleção de Strings . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2
Distância de Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.3
Conceitos Básicos em Programação Linear . . . . . . . . . . . . . . . . . .
9
2.4
Programação Linear Inteira (PLI) . . . . . . . . . . . . . . . . . . . . . . . 10
2.4.1
Algoritmo de Cutting Planes . . . . . . . . . . . . . . . . . . . . . . 11
2.4.2
Algoritmo de Branch-and-Bound . . . . . . . . . . . . . . . . . . . 11
2.4.3
Algoritmo de Branch-and-Cut . . . . . . . . . . . . . . . . . . . . . 12
3 Trabalhos Anteriores
3.1
14
Heurı́stica para o CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4 Estudo em Combinatória Poliédrica
16
4.1
Formulação em Programação Inteira . . . . . . . . . . . . . . . . . . . . . 16
4.2
Nova Classe de Planos de Corte e sua Separação . . . . . . . . . . . . . . . 18
4.3
Limitante Inferior Combinatório . . . . . . . . . . . . . . . . . . . . . . . . 21
5 Resultados Computacionais
23
5.1
Ambiente dos Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.2
Instâncias de Teste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.3
Análise dos Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
6 Comentários Finais
29
3
Capı́tulo 1
Introdução
Robert E. Bixby, em [2], define um problema de otimização combinatória como: Sejam E
um conjunto finito, S uma famı́lia de subconjuntos de E e w ∈ R|E| uma função peso de
valores reais definida sobre os elementos de E. O problema de otimização combinatória
associado é encontrar um conjunto S ∗ ∈ S tal que
w(S ∗ ) = max w(S)
S∈S
onde w(S) =
P
e∈S
w(e).
Nesta pesquisa desenvolveu-se métodos para resolver um problema de seleção de strings
(cadeia de caracteres), conhecido por Closest String Problem (CSP). O CSP é um relevante problema de otimização combinatória da área de bioinformática e tem aplicações
no desenvolvimento de remédios, conforme [5].
A definição do CSP é baseada no conceito de distância de Hamming: Dadas duas
strings quaisquer, s e t, de mesmo tamanho (número de caracteres), a distância de Hamming, denotada por dH (s, t), mede o número de posições em que s e t diferem. Por
exemplo, se s =CCACT e t =TACCA, então dH (s, t) = 4.
O CSP consiste em: dado um conjunto finito S ={s1 , s2 , · · · , sn } com n strings, todas
de mesmo tamanho m, sobre um alfabeto A, deseja-se encontrar uma string x, de tamanho
m, sobre A, que minimiza o valor de d tal que para cada string si ∈ S tenha dH (x, si ) ≤ d.
Em outras palavras, desejou-se encontrar uma string x que é mais próxima a todas as
strings em S, considerando como medida de proximidade a distância Hamming.
Em termos de complexidade computacional, o CSP pertence a classe N P-difı́cil, conforme provado na referência [5]. Existem alguns algoritmos de aproximação para resolver
o CSP, que podem ser vistos nas referências [1, 5, 6]. Em termos de resolução exata do
CSP, é do nosso conhecimento que existe apenas a abordagem descrita na referência [8],
que usa programação linear inteira.
4
Em [7] são apresentados modelos matemáticos para problemas de seleção de strings,
que mantêm uma estreita ligação com o CSP. Estes problemas são definidos formalmente
na subseção 2.1. Decidimos estudar o CSP porque:
• Ele é um problema que surge durante o processo de criação de certos remédios;
• Métodos desenvolvidos para resolver o CSP podem ajudar na compreensão de como
resolver os problemas listados na subseção 2.1;
• Acredita-se que é possı́vel desenvolver um método exato que é melhor do que o
atualmente melhor método ([8]) para o CSP.
As contribuições com esta pesquisa são as seguintes:
• Identificou-se uma classe de inequações válidas (cortes) para o poliedro apresentado
em [8]. Criou-se um algoritmo de tempo polinomial em n, que separa essas inequações;
• Criou-se uma fórmula para o cálculo de limitante inferior no valor de uma solução
ótima.
No capı́tulo 2 definimos alguns problemas associados ao CSP e conceitos básicos sobre
programação linear inteira. No capı́tulo 4 é apresentada uma formulação em programação
linear inteira para o CSP, tal como descrita em [8], bem como uma nova classe de inequações e uma rotina de separação destas inequações. No capı́tulo 5 mostramos experimentos
computacionais. No capı́tulo 6 apresentamos os comentários finais desta pesquisa.
5
Capı́tulo 2
Definições e Conceitos Básicos
Neste capı́tulo define-se cinco problemas associados ao Closest String Problem e métodos
que podem ser utilizados para resolvê-los. Além disso, são lembrados vários conceitos e
técnicas usadas para solucionar problemas de otimização combinatória.
2.1
Problemas de Seleção de Strings
Nesta seção define-se formalmente cinco problemas de seleção de strings associados ao
CSP, cujas versões de decisão pertencem a classe de complexidade NP-Completo, conforme
provado em [5]. Cada problema é exemplificado por uma instância e uma solução. Como
ficará claro no próximo capı́tulo, o estudo realizado para resolver instâncias do CSP é útil
para resolver instâncias daqueles problemas. As definições formais desses problemas são
as seguintes:
Farthest String Problem (FSP)
Dado um conjunto finito S ={s1 , s2 , · · · , sn } com n strings, cada uma de tamanho
m, sobre um alfabeto A, deseja-se encontrar uma string x de tamanho m sobre A, que
maximiza d tal que para qualquer string si ∈ S, tem-se dH (x, si ) ≥ d.
Como exemplo de uma instância do Farthest String Problem considere o conjunto de
strings S = {AAACA,GTCTA,AATGC,CTTAC}. Uma solução ótima é dada pela string
x =TCGAG com d = 4.
Closest Substring Problem (CSubSP)
Dado um conjunto finito S = {s1 , s2 , · · · , sn } com strings de tamanho no mı́nimo
m sobre um alfabeto A, deseja-se encontrar uma string x de tamanho m sobre A, que
minimiza d tal que para toda string si in S, a relação dH (x, y) ≤ d é verdadeira para
alguma substring y, de tamanho m, de si .
6
Como exemplo considere S = {AAT,CCAA,CCTA,TCA}. Uma solução viável é dada
pela string ACA com d = 2.
Farthest Substring Problem (FSubSP)
Dado um conjunto finito S ={s1 , s2 , . . . , sn } com strings de tamanho no mı́nimo m
sobre um alfabeto A, deseja-se encontrar uma string x de tamanho m sobre A, que
maximiza d tal que para toda string si in S e toda substring y, de tamanho m, de si ,
tem-se dH (x, y) ≥ d.
Como exemplo considere S = {AAT,CCAA,CCTA,TCA}. Uma solução viável é a
string ACA com d = 1.
Close to Most String Problem (CMSP)
Dado um conjunto finito S = {s1 , s2 , . . . , sn } com strings de tamanho m sobre um
alfabeto A e um limiar k > 0, deseja-se encontrar uma string x de tamanho m sobre A,
que maximiza o número de strings si ∈ S tal que dH (x, si ) ≤ k.
Como exemplo considere S = {AATCC,CCAAT,CCTAC,TCACC}. Se k = 3, então
uma solução ótima é CCTCT com quatro strings satisfazendo dH (x, si ) ≤ 3. Se k = 2,
então uma solução ótimza é ACAAC e três strings respeitam dH (x, si ) ≤ 2.
Distinguishing String Selection Problem (DSSP)
Dados dois conjuntos finitos de strings Sc e Sf , todas as strings de tamanho no mı́nimo
m, sobre um alfabeto A, e dois números inteiros positivo kc e kf , deseja-se encontrar uma
string x de tamanho m sobre A tal que para cada string sc ∈ Sc , existe alguma substring
yc , de tamanho m, de sc satisfazendo dH (x, yc ) ≤ kc , e para toda substring yf , de tamanho
m, de sf ∈ Sf tem-se dH (x, yf ) ≥ kf .
Como exemplo, considere Sc = {AATCC,CCAAT,CCTAC,TCACC} e o conjunto
Sf = {AATAA,CCACT,GGTAC,TCAAC}. Se kc = 3 e kf = 2, então ACACC é uma
solução viável.
Observe que os quatro primeiros problemas acima são problemas de otimização, enquanto o último é um problema de decisão. Como dito no inı́cio deste capı́tulo, estes cinco
problemas mantêm estreita relação com o CSP.
A figura a seguir mostra as relações entre os problemas, em termos das reduções, e
consequentes complexidades computacionais. Por 2SAT, 3SAT e ISP queremos indicar
os problemas 2-satisfatibilidade, 3-satisfatibilidade e Independent Set Problem, respectivamente. Lembre que é conhecido um algoritmo determinı́stico de tempo polinomial para
o 2SAT e que os problemas 3SAT e ISP pertencem a classe NP-Completo.
–
7
3SAT
[5]
[5]
DSSP
[5]
FSP
FSubSP
[5]
CSP
[5]
[5]
CSubSP
DSSP
ISP
[3]
FFMSP
[3]
[3]
2SAT
CMSP
Figura 2.1: Reduções entre problemas definidos nesta seção e problemas clássicos de
otimização combinatória
8
2.2
Distância de Hamming
Uma métrica em um conjunto X é uma função, chamada função de distância ou simplesmente distância, dada por:
d : X × X → <,
onde < é o conjunto dos números reais. Para todo x, y, z ∈ X, esta função precisa
satisfazer as seguintes condições:
1. d(x, y) ≥ 0 (não-negatividade)
2. d(x, y) = 0 se e somente se x = y (identidade)
3. d(x, y) = d(y, x) (simetria)
4. d(x, z) ≤ d(x, y) + d(y, z) (desigualdade triangular).
Seja (Fm )n o conjunto de todas as n-tuplas ordenadas a = a1 a2 ...an onde cada ai ∈ Fm .
Fm é um alfabeto, o m-ésimo elemento é obtido do conjunto de sequências de sı́mbolos
onde cada sı́mbolo é escolhido do conjunto Fm = {λ1 , λ2 , ..., λm } de m elementos diferentes. A distância de Hamming entre dois vetores x e y de (Fm )n é o número de posições
nas quais eles diferem. Isto é denotado por dH (x, y). Por exemplo, no (F2 )5 temos
dH (00111, 11001) = 4, enquanto em (F3 )4 obtemos dH (0122, 1220) = 3.
A distância de Hamming é uma função distância legı́tima ou uma métrica que deve satisfazer as seguintes condições, para todo x, y, z ∈ (Fm )n :
(i) dH (x, y) ≥ 0
(ii) dH (x, y) = 0 se e somente se x = y
(iii) dH (x, y) = dH (y, x)
(iv) dH (x, z) ≤ dH (x, y) + dH (y, z).
2.3
Conceitos Básicos em Programação Linear
Como é pretendido resolver instâncias do CSP utilizando uma abordagem baseada em
combinatória poliédrica, esta seção relembra alguns conceitos básicos em Programação
Linear. Os teoremas e definições abaixo foram compilados de [4, 9, 12].
Um problema de Programação Linear (PL) pode ser definido como o problema de
maximizar ou minimizar uma função linear sobre uma região descrita por um conjunto
9
de inequações e equações lineares. Os pontos nesta região formam o conjunto de soluções
viáveis do problema PL. Tal problema pode ser escrito na forma de matriz como:
min {cx : Ax ≥ b, x ∈ Rn+ },
onde c ∈ Rn , A é uma matriz m × n de constantes reais e b ∈ Rm .
Teorema 2.1. O conjunto de soluções viáveis X = {x : Ax ≥ b, x ∈ Rn+ } para o problema
é um conjunto convexo, i.e., qualquer ponto, exceto um vértice, em X é uma combinação
linear convexa de outros dois pontos em X .
Definição 2.1. O conjunto convexo X = {x : Ax ≥ b, x ∈ Rn+ } é denominado poliedro.
Se X é limitado, i.e., X ⊆ {x : −w ≤ xj ≤ w, ∀ j ∈ {1, 2, · · · , n}} para algum w ∈ R+ ,
então X é chamado de politopo.
Definição 2.2. Um vértice de um poliedro X é qualquer ponto x ∈ X o qual não pode
ser expresso como uma combinação convexa de outros pontos de X \{x}.
Teorema 2.2. Se o valor ótimo de uma função linear num poliedro X ⊆ Rn é finito, então
ele é atingido em pelo menos um vértice. Se este for obtido em mais que um vértice, então
pode ser obtido também por qualquer ponto que seja uma combinação linear convexa destes
vértices.
Teorema 2.3. Um problema de PL pode ser resolvido em tempo polinomial sobre n, m
e θ, onde n é o número de variáveis do problema, m é o número de restrições, e θ é o
maior coeficiente da matriz A.
2.4
Programação Linear Inteira (PLI)
Nesta seção discutimos alguns métodos normalmente utilizados na resolução de problemas,
que admitem uma formulação em programação linear, onde exige-se soluções inteiras. Os
conceitos discutidos nesta seção foram compilados de [4, 10, 13].
Considere o problema de programação linear abaixo:
min {cx : Ax ≥ b, x ∈ Rn+ },
onde c ∈ Rn , A é uma matriz m × n de constantes reais e b ∈ Rm .
Se as variáveis são restritas a inteiros, x ∈ Zn+ , ao invés de x ∈ Rn+ , o problema é
chamado de problema de Programação Linear Inteira. Além disso, se as variáveis são
restritas a valores 0 ou 1, temos um problema PLI 0-1. As soluções do problema PLI 0-1
são pontos em {0, 1}n satisfazendo o sistema linear Ax ≥ b.
10
Geralmente problemas PLI 0-1 pertencem a classe NP-difı́cil. Uma maneira de resolver
estes problemas é utilizando suas relaxações lineares. Numa relaxação linear as restrições
de integralidade são substituı́das por restrições lineares. Existem duas abordagens clássicas para resolver problemas PLI 0-1 utilizando relaxações lineares: (a) algoritmo de
Cutting Planes Fracionário (ACPF) e o algoritmo de branch-and-bound ou (b) enumeração implı́cita. Denotaremos por S o conjunto de soluções viáveis de um problema PLI
0-1.
2.4.1
Algoritmo de Cutting Planes
ACPF são baseados no uso de inequações válidas (cortes) para S, i.e, inequações que são
satisfeitas por todos os pontos de S.
A cada iteração i de ACPF, uma relaxação LP i do problema P LI é resolvida. Seja
xi uma solução ótima obtida ao se resolver a relaxação linear LP i . Se xi está em S, o
algoritmo pára, retornando xi como uma solução ótima do problema P LI. Caso contrário,
a relaxação deve ser melhorada. Para isto, encontra-se uma desigualdade válida πx ≥ π0
para S que é violada por xi . Uma nova iteração é executada para a relaxação LP i+1 ,
obtida de LP i incluindo-se a desigualdade πx ≥ π0 .
Sejam z i e z i+1 os valores das soluções ótimas de LP i e LP i+1 respectivamente, isto
é, z i = cxi e z i = cxi+1 . Assumindo que o P LI é um problema de minimização, tem-se
que z i+1 ≥ z i , ou seja, o limitante inferior fornecido pelo valor ótimo da relaxação linear
cresce monotonicamente a cada iteração, aproximando-se do valor ótimo do P LI.
O estudo inicial de adição de desigualdades válidas para problemas PLI gerais foi feito
por Gomory na década de 50. Embora o algoritmo proposto por ele sempre termine em
tempo finito, as desigualdades que ele sugeriu para adicionar à formulação (cortes de
Gomory) não eram eficientes na prática, pois o algoritmo torna-se muito lento.
Mais tarde, percebeu-se que o motivo do insucesso obtido pela aplicação dos cortes de
Gomory, era decorrente do seu excesso de generalidade. Independente do problema P LI
que se esteja resolvendo, sempre é possı́vel gerar um corte de Gomory que elimina uma
solução contı́nua. No entanto, esse corte pode não ser suficiente para capturar a estrutura
da envoltória convexa das soluções inteiras do P LI. Cortes com essa propriedade são o
objeto de estudo da Combinatória Poliédrica que fez ressurgir, principalmente a partir da
década de 80, o interesse pelos algoritmos de corte.
2.4.2
Algoritmo de Branch-and-Bound
Branch-and-Bound são esquemas enumerativos fundamentados em duas operações básicas.
11
A primeira é a decomposição do problema original em subproblemas. A segunda operação
envolve o cálculo de limites inferiores (ou superiores) ao valor da função objetivo. O
propósito é acelerar o processo de descarte de subproblemas que não podem gerar soluções
promissoras, diminuindo, consequentemente, a enumeração.
Normalmente, a decomposição é construı́da recursivamente. Isto permite uma representação gráfica de todo o processo em termos de uma árvore de enumeração. Nesta
representação, os filhos de um dado nó formam a decomposição da região viável de seu
pai.
Em geral, para problemas P LI 0-1, a árvore de enumeração é uma árvore binária.
Cada nó i da árvore corresponde a uma relaxação linear LP i do problema P LI definido
em um subconjunto S i de S. Seja xi uma solução ótima encontrada para LP i e z i = cxi .
Dependendo do valor de z i (bound), o nó i pode ser expandido (branching) para outros dois
nós (seus filhos) ou pode ser cortado (ou podado), i.e, o subconjunto de soluções viáveis do
nó i é particionado em dois novos subconjuntos ou ele não será mais particionado durante
os passos seguintes do algoritmo. O algoritmo termina quando todos os nós estiverem
podados. Retorna-se como solução do P LI, a solução inteira do nó da árvore com menor
valor (para um problema de minimização) de função objetivo.
2.4.3
Algoritmo de Branch-and-Cut
Seja Conv(S) a envoltória convexa do conjunto viável S. A envoltória convexa de S é
um poliedro e portanto, pode ser descrita por um sistema de desigualdades e igualdades
lineares. Se o sistema linear que descreve completamente Conv(S) está disponı́vel, o
problema P LI pode, em princı́pio, ser resolvido eficientemente por programação linear,
visto que todos os pontos extremos são soluções viáveis inteiras em S (veja definição 2.2 e
teorema 2.3). Infelizmente, para problemas que pertencem a classe N P -difı́cil, geralmente
o número de desigualdades de tal sistema é exponencial, no tamanho da entrada, e somente
algumas desigualdades da descrição de Conv(S) são conhecidas.
Assuma, portanto que uma certa classe F de desigualdades válidas para Conv(S) são
conhecidas. Além disso, dado um ponto qualquer x ∈ Rn+ assuma que dispõe-se de um
algoritmo que procura por uma desigualdade em F que é violada por x. Tal algoritmo é
chamado uma rotina de separação para F.
Branch-and-Cut é um método para resolver problemas PLI, que incorpora uma fase
de cutting plane ao algoritmo de branch-and-bound. Na fase de cutting plane o algortimo
só irá gerar desigualdades que pertençam à classe F, definida anteriormente.
Para cada nó i da árvore de enumeração, P i = {x ∈ Rm+n : Ai x ≥ b, 0 ≤ x ≤ 1} é o
politopo correspondente a relaxação linear LP i . Se xi é a solução ótima desta relaxação
12
linear e ela tem variáveis fracionárias, a rotina de separação é chamada para procurar
uma desigualdade violada em F. Se a rotina de separação retorna uma desigualdade
πx ≥ π0 , esta desigualdade é incluı́da no sistema de desigualdades definindo P i , e LP i é
resolvido novamente. Continuamos fazendo isto até xi ser inteiro ou z i ser maior do que
o atual upper bound disponı́vel, ou a rotina de separação falhar em produzir uma nova
desigualdade em F que corte o ponto xi . Neste último caso, uma variável é escolhida para
fazer um branching.
Uma aplicação bem sucedida de método de branch-and-cut para resolver problemas
difı́ceis de P LI 0-1 é a relatada em [11], neste caso para o Traveling Salesman Problem.
O sucesso de algoritmos de branch-and-cut depende muito do conhecimento da estrutura
de Conv(S).
13
Capı́tulo 3
Trabalhos Anteriores
Neste capı́tulo descrevemos um trabalho encontrado na literatura cientı́fica que trata o
CSP. Este trabalho propõe uma heurı́stica e três modelos matemáticos para o CSP e
mostra vários resultados computacionais.
3.1
Heurı́stica para o CSP
A heurı́stica proposta em [8] gera soluções iniciais viáveis para o CSP e realiza uma busca
local nessas soluções. Verifica-se que o algoritmo 1 gera resultados iniciais e posteriormente
no algoritmo 2 constroem-se as soluções a partir da solução inicial. Impressionantemente,
este algoritmo é capaz de produzir resultados de excelente qualidade, conforme comprovam
os experimentos computacionais mostrados no capı́tulo 5.
O algoritmo 1 seleciona uma das strings em S e a modifica até que uma solução localmente ótima seja encontrada. Conforme provado em [8], o algoritmo 1 tem complexidade
de tempo O(nmN ), para N ≥ n.
No primeiro passo, o algoritmo procura por uma solução s ∈ S que seja a mais próxima
a todas as demais strings em S. No segundo passo, as distâncias d entre s e o resto das
strings são calculadas. No último passo do algoritmo um procedimento de busca local é
aplicado como segue:
• Seja r uma string em S tal que para dH (r, si ), onde i ∈ {1, · · · , n}, seja a máxima,
e seja s uma solução atual. Logo, para i ∈ {0, ..., m}, se si 6= ri então trocamos os
valores si por ri cuja solução s tende a melhorar. A seguir tal troca é efetuada e a
distância Hamming entre s e as demais strings em S são atualizadas.
• Após analisar as m posições, uma nova string r é selecionada entre as strings em S,
que é a mais afastada das s soluções atuais logo,
14
Input: Instância S = {s1 , · · · , sn }
Output: String s, distância d
s ← {y ∈ S | minsi ∈S dH (y, si )}
d ← maxi∈{1,...,n} dH (s, si )
Melhora Solução(s, d, N )
Algoritmo 1: Gera soluções viáveis para o CSP
Input: instância S, solução corrente s, distância d e parâmetro N (número de
iterações)
Output: solução resultante s e distância d
for k ← 1 to n do
d0k ← dk ← dH (sk , s)
end
for i ← 1 to N do
b ← i tal que dH (si , s) = d /* resolva o empate aleatoriamente */
for j ← 1 to m tal que sbj 6= sj do
max ← −1
for k ← 1 to n tal que k 6= b do
if (sj = skj ) e (sbj 6= skj ) then dk ← dk + 1
else if (sj 6= skj ) e (sbj = skj ) then dk ← dk − 1
if (max < dk ) then max ← dk
end
if d ≥ max /* não é pior */ then
d ← max; tj ← sbj
for k ← 1 to n do d0k ← dk
else
for k ← 1 to n do dk ← d0k
end
end
end
Algoritmo 2: Terceiro passo do Algoritmo 1: Melhora Solução
• O processo se repete continuamente. O número de repetições é controlado pelo
parâmetro N . Os passos em detalhe da busca local são apresentados no algoritmo 2
15
Capı́tulo 4
Estudo em Combinatória Poliédrica
Focados no estudo poliédrico do Closest String Problem (CSP), alcançamos os seguintes
resultados:
(a) Uma classe de inequações válidas para uma formulação proposta em [8] e
(b) Um algoritmo de complexidade polinomial que separa as inequações daquela classe.
Os resultados mostrados neste capı́tulo fazem parte de uma colaboração com o Prof.
Giuseppe Lancia, que trabalha no Department of Mathematical and Computer Science,
University of Udine, Italy.
Começamos o estudo relembrando uma formulação em programação Linear Inteira 0-1
(PLI 0-1) para o CSP, descrita em [8], em seguida apresentamos uma nova classe de planos
de corte e então um algoritmo de branch-and-cut.
4.1
Formulação em Programação Inteira
Em [8] são apresentadas três formulações em PLI 0-1 para o CSP. A terceira delas é baseada no teorema a seguir, que reduz o espaço das soluções viáveis para qualquer instância
do CSP.
Teorema 4.1. [8] Dada uma instância do Closest String Problem, existe uma solução
ótima onde o caracter ótimo na posição k está também na posição k em uma das strings
no conjunto S = {s1 , s2 , . . . , sn } de strings.
Exemplo 4.1. Seja S = {AATCC,CCAAT,CCTAC,TCACC}. Defina Vk = ∪ni=1 {sik }
para k = 1, . . . , m. Então os conjuntos Vk são: V1 = {A, C, T }, V2 = {A, C}, V3 =
{A, T }, V4 = {A, C}, V5 = {C, T }. O Teorema 4.1 garante que para encontrar uma solução
16
ótima, x = (x1 , x2 , x3 , x4 , x5 ), é suficiente atribuir ao componente xk , um elemento do
conjunto Vk para j = 1, . . . , 5. Assim, x =ACTAT é, por exemplo, uma solução viável. A partir da seguinte definição para as variáveis binárias xj,k
(
xj,k =
1 se o caracter j é usado na posição k em uma solução
0 caso contrário
os autores em [8] propuseram a formulação:
min d
X
s.a.:
xj,k = 1
(4.1)
k = 1, . . . , m
(4.2)
i = 1, . . . , n
(4.3)
j ∈ Vk ; k = 1, . . . , m
(4.4)
j∈Vk
d≥m−
m
X
xsik ,k
k=1
xj,k ∈ {0, 1}
d ≥ 0 e inteiro
(4.5)
P
Note que esta formulação tem m + n restrições e 1 + m
k=1 |Vk | variáveis de decisão. A
restrição (4.2) faz com que cada vetor solução x tenha na posição k um dos caracteres em
Vk . A restrição (4.3) calcula a distância de Hamming entre o vetor solução x e as strings
em S. A restrição (4.4) faz com que as variáveis xj,k assumam valores 0 ou 1, enquanto
que a restrição (4.5) garante que a variável d seja um número inteiro não negativo. Por
motivo óbvios, desejamos minimizar o valor de d.
Conforme relatado em [8], a formulação mostrada acima é muito forte. Isto é, os
valores das relaxações lineares, para as várias instâncias testadas, tiveram valores muito
próximos aos valores das soluções ótimas encontradas.
Os resultados descritos naquela referência mostraram evidências de que o método
branch-and-bound, lá utilizado, teve mais dificuldades para resolver instâncias com alfabetos com poucos caracteres. Por exemplo, instâncias com alfabeto binário mostraram-se
mais difı́ceis, para o branch-and-bound, do que instâncias cujo alfabeto tinha quatro caracteres. Esta relação é investigada no capı́tulo 5, Experimentos Computacionais.
Com o intuito de melhorar ainda mais a formulação descrita acima, decidimos procurar
por novas classes de cortes. Na seção a seguir propõe-se uma classe de cortes e um
algoritmo que tem complexidade de tempo polinomial em n e m. Ressalta-se que esta é
a principal contribuição do nosso trabalho.
17
4.2
Nova Classe de Planos de Corte e sua Separação
Considere o Programa Linear (PL) obtido a partir da relaxação da formulação descrita
na seção anterior. Isto é, considere

min d



P


k = 1, . . . , m

j∈Vk xj,k = 1
 s.a.:
Pm
PL :
d ≥ m − k=1 xsik ,k i = 1, . . . , n




0 ≤ xj,k ≤ 1
j ∈ Vk ; k = 1, . . . , m



d≥0
Note os domı́nios das variáveis xj,k e d no programa linear acima.
Assuma que temos uma solução viável, de valor D, para uma instância do CSP. Possivelmente uma boa solução viável, assim que D é provavelmente ótimo. Esta boa solução
viável poderia, por exemplo, ser obtida utilizando um procedimento de arredondamento
a partir da solução da relaxação linear da formulação acima ou a heurı́stica descrita na
seção 3.1.
Seja S = {s1 , s2 , ..., sn }, com |si | = m para i = 1, . . . , n. Tome qualquer string si ∈ S
e considere qualquer subconjunto B de si consistindo de D caracteres. Comparando-se
as correspondentes posições de B em si , tem-se que uma solução ótima para S não pode
ser diferente em todos os caracteres em B, caso contrário esta solução teria valor maior
ou igual a D. Como já tem-se uma solução de valor D, então procura-se por uma solução
de valor menor ou igual D − 1. Portanto, concluı́-se que
X
xsik ,k ≥ 1
(4.6)
k∈Ind(B)
é uma inequação válida (corte) para o PL, onde Ind(B) é o conjunto das ı́ndices de B em
si .
Exemplo 4.2. Seja S = {s1 , s2 , s3 }, onde s1 = ACT , s2 = CCG e s3 = T CA. Considerando o resultado no Teorema 4.1, tem-se que uma solução ótima x = (x1 , x2 , x3 ) para S
satisfaz x1 ∈ V1 = {A, C, T }, x2 ∈ V2 = {C} e x3 ∈ V3 = {A, G, T }. Observe que a string
x = ACG é uma solução viável e tem valor 2.
Para s1 = ACT , as subsequências de comprimento dois são AC, AT, CT . A partir destas subsequências, obtemos os seguintes conjuntos de ı́ndices Ind(AC) = {1, 2},
Ind(AT ) = {1, 3} e Ind(CT ) = {2, 3}. Assim, os cortes obtidos ao considerar s1 = ACT
18
são:
xA,1 + xC,2 ≥ 1
xA,1 + xT,3 ≥ 1
xC,2 + xT,3 ≥ 1
Aplicando-se a mesma ideia para s2 = CCG, obtemos os cojuntos de ı́ndices Ind(CC) =
{1, 2}, Ind(CG) = {1, 3} e Ind(CG) = {2, 3} e portanto os cortes:
xC,1 + xC,2 ≥ 1
xC,1 + xG,3 ≥ 1
xC,2 + xG,3 ≥ 1
Finalmente, para s3 = T CA obtem-se os cojuntos de ı́ndices Ind(T C) = {1, 2}, Ind(T A) =
{1, 3} e Ind(CA) = {2, 3} e portanto os cortes:
xT,1 + xC,2 ≥ 1
xT,1 + xA,3 ≥ 1
xC,2 + xA,3 ≥ 1
Com isto concluı́-se o exemplo.
m
Existem n × D inequações possı́veis (isto é um número exponencial, visto que D
pode ser proporcional a m). Agora mostra-se como encontrar um corte violado (se ele
existe) em tempo polinomial.
Teorema 4.2. Inequações (4.6) podem ser separadas em tempo polinomial, nominalmente
em O(nm log m).
Demonstração. Suponha que x∗ é uma solução fracionária ótima obtida pela relaxação
linear. Considere cada string si ∈ S, uma por vez. Para k = 1, . . . , m defina
aj = x∗si ,k
k
Por exemplo, para s1 temos
a1 = x∗s1 ,1 , a2 = x∗s1 ,2 , a3 = x∗s1 ,3 , . . . , am−1 = x∗s1
1
2
m−1 ,m−1
3
, am = x∗s1m ,m .
Considerando o Exemplo 4.2, temos para s1 = ACT : a1 = x∗A,1 , a2 = x∗C,2 , a3 = x∗T,3 .
Agora ordene os aj em ordem não decrescente, ap(1) ≤ ... ≤ ap(m) , e denote por B o
conjunto dos primeiros D valores nesta ordem dos aj (isto é, B = {p(1), ..., p(D)}). Então
19
B alcança a mı́nima soma possı́vel de x∗ com relação a si . Se esta soma for menor que 1,
então teremos encontramos uma inequação (4.6) violada; caso contrário não há inequações
P
violadas para si , e então passamos para a análise de si+1 . Ou seja, se D
k=1 ap(k) < 1 então
PD
a inequação k=1 xsi [p(k)],p(k) ≥ 1 precisa ser incluı́da no modelo linear.
Para mostrar como ocorre o funcionamento do algoritmo considere o seguinte exemplo.
Exemplo 4.3. Seja S = {AT T GGA, CT GAT G, CT GACT, AGT CGA, GCCT GT } uma
instância do CSP. A partir do conjunto S contrua os conjuntos Vi da seguinte maneira:
V1 = {A, C, G}, V2 = {C, G, T }, V3 = {C, G, T }, V4 = {A, C, G, T }, v5 = {C, G, T } e
v6 = {C, G, T }. O correspondente modelo em programação linear é:
min
s.a. :
d
xA,1 + xC,1 + xG,1 = 1
xC,2 + xG,2 + xT,2 = 1
xC,3 + xG,3 + xT,3 = 1
xA,4 + xC,4 + xG,4 + xT,4 = 1
xC,5 + xG,5 + xT,5 = 1
xA,6 + xG,6 + xT,6 = 1
d + xA,1 + xT,2 + xT,3 + xG,4 + xG,5 + xA,6 ≥ 6
d + xC,1 + xT,2 + xG,3 + xA,4 + xT,5 + xG,6 ≥ 6
d + xC,1 + xT,2 + xG,3 + xA,4 + xC,5 + xT,6 ≥ 6
d + xA,1 + xG,2 + xT,3 + xC,4 + xG,5 + xA,6 ≥ 6
d + xG,1 + xC,2 + xC,3 + xT,4 + xG,5 + xT,6 ≥ 6
0 ≤ xj,k ≤ 1
j ∈ Vk ; k = 1, . . . , 6
d≥0
Uma solução ótima para o programa linear acima é dada por: d = 3.666667, xA,1 =
0.75, xC,1 = 0.25, xT,2 = 0.583333, xG,2 = 0.416667, xG,3 = 1.0, xC,4 = 0.166667, xT,4 =
0.833333, xG,5 = 1.0, xG,6 = 0.5, xT,6 = 0.5 e todas as outras variáveis têm valores iguais
a zero. Sendo d = 3.666667 segue que, em uma solução ótima inteira, o valor de d
precisa ser maior ou igual a 4. Adicionando o plano de corte d ≥ 4 ao programa linear e
resolvendo-o novamente, obtemos a solução: d = 4.0, xA,1 = 0.5, xC,1 = 0.5, xT,2 = 0.5,
xG,2 = 0.5, xG,3 = 1.0, xT,4 = 1.0, xG,5 = 1.0, xG,6 = 1.0 e todas as outras variáveis têm
valores iguais a zero.
Precisamos encontrar uma solução viável com D = 5. Pode-se fazer isto por tentativa
e erro. Considere a seguinte solução para S, x = AT GT CG. Assim, as distâncias de
20
Hamming de x para as strings em S são:
d(x, s1 ) = d(AT T GGA, AT GT CG) = 4
d(x, s2 ) = d(CT GAT G, AT GT CG) = 3
d(x, s3 ) = d(CT GACT, AT GT CG) = 3
d(x, s4 ) = d(AGT CGA, AT GT CG) = 5
d(x, s5 ) = d(GCCT GT, AT GT CG) = 5
Consideramos agora a classe de cortes (4.6): para D = 5 as seguintes inequações são
violadas:
xG,2 + xT,3 + xC,4 + xG,5 + xA,6 ≥ 1
(4.7)
xG,1 + xC,2 + xC,3 + xG,5 + xT,6 ≥ 1
(4.8)
As inequações (4.7) e (4.8) foram determinadas a partir de s4 e s5 , respectivamente.
Incluindo estas inequações no programa linear, junto com d ≥ 4, e resolvendo o programa
linear novamente obtemos uma solução ótima inteira dada por x = CT CCGG e d = 4.
Comparando x com as strings em S vemos:
d(x, s1 ) = d(AT T GGA, CT CCGG) = 4
d(x, s2 ) = d(CT GAT G, CT CCGG) = 3
d(x, s3 ) = d(CT GACT, CT CCGG) = 4
d(x, s4 ) = d(AGT CGA, CT CCGG) = 3
d(x, s5 ) = d(GCCT GT, CT CCGG) = 4
4.3
Limitante Inferior Combinatório
Agora estabelece-se um limite inferior no valor de qualquer solução ótima para qualquer
instância do CSP. Para cada posição j da string si ∈ S, denote por Sjα o subconjunto de
strings de S que têm o caracter α na posição j. Defina djα = n − |Sjα |. Em palavras, djα
é o número de sı́mbolos diferentes de α na posição j nas strings de S. Defina para cada
posição j
dj = min djα
α∈A
e
l Pm d j m
j=1
L=
n
Então obtemos
21
Lema 4.1. L é um limitante inferior válido para o CSP.
Demonstração. Independentemente de qual caracter aparece na posição j em uma solução,
ele entrará em conflito com no mı́nimo dj strings naquela posição. Somando sobre todas
as posições, este é o número total de conflitos (i.e., a soma das distâncias de Hamming)
da solução com relação as strings da instância, e dividindo por n obtemos
que a média da
Pm
d
j
e. Mas como o
distância de Hamming de qualquer solução precisa ser no mı́nimo d j=1
n
máximo é no mı́nimo a média (e podemos também arredondar para o primeiro número
inteiro), obtemos o lema.
No próximo capı́tulo, de resultados computacionais, mostra-se os resultados dos experimentos são realizados com uma implementação de um branch-and-cut. Testa-se esta
implementação em dois cenários: com o uso da classe de cortes e sem o seu uso. Após
realizar diversos experimentos com esta implementação, percebe-se que há uma redução
no tempo de execução da implementação quando a classe de cortes é utilizada.
22
Capı́tulo 5
Resultados Computacionais
Neste capı́tulo apresentamos os experimentos computacionais realizados sobre instâncias
do CSP.
5.1
Ambiente dos Experimentos
Todas as implementações foram desenvolvidas em C++ e utilizou-se o compilador Gnu
C++ sem otimizações. Os testes foram realizados em um computador com a seguinte
configuração: Dell processador Intel Core I5 3.33 Ghz com 4 GB de memória RAM e
sistema operacional Linux Ubuntu 11.04 com endereçamento de 32 bits. O solver IBM
ILOG CPLEX versão 12.4 foi utilizado para resolver relaxações lineares e na implementação do branch-and-cut. Deste ponto em diante do texto trata-se por CPLEX o solver
IBM ILOG CPLEX versão 12.4.
5.2
Instâncias de Teste
Noventa e uma instâncias do CSP foram geradas utilizando o gerador de instâncias descrito na referência [8]. Estas instâncias consideram alfabetos com dois, quatro e vinte
caracteres.
5.3
Análise dos Resultados
Testou-se duas abordagens para solucionar as 91 instâncias do CSP. A primeira abordagem
é um método padrão de Planos de Cortes com um branch-and-bound, onde todos os planos
de cortes são gerados somente no nó raiz da árvore de enumerção do branch-and-cut. Ou
23
seja, o modelo de programação linear correspondente a uma instância é resolvido e caso a
sua solução seja fracionária, então são gerados todos os cortes válidos para esta solução.
Utilizando a classe de inequações, discutida no capı́tulo anterior, para aquela solução,
cortes são inseridos no modelo de programação linear, e a relaxação linerar é novamente
computada. Caso a nova solução seja inteira o método para, caso contrário novos cortes
são inseridos ao modelo e o processo é repetido.
A segunda abordagem é simplesmente resolver os modelos de programação linear inteira correspondentes às instâncias, utilizando o CPLEX.
Os resultados obtidos com as implementações são apresentados nas Tabelas 5.1 a 5.4.
Os cabeçalhos nas tabelas indicam:
• Instância: o tamanho da instância (n, m) e a semente utilizada para gerá-la;
• Relaxação linear: (OPT: valor ótimo, CPU: tempo de CPU, em horas, minutos e
segundos, para calcular a relaxação linear);
• Plano de Cortes: (Método padrão de planos de cortes), informando o número de
planos de cortes inseridos no nó raiz da árvore de enumeração, o valor de uma
solução ótima obtido com esta técnica e o tempo de CPU, e
• Programação Inteira: (OPT: valor ótimo, CPU: tempo de CPU, em horas, minutos
e segundos, para encontrar uma solução ótima inteira).
Foram realizados diversos experimentos com instâncias de diferentes tamanhos. Dos
resultados mostrados nas tabelas conclui-se:
(a) O modelo em programação linear fornece excelentes limitantes inferiores aos valores
de soluções ótimas inteiras;
(b) Foram encontradas relativamente muitas inequações violadas no nó raiz da árvore
de eumeração do branch-and-cut;
(c) Devido o modelo ser muito forte, todas as instâncias testadas puderam ser resolvidas
em pouco tempo (menos de duas horas de tempo de CPU).
24
Tabela 5.1: Instâncias do CSP considerando um alfabeto com dois caracteres
n
10
10
10
10
10
10
10
10
10
10
10
15
15
15
15
15
15
15
15
15
15
15
Instância
m
Semente
1000
543
1250
65743
1500
65743
1750
4432
2000
543
2500
344
3000
34567
3500
344
4000
4432
4500
543
5000
34567
1000
344
1250
543
1500
34567
1750
4432
2000
344
2500
65743
3000
34567
3500
4432
4000
34567
4500
344
5000
543
Relaxação
OPT
375,9
473
566,4
650,8
750,8
945,1
1128
1309,8
1516
1696,6
1892,6
396,6
498,7
591,6
690,2
797,9
987,7
1186,5
1381,1
1588
1779
1985,5
linear
CPU
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
Planos de Corte
NumPC OPT
CPU
0
377
< 1s
0
474
< 1s
10
567
< 1s
0
652
1s
0
752
< 1s
20
946
< 1s
0 1129
< 1s
16 1311
1s
0 1517
< 1s
0 1697
< 1s
20 1893
1s
231
397
6s
282
500
13s
335
592
7s
414
691
6s
796
799
31s
889
989
1m17s
710 1187
32s
1208 1382
1m13s
1057 1589
2m13s
6125 1780 30m56s
4232 1986 20m35s
Programação Inteira
OPT
CPU
377
1s
474
1s
567
< 1s
652
2s
752
1s
946
< 1s
1129
1s
1311
2s
1517
1s
1697
< 1s
1893
1s
397
12s
500
14s
592
13s
691
6s
799
34s
989
1m19s
1187
38s
1382
1m14s
1589
2m15s
1780
31m3s
1986
20m42s
Figura 5.1: Gráficos das diferenças dos tempos de CPU, mostrados nas Tabelas 5.1 a 5.4,
considerando as duas abordagens testadas.
25
Tabela 5.2: Instâncias do CSP considerando um alfabeto com quatro caracteres
n
10
10
10
10
10
15
15
15
15
15
20
20
20
20
20
25
25
25
25
25
30
30
30
30
30
Instância
m Semente
100
1542
200
7121
300
6874
400
8465
500
7212
100
5419
200
6172
300
2454
400
6487
500
3454
100
1464
200
7121
300
6874
400
1985
500
9415
100
5419
200
4212
300
6874
400
1985
500
9415
100
14644
200
3544
300
68747
400
3454
500
62452
Relaxação Linear
OPT
CPU
58,3
< 1s
114,7
< 1s
172,3
< 1s
230,4
< 1s
290,7
< 1s
61,5
< 1s
124,4
< 1s
181,2
< 1s
245,9
< 1s
305,7
< 1s
64,7
< 1s
126,5
< 1s
190,6
< 1s
253,4
< 1s
317,5
< 1s
65,9
< 1s
129,0
< 1s
194,3
< 1s
257,9
< 1s
324,4
< 1s
65,8
< 1s
130,8
< 1s
196,2
< 1s
264,0
< 1s
325,9
< 1s
Planos de Corte
NumPC OPT
CPU
100
59
< 1s
197
115
< 1s
99
173
< 1s
113
231
< 1s
219
291
1s
15
62
< 1s
26
125
< 1s
229
182
1s
52
246
5s
38
306
1s
15
65
1m1s
7
127
< 1s
14
191
21s
10
254
< 1s
14
318
1s
3
67
18s
17
130
< 1s
1
195
< 1s
3
259
7s
3
325 2m32s
2
67
4s
1
132 1m27s
7
197
10s
3
265
< 1s
1
327
1s
26
Programação
OPT
59
115
173
231
291
62
125
182
246
306
65
127
191
254
318
67
130
195
259
325
67
132
197
265
327
Inteira
CPU
< 1s
< 1s
< 1s
< 1s
1s
< 1s
< 1s
1s
9s
1s
2m29s
6s
27s
1s
2s
36s
< 1s
< 1s
14s
2m34s
9s
2m50s
1m30s
1s
3s
Tabela 5.3: Instâncias do CSP considerando um alfabeto com quatro caracteres
n
10
10
10
10
10
10
10
10
10
10
10
15
15
15
15
15
15
15
15
15
15
15
Instância
m
Semente
1000
65743
1250
34567
1500
4432
1750
543
2000
344
2500
4432
3000
344
3500
34567
4000
344
4500
543
5000
543
1000
4432
1250
543
1500
543
1750
4432
2000
4432
2500
65743
3000
34567
3500
34567
4000
344
4500
543
5000
4432
Relaxação Linear
OPT
CPU
577,6
< 1s
722,8
< 1s
873,9
< 1s
1013,8
< 1s
1157,9
< 1s
1446,7
< 1s
1746
< 1s
2033,3
< 1s
2306,2
< 1s
2604
< 1s
2909
< 1s
610,7
< 1s
765,0
< 1s
915,7
< 1s
1070,9
< 1s
1225,9
< 1s
1526,6
< 1s
1826,8
< 1s
2137
< 1s
2447,6
< 1s
2754,1
< 1s
3057,1
< 1s
Planos de Corte
NumPC OPT
CPU
169
578
3s
295
723
10s
344
874
15s
208 1014
10s
721 1158
51s
563 1447
48s
24 1746
12s
477 2034 1m10s
19 2307
13s
93 2604
36s
10 2909
9s
70
611
7s
119
766
8s
31
916
4s
1 1071
11s
0 1226
7s
0 1527
7s
3 1827
10s
1 2137
26s
1 2448
28s
3 2755
11s
0 3058
8s
27
Programação Inteira
OPT
CPU
578
4s
723
11s
874
16s
1014
12s
1158
53s
1447
52s
1746
17s
2034
1m13s
2307
17s
2604
42s
2909
18s
611
13s
766
9s
916
5s
1071
15s
1226
13s
1527
12s
1827
19s
2137
52s
2448
33s
2755
14s
3058
14s
Tabela 5.4: Instâncias do CSP considerando um alfabeto com vinte caracteres
n
10
10
10
10
10
10
10
10
10
10
10
15
15
15
15
15
15
15
15
15
15
15
Instância
m
Semente
1000
543
1250
4432
1500
4432
1750
34567
2000
543
2500
344
3000
65743
3500
344
4000
543
4500
4432
5000
34567
1000
4432
1250
65743
1500
34567
1750
65743
2000
543
2500
344
3000
34567
3500
4432
4000
65743
4500
34567
5000
65743
Relaxação
OPT
780
975,7
1175,7
1370,6
1565,7
1957,2
2343,2
2737,6
3136,3
3517,7
3915,2
819,1
1026,0
1229,7
1434,4
1643,8
2048,9
2455,0
2869,4
3276,3
3688
4095,2
linear
CPU
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
< 1s
1s
1s
1s
< 1s
< 1s
< 1s
< 1s
< 1s
1s
1s
1s
1s
2s
2s
Planos de Corte
NumPC OPT
CPU
145
780
4s
126
976
4s
113 1176
6s
135 1371
8s
110 1566
11s
174 1958
19s
238 2344
27s
40 2738
14s
122 3137
36s
135 3518
43s
86 3916
35s
2228
820
2m54s
923 1027
46s
403 1230
26s
2311 1435
9m51s
477 1644
39s
1058 2049
3m2s
3500 2456
44m5s
1603 2870
1m17s
1559 3277
11m7s
3417 3688 1h16m21s
1395 4096
11m39s
28
Programação Inteira
OPT
CPU
780
5s
976
6s
1176
9s
1371
11s
1566
14s
1958
23s
2344
31s
2738
18s
3137
41s
3518
49s
3916
41s
820
2m55s
1027
47s
1230
28s
1435
9m55s
1644
44s
2049
3m8s
2456
44m12s
2870
1m24s
3277
11m14s
3688
1h16m31s
4096
11m47s
Capı́tulo 6
Comentários Finais
Esta dissertação é a respeito do Closest String Problem (CSP), um problema de otimização
combinatória que aparece na área de Biologia Computacional. Dada a sua importância,
dezenas de artigos foram publicados sobre este problema. O CSP pertence a classe de complexidade NP-difı́cil e diversas técnicas foram aplicadas para desenvolver algoritmos para
o mesmo. São também conhecidos algoritmos de aproximação, heurı́sticas sem comprovação de garantia de otimalidade e métodos exatos (branch-and-cut) para resolver instâncias
do problema.
Na referência [8] foram propostos três formulações em programação linear inteira para
o CSP. Nesta dissertação continuou-se o trabalho iniciado em [8] e propomos uma classe de
inequações válidas (planos de corte) juntamente com um algoritmo de separação destas.
Provou-se que embora o número destas inequações seja exponencial em n e m, respectivamente número de strings e o tamanho destas strings, o problema de separação é resolvido
em tempo polinomial em n e m. Este é um importante resultado teórico e prático alcançado.
Com o intuito de verificar o quão útil é a nova classe de planos de corte, foram realizados experimentos computacionais com a implementação de um branch-and-cut. A
implementação utilizou o solver IBM ILOG CPLEX 12.4 para calcular as relaxações lineares dos modelos. Como já era esperado o modelo matemático descrito em [8] fornece
excelentes limites inferiores nos valores de soluções ótimas.
Os experimentos computacionais, obtidos com a implementação de um branch-andcut, dão evidências claras de que esta implementação é mais rápida quanto maior for o
número de planos de corte gerados.
Ainda como resultado desta pesquisa, criamos uma fórmula para calcular limites inferiores nos valores de soluções ótimas. Essas contribuições serão utilizadas em pesquisas
futuras.
29
Referências Bibliográficas
[1] A. Ben-Dor, G. Lancia, J. Perone, and R. Ravi, Banishing bias from consensus sequences, Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching (Aarhus, Denmark) (A. Apostolico and J. Hein, eds.), Lecture notes in computer science, no. 1264, Springer-Verlag, 1997, pp. 247–261.
[2] R. E. Bixby, Notes on combinatorial optimization, Tech. report, Rice University,
Department of Computational and Applied Mathematics, 1987.
[3] C. Boucher, G. M. Landau, A. Levy, D. Pritchard, and O. Weimann, On approximating string selection problems with outliers, CoRR abs/1202.2820 (2012), 427–438.
[4] C. C. de Souza, The graph equipartition problem: Optimal solutions, extensions and
applications, Ph.D. thesis, Université Catholique de Louvain, 1993.
[5] K. Lanctot, M. Li, B. Ma, S. Wang, and L. Zhang, Distinguishing string selection
problems, Information and Computation 185 (2003), no. 1, 41–55.
[6] M. Li, B. Ma, and L. Wang, On the closest string and substring problems, Journal of
the ACM 49 (2002), no. 2, 157–171.
[7] C. N. Meneses, P. M. Pardalos, M. G. C. Resende, and A. Vazacopoulos, Modeling
and solving string selection problems, BIOMAT 2005 International Symposium on
Mathematical and Computational Biology – Selected Contributed Papers, 2005.
[8] C.N. Meneses, Z. Lu, C.A.S. Oliveira, and P.M. Pardalos, Optimal solutions for the
closest string problem via integer programming, INFORMS Journal on Computing
16 (2004), no. 4, 419–429.
[9] M. Minoux, Mathematical programming: Theory and algorithms, Wiley-Interscience,
1986.
[10] G. L. Nemhauser and L. A. Wolsey, Integer and combinatorial optimization, John
Wiley and Sons, New York, 1988.
30
[11] M. W. Padberg and M. Grötschel, Polyhedral computations, John Wiley and Sons,
1985.
[12] A. Schrijver, Theory of linear and integer programming, John Wiley and Sons, 1986.
[13] H. A. Taha, Operations research - an introduction, fourth edition, Macmillan Publishing Company, 1987.
31