Este trabalho aborda o problema multiestágio de planejamento e programação da produção em indústrias cervejeiras. O processo de fabricação de cerveja pode ser dividido em duas etapas principais: preparação do líquido e envase. A primeira etapa ocorre, na maior parte do tempo, dentro de tanques de fermentação e maturação. A segunda ocorre nas linhas de envase, podendo ter início assim que o líquido estiver pronto nos tanques. O tempo de preparação do líquido demora vários dias, enquanto que na maioria das indústrias de bebidas carbonatadas este tempo é de no máximo algumas horas. O objetivo deste estudo é obter planos de produção viáveis que visam otimizar as decisões de programação envolvidas nestes processos. Visitas a cervejarias no Brasil e em Portugal foram realizadas para uma maior familiaridade do processo de produção e dados foram coletados. Modelos de programação inteira mista para representar o problema foram desenvolvidos, baseados em abordagens CSLP (The Continuous Setup Lot-Sizing Problem), GLSP (General Lot Sizing and Scheduling Problem), SPL (Simple Plant Location Problem) e ATSP (Asymmetric Travelling Salesman Problem). Os resultados mostram que os modelos são coerentes e representam adequadamente o problema, entretanto, mostram-se difíceis de serem resolvidos na otimalidade. Esta dificuldade de resolução dos modelos motivou o desenvolvimento de procedimentos MIP-heurísticos, como também de uma metaheurística GRASP (Greedy Randomized Adaptive Search Procedure). As soluções obtidas pelos procedimentos heurísticos são de boa qualidade, quando comparadas ao melhor limitante inferior encontrado por meio da resolução dos modelos matemáticos. Os testes computacionais foram realizados utilizando instâncias geradas com base em dados reais. / This study deals with the multistage lot-sizing and scheduling problem in breweries. The brewing process can be divided into two main stages: preparation and filling of the liquid. The first stage occurs most of the time in fermentation and maturation tanks. The second stage occurs in the filling lines and it can start as soon as the liquid gets ready. The preparation time of the liquid takes several days, while in the carbonated beverage industries this time is at most a few hours. The purpose of this study is to obtain feasible production plans aimed at optimizing the decisions involved in these processes. Visits to brewery industries in Brazil and Portugal were held to a greater familiarity of the production process and data were collected. Mixed integer programming models have been developed to represent the problem, based on approaches for the CSLP (The Continuous Setup Lot-Sizing Problem), GLSP (General Lot Sizing and Scheduling Problem), SPL (Simple Plant Location Problem) and ATSP (Asymmetric Travelling Salesman Problem). The results show that the models are consistent and adequately represent the problem; however, they are difficult to be solved at optimality. This motivated the development of MIP-heuristic procedures, as well as a meta-heuristic GRASP (Greedy Randomized Adaptive Search Procedure). The obtained solutions by the heuristics are of good quality, when compared to the best lower bound found by solving the mathematical models. The tests were conducted using generated instances based on real data.

Exploramos o seguinte problema: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y sem símbolos repetidos. Estudamos a estrutura deste problema, particularmente do ponto de vista de grafos e de combinatória poliédrica. Desenvolvemos algoritmos de aproximação e heurísticas para este problema. O enfoque deste trabalho está na construção de um algoritmo baseado na técnica branch-and-cut, aproveitando-nos de um algoritmo de separação eficiente e de heurísticas e técnicas para encontrarmos uma solução ótima mais cedo. Também estudamos um problema mais fácil no qual este problema é baseado: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y. Exploramos este problema do ponto de vista de combinatória poliédrica e descrevemos vários algoritmos conhecidos para resolvê-lo. / We explore the following problem: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y without repeated symbols. We study the structure of this problem, particularly from the point of view of graphs and polyhedral combinatorics. We develop approximation algorithms and heuristics for this problem. The focus of this work is in the construction of an algorithm based on the branch-and-cut technique, taking advantage of an efficient separation algorithm and of heuristics and techniques to find an optimal solution earlier. We also study an easier problem on which this problem is based: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y. We explore this problem from the point of view of polyhedral combinatorics and describe several known algorithms to solve it.

Orientador: Ariovaldo Verandio Garcia, Ruben Augusto Romero Lazaro / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T06:56:43Z (GMT). No. of bitstreams: 1 RiderFlores_MarcosJulio_D.pdf: 1021887 bytes, checksum: 6000961c2f5457b410ac691912476270 (MD5) Previous issue date: 2006 / Resumo: Neste trabalho são propostos modelos matemáticos e técnicas de solução para resolver o problema de planejamento da expansão de sistemas de transmissão através de três enfoques. a) Usando o modelo de corrente alternada do sistema de transmissão e um algoritmo heurístico construtivo especializado para resolver o problema de planejamento, e, ainda, realiza-se uma primeira tentativa de alocação de fontes de potência reativas; b) Usando o modelo de corrente contínua e técnicas de programação não-linear especializadas. Nesse caso emprega-se uma versão relaxada do problema de planejamento da expansão de sistemas de transmissão usando o modelo de corrente contínua, onde a integralidade das variáveis de investimento é desprezada. Resolve-se o problema de programação não-linear, modelado de forma matricial com um algoritmo de otimização especializado e, além disso, um algoritmo heurístico construtivo especializado é utilizado para resolver o problema de planejamento. c) Usando o modelo de corrente contínua e um algoritmo Branch and Bound (B&B) sem empregar técnicas de decomposição. Para isso foram redefinidos os chamados testes de sondagem no algoritmo B&B e em cada nó da árvore de B&B tem-se um problema de programação não-linear que são resolvidos usando a metodologia desenvolvida no item (b). Os ítens (a), (b) e (c) requerem a solução de problemas de programação não-linear diferenciados. Uma revisão das características principais da resolução iterativa dos métodos de pontos interiores é apresentada. Foi desenvolvida uma técnica baseada em uma combinação de métodos de pontos interiores de alta ordem (MPI-AO) para resolver os problemas de programação não-linear de forma rápida, eficiente e robusta. Essa combinação dos MPI-AO tem como objetivo colocar num único método as características particulares de cada um dos MPI-AO e melhorar o desempenho computacional comparado com os MPI-AO de forma individual / Abstract: In this work mathematical models and solution techniques are proposed to solve the power system transmission expansion planning problem through three approaches: a) Using the nonlinear model ofthe transmission system (AC model) and a specialized constructive heuristic algorithm to solve the problem and, yet, a first attempt to allocate reactive power sources is also considered; b) Using the direct-current (DC) model and specialized techniques of nonlinear programming. In this case a version of the power system transmission expansion planning problem using the DC model where the integrality of the investment variables is relaxed is used. The nonlinear programming problem is solved with a specialized optimization algorithm and, moreover, a constructive heuristic algorithm is employed to solve the planning problem. c) Using the DC model and Branch and Bound (B&B) algorithm without the use of decomposition techniques. The so called fathoming tests of the B&B were redefined and at each node of the tree a nonlinear programming problem is solved using the method developed in b). Items a), b) and c) require the solution of distinct problems of nonlinear programming. A revision of the main characteristics of the iterative solution of the interior points methods is presented. An optimization technique based on a combination of the higher order interior point methods (HO-IPM) had been developed to solve the nonlinear programming problems in a fast, efficient and robust way. This combination of the HO-IPM has as objective to explore the particular characteristics of each method in a single one and to improve the comparative computational performance with the HO-IPM of individual form / Doutorado / Energia Eletrica / Doutor em Engenharia Elétrica

Submitted by Franciele Moreira (francielemoreyra@gmail.com) on 2017-10-20T16:09:47Z No. of bitstreams: 2 Dissertação - Lorrany Cristina da Silva - 2017.pdf: 8394886 bytes, checksum: 9cc1461b937a65a8c50964b3dea86623 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-10-23T10:05:52Z (GMT) No. of bitstreams: 2 Dissertação - Lorrany Cristina da Silva - 2017.pdf: 8394886 bytes, checksum: 9cc1461b937a65a8c50964b3dea86623 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-10-23T10:05:52Z (GMT). No. of bitstreams: 2 Dissertação - Lorrany Cristina da Silva - 2017.pdf: 8394886 bytes, checksum: 9cc1461b937a65a8c50964b3dea86623 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-06-28 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Three different integer linear programming models for the Vehicle Routing Problem with Two-dimensional Loading Constraints are developed in this work. The version of the problem studied considers that the unloading of the rectangular items can respect or not the sequence of the clients visited on the route, that is, we solve the sequential and unrestricted versions of the problem. The first model deals with the problem completely, that is, with all constraints inserted at once. The second and third models are based, respectively, on a three- and two-index formulation. Separation routines are considered to detect violated inequalities related with packing on the second and third models, while the third model also considers cuts on connectivity and capacity. Computational experiments were carried out over instances of the literature with the quantity of customers ranging from 15 to 36 and items from 15 to 114, besides to consider the cases in which the cost of traversing an edge is integer and real. The models with cuts on demand were better in relation to the first model, besides being competitive when comparing with the results fromthe literature. The first model solved 4 of the 80 instances, the three-index model solved 7 and, the two-index model solved 53. On the sequential version, the adopted model solved 33 instances for the case with integer costs (and 37 for the case with real costs). In comparing with a recent heuristic from the literature, the best model was capable of tying in 48 instances in the unrestricted version and 24 in the sequential version. / Neste trabalho desenvolvem-se três modelos de programação linear inteira para o Problema de Roteamento de Veículos com Restrições de Empacotamento Bidimensional. A versão do problema estudado considera que o descarregamento dos itens retangulares pode respeitar (ou não) a sequência de clientes visitados na rota, ou seja, resolve-se as versões sequencial e irrestrita do problema. O primeiro modelo trata do problema de forma completa, isto é, com todas as restrições inseridas de uma só vez. O segundo e o terceiro modelo são baseados, respectivamente, em uma formulação de três e dois índices. Rotinas de separação são consideradas para detectar desigualdades violadas de empacotamento no segundo e no terceiro modelo, enquanto o último modelo considera também cortes de conectividade e capacidade. Experimentos computacionais foram realizados em instâncias da literatura com número de clientes variando de 15 a 36 e itens de 15 até 114, além de considerar os casos em que o custo da aresta é inteiro ou real. Os modelos com cortes sob demanda foram melhores em relação ao primeiro modelo, além de serem competitivos quando comparado com a literatura. O modelo completo encontrou a solução ótima em 4 das 80 instâncias, o modelo de três índices 7 e o modelo de dois índices 53. Na versão sequencial, o modelo adotado resolveu 33 instâncias para o custo inteiro (e 37 para o custo real). Na comparação com uma heurística recente da literatura, o melhor modelo conseguiu empatar em 48 instâncias na versão irrestrita e em 24 na versão sequencial.

Submitted by Erika Demachki (erikademachki@gmail.com) on 2017-06-21T21:21:46Z No. of bitstreams: 2 Dissertação - Liliane de Azevedo Oliveira - 2017.pdf: 1274368 bytes, checksum: 9b7a4aa781e0951c3f12045277a55582 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Erika Demachki (erikademachki@gmail.com) on 2017-06-29T18:27:23Z (GMT) No. of bitstreams: 2 Dissertação - Liliane de Azevedo Oliveira - 2017.pdf: 1274368 bytes, checksum: 9b7a4aa781e0951c3f12045277a55582 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-06-29T18:27:23Z (GMT). No. of bitstreams: 2 Dissertação - Liliane de Azevedo Oliveira - 2017.pdf: 1274368 bytes, checksum: 9b7a4aa781e0951c3f12045277a55582 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-02-22 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / In this work we applied an algorithm based on the resolution of integer linear models for the problem of packing boxes into a single container considering the cargo stability constraint. The problem consists of arranging items (boxes) of different sizes inside a large object (container) to maximize the occupied container volume while respecting the imposed constraints. Four methods are investigated and compared due to vertical cargo stability, in which three of these methods are proposed in this work and based on the equilibrium of rigid bodies, and the other one is based on the factor of support of boxes bottom faces. In the case of the factor of support, a set of constraints can be inserted totally in the integer formulation, while in the other methods cutting planes are inserted during optimization of the formulation by a branch-and-cut algorithm. Computational tests on instances from the literature show that the usage of a factor of support underestimates the value of the optimal solution. The computational tests showed that the use of the factor of support may underestimate the solution, but its use with integer linear programming models has the advantage that feasible solutions are stable, while the other developed methods only verify stability and thus they depend of the integer linear program to return feasible solutions more quickly. By the way, the methods for the cargo stability developed here also overcame the factor of support for tests involving different types of mesh to pack into the container. / Aplica-se um algoritmo baseado na resolução de modelos de programação linear inteira para o problema de carregamento de caixas dentro de um único contêiner considerando a restrição de estabilidade de carga. O problema em estudo consiste em arranjar itens (caixas) de diferentes tamanhos dentro de um objeto maior (contêiner), de maneira maximizar a ocupação do volume do contêiner enquanto respeita as restrições dadas. Quatro métodos são investigados e comparados quanto a estabilidade vertical do empacotamento, sendo que três deles são desenvolvidos neste trabalho e baseados em conceitos do equilíbrio de corpos rígidos, enquanto um deles é baseado no fator de suporte da base das caixas. No caso do fator de suporte, um conjunto de restrições pode ser inserido totalmente dentro da formulação inteira, enquanto nos demais métodos planos de corte são inseridos durante a resolução da formulação por um algoritmo branch-and-cut. Os testes computacionais mostraram que o uso do fator de suporte pode subestimar a solução, porém seu uso com modelos de programação linear inteira tem a vantagem das soluções viáveis poderem ser estáveis, enquanto os demais métodos desenvolvidos apenas verificam a estabilidade e, assim, dependem do programa linear inteiro retornar soluções viáveis mais rapidamente. Os métodos para a estabilidade de carga desenvolvidos neste trabalho mostraram-se superiores ao fator de suporte para testes envolvendo diferentes tipos de malhas para o empacotamento no contêiner.

O sequenciamento e a programação da produção trazem grandes benefícios financeiros às empresas se realizados de forma adequada. Atualmente, soluções generalizadas apresentam resultados aceitáveis, porém têm como consequência benefícios inferiores quando comparados a estudos específicos. O ramo da otimização de resultados possui dois tipos de soluções: as exatas para problemas de menores dimensões e não exatas, ou heurísticas, para problemas de médias e grandes dimensões. Este trabalho apresenta algoritmos exatos do tipo Branch & Bound e Modelos de Programação Linear Inteira Mista para solucionar quatro variações de problemas de scheduling: Fm|block|∑Cjm, Fm|block|∑Tj, Fm|block, Sijk|∑Cjm e Fm|block, Sijk|∑Tj. As abordagens utilizadas são inéditas na literatura e apresentaram resultados animadores para a maioria dos cenários. O limitante para o tempo total de fluxo obteve resposta ótima em 100% dos casos para problemas de até 20 tarefas e 4 máquinas em menos de uma hora. Para o tempo total de atraso, o limitante se mostrou mais eficiente quando os valores das due dates apresentam alta taxa de dispersão. Para os casos com setup, foram elaboradas três variações de limitantes para cada problema. O limitante com setup que apresentou o melhor desempenho foi o que obteve a melhor relação entre o seu valor numérico e seu custo computacional. Os modelos MILP solucionaram 100% dos problemas sem setup para até 20 tarefas e 4 máquinas e para os casos com setup, foram solucionados problemas de até 14 tarefas e 4 máquinas no tempo limite de uma hora. Os testes computacionais mostram a eficiência na redução do número de nós e, consequentemente, no tempo de execução. Portanto, o estudo realizado indica que, para problemas de pequeno porte e médio, os métodos em questão possuem grande potencial para aplicações práticas. / Job Sequence and Programming give benefits both financial and organizational to any company when performed properly. Nowadays, there is still a gap between theory and practice due to solutions that are short in specification. The analyzed problems differ in type and dimension thus modifying its complexity. The results optimization field is divided into two types of solution: the exact solution for minor problems and the non-exact solution for greater dimension problems. The present paper presents exact algorithms to solve the problems Fm|block|∑Cjm, Fm|block|∑Tj, Fm|block, Sijk|∑Cjm by the Branch & Bounds and Mixed Integer Linear Program models. The approaches are new and presented good results for most cases. Bounds for the no-setup total flow time scenario solved 100% of the 20 jobs and 4 machines cases. High dispersion range due dates contributed for the effectiveness of the no-setup total tardiness bound\'s effectiveness. Three different approaches were developed for the setup cases. The best approach aimed to optimize the value/effort factor for the B&B. The Mixed Integer Linear Program models solved 100% of the no-setup cases for 20 jobs and 4 machines. The MILPs setup cases solved optimally 14 jobs and 4 machines cases. Computational tests were executed and analyzed and they highlighted the node count reduction and, consequently, the execution time. The present study points out that the exact methods can be applied to small and medium scheduling problems in practice.

Sejam GI = (VI ,AI) e GM = (VM,AM) dois grafos simples. Um mapeamento de GI para GM é um conjunto de associações, tal que cada vértice de VI está associado a um vértice de VM, e cada aresta de AI está associada a um par de vértices de VM. A cada possível associação é atribuído um custo. O problema de correspondência inexata entre grafos (PCIG) consiste em encontrar um mapeamento de GI para GM, tal que a soma dos custos de suas associações seja mínima. Nesta dissertação, resumimos os resultados encontrados na literatura sobre o PCIG e algumas de suas variações. Os resultados que incluímos aqui tratam sobre a questão de como formular o PCIG e algumas de suas variações, através de programação linear inteira. Provamos alguns resultados de complexidade computacional que relacionam variações do PCIG a problemas clássicos, como isomorfismo e partição de grafos. Fornecemos uma formulação através de programação linear inteira para o PCCA (uma variante do PCIG com conexidade e cobertura de arestas). Mostramos que o PCCA é NP-difícil quando os grafos de entrada são completos ou árvores (chamamos o segundo caso de PCCA para árvores). Apresentamos uma formulação linear inteira e um algoritmo - que é polinomial se o grau máximo dos vértices de VM for limitado por uma constante - para o PCCA para árvores. Mostramos um caso especia em que o PCCA para árvores pode ser resolvido em tempo polinomial. Por último, exibimos alguns resultados experimentais, inclusive com instâncias reais de uma aplicação do problema. / Let GI = (VI ,AI) and GM = (VM,AM) be two simple graphs. A mapping from GI to GM is an association set, such that each vertex in VI is associated to a vertex in VM, and each edge in AI is associated to a pair of vertices of VM. A cost is defined to each possible association. The inexact graph correspondence problem (IGCP) consists in finding a mapping from GI to GM, such that the sum of its associations costs is minimized. In this dissertation, we summarize the results found in the literature about the IGCP and some variations. The results included here address the question of how to formulate the IGCP and some variations, using integer linear programming. We prove some computational complexity results which relate IGCP variations with classical problems, like graph isomorphism and partitioning. We give an integer linear programming formulation to the ICEC (IGCP with connectivity and edges cover). We show that the ICEC is NP-hard when the input graphs are complete or trees (we call the second case ICEC for trees). We introduce an integer linear formulation and an algorithm - which has polynomial running time if the vertices of VM have maximum degree bounded by a constant - to the ICEC for trees. We show a especial case in which the ICEC for trees can be solved in polynomial time. Finally, we present some experimental results, also with instances of a real application of the problem.

Orientador: Francisco de Assis Magalhães Gomes Neto / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T19:03:25Z (GMT). No. of bitstreams: 1 Villela_PedroFerraz_D.pdf: 10794575 bytes, checksum: 746b8aebf0db423d557d9c5fe1446592 (MD5) Previous issue date: 2014 / Resumo: Neste trabalho, propomos um método exato para obter o conjunto solução de um problema biobjetivo quadrático de otimização de carteiras de investimento, que envolve variáveis binárias. Nosso algoritmo é baseado na junção de três algoritmos específicos. O primeiro encontra uma curva associada ao conjunto solução de problemas biobjetivo contínuos por meio de um método de restrições ativas, o segundo encontra o ótimo de um problema de programação quadrática inteira mista pelo método Branch-and-Bound, e o terceiro encontra a interseção de duas curvas associadas a problemas biobjetivo distintos. Ao longo do texto, algumas heurísticas e métodos adicionais também são introduzidos, com o propósito de acelerar a convergência do algoritmo proposto. Além disso, o nosso método pode ser visto como uma nova contribuição na área, pois ele determina, de forma exata, a curva associada ao conjunto solução do problemas biobjetivo inteiro misto, algo que é incomum na literatura, pois o problema alvo geralmente é abordado via métodos meta-heurísticos. Ademais, ele mostrou ser eficiente do ponto de vista do tempo computacional, pois encontra o conjunto solução do problema em poucos segundos / Abstract: In this work, we propose an exact method to find the solution set of a mixed quadratic bi-objective portfolio optimization problem. Our method is based on the combination of three specific algorithms. The first one obtains a curve associated with the solution set of a continuous bi-objective problem through an active set algorithm, the second one solves a mixed quadratic optimization problem through the Branch-and-Bound method, and the third one searches the intersection of two curves associated with distinct bi-objective problems. Throughout the text, some heuristics are also introduced in order to accelerate the performance of the method. Moreover, our method can be seen as a new contribution to the field, since it finds, in an exact way, the curve related to the solution set of the mixed integer bi-objective problem, something uncommon in the corresponding literature, where the target problem is usually approached by metaheuristic methods. Additionally, it has also shown to be efficient in terms of running time, being capable of finding the problem's solution set within a much faster time frame / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

L'étude des phases de la matière est d'un intérêt fondamental en physique. La théorie de Landau, qui est le "modèle standard" des transitions de phases, caractérise les phases de la matière en termes des brisures de symétrie, décrites par un paramètre d'ordre local. Cette théorie a permis la description de phénomènes remarquables tels que la condensation de Bose-Einstein, la supraconductivité et la superfluidité.<p><p>Il existe cependant des phases qui échappent à la description de Landau. Il s'agit des phases quantiques topologiques. Celles-ci constituent un nouveau paradigme et sont caractérisées par un ordre global défini par un invariant topologique. Ce dernier classe les objets ou systèmes de la manière suivante: deux objets appartiennent à la même classe topologique s'il est possible de déformer continument le premier objet en le second. Cette propriété globale rend le système robuste contre des perturbations locales telles que le désordre. <p><p>Les atomes froids constituent une plateforme idéale pour simuler les phases quantiques topologiques. Depuis l'invention du laser, les progrès en physique atomique et moléculaire ont permis un contrôle de la dynamique et des états internes des atomes. La réalisation de gaz quantiques,tels que les condensats de Bose-Einstein et les gaz dégénérés de Fermi, ainsi que la réalisation de réseaux optiques à l'aide de faisceaux lasers, permettent d'étudier ces nouvelles phases de la matière et de simuler aussi la physique du solide cristallin.<p><p>Dans cette thèse, nous nous concentrons sur l'etude d'isolants topologiques avec des atomes froids. Ces derniers sont isolants de volume mais possèdent des états de surface qui sont conducteurs, protégés par un invariant topologique. Nous traitons trois sujets principaux. Le premier sujet concerne la génération dynamique d'un isolant topologique de Mott. Ici, les interactions engendrent l'isolant topologique et ce, sans champ de jauge de fond. Le second sujet concerne la détection des isolants topologiques dans les expériences d'atomes froids. Nous proposons deux méthodes complémentaires pour caractériser celles-ci. Finalement, le troisième sujet aborde des thèmes au-delà de la définition standard d'isolant topologique. Nous avons d'une part proposé un algorithme efficace pour calculer la conductivité de Berry, la contribution topologique à la conductivité transverse lorsque l'énergie de Fermi se trouve dans une bande d'énergie. D'autre part, nous avons utilisé des méthodes pour caractériser les propriétés quantiques topologiques de systèmes non-périodiques.<p><p>L'étude des isolants topologiques dans les expériences d'atomes froids est un sujet de recherche récent et en pleine expansion. Dans ce contexte, cette thèse apporte plusieurs contributions théoriques pour la simulation de systèmes quantiques sur réseau avec des atomes froids. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

There are many real cases where a company needs to determine the price of its products so as to maximise its revenue or profit.<p>To do so, the company must consider customers' reactions to these prices, as they may refuse to buy a given product or service if its price is too high. This is commonly known in literature as a pricing problem.<p>This class of problems, which is typically bilevel, was first studied in the 1990s and is NP-hard, although polynomial algorithms do exist for some particular cases. Many questions are still open on this subject.<p><p>The aim of this thesis is to investigate mathematical properties of pricing problems, in order to find structural properties, formulations and solution methods that are as efficient as possible. In particular, we focus our attention on pricing problems over a network. In this framework, an authority owns a subset of arcs and imposes tolls on them, in an attempt to maximise his/her revenue, while users travel on the network, seeking for their minimum cost path.<p><p>First, we provide a detailed review of the state of the art on bilevel pricing problems. <p>Then, we consider a particular case where the authority is using an unit toll scheme on his/her subset of arcs, imposing either the same toll on all of them, or a toll proportional to a given parameter particular to each arc (for instance a per kilometre toll). We show that if tolls are all equal then the complexity of the problem is polynomial, whereas in case of proportional tolls it is pseudo-polynomial.<p>We then address a robust approach taking into account uncertainty on parameters. We solve some polynomial cases of the pricing problem where uncertainty is considered using an interval representation.<p><p>Finally, we focus on another particular case where toll arcs are connected such that they constitute a path, as occurs on highways. We develop a Dantzig-Wolfe reformulation and present a Branch-and-Cut-and-Price algorithm to solve it. Several improvements are proposed, both for the column generation algorithm used to solve the linear relaxation and for the branching part used to find integer solutions. Numerical results are also presented to highlight the efficiency of the proposed strategies. This problem is proved to be APX-hard and a theoretical comparison between our model and another one from the literature is carried out. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished