[pt] Nesse trabalho, estudamos online packing integer programs, cujas colunas são
reveladas uma a uma. Já que algoritmos ótimos foram encontrados para o modelo
RANDOMORDER– onde a ordem na qual as colunas são reveladas para o algoritmo
é aleatória – o foco da área se voltou para modelo menos otimistas. Um desses
modelos é o modelo MIXED, no qual algumas colunas são ordenadas de forma
adversária, enquanto outras chegam em ordem aleatória. Pouquíssimos resultados
são conhecidos para online packing IPs no modelo MIXED, que é o objeto do nosso
estudo. Consideramos problemas de online packing com d dimensões de ocupação
(d restrições de empacotamento), cada uma com capacidade B. Assumimos que
todas as recompensas e ocupações dos itens estão no intervalo [0, 1]. O objetivo do
estudo é projetar um algoritmo no qual a presença de alguns itens adversários tenha
um efeito limitado na competitividade do algoritmo relativa às colunas de ordem
aleatória. Portanto, usamos como benchmark OPTStoch, que é o valor da solução
ótima offline que considera apenas a parte aleatória da instância. Apresentamos um
algoritmo que obtém recompensas de pelo menos (1 − 5lambda − Ó de epsilon)OPTStoch com
alta probabilidade, onde lambda é a fração de colunas em ordem adversária.
Para conseguir tal garantia, projetamos um algoritmo primal-dual onde as
decisões são tomadas pelo algoritmo pela avaliação da recompensa e ocupação
de cada item, de acordo com as variáveis duais do programa inteiro. Entretanto,
diferentemente dos algoritmos primais-duais para o modelo RANDOMORDER, não
podemos estimar as variáveis duais pela resolução de um problema reduzido. A
causa disso é que, no modelo MIXED, um adversário pode facilmente manipular
algumas colunas, para atrapalhar nossa estimação. Para contornar isso, propomos o
uso de tecnicas conhecidas de online learning para aprender as variáveis duais do
problema de forma online, conforme o problema progride. / [en] We study online packing integer programs, where the columns arrive one
by one. Since optimal algorithms were found for the RANDOMORDER model –
where columns arrive in random order – much focus of the area has been on less
optimistic models. One of those models is the MIXED model, where some columns
are adversarially ordered, while others come in random-order. Very few results are
known for packing IPs in the MIXED model, which is the object of our study.
We consider online IPs with d occupation dimensions (d packing constraints),
each one with capacity (or right-hand side) B. We also assume all items rewards
and occupations to be less or equal to 1. Our goal is to design an algorithm
where the presence of adversarial columns has a limited effect on the algorithm s
competitiveness relative to the random-order columns. Thus, we use OPTStoch – the
offline optimal solution considering only the random-order part of the input – as a
benchmark.We present an algorithm that, relative to OPTStoch, is (1−5 lambda− OBig O of epsilon)-competitive with high probability, where lambda is the fraction of adversarial columns.
In order to achieve such a guarantee, we make use of a primal-dual algorithm
where the decision variables are set by evaluating each item s reward and occupation
according to the dual variables of the IP, like other algorithms for the RANDOMORDER
model do. However, we can t hope to estimate those dual variables by
solving a scaled version of problem, because they could easily be manipulated by
an adversary in the MIXED model. Our solution was to use online learning techniques
to learn all aspects of the dual variables in an online fashion, as the problem
progresses.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:61783 |
| Date | 23 January 2023 |
| Creators | DAVID BEYDA |
| Contributors | MARCO SERPA MOLINARO, MARCO SERPA MOLINARO, MARCO SERPA MOLINARO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | English |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0022 seconds