Título
[en] ON THE MIN DISTANCE SUPERSET PROBLEM
Título
[pt] SOBRE O PROBLEMA DE SUPERSET MÍNIMO DE DISTÂNCIAS
Autor
[pt] LEONARDO LOBO DA CUNHA DA FONTOURA
Vocabulário
[pt] OTIMIZACAO QUADRATICA
Vocabulário
[pt] OTIMIZACAO INTEIRA
Vocabulário
[pt] MAPEAMENTO DE SITIOS DE RESTRICAO
Vocabulário
[pt] TURNPIKE PROBLEM
Vocabulário
[pt] PARTIAL DIGEST PROBLEM
Vocabulário
[pt] MODELAGEM MATEMATICA
Vocabulário
[en] QUADRATIC OPTIMIZATION
Vocabulário
[en] INTEGER OPTIMIZATION
Vocabulário
[en] RESTRICTION SITE MAPPING
Vocabulário
[en] TURNPIKE PROBLEM
Vocabulário
[en] PARTIAL DIGEST PROBLEM
Vocabulário
[en] MATHEMATICAL MODELING
Resumo
[pt] O Partial Digest Problem (problema de digestão parcial), também
conhecido como o Turnpike Problem, consiste na construção de um conjunto
de pontos na reta real dadas as distâncias não designadas entre todos os
pares de pontos. Uma variante deste problema, chamada Min Distance
Superset Problem (problema de superset de distância mínimo), lida com
entradas incompletas em que algumas distâncias podem estar faltando. O
objetivo deste problema é encontrar um conjunto mínimo de pontos na reta
real, tal que as distâncias entre cada par de pontos contenham todas as
distâncias de entrada.
As principais contribuições deste trabalho são duas formulações de programação matemática diferentes para o Min Distance Superset Problem:
uma formulação de programação quadrática e uma formulação de programação inteira. Mostramos como aplicar um método de cálculo direto
de limites de valores de variáveis através de uma relaxação Lagrangeana da
formulação quadrática. Também introduzimos duas abordagens diferentes
para resolver a formulação inteira, ambas baseadas em buscas binárias na
cardinalidade de uma solução ótima. A primeira baseia-se num subconjunto
de variáveis de decisão, na tentativa de lidar com um problema de viabilidade
mais simples, e o segundo é baseado na distribuição de distâncias entre
possíveis pontos disponíveis.
Resumo
[en] The Partial Digest Problem, also known as the Turnpike Problem,
consists of building a set of points on the real line given their unlabeled
pairwise distances. A variant of this problem, named Min Distance Superset
Problem, deals with incomplete input in which distances may be missing.
The goal is to find a minimal set of points on the real line such that the
multiset of their pairwise distances is a superset of the input.
The main contributions of this work are two different mathematical
programming formulations for the Min Distance Superset Problem:
a quadratic programming formulation and an integer programming
formulation.We show how to apply direct computation methods for variable
bounds on top of a Lagrangian relaxation of the quadratic formulation. We
also introduce two approaches to solve the integer programming formulation,
both based on binary searches on the cardinality of an optimal solution.
One is based on a subset of decision variables, in an attempt to deal with a
simpler feasibility problem, and the other is based on distributing available
distances between possible points.
Orientador(es)
THIBAUT VICTOR GASTON VIDAL
Coorientador(es)
MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO
Banca
HELIO CORTES VIEIRA LOPES
Banca
MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO
Banca
THIBAUT VICTOR GASTON VIDAL
Banca
CARLILE CAMPOS LAVOR
Catalogação
2016-06-09
Apresentação
2015-08-19
Tipo
[pt] TEXTO
Formato
application/pdf
Idioma(s)
INGLÊS
Referência [pt]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=26566@1
Referência [en]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=26566@2
Referência DOI
https://doi.org/10.17771/PUCRio.acad.26566
Arquivos do conteúdo
NA ÍNTEGRA PDF