Fornecedores necessitam atender a demanda de seus clientes da forma mais adequada possível e mantendo a qualidade de seu serviço, porém em muitos casos essa demanda é desconhecida. Esse problema pode ser modelado como um problema de roteirização e estoque com demanda estocástica o qual inclui o controle de estoque, transporte do produto e decisões de agendamento da entrega. Existem vários trabalhos na literatura para resolver esse problema, porém nenhum deles lida com janela de tempo de atendimento, capacidade máxima de estoque tanto no cliente quanto no depósito e o nível de confiança de atendimento individualizado para cada cliente. O objetivo principal deste trabalho é propor um novo algoritmo baseado em otimização matemática para lidar com esse problema mais realista. Além disso, este trabalho tem como objetivo secundário melhorar o algoritmo de estado da arte baseado em otimização matemática, visando encontrar soluções com um menor tempo computacional e custo. Foram realizados experimentos com instâncias sintéticas com 15 até 50 clientes, as quais são geradas aleatoriamente, e com uma instância real, baseada na experiência profissional no mercado empresarial e em cenários reais de distribuição na cidade de São Paulo / Providers need to supply the demand of their clients as optimally as possible and maintaining the quality of their service, however in many cases this demand is unknown. This problem can be modeled as a inventory routing problem with stochastic demand, which includes inventory control, product transportation and delivery scheduling decisions. There are several papers in the literature to solve this problem, but none of them deals with service time window, maximum stock capacity for both the customer and the depot and individualized confidence level for each costumer. The main objective of this work is to propose a new algorithm based on mathematical optimization to deal with this more realistic problem. In addition, this work has as secondary objective to improve the state of the art algorithm based on mathematical optimization, aiming to find solutions with a lower computational time and cost. Experiments were performed with synthetic instances with 15 to 50 clients, which are randomly generated, and with a real instance, based on professional experience in the business market and in real distribution scenarios in the city of São Paulo

DIAS, Fábio Carlos Sousa. Algoritmos para o problema de localização simples baseados nas formulações clássica e canônica. 2008. 81 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2008. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-22T17:13:52Z No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-22T17:16:23Z (GMT) No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5) / Made available in DSpace on 2016-06-22T17:16:23Z (GMT). No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5) Previous issue date: 2008 / In this work, we study the Simple Plant Location Problem (SPLP). Using its classical mathematical programming formulation and another recently proposed formulation, we develop several algorithms to …nd lower and upper bounds for the problem as well as branch-and-bound algorithms. With the classical formulation, such bounds are obtained via the data correction method and dominance criteria between …xed and transportation costs. We propose a projection of this formulation that has shown to be computationally atractive. Using the new formulation, we propose and prove the correctness of several iterative procedures that attempt to …nd an optimal solution to the problem by solving a sequence of parametric sub-problems, each one obtained by removing some variables and constraints of the original formulation. At each iteration of this process, we can obtain lower and upper bounds. We also apply Lagrangean relaxation to this new formulation in order to get other bounds. We consider several possibilities of relaxing the constraints. In addition, we develop branch-and-bound algorithms based on both formulations and the obtained bounds. We evaluate the computational e¢ ciency of all proposed algorithms with hard test instances from the literature. Computational results are reported and comparisons with other algorithms from the literature are carried out. / Neste trabalho, estudamos o problema de localização simples (SPLP - Simple Plant Location Problem). Usando a formulação matemática clássica e uma outra formulação proposta recentemente, desenvolvemos vários algoritmos para encontrar limites inferiores e superiores, bem como algoritmos tipo branch-and-bound. Com a formulação clássica, tais limites são obtidos utilizando o método de correção de dados e critérios de dominância entre os custos …xos e de transporte. Propomos uma projeção dessa formulação, que se mostrou computacionalmente atrativa. Usando a nova formulação propomos e mostramos a corretude de vários procedimentos iterativos que procuram encontrar uma solução para o problema, resolvendo uma seqüência de subproblemas paramétricos obtidos com a remoção de variáveis e restrições da formulação original. Em cada iteração desse processo, podemos gerar limites inferiores e superiores. Aplicamos ainda relaxação lagrangeana a essa nova formulação para obter outros limites. Analisamos várias possibilidades de relaxação das restrições. Desenvolmento também algoritmos branch-and-bound baseados em ambas as formulações e nos limites obtidos. Avaliamos a e…ciência computacional de todos os algoritmos com instâncias de teste difíceis, disponíveis na literatura. Resultados computacionais e comparações com outros algoritmos da literatura são reportados.

Orientador: Prof. Dr. Alysson Fábio Ferrari / Tese (doutorado) - Universidade Federal do ABC, Programa de Pós-Graduação em Física, 2016. / Operadores contendo derivadas superiores não estão incluídos no Modelo Padrão Estendido (SME) e podem ter relevância na busca por uma teoria que opere na escala de Planck. Nessa tese de doutorado investigamos algumas consequências físicas no regime de baixas energias devido a violação de Lorentz (Lorentz violation, ou LV) gerada por operadores desse tipo. Começamos com um modelo constituído pelo campo fermiônico carregado e massivo , pelo campo do fóton A e pelo campo do tipo áxion (ALP ou axion-like-particle) . A LV aparece através dos acoplamentos não mínimos Fd e 5=b , onde d e b são os vetores constantes responsáveis pela introdução da LV. Assumimos que o campo fermiônico tem massa muito grande, e integramos a ação efetiva no campo do férmion, obtendo então como correção quântica de uma laço uma interação efetiva a baixa energia entre o campo do fóton e o campo do ALP, que resulta ser do mesmo tipo de interação que tem sido investigado em pesquisas experimentais atuais. Em seguida, estudamos outras consequências da interação Fd por meio correções quânticas de um laço, agora exclusivamente no setor de fóton. Mostramos que tal interação LV é responsável por gerar na ação efetiva operadores LV com derivadas superiores. Dentre as correções quânticas geradas consideramos a correção até primeira ordem no parâmetro LV d, juntamente com as correções não lineares de mais baixa ordem, e investigamos efeitos da LV na propagação de ondas eletromagnéticas em uma região contendo um campo magnético forte e constante. Por fim investigamos consequências físicas adicionais da interação Fd por meio das interações entre fontes externas intermediadas pelo campo eletromagnético, onde discutimos os principais fenômenos físicos que emergem dessa teoria e que não são contemplados na teoria de Maxwell usual. / Higher derivatives operators are not included in the Standard Model Extension (SME) and they can have relevance in the search by a theory which operates in the Planck energy scale. In this PhD thesis we investigate some physical consequences in the low energy regime due to LV which was generated by this kind of operators. We start with a model in the high energy regime that is constituted by the charged massive fermionic field , by the photon field A and by the axion-like-particle (ALP) field . The LV appear in our model due to the two couplings Fd and 5=b , where d and b are the constant vectors responsible for introducing the LV. We assume the fermion mass to be very high and we integrate the effective action in the fermion field, obtaining as one-loop quantum correction an effective interaction in the low energy regime between the photon field and ALP field, which we show to be of the same form as the one studied in current experimental searches. Then, we study other physical consequences of the interaction Fd through one-loop quantum corrections in the pure photon sector. We show that such LV interaction generates in the effective action Lorentz violating higher derivatives operators. Among the generated quantum corrections we consider the ones of the first order in the LV parameter d; together with the lowest order non-linear corrections, and we investigate the effects of the LV in the electromagnetic wave propagation in a region with a strong, constant magnetic field. To finish, we investigate additional physical consequences of the interaction Fd through interactions between external sources intermediated by the electromagnetic field, where we discuss the main physical phenomena that emerge of this theory which have no counterpart in Maxwell theory.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Nesta dissertaÃÃo, nosso principal objetivo foi desenvolver uma tÃcnica de resoluÃÃo para um problema na Ãrea de telecomunicaÃÃes. O problema em questÃo à chamado de problema de PonderaÃÃo de Rodadas (PR) e foi inicialmente proposto em [Klasing,Morales,Perennes, 2008]. O contexto do problema envolve uma rede sem fio, onde as comunicaÃÃes sÃo realizadas via ondas de rÃdio e a rede funciona atravÃs de uma operaÃÃo da rede que satisfaz certas restriÃÃes. Inicialmente, explicamos como à formada uma rede de rÃdio e descrevemos a forma de operaÃÃo da rede de rÃdio junto Ãs restriÃÃes usando um modelo matemÃtico. Em seguida, formalizamos o problema PR como um problema de otimizaÃÃo, especificando suas restriÃÃes, correspondente à geraÃÃo do conjunto de possÃveis operaÃÃes da rede, e critÃrio de otimizaÃÃo, referente ao uso dos recursos da rede. Posteriormente, mostramos um estudo preliminar do problema de ColoraÃÃo FracionÃria (CF) e apresentamos uma tÃcnica de resoluÃÃo deste problema atravÃs do uso de uma heurÃstica lagrangeana baseada em uma relaxaÃÃo lagrangeana de uma formulaÃÃo de programaÃÃo inteira do problema. Essa tÃcnica de resoluÃÃo à entÃo adaptada para o problema PR, consistindo na principal contribuiÃÃo de nossa pesquisa. Por fim, mostramos os resultados computacionais e anÃlises das nossas implementaÃÃes para os problemas CF e PR. / In this dissertation, our main objective was to develop a technique for resolution to a problem in the area of telecommunications. The problem in question is called Round Weighting Problem (RWP) and was originally proposed in (KLASING; MORALES; PeRENNES, 2008). The context of the problem involves a wireless network where communications are performed by radio waves and the network operates through a network operation that satises the constraints of the problem. Initially, we explain how a radio network is formed and describe the mode of operation of the radio network with restrictions using a mathematical model. Then, we formalize the RWP as an optimization problem, specifying their restrictions, corresponding to the generation of the set of possible network operations, and optimization criterion, regarding the use of network resources. Subsequently, we show a preliminary study of the Fractional Coloring problem (FC problem) and present a technique to solve this problem through the use of a lagrangian heuristic based on a lagrangian relaxation of an integer programming formulation of the problem. This resolution technique is then adapted to the RWP, consisting in the main contribution of our research. Finally, we show the computational results and analyzes of our implementations for the Fractional Coloring problem and RWP.

Orientadores: Carlos Eduardo Durán Fernandez, Marcos Benevenutto Jardim / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-16T11:28:16Z (GMT). No. of bitstreams: 1 Vitorio_HenriquedeBarrosCorreia_D.pdf: 1074812 bytes, checksum: e23ca71f5e87d6990c05425cdcb87bee (MD5) Previous issue date: 2010 / Resumo: A presente tese dá continuidade ao recente trabalho de J.C . Álvarez e C.E. Durán acerca dos invariantes geométricos de uma classe genérica de curvas em variedades de Grassmann, ditas "curvas fanning". Mais precisamente, considera-se como tais curvas de planos lagrangeanos comportam-se mediante uma redução simplética, e conclui-se a existência de dois novos invariantes que desempenham um papel fundamental neste contexto, mais notavelmente a maneira pela qual eles generalizam as bem conhecidas fórmulas de O'Neill para submersões isométricas / Abstract: The present thesis gives continuity to the recent work of J.C. Álvarez e C.E. Durán about the geometric invariants of a generic class of curves in the Grassmann manifolds, called "fanning curves". More precisely, we look at how such curves of lagrangean planes behave under a symplectic reduction, and establish the existence of two new invariants which play a fundamental role in that context, more notably the way they generalize the well known O'Neill's formulas for isometric submersions / Doutorado / Matematica / Doutor em Matemática

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Neste trabalho, estudamos o problema de localizaÃÃo simples (SPLP - Simple Plant Location Problem). Usando a formulaÃÃo matemÃtica clÃssica e uma outra formulaÃÃo proposta recentemente, desenvolvemos vÃrios algoritmos para encontrar limites inferiores e superiores, bem como algoritmos tipo branch-and-bound. Com a formulaÃÃo clÃssica, tais limites sÃo obtidos utilizando o mÃtodo de correÃÃo de dados e critÃrios de dominÃncia entre os custos …xos e de transporte. Propomos uma projeÃÃo dessa formulaÃÃo, que se mostrou computacionalmente atrativa. Usando a nova formulaÃÃo propomos e mostramos a corretude de vÃrios procedimentos iterativos que procuram encontrar uma soluÃÃo para o problema, resolvendo uma seqÃÃncia de subproblemas paramÃtricos obtidos com a remoÃÃo de variÃveis e restriÃÃes da formulaÃÃo original. Em cada iteraÃÃo desse processo, podemos gerar limites inferiores e superiores. Aplicamos ainda relaxaÃÃo lagrangeana a essa nova formulaÃÃo para obter outros limites. Analisamos vÃrias possibilidades de relaxaÃÃo das restriÃÃes. Desenvolmento tambÃm algoritmos branch-and-bound baseados em ambas as formulaÃÃes e nos limites obtidos. Avaliamos a e…ciÃncia computacional de todos os algoritmos com instÃncias de teste difÃceis, disponÃveis na literatura. Resultados computacionais e comparaÃÃes com outros algoritmos da literatura sÃo reportados. / In this work, we study the Simple Plant Location Problem (SPLP). Using its classical mathematical programming formulation and another recently proposed formulation, we develop several algorithms to …nd lower and upper bounds for the problem as well as branch-and-bound algorithms. With the classical formulation, such bounds are obtained via the data correction method and dominance criteria between …xed and transportation costs. We propose a projection of this formulation that has shown to be computationally atractive. Using the new formulation, we propose and prove the correctness of several iterative procedures that attempt to …nd an optimal solution to the problem by solving a sequence of parametric sub-problems, each one obtained by removing some variables and constraints of the original formulation. At each iteration of this process, we can obtain lower and upper bounds. We also apply Lagrangean relaxation to this new formulation in order to get other bounds. We consider several possibilities of relaxing the constraints. In addition, we develop branch-and-bound algorithms based on both formulations and the obtained bounds. We evaluate the computational e ciency of all proposed algorithms with hard test instances from the literature. Computational results are reported and comparisons with other algorithms from the literature are carried out.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-03-31T11:28:07Z No. of bitstreams: 1 jesuscernadesgomez.pdf: 1031961 bytes, checksum: 184ef4c8e577aada634107338cd8a4ee (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-04-24T02:56:11Z (GMT) No. of bitstreams: 1 jesuscernadesgomez.pdf: 1031961 bytes, checksum: 184ef4c8e577aada634107338cd8a4ee (MD5) / Made available in DSpace on 2016-04-24T02:56:11Z (GMT). No. of bitstreams: 1 jesuscernadesgomez.pdf: 1031961 bytes, checksum: 184ef4c8e577aada634107338cd8a4ee (MD5) Previous issue date: 2013-06-07 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho tem por finalidade apresentar um método para a solução de problemas de otimização não-convexos e não-diferenciáveis. O método, chamado IED (Interior Epigraph Directions), aplica-se a problemas de otimização cuja função objetivo é contínua e definida em um subconjunto compacto de Rn, sujeita a restrições de igualdade e/ou desigualdade. O método IED considera o problema dual induzido por uma função lagrangeana aumentada e obtém a solução primal gerando uma sequêmcia de pontos no interior do epígrafo da função dual. Primeiramente, um subgradiente é usado para gerar uma aproximação linear do problema dual. Em seguida, usa-se esta aproximação linear para definir-se uma direção de busca interior ao epígrafo da função dual. Obtém-se então, a partir de um ponto no interior do epígrafo, um novo ponto interior e, consequêntemente, uma sequência de pontos interiores é construida. Essa sequência produz uma sequência dual que por sua vez origina uma sequência primal, através da solução de um subproblema originado pela dualidade. A análise de convergência do algoritmo é também apresentada bem como resultados numéricos da solução de problema extraídos da literatura. / This work presents a method for solving constrained nonsmooth and nonconvex optimization problems. Themethod, called IED (Interior Epigraph Directions) can be applied to optimization problems with continuos objective functions defined over compact subsets of Rn and subjected to equalities and/or inequalities constraints. The IED method considers the dual problem induced by a generalized augmented Lagrangian function and obtains the primal solution by generating a sequence of iterates in the interior of the dual function. First, a subgradient is used to build a linear approximation to the dual problem. Then, this linear approximation is used to define a search direction in the interior of the dual function. From an interior point of the epigraph, a new point is obtained and an interior sequence to the epigraph is built, This sequence of interior points generates a dual sequence which in its turn generates a primal sequence by solving a problem originated by duality. The convergence analysis is also presented as well as numerical result of several problems obtained from de literature.

Submitted by Geandra Rodrigues (geandrar@gmail.com) on 2018-07-12T12:23:47Z No. of bitstreams: 1 hernandojoserochafranco.pdf: 1674623 bytes, checksum: f6df7317dd6a8e94e51045dbf75e8241 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2018-07-17T11:56:13Z (GMT) No. of bitstreams: 1 hernandojoserochafranco.pdf: 1674623 bytes, checksum: f6df7317dd6a8e94e51045dbf75e8241 (MD5) / Made available in DSpace on 2018-07-17T11:56:13Z (GMT). No. of bitstreams: 1 hernandojoserochafranco.pdf: 1674623 bytes, checksum: f6df7317dd6a8e94e51045dbf75e8241 (MD5) Previous issue date: 2018-06-08 / A teoria clássica de otimização presume a existência de certas condições, por exemplo, que as funções envolvidas em um problema desta natureza sejam pelo menos uma vez continuamente diferenciáveis. Entretanto, em muitas aplicações práticas que requerem o emprego de métodos de otimização, essa característica não se encontra presente. Problemas de otimização não diferenciáveis são considerados mais difíceis de lidar. Nesta classe, aqueles que envolvem funções não convexas são ainda mais complexos. O Interior Epigraph Directions (IED) é um método de otimização que se baseia na teoria da Dualidade Lagrangeana e se aplica à resolução de problemas não diferenciáveis, não convexos e com restrições. Neste estudo, apresentamos duas novas versões para o referido método a partir de implementações computacionais de outros algoritmos. A primeira versão, denominada IED+NFDNA, recebeu a incorporação de uma implementação do algoritmo Nonsmooth Feasible Direction Nonconvex Algorithm (NFDNA). Esta versão, ao ser aplicada em experimentos numéricos com problemas teste da literatura, apresentou desempenho satisfatório quando comparada ao IED original e a outros solvers de otimização. Com o objetivo de aperfeiçoar mais o método, reduzindo sua dependência de parâmetros iniciais e também do cálculo de subgradientes, uma segunda versão, IED+GA, foi desenvolvida com a utilização de algoritmos genéticos. Além da resolução de problemas teste, o IED-FGA obteve bons resultados quando aplicado a problemas de engenharia. / The classical theory of optimization assumes the existence of certain conditions, for example, that the functions involved in a problem of this nature are at least once continuously differentiable. However, in many practical applications that require the use of optimization methods, this characteristic is not present. Non-differentiable optimization problems are considered more difficult to deal with. In this class, those involving nonconvex functions are even more complex. Interior Epigraph Directions (IED) is an optimization method that is based on Lagrangean duality theory and applies to the resolution of non-differentiable, non-convex and constrained problems. In this study, we present two new versions for this method from computational implementations of other algorithms. The first version, called IED + NFDNA, received the incorporation of an implementation of the Nonsmooth Feasible Direction Nonconvex Algorithm (NFDNA) algorithm. This version, when applied in numerical experiments with problems in the literature, presented satisfactory performance when compared to the original IED and other optimization solvers. A second version, IED + GA, was developed with the use of genetic algorithms in order to further refine the method, reducing its dependence on initial parameters and also on the calculation of subgradients. In addition to solving test problems, IED + GA achieved good results when applied to engineering problems.

[pt] Nesta tese são propostos modelos e algoritmos aproximados para o Problema da Árvore Geradora de Custo Mínimo com Restrição de Diâmetro (AGMD). Este problema modela tipicamente aplicações em projetos de redes de computadores onde todos os vértices devem comunicar-se entre si a um custo mínimo, garantindo um certo nível de serviço. Os modelos propostos por Achuthan e Caccetta para o AGMD são reforçados através da introdução de restrições válidas. Uma relaxação lagrangeana é proposta para o modelo de multifluxo básico de Gouveia e Magnanti. Essa relaxação é utilizada para o desenvolvimento de heurísticas lagrangeanas. Adaptações são realizadas nas heurísticas construtivas propostas por Deo e Abdalla, e por Raidl e Julstrom. São propostas ainda quatro estratégias de busca local, uma heurística do tipo GRASP e outra híbrida. São obtidos limites superiores a menos de 2% do ótimo para as classes de instâncias usadas nos trabalhos de Gouveia e Magnanti, e de Santos, Lucena e Ribeiro. Além disto, obteve-se os melhores resultados conhecidos até o presente momento para 11 instâncias de grafos completos usadas por Raidl, Julstrom e Gruber. / [en] In this work, models and approximation algorithms to solve the Diameter Constrained Minimum Spanning Tree Problem (AGMD) are proposed. This problem typically models network design applications where all vertices must communicate with each other at a minimum cost, while meeting a given quality requirement. The formulations proposed by Achuthan and Caccetta are strengthened with valid inequalities. A lagrangean relaxation is proposed for the multicommodity flow model developed by Gouveia and Magnanti. Adaptations are made in the constructive heuristics proposed by Deo and Abdalla and by Raidl and Julstrom. Four local search procedures, a GRASP algorithm and a hybrid heuristic are proposed. Upper bounds within 2% of the optimal solution values are obtained for the two classes of instances used by Gouveia and Magnanti and by Santos, Lucena and Ribeiro. Moreover, stronger upper bounds are reported for 11 instances in complete graphs used by Raidl, Julstrom and Gruber