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.

A study of the polycomb group complexes in the maintenance of heterochromatic genome stability and Alzheimer's disease.

La démence d'Alzheimer est une maladie neurodégénérative caractérisée par une perte progressive et irreversible des fonctions cognitives et des compétences intellectuelles. La maladie d’Alzheimer se présente sous deux formes: la forme familiale ou précoce (EOAD) qui représente 5% des cas et elle est liée à des mutations génétiques affectant le métabolisme des peptides amyloïde; et la forme tardive ou sporadique (LOAD) qui représente 95% des cas mais son étiologie est encore mal définie. Cependant, le vieillissement reste le principal facteur de risque pour développer LOAD. Les changements épigénétiques impliquant des modifications des histones jouent un rôle crucial dans les maladies neurodégénératives et le vieillissement lié à l'âge. Des données récentes ont décrit LOAD comme un désordre de l'épigénome et ont associé ce trouble à l'instabilité génomique. Les protéines Polycomb sont des modificateurs épigénétiques qui induisent le remodelage de la chromatine et la répression des gènes à l'hétérochromatine facultative. Nous rapportons que les souris hétérozygotes pour une protéine Polycomb développent avec l'âge un trouble neurologique ressemblant à LOAD caractérisé par l’altération des fonctions cognitives, la phosphorylation de la protéine tau, l'accumulation des peptides amyloïde, et le dysfonctionnement synaptique. Ce phénotype pathologique est précédé par la décondensation de l’hétérochromatine neuronale et l'activation de la réponse aux dommages à l'ADN. Parallèlement, une réduction d’expression de polycomb, malformations de l'hétérochromatine neuronale, et l'accumulation de dommages à l'ADN étaient également présents dans les cerveaux de patients LOAD. Remarquablement, les dommages de l'ADN ne sont pas distribués de façon aléatoire sur le génome mais sont enrichis au niveau des séquences répétitives. Les conclusions présentées dans cette thèse ont identifié des modifications épigénétiques spécifiques qui conduisent à une instabilité génomique aberrante menant à la formation de LOAD. Ces résultats vont aider au développement de nouveaux traitements qui peuvent potentiellement ralentir la neurodégénérescence.

Genetic studies on the role of type IA DNA topoisomerases in DNA metabolism and genome maintenance in Escherichia coli

Le surenroulement de l’ADN est important pour tous les processus cellulaires qui requièrent la séparation des brins de l’ADN. Il est régulé par l’activité enzymatique des topoisomérases. La gyrase (gyrA et gyrB) utilise l’ATP pour introduire des supertours négatifs dans l’ADN, alors que la topoisomérase I (topA) et la topoisomérase IV (parC et parE) les éliminent. Les cellules déficientes pour la topoisomérase I sont viables si elles ont des mutations compensatoires dans un des gènes codant pour une sous-unité de la gyrase. Ces mutations réduisent le niveau de surenroulement négatif du chromosome et permettent la croissance bactérienne. Une de ces mutations engendre la production d'une gyrase thermosensible. L’activité de surenroulement de la gyrase en absence de la topoisomérase I cause l’accumulation d’ADN hyper-surenroulé négativement à cause de la formation de R-loops. La surproduction de la RNase HI (rnhA), une enzyme qui dégrade l’ARN des R-loops, permet de prévenir l’accumulation d’un excès de surenroulement négatif. En absence de RNase HI, des R-loops sont aussi formés et peuvent être utilisés pour déclencher la réplication de l’ADN indépendamment du système normal oriC/DnaA, un phénomène connu sous le nom de « constitutive stable DNA replication » (cSDR). Pour mieux comprendre le lien entre la formation de R-loops et l’excès de surenroulement négatif, nous avons construit un mutant conditionnel topA rnhA gyrB(Ts) avec l’expression inductible de la RNase HI à partir d’un plasmide. Nous avons trouvé que l’ADN des cellules de ce mutant était excessivement relâché au lieu d'être hypersurenroulé négativement en conditions de pénurie de RNase HI. La relaxation de l’ADN a été montrée comme étant indépendante de l'activité de la topoisomérase IV. Les cellules du triple mutant topA rnhA gyrB(Ts) forment de très longs filaments remplis d’ADN, montrant ainsi un défaut de ségrégation des chromosomes. La surproduction de la topoisomérase III (topB), une enzyme qui peut effectuer la décaténation de l’ADN, a corrigé les problèmes de ségrégation sans toutefois restaurer le niveau de surenroulement de l’ADN. Nous avons constaté que des extraits protéiques du mutant topA rnhA gyrB(Ts) pouvaient inhiber l’activité de surenroulement négatif de la gyrase dans des extraits d’une souche sauvage, suggérant ainsi que la pénurie de RNase HI avait déclenché une réponse cellulaire d’inhibition de cette activité de la gyrase. De plus, des expériences in vivo et in vitro ont montré qu’en absence de RNase HI, l’activité ATP-dépendante de surenroulement négatif de la gyrase était inhibée, alors que l’activité ATP-indépendante de cette enzyme demeurait intacte. Des suppresseurs extragéniques du défaut de croissance du triple mutant topA rnhA gyrB(Ts) qui corrigent également les problèmes de surenroulement et de ségrégation des chromosomes ont pour la plupart été cartographiés dans des gènes impliqués dans la réplication de l’ADN, le métabolisme des R-loops, ou la formation de fimbriae. La deuxième partie de ce projet avait pour but de comprendre les rôles des topoisomérases de type IA (topoisomérase I et topoisomérase III) dans la ségrégation et la stabilité du génome de Escherichia coli. Pour étudier ces rôles, nous avons utilisé des approches de génétique combinées avec la cytométrie en flux, l’analyse de type Western blot et la microscopie. Nous avons constaté que le phénotype Par- et les défauts de ségrégation des chromosomes d’un mutant gyrB(Ts) avaient été corrigés en inactivant topA, mais uniquement en présence du gène topB. En outre, nous avons démontré que la surproduction de la topoisomérase III pouvait corriger le phénotype Par- du mutant gyrB(Ts) sans toutefois corriger les défauts de croissance de ce dernier. La surproduction de topoisomérase IV, enzyme responsable de la décaténation des chromosomes chez E. coli, ne pouvait pas remplacer la topoisomérase III. Nos résultats suggèrent que les topoisomérases de type IA jouent un rôle important dans la ségrégation des chromosomes lorsque la gyrase est inefficace. Pour étudier le rôle des topoisomérases de type IA dans la stabilité du génome, la troisième partie du projet, nous avons utilisé des approches génétiques combinées avec des tests de « spot » et la microscopie. Nous avons constaté que les cellules déficientes en topoisomérase I avaient des défauts de ségrégation de chromosomes et de croissance liés à un excès de surenroulement négatif, et que ces défauts pouvaient être corrigés en inactivant recQ, recA ou par la surproduction de la topoisomérase III. Le suppresseur extragénique oriC15::aph isolé dans la première partie du projet pouvait également corriger ces problèmes. Les cellules déficientes en topoisomérases de type IA formaient des très longs filaments remplis d’ADN d’apparence diffuse et réparti inégalement dans la cellule. Ces phénotypes pouvaient être partiellement corrigés par la surproduction de la RNase HI ou en inactivant recA, ou encore par des suppresseurs isolés dans la première partie du projet et impliques dans le cSDR (dnaT18::aph et rne59::aph). Donc, dans E. coli, les topoisomérases de type IA jouent un rôle dans la stabilité du génome en inhibant la réplication inappropriée à partir de oriC et de R-loops, et en empêchant les défauts de ségrégation liés à la recombinaison RecA-dépendante, par leur action avec RecQ. Les travaux rapportés ici révèlent que la réplication inappropriée et dérégulée est une source majeure de l’instabilité génomique. Empêcher la réplication inappropriée permet la ségrégation des chromosomes et le maintien d’un génome stable. La RNase HI et les topoisomérases de type IA jouent un rôle majeur dans la prévention de la réplication inappropriée. La RNase HI réalise cette tâche en modulant l’activité de surenroulement ATP-dependante de la gyrase, et en empêchant la réplication à partir des R-loops. Les topoisomérases de type IA assurent le maintien de la stabilité du génome en empêchant la réplication inappropriée à partir de oriC et des R-loops et en agissant avec RecQ pour résoudre des intermédiaires de recombinaison RecA-dépendants afin de permettre la ségrégation des chromosomes.

Essays on oil price fluctuations and macroeconomic activity

Dans cette thèse, je me suis intéressé aux effets des fluctuations du prix de pétrole sur l'activité macroéconomique selon la cause sous-jacente ces fluctuations. Les modèles économiques utilisés dans cette thèse sont principalement les modèles d'équilibre général dynamique stochastique (de l'anglais Dynamic Stochastic General Equilibrium, DSGE) et les modèles Vecteurs Autorégressifs, VAR. Plusieurs études ont examiné les effets des fluctuations du prix de pétrole sur les principaux variables macroéconomiques, mais très peu d'entre elles ont fait spécifiquement le lien entre les effets des fluctuations du prix du pétrole et la l'origine de ces fluctuations. Pourtant, il est largement admis dans les études plus récentes que les augmentations du prix du pétrole peuvent avoir des effets très différents en fonction de la cause sous-jacente de cette augmentation. Ma thèse, structurée en trois chapitres, porte une attention particulière aux sources de fluctuations du prix de pétrole et leurs impacts sur l'activité macroéconomique en général, et en particulier sur l'économie du Canada. Le premier chapitre examine comment les chocs d'offre de pétrole, de demande agrégée, et de demande de précaution de pétrole affectent l'économie du Canada, dans un Modèle d'équilibre Général Dynamique Stochastique estimé. L'estimation est réalisée par la méthode Bayésienne, en utilisant des données trimestrielles canadiennes sur la période 1983Q1 à 2010Q4. Les résultats montrent que les effets dynamiques des fluctuations du prix du pétrole sur les principaux agrégats macro-économiques canadiens varient en fonction de leurs sources. En particulier, une augmentation de 10% du prix réel du pétrole causée par des chocs positifs sur la demande globale étrangère a un effet positif significatif de l'ordre de 0,4% sur le PIB réel du Canada au moment de l'impact et l'effet reste positif sur tous les horizons. En revanche, une augmentation du prix réel du pétrole causée par des chocs négatifs sur l'offre de pétrole ou par des chocs positifs de la demande de pétrole de précaution a un effet négligeable sur le PIB réel du Canada au moment de l'impact, mais provoque une baisse légèrement significative après l'impact. En outre, parmi les chocs pétroliers identifiés, les chocs sur la demande globale étrangère ont été relativement plus important pour expliquer la fluctuation des principaux agrégats macroéconomiques du Canada au cours de la période d'estimation. Le deuxième chapitre utilise un modèle Structurel VAR en Panel pour examiner les liens entre les chocs de demande et d'offre de pétrole et les ajustements de la demande de travail et des salaires dans les industries manufacturières au Canada. Le modèle est estimé sur des données annuelles désagrégées au niveau industriel sur la période de 1975 à 2008. Les principaux résultats suggèrent qu'un choc positif de demande globale a un effet positif sur la demande de travail et les salaires, à court terme et à long terme. Un choc négatif sur l'offre de pétrole a un effet négatif relativement faible au moment de l'impact, mais l'effet devient positif après la première année. En revanche, un choc positif sur la demande précaution de pétrole a un impact négatif à tous les horizons. Les estimations industrie-par-industrie confirment les précédents résultats en panel. En outre, le papier examine comment les effets des différents chocs pétroliers sur la demande travail et les salaires varient en fonction du degré d'exposition commerciale et de l'intensité en énergie dans la production. Il ressort que les industries fortement exposées au commerce international et les industries fortement intensives en énergie sont plus vulnérables aux fluctuations du prix du pétrole causées par des chocs d'offre de pétrole ou des chocs de demande globale. Le dernier chapitre examine les implications en terme de bien-être social de l'introduction des inventaires en pétrole sur le marché mondial à l'aide d'un modèle DSGE de trois pays dont deux pays importateurs de pétrole et un pays exportateur de pétrole. Les gains de bien-être sont mesurés par la variation compensatoire de la consommation sous deux règles de politique monétaire. Les principaux résultats montrent que l'introduction des inventaires en pétrole a des effets négatifs sur le bien-être des consommateurs dans chacun des deux pays importateurs de pétrole, alors qu'il a des effets positifs sur le bien-être des consommateurs dans le pays exportateur de pétrole, quelle que soit la règle de politique monétaire. Par ailleurs, l'inclusion de la dépréciation du taux de change dans les règles de politique monétaire permet de réduire les coûts sociaux pour les pays importateurs de pétrole. Enfin, l'ampleur des effets de bien-être dépend du niveau d'inventaire en pétrole à l'état stationnaire et est principalement expliquée par les chocs sur les inventaires en pétrole.

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.

Price, profitability and employment in the handloom industry in kerala

The present study is on the nature, problems and prospects of the handloom industry in Kerala. The problems of the industry are mostly in the nature of low earnings of the workers, underutilisation of the existing capacity and low profit in its various sectors. The majority of the handloom co-operative societies are either dormant or facing liquidation. The income and employment of weavers are so pitiably low that they are living in utter poverty and starvation. Frequent price fluctuations of yarns, dyes and chemicals increase the cost of production and reduce the profitability. Consequently handloom fabrics are not able to compete with mill cloths and powerloom products. Accumulating the unsold stocks in the godowns of co-operative societies and with master weavers has become the practice of the day. Spinning mills in Kerala are producing only lower counts of yarns. S, handloom industry has to depend on textile mills in Tamil Nadu for higher counts of yarn. They create artificial scarcity and increase the prices exflorbitantly. Wage rates prevailing in Kerala are higher than those in Tamil Hadu. So rich master weavers are migrating to Tamil.Nadu and exporting the fabrics. under the label 'Kera1a Handlooms'. Governmental efforts to tackle the crisis by way of rebates and subsidies are found to be futile.

Right to Maintenance Under Criminal Law - A Critical Study

Some study has been made earlier, but no attempt has ever been made to make the study comprehensive and comparative. There exists also no information as to the working of the system. Hence the work is undertaken to provide first hand knowledge of the legal institutions that had handled and now handles annually large masses of deprived and neglected population. An investigation is also necessary to know the legal and social characteristics of the jurisdiction enjoined on the court so that this will help compare the law in the statute with the law and practice. The evaluation of the working system in the changed social atmosphere is also an urgent need of the hour

Integrating TPM and QFD for improving quality in maintenance engineering

To provide maintenance engineering community with a model named “Maintenance quality function deployment” (MQFD) for nourishing the synergy of quality function deployment (QFD) and total productive maintenance (TPM) and enhancing maintenance quality of products and equipment.The principles of QFD and TPM were studied. MQFD model was designed by coupling these two principles. The practical implementation feasibility of MQFD model was checked in an automobile service station.Both QFD and TPM are popular approaches and several benefits of implementing them have been reported worldwide. Yet the world has not nourished the synergic power of integrating them. The MQFD implementation study reported in this paper has revealed its practical validity

A New Model For Reliability Centered Maintenance In Petroleum Refineries

Refiners today operate their equipment for prolonged periods without shutdown. This is primarily due to the increased pressures of the market resulting in extended shutdown-to-shutdown intervals. This places extreme demands on the reliability of the plant equipment. The traditional methods of reliability assurance, like Preventive Maintenance, Predictive Maintenance and Condition Based Maintenance become inadequate in the face of such demands. The alternate approaches to reliability improvement, being adopted the world over are implementation of RCFA programs and Reliability Centered Maintenance. However refiners and process plants find it difficult to adopt this standardized methodology of RCM mainly due to the complexity and the large amount of analysis that needs to be done, resulting in a long drawn out implementation, requiring the services of a number of skilled people. These results in either an implementation restricted to only few equipment or alternately, one that is non-standard. The paper presents the current models in use, the core requirements of a standard RCM model, the alternatives to classical RCM, limitations in the existing model, classical RCM and available alternatives to RCM and will then go on to present an ‗Accelerated‘ approach to RCM implementation, that, while ensuring close conformance to the standard, does not place a large burden on the implementers

The empirical study of the price mechanism in the Chinese housing market

In China, the history of the establishment of the private housing market is pretty short. Actually in less then two decades, the market has grown from almost the scratch to playing an important role in the economy. A great achievement! But many problems also exist. They need to be properly addressed and solved. Price problem---simply put, housing price is too high--- is one of them, and this paper is focused on it. Three basic questions are posed, i.e. (1) how to judge the housing affordability? (2) why the housing price is so high? (3) how to solve the housing price problem. The paper pays particular attention to answering the second question. Except the numerous news reports and surveys show that most of the ordinary city dwellers complained about the high housing price, the mathematical means, the four ratios, are applied to judge the housing affordability in Shanghai and Shenzhen. The results are very clear that the price problem is severe. So why? Something is wrong with the price mechanism. This research shows that mainly these five factors contribute to the price problem: the housing reform, the housing development model, the unbalanced housing market, the housing project financing and the poor governmental management. Finally the paper puts forward five suggestions to solve the housing price problem in first-hand private Chinese housing market. They include: the establishment of real estate information system, the creation of specific price management department, the government price regulation, the property tax and the legalization of "cushion money".

Domestic policy responses to the food price crisis: The case of Bolivia

In face of the global food crisis of 2007-2008, severe concerns arose about how developing countries would be affected by the extreme short-term fluctuations in international commodity prices. We examine the effects of the crisis on Bolivia, one of the poorest countries of the Americas. We focus on the effectiveness of the domestic policy interventions in preventing spillovers of the development of international food prices to domestic markets. Using a cointegration model, we study price interdependencies of wheat flour, sunflower oil and poultry. The analysis suggests that the policy measures taken had little effect on food security during the food crisis. Throughout the entire period, perfect price transmission between the Bolivian poultry and sunflower oil markets and the respective international reference markets existed. Bolivian prices were determined by international prices and the policy interventions in the markets of these two commodities were not found to have had an effect. The government's large-scale wheat flour imports did not shield Bolivian consumers from the shocks of international prices.

Impact on Policy Responses to Food Price Crisis and Rural Food Security in Sri Lanka

In Sri Lanka policy responses have direct impacts on rural dwellers. Over 80% of Sri Lanka’s population live in rural areas and 90% of them represent low income dwellers. Their production system may be hampered by fragmented landholding, poor economics of scale, low investment levels resulting from poor financial services as well as inappropriate or limited technology. They are vulnerable to price hikes of basic foods and food security issues due to fragmented landholding and poor financial services. Policy measures to reduce the transmission of higher international prices in domestic markets exist to protect the food security of the vulnerable population. This paper will discuss the food policy and strategies implemented by the government and outside to the above facts this paper also describes the effectiveness of the policies forwarded by the government. The objective of this study is to analyse the impact of policy responses to the food price crisis and rural food security in Sri Lanka. Outside of the above facts this study also treats the impact of policies and decisions on the nutritional condition of rural dwellers. Furthermore this study is to analyse the fluctuation of buying power with the price hikes and the relation of above facts with issues like malnutrition. This paper discusses why policy makers should pay greater attention to rural dwellers and describes the multiple pathways through which food price increases have on rural people. It also provides evidence of the impact of this crisis in particular, through hidden hunger, and discusses how current policy responses should adjust and improve to protect the rural dwellers in the short and long term.

On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs

A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two algorithms, one serial and one parallel, to maintain series-parallel (SP) relationships "on the fly" for fork-join multithreaded programs. The serial SP-order algorithm runs in O(1) amortized time per operation. In contrast, the previously best algorithm requires a time per operation that is proportional to Tarjan’s functional inverse of Ackermann’s function. SP-order employs an order-maintenance data structure that allows us to implement a more efficient "English-Hebrew" labeling scheme than was used in earlier race detectors, which immediately yields an improved determinacy-race detector. In particular, any fork-join program running in T₁ time on a single processor can be checked on the fly for determinacy races in O(T₁) time. Corresponding improved bounds can also be obtained for more sophisticated data-race detectors, for example, those that use locks. By combining SP-order with Feng and Leiserson’s serial SP-bags algorithm, we obtain a parallel SP-maintenance algorithm, called SP-hybrid. Suppose that a fork-join program has n threads, T₁ work, and a critical-path length of T[subscript ∞]. When executed on P processors, we prove that SP-hybrid runs in O((T₁/P + PT[subscript ∞]) lg n) expected time. To understand this bound, consider that the original program obtains linear speed-up over a 1-processor execution when P = O(T₁/T[subscript ∞]). In contrast, SP-hybrid obtains linear speed-up when P = O(√T₁/T[subscript ∞]), but the work is increased by a factor of O(lg n).