[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. / [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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:26566 |
| Date | 09 June 2016 |
| Creators | LEONARDO LOBO DA CUNHA DA FONTOURA |
| Contributors | THIBAUT VICTOR GASTON VIDAL |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | English |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0022 seconds