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.

The Transformation Problem : an Aleternative Solution with an Identical Aggregate Profit Rate in the Labor value and the Monetary Space.

The aim of this paper is to demonstrate that, even if Marx's solution to the transformation problem can be modified, his basic conclusions remain valid. the proposed alternative solution which is presented hare is based on the constraint of a common general profit rate in both spaces and a money wage level which will be determined simultaneously with prices.

The Transformation Problem : an Aleternative Solution with an Identical Aggregate Profit Rate in the Labor value and the Monetary Space.

The aim of this paper is to demonstrate that, even if Marx's solution to the transformation problem can be modified, his basic conclusions remain valid. the proposed alternative solution which is presented hare is based on the constraint of a common general profit rate in both spaces and a money wage level which will be determined simultaneously with prices.

Externalities, Potential, Value and Consistency

We provide new characterization results for the value of games in partition function form. In particular, we use the potential of a game to define the value. We also provide a characterization of the class of values which satisfies one form of reduced game consistency.

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.

Equality and Value-holism

Dans cet article je considère un récent défi à l’égalitarisme développé par Michael Huemer. Le challenge de Huemer prend la forme d’un dilemme : les égalitaristes peuvent être soit atomistes soit holistes en ce qui concerne la valeur de l’égalité. S’ils sont atomistes, alors ils doivent acceptés que l’égalité n’ait pas de valeur intrinsèque ; s’ils sont holistes, alors leur point ce vue est inconsistant avec une intuitive mais très plausible forme de conséquentialisme. Je montre que ce dilemme ne doit pas perturber les égalitaristes. Ils peuvent être holistes en ce qui concerne la valeur et adhérer en même temps au conséqeuntialisme.

Perfectionism, Economic (dis)Incentives, and Political Coercion

May a government attempt to improve the lives of its citizens by promoting the activities it deems valuable and discouraging those it disvalues? May it engage in such a practice even when doing so is not a requirement of justice in some strict sense, and even when the judgments of value and disvalue in question are likely to be subject to controversy among its citizens? These questions have long stood at the center of debates between political perfectionists and political neutralists. In what follows I address a prominent cluster of arguments against political perfectionism—namely, arguments that focus on the coercive dimensions of state action. My main claim is simple: whatever concerns we might have about coercion, arguments from coercion fall short of supporting a thoroughgoing rejection of perfectionism, for the reason that perfectionist policies need not be coercive. Thlist challenges to this last claim.

Logiciels de traduction automatique: protection, responsabilité

La présente recherche a pour but de faire le point sur l'état du droit canadien et sur ses perspectives futures en relation avec les œuvres créées par ordinateurs. L'outil terminologique choisi pour notre objectif est le logiciel de traduction automatique multilingue qui, à cause de sa complexité, s'éloigne le plus du programmeur « créateur» et se rapproche le plus d'œuvres qui ne peuvent être directement attribuées aux linguistes et programmeurs. Ces outils et leurs créations seront d'après nous les prochains outils technologiques à confronter le droit. En effet, dans un avenir prévisible, considérant l'évolution technologique, ces logiciels produiront des textes qui bénéficieront d'une valeur commerciale ajoutée et c'est alors que certains feront valoir leurs « droits », non seulement sur les textes mais aussi sur la technologie. Pour atteindre cet objectif, nous débuterons par un retour historique sur la technologie et ses origines. Par la suite, nous ferons une analyse de la protection actuelle accordée aux logiciels, aux banques de données et aux traductions qu'ils produisent. Nous déterminerons ensuite qui sera responsable des textes produits en relation avec le texte d'origine et avec sa résultante au niveau du droit d'auteur et de celui de la responsabilité civile. Cette recherche nous amènera à conclure que le droit actuel est « mésadapté » tant à l'égard de la protection qu'au niveau de la responsabilité. Ces conclusions devront d'après nous imposer un retour aux principes fondamentaux du droit. Ce fondamentalisme légal sera pour nous le prix à payer pour la légitimité. En effet, plus particulièrement concernant le droit d'auteur, nous conclurons qu'il devra cesser d'être le « fourre-tout» du droit de la propriété intellectuelle et redevenir ce qu'il doit être: un droit qui protège la créativité. Cette démarche prospective tirera ses racines du fait que nous serons obligés de conclure que les juristes canadiens ont refusé, à tort à notre point de vue, de renvoyer au monde des brevets les méthodes et procédés nouveaux et inventifs, ce qui donc a introduit des problématiques inutiles qui exacerbent l'incertitude. Finalement, notre cheminement nous dirigera vers le droit de la responsabilité où nous soutiendrons que le fournisseur ne peut actuellement être responsable du texte produit puisqu'il ne participe pas directement aux choix et ne porte pas atteinte au contenu. Voici donc en quelques mots le cœur de notre recherche qui entrouvre une boîte de Pandore.

Models and algorithms for the capacitated location-routing problem

Le problème de localisation-routage avec capacités (PLRC) apparaît comme un problème clé dans la conception de réseaux de distribution de marchandises. Il généralisele problème de localisation avec capacités (PLC) ainsi que le problème de tournées de véhicules à multiples dépôts (PTVMD), le premier en ajoutant des décisions liées au routage et le deuxième en ajoutant des décisions liées à la localisation des dépôts. Dans cette thèse on dévelope des outils pour résoudre le PLRC à l’aide de la programmation mathématique. Dans le chapitre 3, on introduit trois nouveaux modèles pour le PLRC basés sur des flots de véhicules et des flots de commodités, et on montre comment ceux-ci dominent, en termes de la qualité de la borne inférieure, la formulation originale à deux indices [19]. Des nouvelles inégalités valides ont été dévelopées et ajoutées aux modèles, de même que des inégalités connues. De nouveaux algorithmes de séparation ont aussi été dévelopés qui dans la plupart de cas généralisent ceux trouvés dans la litterature. Les résultats numériques montrent que ces modèles de flot sont en fait utiles pour résoudre des instances de petite à moyenne taille. Dans le chapitre 4, on présente une nouvelle méthode de génération de colonnes basée sur une formulation de partition d’ensemble. Le sous-problème consiste en un problème de plus court chemin avec capacités (PCCC). En particulier, on utilise une relaxation de ce problème dans laquelle il est possible de produire des routes avec des cycles de longueur trois ou plus. Ceci est complété par des nouvelles coupes qui permettent de réduire encore davantage le saut d’intégralité en même temps que de défavoriser l’apparition de cycles dans les routes. Ces résultats suggèrent que cette méthode fournit la meilleure méthode exacte pour le PLRC. Dans le chapitre 5, on introduit une nouvelle méthode heuristique pour le PLRC. Premièrement, on démarre une méthode randomisée de type GRASP pour trouver un premier ensemble de solutions de bonne qualité. Les solutions de cet ensemble sont alors combinées de façon à les améliorer. Finalement, on démarre une méthode de type détruir et réparer basée sur la résolution d’un nouveau modèle de localisation et réaffectation qui généralise le problème de réaffectaction [48].

Did Gold Remain Relevant in the Post-1971 International Monetary System?

The central hypothesis to be tested is the relevance of gold in the determination of the value of the US dollar as an international reserve currency after 1971. In the first section the market value of the US dollar is analysed by looking at new forms of value (financial derivative products), the dollar as a safe haven, the choice of a standard of value and the role of SDRs in reforming the international monetary system. Based on dimensional analysis, the second section analyses the definition and meaning of a numéraire for international currency and the justification for a variable standard of value based on a commodity (gold). The second section is the theoretical foundation for the empirical and econometric analysis in the third and fourth sections. The third section is devoted to the specification of an econometric model and a graphical analysis of the data. It is clear that an inverse relation exists between the value of the US dollar and the price of gold. The fourth section shows the estimations of the different specifications of the model including linear regression and cointegration analysis. The most important econometric result is that the null hypothesis is rejected in favour of a significant link between the price of gold and the value of the US dollar. There is also a positive relationship between gold price and inflation. An inverse statistically significant relation between gold price and monetary policy is shown by applying a dynamic model of cointegration with lags.

High-amylose carboxymethyl starch matrices for oral sustained drug-release : in vitro and in vivo evaluation

Les amidons non modifiées et modifiés représentent un groupe d’excipients biodégradables et abondants particulièrement intéressant. Ils ont été largement utilisés en tant qu’excipients à des fins diverses dans des formulations de comprimés, tels que liants et/ou agents de délitement. Le carboxyméthylamidon sodique à haute teneur en amylose atomisé (SD HASCA) a été récemment proposé comme un excipient hydrophile à libération prolongée innovant dans les formes posologiques orales solides. Le carboxyméthylamidon sodique à haute teneur en amylose amorphe (HASCA) a d'abord été produit par l'éthérification de l'amidon de maïs à haute teneur en amylose avec le chloroacétate. HASCA a été par la suite séché par atomisation pour obtenir le SD HASCA. Ce nouvel excipient a montré des propriétés présentant certains avantages dans la production de formes galéniques à libération prolongée. Les comprimés matriciels produits à partir de SD HASCA sont peu coûteux, simples à formuler et faciles à produire par compression directe. Le principal objectif de cette recherche était de poursuivre le développement et l'optimisation des comprimés matriciels utilisant SD HASCA comme excipient pour des formulations orales à libération prolongée. A cet effet, des tests de dissolution simulant les conditions physiologiques du tractus gastro-intestinal les plus pertinentes, en tenant compte de la nature du polymère à l’étude, ont été utilisés pour évaluer les caractéristiques à libération prolongée et démontrer la performance des formulations SD HASCA. Une étude clinique exploratoire a également été réalisée pour évaluer les propriétés de libération prolongée de cette nouvelle forme galénique dans le tractus gastro-intestinal. Le premier article présenté dans cette thèse a évalué les propriétés de libération prolongée et l'intégrité physique de formulations contenant un mélange comprimé de principe actif, de chlorure de sodium et de SD HASCA, dans des milieux de dissolution biologiquement pertinentes. L'influence de différentes valeurs de pH acide et de temps de séjour dans le milieu acide a été étudiée. Le profil de libération prolongée du principe actif à partir d'une formulation de SD HASCA optimisée n'a pas été significativement affecté ni par la valeur de pH acide ni par le temps de séjour dans le milieu acide. Ces résultats suggèrent une influence limitée de la variabilité intra et interindividuelle du pH gastrique sur la cinétique de libération à partir de matrices de SD HASCA. De plus, la formulation optimisée a gardé son intégrité pendant toute la durée des tests de dissolution. L’étude in vivo exploratoire a démontré une absorption prolongée du principe actif après administration orale des comprimés matriciels de SD HASCA et a montré que les comprimés ne se sont pas désintégrés en passant par l'estomac et qu’ils ont résisté à l’hydrolyse par les α-amylases dans l'intestin. Le deuxième article présente le développement de comprimés SD HASCA pour une administration orale une fois par jour et deux fois par jour contenant du chlorhydrate de tramadol (100 mg et 200 mg). Ces formulations à libération prolongée ont présenté des valeurs de dureté élevées sans nécessiter l'ajout de liants, ce qui facilite la production et la manipulation des comprimés au niveau industriel. La force de compression appliquée pour produire les comprimés n'a pas d'incidence significative sur les profils de libération du principe actif. Le temps de libération totale à partir de comprimés SD HASCA a augmenté de manière significative avec le poids du comprimé et peut, de ce fait, être utilisé pour moduler le temps de libération à partir de ces formulations. Lorsque les comprimés ont été exposés à un gradient de pH et à un milieu à 40% d'éthanol, un gel très rigide s’est formé progressivement sur leur surface amenant à la libération prolongée du principe actif. Ces propriétés ont indiqué que SD HASCA est un excipient robuste pour la production de formes galéniques orales à libération prolongée, pouvant réduire la probabilité d’une libération massive de principe actif et, en conséquence, des effets secondaires, même dans le cas de co-administration avec une forte dose d'alcool. Le troisième article a étudié l'effet de α-amylase sur la libération de principe actif à partir de comprimés SD HASCA contenant de l’acétaminophène et du chlorhydrate de tramadol qui ont été développés dans les premières étapes de cette recherche (Acetaminophen SR et Tramadol SR). La modélisation mathématique a montré qu'une augmentation de la concentration d’α-amylase a entraîné une augmentation de l'érosion de polymère par rapport à la diffusion de principe actif comme étant le principal mécanisme contrôlant la libération de principe actif, pour les deux formulations et les deux temps de résidence en milieu acide. Cependant, même si le mécanisme de libération peut être affecté, des concentrations d’α-amylase allant de 0 UI/L à 20000 UI/L n'ont pas eu d'incidence significative sur les profils de libération prolongée à partir de comprimés SD HASCA, indépendamment de la durée de séjour en milieu acide, le principe actif utilisé, la teneur en polymère et la différente composition de chaque formulation. Le travail présenté dans cette thèse démontre clairement l'utilité de SD HASCA en tant qu'un excipient à libération prolongée efficace.

Optimization models and methods for real-time transportation planning in forestry

Lors du transport du bois de la forêt vers les usines, de nombreux événements imprévus peuvent se produire, événements qui perturbent les trajets prévus (par exemple, en raison des conditions météo, des feux de forêt, de la présence de nouveaux chargements, etc.). Lorsque de tels événements ne sont connus que durant un trajet, le camion qui accomplit ce trajet doit être détourné vers un chemin alternatif. En l’absence d’informations sur un tel chemin, le chauffeur du camion est susceptible de choisir un chemin alternatif inutilement long ou pire, qui est lui-même "fermé" suite à un événement imprévu. Il est donc essentiel de fournir aux chauffeurs des informations en temps réel, en particulier des suggestions de chemins alternatifs lorsqu’une route prévue s’avère impraticable. Les possibilités de recours en cas d’imprévus dépendent des caractéristiques de la chaîne logistique étudiée comme la présence de camions auto-chargeurs et la politique de gestion du transport. Nous présentons trois articles traitant de contextes d’application différents ainsi que des modèles et des méthodes de résolution adaptés à chacun des contextes. Dans le premier article, les chauffeurs de camion disposent de l’ensemble du plan hebdomadaire de la semaine en cours. Dans ce contexte, tous les efforts doivent être faits pour minimiser les changements apportés au plan initial. Bien que la flotte de camions soit homogène, il y a un ordre de priorité des chauffeurs. Les plus prioritaires obtiennent les volumes de travail les plus importants. Minimiser les changements dans leurs plans est également une priorité. Étant donné que les conséquences des événements imprévus sur le plan de transport sont essentiellement des annulations et/ou des retards de certains voyages, l’approche proposée traite d’abord l’annulation et le retard d’un seul voyage, puis elle est généralisée pour traiter des événements plus complexes. Dans cette ap- proche, nous essayons de re-planifier les voyages impactés durant la même semaine de telle sorte qu’une chargeuse soit libre au moment de l’arrivée du camion à la fois au site forestier et à l’usine. De cette façon, les voyages des autres camions ne seront pas mo- difiés. Cette approche fournit aux répartiteurs des plans alternatifs en quelques secondes. De meilleures solutions pourraient être obtenues si le répartiteur était autorisé à apporter plus de modifications au plan initial. Dans le second article, nous considérons un contexte où un seul voyage à la fois est communiqué aux chauffeurs. Le répartiteur attend jusqu’à ce que le chauffeur termine son voyage avant de lui révéler le prochain voyage. Ce contexte est plus souple et offre plus de possibilités de recours en cas d’imprévus. En plus, le problème hebdomadaire peut être divisé en des problèmes quotidiens, puisque la demande est quotidienne et les usines sont ouvertes pendant des périodes limitées durant la journée. Nous utilisons un modèle de programmation mathématique basé sur un réseau espace-temps pour réagir aux perturbations. Bien que ces dernières puissent avoir des effets différents sur le plan de transport initial, une caractéristique clé du modèle proposé est qu’il reste valable pour traiter tous les imprévus, quelle que soit leur nature. En effet, l’impact de ces événements est capturé dans le réseau espace-temps et dans les paramètres d’entrée plutôt que dans le modèle lui-même. Le modèle est résolu pour la journée en cours chaque fois qu’un événement imprévu est révélé. Dans le dernier article, la flotte de camions est hétérogène, comprenant des camions avec des chargeuses à bord. La configuration des routes de ces camions est différente de celle des camions réguliers, car ils ne doivent pas être synchronisés avec les chargeuses. Nous utilisons un modèle mathématique où les colonnes peuvent être facilement et naturellement interprétées comme des itinéraires de camions. Nous résolvons ce modèle en utilisant la génération de colonnes. Dans un premier temps, nous relaxons l’intégralité des variables de décision et nous considérons seulement un sous-ensemble des itinéraires réalisables. Les itinéraires avec un potentiel d’amélioration de la solution courante sont ajoutés au modèle de manière itérative. Un réseau espace-temps est utilisé à la fois pour représenter les impacts des événements imprévus et pour générer ces itinéraires. La solution obtenue est généralement fractionnaire et un algorithme de branch-and-price est utilisé pour trouver des solutions entières. Plusieurs scénarios de perturbation ont été développés pour tester l’approche proposée sur des études de cas provenant de l’industrie forestière canadienne et les résultats numériques sont présentés pour les trois contextes.