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.

Excitonic behaviour in polymeric semiconductors : the effect of morphology and composition in heterostructures

La compréhension des interrelations entre la microstructure et les processus électroniques dans les polymères semi-conducteurs est d’une importance primordiale pour leur utilisation dans des hétérostructures volumiques. Dans cette thèse de doctorat, deux systémes diffèrents sont étudiés ; chacun de ces systèmes représente une approche diffèrente pour optimiser les matériaux en termes de leur microstructure et de leur capacité à se mettre en ordre au niveau moléculaire. Dans le premier système, j’ai effectué une analyse complète des principes de fonctionnement d’une cellule photovoltaïque hybride à base des nanocristaux d’oxyde de zinc (ZnO) et du poly (3-hexylthiophène) (P3HT) par absorption photoinduite en régime quasi-stationnaire (PIA) et la spectroscopie PIA en pompage modulé dépendant de la fréquence. L’interface entre le donneur (le polymère P3HT) et l’accepteur (les nanoparticules de ZnO), où la génération de charges se produit, joue un rôle important dans la performance des cellules photovoltaïques hybrides. Pour améliorer le mécanisme de génération de charges du P3H: ZnO, il est indispensable de modifier l’interface entre ses constituants. Nous avons démontré que la modification d’interface moléculaire avec cis-bis (4, 40 - dicarboxy-2, 20bipyridine) ruthénium (II) (N3-dye) et a-Sexithiophen-2 yl-phosphonique (6TP) a améliorée le photocourant et la performance dans les cellules P3HT: ZnO. Le 6TP et le N3 s’attachent à l’interface du ZnO, en augmentant ainsi l’aire effective de la surface donneur :accepteur, ce qui contribue à une séparation de charge accrue. De plus, le 6TP et le N3 réduisent la densité de pièges dans le ZnO, ce qui réduit le taux de recombinaison des paires de charges. Dans la deuxième partie, jai introduit une matrice hôte polymérique de polystyréne à masse molaire ulra-élevée, qui se comporte comme un solide pour piéger et protéger une solution de poly [2-méthoxy, 5- (2´-éthyl-hexoxy) -1,4-phénylènevinylène- PPV] (MEHPPV) pour utilisation dans des dispositifs optoèlectroniques quantiques. Des travaux antérieurs ont montré que MEH-PPV en solution subit une transition de conformation, d’une conformation enroulé à haute température (phase bleue) à une conformation de chaîne étendue à basse température (phase rouge). La conformation de la chaîne étendue de la solution MEH-PPV favorise les caractéristiques nécessaires à l’amélioration des dispositifs optoélectroniques quantiques, mais la solution ne peut pas être incorporées dans le dispositif. J’ai démontré que la caractéristique de la phase rouge du MEH-PPV en solution se maintient dans une matrice hôte polymérique de polystyrène transformé de masse molaire très élevée, qui se comporte comme un solide (gel de MEH-PPV/UHMW PS), par le biais de la spectroscopie de photoluminescence (PL) dépendant de la température (de 290K à 80 K). La phase rouge du gel MEH-PPV/UHMW PS se manifeste par des largeurs de raie étroites et une intensité augmentée de la transition 0-0 de la progression vibronique dans le spectre de PL ainsi qu’un petit décalage de Stokes entre la PL et le spectre d’absorption à basse température. Ces approches démontrent que la manipulation de la microstructure et des propriétés électroniques des polymères semi-conducteurs ont un impact direct sur la performance de dispositifs pour leurs développements technologiques continus.

Profil des étudiants entamant des études universitaires et analyse des choix d’études

Cet article a pour objectif de développer, à partir d’une base de données inédite portant sur les étudiants s’inscrivant pour la première fois en première année à l’université en Belgique francophone, une étude socio-graphique du profil de ces étudiants et de leurs choix d’études, en prenant en compte plusieurs variables sociologiques et académiques : le sexe, le niveau de diplôme des parents, le statut de boursier et diverses variables décrivant le parcours scolaire antérieur. Il s’agit notamment de mesurer l’écart qui nous sépare d’une situation parfaite d’« égalité des chances » d’accès aux études universitaires, où la répartition des étudiants selon le domaine ou le secteur d’études serait indépendante des « variables héritées » liées au sexe ou aux origines sociales.

Gestion de flotte avec fenêtres horaires : approches de résolution mixtes utilisant la programmation par contraintes

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Reconnaissance de visages à partir de modèles tridimensionnels

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Understanding retargeting compilation techniques for network processors

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Étude électrophysiologique, pharmacologique et anatomique des mécanismes impliqués dans la modulation de l'excitabilité des afférences fusoriales du noyau mésencéphalique du trijumeau

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Geochemistry of basement basaltic rocks of ODP Hole 131-808C

Major- and trace-element analyses, mineral chemistry, and Sr-Nd isotopic determinations were obtained on representative igneous rocks drilled from the Nankai accretionary complex (Site 808) during Ocean Drilling Program Leg 131. For the first time, the oceanic basement of the subducting plate below an accretionary prism has been reached. The Nankai Trough basement was encountered at a depth of 1289.9 mbsf and a total of 37.1 m of igneous rocks, middle Miocene (15.6 Ma) in age, was penetrated. Two main lithological units have been distinguished from the top downward; sill-like rocks (Unit I: Cores 105, 106, 107) and pillow lavas (Unit II: Core 108). Basalts are predominantly nonvesicular, hypocrystalline, aphyric to slightly phyric with intersertal to intergranular textures. Alteration is generally slight to moderate. All the basaltic rocks are cut by ramifying veins of varying widths. Secondary mineral assemblages (including vein fillings) are typical of submarine alteration and zeolite to low greenschist facies metamorphism. The order of crystallization of primary minerals is: olivine, plagioclase, clinopyroxene. This, together with mineral chemistry, characterized by forsteritic olivine (Fo 84-85), highly anorthitic Plagioclase (up to An 90), and in particular the composition of clinopyroxene, are typical of normal mid-ocean ridge basalts (MORB). In terms of Zr/Y (2.9-3.8) and Zr/Nb (21-58), all the analyzed samples plot in the normal MORB field. The chondrite-normalized REE patterns confirm the close affinity with normal MORB type (LaN/SmN: 0.6-0.8). Note that such magmatism does not reveal any evidence of subduction-related geochemical components. The 87Sr/86Sr isotopic ratios range from 0.70339 in pillow lavas to 0.70317 in the least-altered basalts of sill units (ratios reduced to 0.70265-0.70271 by HC1 2.5 N hot leaching), whereas 143Nd/144Nd ratios are 0.51314-0.51326. These values conform with those of normal MORB. Stratigraphy, petrography, and geochemistry of the basaltic rocks recovered at Site 808 appear very similar to those from the Shikoku Basin basement (particularly Sites 442 and 443, DSDP Leg 58), analogously identified as normal MORB.

Descriptions of 104 gravity and piston sediment cores from POLARSTERN expedition ARK-VIII/3 to the Arctic Ocean

Sediment descriptions and lithostratigraphy (chapter 6.4) NANSEN BASIN The upperrnost 20-50 cm of sedirnents in the Nansen Basin norrnally cornprise soft dark brown, brown-grayish and brown clay. Except for the toprnost clay, the four piston cores retrieved, contained quite different lithologies: a rnuddy diarnicton with outsized clasts (PS2157-6), sandy-silt beds alternating with clay beds (PS2159-6), and silty clay beds of brownish and grayish colours (PS2161-3). Core PS2208-3 was retrieved frorn a plateau on a searnount. The plateau was serni-encircled by hills. The upper 250 cm of this core cornprise brown and olive brown clays. Below these are several sandlayers and a 74 cm thick unit of a sandy mud with rnud-clasts up to 20 cm in diameter. GAKKEL RIDGE The uppermost 20-50 cm of sediments on the Gakkel Ridge comprise soft dark brown, brown, grayish brown clay. In most of the cores there are two horizons of brown clay separated by olive brown clay. The upper horizon is darker. The older stratigraphy is rather varied. Core PS2165-1 contains several thin gray sandlsilt layers, probably distal turbidites. The sarne is found in Core PS2167-1. This core also has a thick (approx. 2 rn) coarse grained turbidite containing large rnud clasts and basaltic rock fragrnents. The color of the turbiditic layers is dark gray. There are several horizons of hernipelagic sandylsilty clays with quite a variety in colours; black, gray, olive, brown, yellowish brown and reddish. The colour variation rnay be due to hydrotherrnal activity or provenance or a shift in redox potential. Cores PS2168-2 and PS2169-1 have typical sequences of very dark gray sandy mud with sharp lower boundaries grading upwards into olive brown clay. Below the lower boundary is often a thin (1-2 cm) gray clay layer. AMUNDSEN BASIN The giant box cores (GKG) provided in most cases excellently preserved sedirnent surfaces which consisted in the entire Amundsen Basin of dark brown to dark grayish brown silty clay with few dropstones and common calcareous microfossils (foraminifers and calcareous nannofossils). The brown and grayish brown color of the sediment surface is a result of the oxidizing conditions at the seafloor due to the rapid renewal of the bottom water rnasses. Planktic forarninifers and calcareous nannofossils are relatively frequent and well preserved despite the rernote location of the basin and its water depths of >4000 rn. Srnear slide descriptions have shown that the surface sedirnents consist dorninantly of clays to silty rnuds with clay rninerals and quartz as the rnost important constituents. The coarse fractions contained besides planktic and benthic forarninifers and coarse clastic rnaterials, rare bivalves, dropstones and mud clasts. The Station PS2190 at the North Pole is a particular good exarnple of the type of sedirnents deposited at the sea floor surface of the Arnundsen Basin, with hornogenous dark brown soft clay covering a sedirnent sequence of highly variable cornposition. Nurnerous giant box cores also provide insight into the detailed lithostratigraphy of the upperrnost sedirnent layers. Twelve box cores have been collected frorn the Arnundsen Basin. Below the youngest unit of 5-20 crn thick silty clays deposits of variable stratigraphies have been found, rnostly consisting of clays or silty clays. In a few instances turbidites have been observed. Benthic forarninifers have not been found in the surface sedirnents. Other fossils were extrernely rare. Bioturbation is weakly developed on all stations. Benthic anirnals seern to live only in and on the upperrnost 2 cm of the uppermost sediment layer. They cornprise amphipods (on all stations) and holothurians, bryozoans, polychaetes, and porifers at one station each. LOMONOSOV RIDGE Sediments from the Lomonosov Ridge show a variety of colors and textures. Following smear slide analyses they are composed mostly of clay minerals and quartz with mica and feldspars, especially in the siltier and sandier parts. Volcanic glass, microcrystalline carbonate, opaque minerals and green amphibole are occasional accessories. The sediments from the Lomonosov Ridge show a noticeable difference from sediments collected from the surrounding basins. Lomonosov Ridge sediments are richer in silt and sand than basin sediments. Occasional turbidites occur in ridge sediments but these must be of entirely local origin. The ridge sediments include frequent layers of "cottage cheese" texture made up of what appear to be small, angular mud clasts of a variety of colors.

(Figure 2) Stratigraphic distribution of Schizosphaerella in DSDP Hole 79-547B

The Jurassic (hemi)pelagic continental margin deposits drilled at Hole 547B, off the Moroccan coast, reveal striking Tethyan affinity. Analogies concern not only types and gross vertical evolution of facies, but also composition and textures of the fine sediment and the pattern of diagenetic alteration. In this context, the occurrence of the nanno-organism Schizosphaerella Deflandre and Dangeard (sometimes as a conspicuous portion of the fine-grained carbonate fraction) is of particular interest. Schizosphaerella, an incertae sedis taxon, has been widely recorded as a sediment contributor from Tethyan Jurassic deeper-water carbonate facies exposed on land. Because of its extremely long range (Hettangian to early Kimmeridgian), the genus Schizosphaerella (two species currently described, S. punctulata Deflandre and Dangeard and S. astrea Moshkovitz) is obviously not of great biostratigraphic interest. However, it is of interest in sedimentology and petrology. Specifically, Schizosphaerella was often the only component of the initial fine-grained fraction of a sediment that was able to resist diagenetic obliteration. However, alteration of the original skeletal structure did occur to various degrees. Crystal habit and mineralogy of the fundamental skeletal elements, as well as their mode of mutual arrangement in the test wall with the implied high initial porosity of the skeleton (60-70%), appear to be responsible for this outstanding resistance. Moreover, the ability to concentrate within and, in the case of the species S. punctulata, around the skeleton, large amounts of diagenetic calcite also contributed to the resistance. In both species of Schizosphaerella, occlusion of the original skeletal void space during diagenesis appears to have proceeded in an analogous manner, with an initial slight uniform syntaxial enlargement of the basic lamellar skeletal crystallites followed, upon mutual impingement, by uneven accretion of overgrowth cement in the remaining skeletal voids. However, distinctive fabrics are evident according to the different primary test wall architecture. In S. punctulata, intraskeletal cementation is usually followed by the growth of a radially structured crust of bladed to fibrous calcite around the valves. These crusts are interpreted as a product of aggrading neomorphism, associated with mineralogic stabilization of the original, presumably polyphase, sediment. Data from Hole 547B, along with inferences, drawn from the fabric relationships, suggest that the crusts formed and (inferentially) mineralogic stabilization occurred at a relatively early time in the diagenetic history in the shallow burial realm. An enhanced rate of lithification at relatively shallow burial depths and thus the chance for neomorphism to significantly influence the textural evolution of the buried sediment may be related to a lower Mg/Ca concentration ratio in the oceanic system and, hence, in marine pore waters in pre-Late Jurassic times.

Geochemistry of Chixulub ejecta in ODP Leg 207 holes

An up to 2-cm thick Chicxulub ejecta deposit marking the Cretaceous-Paleogene (K-Pg) boundary (the "K-T" boundary) was recovered in six holes drilled during ODP Leg 207 (Demerara Rise, tropical western Atlantic). Stunning features of this deposit are its uniformity over an area of 30 km2 and the total absence of bioturbation, allowing documentation of the original sedimentary sequence. High-resolution mineralogical, petrological, elemental, isotopic (Sr-Nd), and rock magnetic data reveal a distinct microstratigraphy and a range of ejecta components. The deposit is normally graded and composed predominantly of rounded, 0.1- to max. 1-mm sized spherules. Spherules are altered to dioctahedral aluminous smectite, though occasionally relict Si-Al-rich hydrated glass is also present, suggesting acidic precursor lithologies. Spherule textures vary from hollow to vesicle-rich to massive; some show in situ collapse, others include distinct Fe-Mg-Ca-Ti-rich melt globules and lath-shaped Al-rich quench crystals. Both altered glass spherules and the clay matrix (Site 1259B) display strongly negative epsilon-Nd (T=65Ma) values (-17) indicating uptake of Nd from contemporaneous ocean water during alteration. Finally, Fe-Mg-rich spherules, shocked quartz and feldspar grains, few lithic clasts, as well as abundant accretionary and porous carbonate clasts are concentrated in the uppermost 0.5-0.7 mm of the deposit. The carbonate clasts display in part very unusual textures, which are interpreted to be of shock-metamorphic origin. The preservation of delicate spherule textures, normal grading with lack of evidence for traction transport, and sub-millimeter scale compositional trends provide evidence for this spherule deposit representing a primary air-fall deposit not affected by significant reworking. The ODP Leg 207 spherule deposit is the first known dual-layer K-Pg boundary in marine settings; it incorporates compositional and stratigraphic aspects of both proximal and distal marine sites. Its stratigraphy strongly resembles the dual-layer K-Pg boundary deposits in the terrestrial Western Interior of North America (although there carbonate phases are not preserved). The occurrence of a dual ejecta layer in these quite different sedimentary environments - separated by several thousands of kilometers - provides additional evidence for an original sedimentary sequence. Therefore, the layered nature of the deposit may document compositional differences between ballistic Chicxulub ejecta forming the majority of the spherule deposit, and material falling out from the vapor (ejecta) plume, which is concentrated in the uppermost part.

Carbon14 ages of surface sediment samples from ther Persian Gulf

A simplified classification of the Holocene sediments based on textures and grain type results in fourteen major units, twelve of which are essentially carbonate in composition. A brief description and photographic illustration of these units, together with the sedimentary and diagenetic processes which have contributed to their formation, is designed to give the reader a broad but valid impression of Persian Gulf sediments. The distribution of the fourteen sediment units throughout the Arabian parts of the basin, although complicated by numerous local bathymetric highs and depressions, is relatively simple. Because the Arabian sea floor slopes progressively from a windward shoreline to the basin center there is increasing protection from wave action towards the center of the basin. As a result sediments grade from skeletal, oolitic and pelletoidal sands (and muds in coastal lagoons) and fringing reefs, through an irregular zone of compound grain sands,into widespread skeletal muddy sands, and finally into basin center muds. These simple relationships vary laterally around the Arabian side of the gulf. Lateral variation is dependant upon orientation of the regional slope with respect to the prevailing NW wind-driven waves, angle of slope, and presence or absence of regional, structurally based barriers.

Age determination on monazite from Forefinger Point granulites, East Antarctica (Table 2.6-1)

Electron microprobe (EMP) dating on monazite in granulite- facies rocks from Forefinger Point, East Antarctica, yielded dominant ages of 500 Ma on matrix monazites.They are associated with secondary cordierite, biotite and sapphirine, formed during nearly isothermal decompression after the high P-T assemblages involving garnet, orthopyroxene and sillimanite. Older ages around 750-1000 Ma are detected in monazite cores and in monazite inclusions in garnet porphyroblast. Combining the available age data and the reaction textures, it becomes evident that the Forefinger Point granulites have been overprinted by a granulite-facies decompressional event of Pan-African age. Moreover, EMP monazite dating imply that the Forefinger Point granulites have experienced at least two stages of metamorphic evolution.

Quartz grain microtextures of sediments from ODP Hole 188-1166A (Table 1)

This paper presents the results of the scanning electron microscopic (SEM) analysis of quartz grains from a selection of samples at Site 1166. Ocean Drilling Program Leg 188 drilled Site 1166 on the Prydz Bay continental shelf, Antarctica, to document onset and fluctuations of East-Antarctic glaciation. This site recovered Upper Pliocene-Holocene glacial sediments directly above Cretaceous through Lower Oligocene sediments recording the transition from preglacial to early glacial conditions. SEM analysis of quartz grains at Site 1166 was used to characterize the glacial and preglacial sediments by their diagnostic textures. Angular edges, edge abrasion as well as arcuate to straight steps, are the most frequent features in glacial deposits. The highest frequency of grains with round edges is present in Middle-Late Eocene fluvio-deltaic sands. However, angular outlines, fractured plates with subparallel linear fractures and edge abrasion indicating glacier influence are also present. Preglacial carbonaceous mudstone and laminated gray claystone show distinctive high relief quartz grains and some chemical weathering on grain surfaces. The results of the microtextural analysis of quartz grains are used to verify some critical periods of ice sheet evolution, such as the transition from the East Antarctic preglacial to glacial conditions on the continental shelf from Middle/Late Eocene to Late Eocene/Early Oligocene time.