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.

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.

Modélisation du carnet d'ordres limites et prévision de séries temporelles

Le contenu de cette thèse est divisé de la façon suivante. Après un premier chapitre d’introduction, le Chapitre 2 est consacré à introduire aussi simplement que possible certaines des théories qui seront utilisées dans les deux premiers articles. Dans un premier temps, nous discuterons des points importants pour la construction de l’intégrale stochastique par rapport aux semimartingales avec paramètre spatial. Ensuite, nous décrirons les principaux résultats de la théorie de l’évaluation en monde neutre au risque et, finalement, nous donnerons une brève description d’une méthode d’optimisation connue sous le nom de dualité. Les Chapitres 3 et 4 traitent de la modélisation de l’illiquidité et font l’objet de deux articles. Le premier propose un modèle en temps continu pour la structure et le comportement du carnet d’ordres limites. Le comportement du portefeuille d’un investisseur utilisant des ordres de marché est déduit et des conditions permettant d’éliminer les possibilités d’arbitrages sont données. Grâce à la formule d’Itô généralisée il est aussi possible d’écrire la valeur du portefeuille comme une équation différentielle stochastique. Un exemple complet de modèle de marché est présenté de même qu’une méthode de calibrage. Dans le deuxième article, écrit en collaboration avec Bruno Rémillard, nous proposons un modèle similaire mais cette fois-ci en temps discret. La question de tarification des produits dérivés est étudiée et des solutions pour le prix des options européennes de vente et d’achat sont données sous forme explicite. Des conditions spécifiques à ce modèle qui permettent d’éliminer l’arbitrage sont aussi données. Grâce à la méthode duale, nous montrons qu’il est aussi possible d’écrire le prix des options européennes comme un problème d’optimisation d’une espérance sur en ensemble de mesures de probabilité. Le Chapitre 5 contient le troisième article de la thèse et porte sur un sujet différent. Dans cet article, aussi écrit en collaboration avec Bruno Rémillard, nous proposons une méthode de prévision des séries temporelles basée sur les copules multivariées. Afin de mieux comprendre le gain en performance que donne cette méthode, nous étudions à l’aide d’expériences numériques l’effet de la force et la structure de dépendance sur les prévisions. Puisque les copules permettent d’isoler la structure de dépendance et les distributions marginales, nous étudions l’impact de différentes distributions marginales sur la performance des prévisions. Finalement, nous étudions aussi l’effet des erreurs d’estimation sur la performance des prévisions. Dans tous les cas, nous comparons la performance des prévisions en utilisant des prévisions provenant d’une série bivariée et d’une série univariée, ce qui permet d’illustrer l’avantage de cette méthode. Dans un intérêt plus pratique, nous présentons une application complète sur des données financières.

Les municipalités dans le secteur énergétique québécois : le cas du chauffage urbain

In a global context of climate change and energy transition, Quebec seems to be privileged, producing a large amount of cheap hydroelectricity. But aside from the established popular belief that Quebec’s energy is abundant, clean and inexpensive, Quebec’s energy future is still precarious. Within a few decades, Quebec will have to import a significant amount of electricity at a higher price than it actually produces it; the cheap exploitable hydro resources will not only get scarcer if not nonexistent; and the national hydroelectric ``cultural`` heritage even seems to quell the development of alternative energies, letting few space for local innovation coming from municipalities. While in many countries, municipalities are recognised as key figures in the energy sector, here, in Quebec, their role in the national energy system seems marginal. As main actors responsible for territorial planning, it seams that municipalities could play a more important role on Quebec’s energy scene. So they can densify their territory, develop active and collective solutions to transportation issues, they can adopt exemplary energetic habits, they can produce their own energy with wind, solar or even district heating systems. District heating and heat networks being less well know and documented in Quebec, the present study aims at explaining their low penetration level in the Quebec energy landscape. The study also attempts to understand what are the main hurdles to the implementation of district heating in Quebec’s particular energetic context. Finally, the research tries to open a discussion on the motives that could incite municipalities to adopt district heating as an energy alternative. Based on some twenty interviews with key actors of the energy and municipal sectors, the findings give some indications that the low penetration level of district heating in the Quebec municipalities could explain itself in part by : the low priced hydroelectricity, the presence of a comfortable, sufficient and pervasive Hydro-Quebec(er) culture, and also by organizational dynamic and a certain political inertia which limit the appropriation of an energy competence by local governments. In turn, the study shows that district heating solutions are more likely to develop in contexts in which : there are minimum urban or energy density levels; the development of district heating coincides with the local or regional economic structure; and where exist a mobilising local leader or local visions from a community in favor of the implementation of alternative energy systems.

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.

Trois essais en macroéconomie

Les fluctuations économiques représentent les mouvements de la croissance économique. Celle-ci peut connaître des phases d'accélération (expansion) ou de ralentissement (récession), voire même de dépression si la baisse de production est persistente. Les fluctuations économiques sont liées aux écarts entre croissance effective et croissance potentielle. Elles peuvent s'expliquer par des chocs d'offre et demande, ainsi que par le cycle du crédit. Dans le premier cas, les conditions de la production se trouvent modifiées. C'est le cas lorsque le prix des facteurs de production (salaires, prix des matières premières) ou que des facteurs externes influençant le prix des produits (taux de change) évolue. Ainsi, une hausse du prix des facteurs de production provoque un choc négatif et ralentit la croissance. Ce ralentissement peut être également dû à un choc de demande négatif provoqué par une hausse du prix des produits causée par une appréciation de la devise, engendrant une diminution des exportations. Le deuxième cas concerne les variables financières et les actifs financiers. Ainsi, en période d'expansion, les agents économiques s'endettent et ont des comportements spéculatifs en réaction à des chocs d'offre ou demande anticipés. La valeur des titres et actifs financiers augmente, provoquant une bulle qui finit par éclater et provoquer un effondrement de la valeur des biens. Dès lors, l'activité économique ne peut plus être financée. C'est ce qui génère une récession, parfois profonde, comme lors de la récente crise financière. Cette thèse inclut trois essais sur les fluctuations macroéconomiques et les cycles économiques, plus précisément sur les thèmes décrit ci-dessus. Le premier chapitre s'intéresse aux anticipations sur la politique monétaire et sur la réaction des agents écononomiques face à ces anticipations. Une emphase particulière est mise sur la consommation de biens durables et l'endettement relié à ce type de consommation. Le deuxième chapitre aborde la question de l'influence des variations du taux de change sur la demande de travail dans le secteur manufacturier canadien. Finalement, le troisième chapitre s'intéresse aux retombées économiques, parfois négatives, du marché immobilier sur la consommation des ménages et aux répercussions sur le prix des actifs immobiliers et sur l'endettement des ménages d'anticipations infondées sur la demande dans le marché immobilier. Le premier chapitre, intitulé ``Monetary Policy News Shocks and Durable Consumption'', fournit une étude sur le lien entre les dépenses en biens durables et les chocs monétaires anticipés. Nous proposons et mettons en oeuvre une nouvelle approche pour identifier les chocs anticipés (nouvelles) de politique monétaire, en les identifiant de manière récursive à partir des résidus d’une règle de Taylor estimée à l’aide de données de sondage multi-horizon. Nous utilisons ensuite les chocs anticipés inférer dans un modèle autorégressif vectoriel structurel (ARVS). L’anticipation d’une politique de resserrement monétaire mène à une augmentation de la production, de la consommation de biens non-durables et durables, ainsi qu’à une augmentation du prix réel des biens durables. Bien que les chocs anticipés expliquent une part significative des variations de la production et de la consommation, leur impact est moindre que celui des chocs non-anticipés sur les fluctuations économiques. Finalement, nous menons une analyse théorique avec un modèle d’équilibre général dynamique stochastique (EGDS) avec biens durables et rigidités nominales. Les résultats indiquent que le modèle avec les prix des biens durables rigides peut reproduire la corrélation positive entre les fonctions de réponse de la consommation de biens non-durables et durables à un choc anticipé de politique monétaire trouvées à l’aide du ARVS. Le second chapitre s'intitule ``Exchange Rate Fluctuations and Labour Market Adjustments in Canadian Manufacturing Industries''. Dans ce chapitre, nous évaluons la sensibilité de l'emploi et des heures travaillées dans les industries manufacturières canadiennes aux variations du taux de change. L’analyse est basée sur un modèle dynamique de demande de travail et utilise l’approche en deux étapes pour l'estimation des relations de cointégration en données de panel. Nos données sont prises d’un panel de 20 industries manufacturières, provenant de la base de données KLEMS de Statistique Canada, et couvrent une longue période qui inclut deux cycles complets d’appréciation-dépréciation de la valeur du dollar canadien. Les effets nets de l'appréciation du dollar canadien se sont avérés statistiquement et économiquement significatifs et négatifs pour l'emploi et les heures travaillées, et ses effets sont plus prononcés dans les industries davantage exposées au commerce international. Finalement, le dernier chapitre s'intitule ``Housing Market Dynamics and Macroprudential Policy'', dans lequel nous étudions la relation statistique suggérant un lien collatéral entre le marché immobilier and le reste de l'économique et si ce lien est davantage entraîné par des facteurs de demandes ou d'offres. Nous suivons également la littérature sur les chocs anticipés et examinons un cyle d'expansion-récession peut survenir de façon endogène la suite d'anticipations non-réalisées d'une hausse de la demande de logements. À cette fin, nous construisons un modèle néo-Keynésien au sein duquel le pouvoir d’emprunt du partie des consommateurs est limité par la valeur de leur patrimoine immobilier. Nous estimons le modèle en utilisant une méthode Bayésienne avec des données canadiennes. Nous évaluons la capacité du modèle à capter les caractéristiques principales de la consommation et du prix des maisons. Finalement, nous effectuons une analyse pour déterminer dans quelle mesure l'introduction d'un ratio prêt-à-la-valeur contracyclique peut réduire l'endettement des ménages et les fluctuations du prix des maisons comparativement à une règle de politique monétaire répondant à l'inflation du prix des maisons. Nous trouvons une relation statistique suggérant un important lien collatéral entre le marché immobilier et le reste de l'économie, et ce lien s'explique principalement par des facteurs de demande. Nous constatons également que l'introduction de chocs anticipés peut générer un cycle d'expansion-récession du marché immobilier, la récession faisant suite aux attentes non-réalisées par rapport à la demande de logements. Enfin, notre étude suggère également qu'un ratio contracyclique de prêt-à-la-valeur est une politique utile pour réduire les retombées du marché du logement sur la consommation par l'intermédiaire de la valeur garantie.

Frustrated limit cycle and irregular behaviour in a nonlinear pendulum

We discuss how the presence of frustration brings about irregular behaviour in a pendulum with nonlinear dissipation. Here frustration arises owing to particular choice of the dissipation. A preliminary numerical analysis is presented which indicates the transition to chaos at low frequencies of the driving force.

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.

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.

alr approach for replacing values below the detection limit

All of the imputation techniques usually applied for replacing values below the detection limit in compositional data sets have adverse effects on the variability. In this work we propose a modification of the EM algorithm that is applied using the additive log-ratio transformation. This new strategy is applied to a compositional data set and the results are compared with the usual imputation techniques