Développement d’un algorithme de branch-and-price-and-cut pour le problème de conception de réseau avec coûts fixes et capacités

De nombreux problèmes en transport et en logistique peuvent être formulés comme des modèles de conception de réseau. Ils requièrent généralement de transporter des produits, des passagers ou encore des données dans un réseau afin de satisfaire une certaine demande tout en minimisant les coûts. Dans ce mémoire, nous nous intéressons au problème de conception de réseau avec coûts fixes et capacités. Ce problème consiste à ouvrir un sous-ensemble des liens dans un réseau afin de satisfaire la demande, tout en respectant les contraintes de capacités sur les liens. L'objectif est de minimiser les coûts fixes associés à l'ouverture des liens et les coûts de transport des produits. Nous présentons une méthode exacte pour résoudre ce problème basée sur des techniques utilisées en programmation linéaire en nombres entiers. Notre méthode est une variante de l'algorithme de branch-and-bound, appelée branch-and-price-and-cut, dans laquelle nous exploitons à la fois la génération de colonnes et de coupes pour la résolution d'instances de grande taille, en particulier, celles ayant un grand nombre de produits. En nous comparant à CPLEX, actuellement l'un des meilleurs logiciels d'optimisation mathématique, notre méthode est compétitive sur les instances de taille moyenne et supérieure sur les instances de grande taille ayant un grand nombre de produits, et ce, même si elle n'utilise qu'un seul type d'inégalités valides.

L'algorithme de Branch and Price and Cut pour le problème de conception de réseaux avec coûts fixes et sans capacité

Le problème de conception de réseaux est un problème qui a été beaucoup étudié dans le domaine de la recherche opérationnelle pour ses caractéristiques, et ses applications dans des nombreux domaines tels que le transport, les communications, et la logistique. Nous nous intéressons en particulier dans ce mémoire à résoudre le problème de conception de réseaux avec coûts fixes et sans capacité, en satisfaisant les demandes de tous les produits tout en minimisant la somme des coûts de transport de ces produits et des coûts fixes de conception du réseau. Ce problème se modélise généralement sous la forme d’un programme linéaire en nombres entiers incluant des variables continues. Pour le résoudre, nous avons appliqué la méthode exacte de Branch-and-Bound basée sur une relaxation linéaire du problème avec un critère d’arrêt, tout en exploitant les méthodes de génération de colonnes et de génération de coupes. Nous avons testé la méthode de Branch-and-Price-and-Cut sur 156 instances divisées en cinq groupes de différentes tailles, et nous l’avons comparée à Cplex, l’un des meilleurs solveurs d’optimisation mathématique, ainsi qu’à la méthode de Branch-and- Cut. Notre méthode est compétitive et plus performante sur les instances de grande taille ayant un grand nombre de produits.

Algorithme de branch-and-price-and-cut pour le problème de conception de réseaux avec coûts fixes, capacités et un seul produit

De nombreux problèmes liés aux domaines du transport, des télécommunications et de la logistique peuvent être modélisés comme des problèmes de conception de réseaux. Le problème classique consiste à transporter un flot (données, personnes, produits, etc.) sur un réseau sous un certain nombre de contraintes dans le but de satisfaire la demande, tout en minimisant les coûts. Dans ce mémoire, on se propose d'étudier le problème de conception de réseaux avec coûts fixes, capacités et un seul produit, qu'on transforme en un problème équivalent à plusieurs produits de façon à améliorer la valeur de la borne inférieure provenant de la relaxation continue du modèle. La méthode que nous présentons pour la résolution de ce problème est une méthode exacte de branch-and-price-and-cut avec une condition d'arrêt, dans laquelle nous exploitons à la fois la méthode de génération de colonnes, la méthode de génération de coupes et l'algorithme de branch-and-bound. Ces méthodes figurent parmi les techniques les plus utilisées en programmation linéaire en nombres entiers. Nous testons notre méthode sur deux groupes d'instances de tailles différentes (gran-des et très grandes), et nous la comparons avec les résultats donnés par CPLEX, un des meilleurs logiciels permettant de résoudre des problèmes d'optimisation mathématique, ainsi qu’avec une méthode de branch-and-cut. Il s'est avéré que notre méthode est prometteuse et peut donner de bons résultats, en particulier pour les instances de très grandes tailles.

Algorithme de branch-and-price-and-cut pour le problème de conception de réseaux avec coûts fixes, capacités et un seul produit

De nombreux problèmes liés aux domaines du transport, des télécommunications et de la logistique peuvent être modélisés comme des problèmes de conception de réseaux. Le problème classique consiste à transporter un flot (données, personnes, produits, etc.) sur un réseau sous un certain nombre de contraintes dans le but de satisfaire la demande, tout en minimisant les coûts. Dans ce mémoire, on se propose d'étudier le problème de conception de réseaux avec coûts fixes, capacités et un seul produit, qu'on transforme en un problème équivalent à plusieurs produits de façon à améliorer la valeur de la borne inférieure provenant de la relaxation continue du modèle. La méthode que nous présentons pour la résolution de ce problème est une méthode exacte de branch-and-price-and-cut avec une condition d'arrêt, dans laquelle nous exploitons à la fois la méthode de génération de colonnes, la méthode de génération de coupes et l'algorithme de branch-and-bound. Ces méthodes figurent parmi les techniques les plus utilisées en programmation linéaire en nombres entiers. Nous testons notre méthode sur deux groupes d'instances de tailles différentes (gran-des et très grandes), et nous la comparons avec les résultats donnés par CPLEX, un des meilleurs logiciels permettant de résoudre des problèmes d'optimisation mathématique, ainsi qu’avec une méthode de branch-and-cut. Il s'est avéré que notre méthode est prometteuse et peut donner de bons résultats, en particulier pour les instances de très grandes tailles.

Méthode de génération de colonnes pour les problèmes de conception de réseaux avec coûts d’ajout de capacité

Les problèmes de conception de réseaux ont reçu un intérêt particulier et ont été largement étudiés de par leurs nombreuses applications dans différents domaines, tels que les transports et les télécommunications. Nous nous intéressons dans ce mémoire au problème de conception de réseaux avec coûts d’ajout de capacité. Il s’agit d’installer un ensemble d’équipements sur un réseau en vue de satisfaire la demande, tout en respectant les contraintes de capacité, chaque arc pouvant admettre plusieurs équipements. L’objectif est de minimiser les coûts variables de transport des produits et les coûts fixes d’installation ou d’augmentation de capacité des équipements. La méthode que nous envisageons pour résoudre ce problème est basée sur les techniques utilisées en programmation linéaire en nombres entiers, notamment celles de génération de colonnes et de coupes. Ces méthodes sont introduites dans un algorithme général de branch-and-bound basé sur la relaxation linéaire. Nous avons testé notre méthode sur quatre groupes d’instances de tailles différentes, et nous l’avons comparée à CPLEX, qui constitue un des meilleurs solveurs permettant de résoudre des problèmes d’optimisation, ainsi qu’à une méthode existante dans la littérature combinant des méthodes exactes et heuristiques. Notre méthode a été plus performante que ces deux méthodes, notamment pour les instances de très grandes tailles.

Essays in International Trade

Dans ma thèse doctorale, j'étudie trois facteurs importants qui caractérisent le commerce international : les différences technologiques entre les pays, les barrières à l'entrée sous la forme de coûts fixes et la migration internationale. Le premier chapitre analyse si les différences technologiques entre les pays peuvent expliquer la spécialisation dans le commerce international entre les pays. Pour mesurer le niveau de la spécialisation, je calcule les index de concentration pour la valeur des importations et des exportations et décompose la concentration totale dans la marge de produits extensive (nombre de produits commercialisés) et la marge de produits intensive (volume de produits commercialisés). En utilisant des données commerciales détaillées au niveau du produit dans 160 pays, mes résultats montrent que les exportations sont plus concentrées que les importations, que la spécialisation se produit principalement au niveau de la marge intensive du produit, et que les économies plus grandes disposent d'importations et d'exportations plus diversifiées, car elles commercialisent plus de produits. Compte tenu de ces faits, j'évalue la capacité du modèle Eaton-Kortum, le principal modèle de la théorie ricardienne du commerce, pour représenter les preuves empiriques. Les résultats montrent que la spécialisation à travers l'avantage comparatif induit par les différences de technologie peut expliquer les faits qualitatifs et quantitatifs. De plus, j'évalue le rôle des déterminants clés de la spécialisation : le degré de l'avantage comparatif, l'élasticité de la substitution et la géographie. Une implication de ces résultats est qu'il est important d’évaluer jusqu'à quel point la volatilité de production mesurée par la volatilité du PIB est motivée par la spécialisation des exportations et des importations. Étant donné le compromis entre l'ouverture du commerce et la volatilité de production, les bénéfices tirés du commerce peuvent s'avérer plus faibles que ceux estimés précédemment. Par conséquent, les politiques commerciales alternatives telles que l'ouverture graduelle au commerce combinée à la diversification de la production pour réduire la concentration de l'exportation peuvent se révéler être une meilleure stratégie que l'approche du laissez-faire. En utilisant la relation entre la taille du marché et l’entrée de firmes et produits, le deuxième chapitre évalue si les barrières à l'entrée sous la forme de coûts fixes à exporter sont au niveau de la firme ou au niveau du produit. Si les coûts fixes se trouvent au niveau de la firme, la firme multiproduits a un avantage de coût de production par rapport aux autres firmes parce qu’elles peuvent diviser les coûts fixes sur plusieurs produits. Dans ce cas, le commerce international sera caractérisé par peu de firmes qui exportent beaucoup des produits. Si les coûts fixes sont au niveau du produit, l’entrée d’un produit est associée avec l’entrée de plusieurs firmes. La raison est qu’une fois que la première firme entre et paye les coûts fixes du produit, elle crée un effet d’entrainement qui réduit les coûts fixes pour des firmes rivales. Dans ce cas, le commerce international sera caractérisé par plusieurs firmes qui vendent des variétés différentes du même produit. En utilisant des données détaillées provenant de 40 pays exportateurs à travers 180 marchés de destination, mes résultats montrent que les barrières à l'entrée se trouvent principalement au niveau du produit. Un marché plus large favorise l'expansion d'un plus grand nombre d’entreprises au sein d'une catégorie de produit plutôt que de permettre aux entreprises produisant plusieurs produits de croître dans une gamme de produits. En regardant la différence entre le nombre d'exportateurs au sein d'une catégorie de produit dans des destinations données, je trouve que le taux d'entrée de firmes augmente significativement après qu'un produit entre la première fois dans le marché. J'en déduis donc que le premier entrant réduit les coûts fixes pour les firmes suivantes. Mes recherches démontrent également que malgré une plus grande compétition sur le marché du produit, les entreprises disposent de revenus d'exportation supérieurs et sont plus susceptibles de rester sur les marchés internationaux. Ces résultats sont cohérents avec l’hypothèse que l’effet d’entrainement incite l'entrée de firmes rivales et permettent aux entreprises de produire à plus grande échelle. Cette recherche dévoile un nombre de conclusions importantes. D'abord, les politiques commerciales encouragent l'entrée de nouveaux produits, par exemple, en promouvant des produits dans les marchés de destination entraînant ainsi des retombées qui se traduiront par un taux de participation plus élevé de l'entreprise et une croissance de l'exportation. Deuxièmement, les consommateurs du pays importateur peuvent bénéficier de prix plus bas pour le produit en réduisant les barrières techniques du commerce. Troisièmement, lorsque l'on effectue des expérimentations politiques sous la forme de réduction des coûts commerciaux, il est de coutume de considérer uniquement une baisse des coûts marginaux et d'évaluer les répercussions sur le bien-être du consommateur. Cependant, un élément important des accords commerciaux est la réduction des barrières techniques au commerce grâce à la négociation de normes communes pour un produit. Négliger l'existence des barrières à l'entrée et les conséquences des réaffectations de l'industrie affaiblit l'impact des réformes commerciales. Le troisième chapitre prend en compte le rôle de l'information dans la facilitation du commerce international. Les immigrants réduisent les coûts de transaction dans le commerce international en fournissant des informations sur les possibilités d'échange avec leur pays d'origine. En utilisant des données géographiques détaillées sur l'immigration et les importations aux États-Unis entre 1970 et 2005, je quantifie l'incidence qu'ont les nouveaux immigrants sur la demande pour les importations de biens intermédiaires aux États-Unis. Pour établir le lien cause à effet entre le commerce et la migration, j’exploite l'important afflux d'immigrants d'Amérique centrale après l'ouragan Mitch. Les résultats montrent que l'augmentation de dix pour cent d'immigrants a fait croître la demande pour les importations de biens intermédiaires de 1,5 pour cent. Mes résultats sont robustes aux problèmes de la causalité inverse ou la décision d’émigrer est causée par des opportunités de faire du commerce.

Les économies de taille en production laitière en Amérique du Nord

Après une période où la valeur des quotas laitiers a été en forte croissance au Québec, un plafond à cette valeur a été fixé à compter de 2007. Ce plafond a eu pour effet de limiter l’offre de quota sur le marché et la croissance de la taille des entreprises laitières québécoises. Cette situation soulève un questionnement sur l’efficience économique, le blocage de la croissance des entreprises les empêchant de bénéficier d’économies de taille, si bien entendu il en existe. En conséquence, cette étude s’intéresse aux économies de taille en production laitière en Amérique du Nord. Les économies de taille des entreprises ont été mesurées à l’aide d’une régression linéaire multiple à partir de certains indicateurs de coût monétaire et non monétaire. Cette analyse comprend quatre strates de taille formées à partir d’un échantillon non aléatoire de 847 entreprises du Québec, de l’État de New York et de la Californie, ainsi qu’à partir d’un groupe d’entreprises efficientes (groupe de tête). Les résultats démontrent l’existence d’économies de taille principalement au niveau des coûts fixes et plus particulièrement des coûts fixes non monétaires. Ils révèlent aussi que les deux indicateurs où l’effet des économies de taille est le plus important sont le coût du travail non rémunéré et l’amortissement. Par ailleurs, lorsque la taille d’une entreprise augmente, les économies de taille supplémentaires réalisées deviennent de moins en moins importantes. Enfin, les résultats indiquent qu’il existe des déséconomies de taille au niveau des coûts d’alimentation. Les résultats obtenus au niveau du groupe de tête vont dans le même sens. Ils confirment également qu’il est possible pour les grandes entreprises efficientes de réaliser des économies de taille pour la plupart des indicateurs de coût. Toutefois, les économies additionnelles que ces entreprises peuvent réaliser sont moins importantes que celles obtenues par les petites entreprises efficientes. Mots clés : Agriculture, production laitière, Amérique du Nord, économies de taille, efficience économique, régression linéaire.

Cooperation using a robotic ad hoc network made from Bluetooth, JXTA, OSGi and other commercial off the shelf (COTS) products

Abstract - Mobile devices in the near future will need to collaborate to fulfill their function. Collaboration will be done by communication. We use a real world example of robotic soccer to come up with the necessary structures required for robotic communication. A review of related work is done and it is found no examples come close to providing a RANET. The robotic ad hoc network (RANET) we suggest uses existing structures pulled from the areas of wireless networks, peer to peer and software life-cycle management. Gaps are found in the existing structures so we describe how to extend some structures to satisfy the design. The RANET design supports robot cooperation by exchanging messages, discovering needed skills that other robots on the network may possess and the transfer of these skills. The network is built on top of a Bluetooth wireless network and uses JXTA to communicate and transfer skills. OSGi bundles form the skills that can be transferred. To test the nal design a reference implementation is done. Deficiencies in some third party software is found, specifically JXTA and JamVM and GNU Classpath. Lastly we look at how to fix the deciencies by porting the JXTA C implementation to the target robotic platform and potentially eliminating the TCP/IP layer, using UDP instead of TCP or using an adaptive TCP/IP stack. We also propose a future areas of investigation; how to seed the configuration for the Personal area network (PAN) Bluetooth protocol extension so a Bluetooth TCP/IP link is more quickly formed and using the STP to allow multi-hop messaging and transfer of skills.

A condition monitoring platform using COTS wireless sensor networks - Lessons and experience

Developments in Micro-Electro-Mechanical Systems (MEMS), wireless communication systems and ad-hoc networking have created new dimensions to improve asset management not only during the operational phase but throughout an asset's lifecycle based on using improved quality of information obtained with respect to two key aspects of an asset: its location and condition. In this paper, we present our experience as well as lessons learnt from building a prototype condition monitoring platform to demonstrate and to evaluate the use of COTS wireless sensor networks to develop a prototype condition monitoring platform with the aim of improving asset management by providing accurate and real-time information. © 2010 IEEE.

A study of user requirements for COTS: computer off the shelf software solutions

[This abstract is based on the authors' abstract.]Three new standards to be applied when adopting commercial computer off-the-shelf (COTS) software solutions are discussed. The first standard is for a COTS software life cycle, the second for a software solution user requirements life cycle, and the third is a checklist to help in completing the requirements. The standards are based on recent major COTS software solution implementations.

WCET analysis considering contention on memory bus in COTS-based multicores

The usage of COTS-based multicores is becoming widespread in the field of embedded systems. Providing realtime guarantees at design-time is a pre-requisite to deploy real-time systems on these multicores. This necessitates the consideration of the impact of the contention due to shared low-level hardware resources on the Worst-Case Execution Time (WCET) of the tasks. As a step towards this aim, this paper first identifies the different factors that make the WCET analysis a challenging problem in a typical COTS-based multicore system. Then, we propose and prove, a mathematically correct method to determine tight upper bounds on the WCET of the tasks, when they are co-scheduled on different cores.

Response time analysis of COTS-Based multicores considering the contention on the shared memory bus

The current industry trend is towards using Commercially available Off-The-Shelf (COTS) based multicores for developing real time embedded systems, as opposed to the usage of custom-made hardware. In typical implementation of such COTS-based multicores, multiple cores access the main memory via a shared bus. This often leads to contention on this shared channel, which results in an increase of the response time of the tasks. Analyzing this increased response time, considering the contention on the shared bus, is challenging on COTS-based systems mainly because bus arbitration protocols are often undocumented and the exact instants at which the shared bus is accessed by tasks are not explicitly controlled by the operating system scheduler; they are instead a result of cache misses. This paper makes three contributions towards analyzing tasks scheduled on COTS-based multicores. Firstly, we describe a method to model the memory access patterns of a task. Secondly, we apply this model to analyze the worst case response time for a set of tasks. Although the required parameters to obtain the request profile can be obtained by static analysis, we provide an alternative method to experimentally obtain them by using performance monitoring counters (PMCs). We also compare our work against an existing approach and show that our approach outperforms it by providing tighter upper-bound on the number of bus requests generated by a task.

Finding an upper bound on the increase in execution time due to contention on the memory bus in COTS-based multicore systems

Contention on the memory bus in COTS based multicore systems is becoming a major determining factor of the execution time of a task. Analyzing this extra execution time is non-trivial because (i) bus arbitration protocols in such systems are often undocumented and (ii) the times when the memory bus is requested to be used are not explicitly controlled by the operating system scheduler; they are instead a result of cache misses. We present a method for finding an upper bound on the extra execution time of a task due to contention on the memory bus in COTS based multicore systems. This method makes no assumptions on the bus arbitration protocol (other than assuming that it is work-conserving).