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.

The berth allocation problem at port terminals : a column generation framework

Le problème d'allocation de postes d'amarrage (PAPA) est l'un des principaux problèmes de décision aux terminaux portuaires qui a été largement étudié. Dans des recherches antérieures, le PAPA a été reformulé comme étant un problème de partitionnement généralisé (PPG) et résolu en utilisant un solveur standard. Les affectations (colonnes) ont été générées a priori de manière statique et fournies comme entrée au modèle %d'optimisation. Cette méthode est capable de fournir une solution optimale au problème pour des instances de tailles moyennes. Cependant, son inconvénient principal est l'explosion du nombre d'affectations avec l'augmentation de la taille du problème, qui fait en sorte que le solveur d'optimisation se trouve à court de mémoire. Dans ce mémoire, nous nous intéressons aux limites de la reformulation PPG. Nous présentons un cadre de génération de colonnes où les affectations sont générées de manière dynamique pour résoudre les grandes instances du PAPA. Nous proposons un algorithme de génération de colonnes qui peut être facilement adapté pour résoudre toutes les variantes du PAPA en se basant sur différents attributs spatiaux et temporels. Nous avons testé notre méthode sur un modèle d'allocation dans lequel les postes d'amarrage sont considérés discrets, l'arrivée des navires est dynamique et finalement les temps de manutention dépendent des postes d'amarrage où les bateaux vont être amarrés. Les résultats expérimentaux des tests sur un ensemble d'instances artificielles indiquent que la méthode proposée permet de fournir une solution optimale ou proche de l'optimalité même pour des problème de très grandes tailles en seulement quelques minutes.

A heuristic algorithm for the Capacitated Vehicle Routing Problem with Synchronized Pick-ups and Drop-offs : a case study for medications delivery and supervision in DR Congo

Dans des contextes de post-urgence tels que le vit la partie occidentale de la République Démocratique du Congo (RDC), l’un des défis cruciaux auxquels font face les hôpitaux ruraux est de maintenir un niveau de médicaments essentiels dans la pharmacie. Sans ces médicaments pour traiter les maladies graves, l’impact sur la santé de la population est significatif. Les hôpitaux encourent également des pertes financières dues à la péremption lorsque trop de médicaments sont commandés. De plus, les coûts du transport des médicaments ainsi que du superviseur sont très élevés pour les hôpitaux isolés ; les coûts du transport peuvent à eux seuls dépasser ceux des médicaments. En utilisant la province du Bandundu, RDC pour une étude de cas, notre recherche tente de déterminer la faisabilité (en termes et de la complexité du problème et des économies potentielles) d’un problème de routage synchronisé pour la livraison de médicaments et pour les visites de supervision. Nous proposons une formulation du problème de tournées de véhicules avec capacité limitée qui gère plusieurs exigences nouvelles, soit la synchronisation des activités, la préséance et deux fréquences d’activités. Nous mettons en œuvre une heuristique « cluster first, route second » avec une base de données géospatiales qui permet de résoudre le problème. Nous présentons également un outil Internet qui permet de visualiser les solutions sur des cartes. Les résultats préliminaires de notre étude suggèrent qu’une solution synchronisée pourrait offrir la possibilité aux hôpitaux ruraux d’augmenter l’accessibilité des services médicaux aux populations rurales avec une augmentation modique du coût de transport actuel.

Assessment of PEG on Polymeric Particles Surface, a Key Step in Drug Carrier Translation

Injectable drug nanocarriers have greatly benefited in their clinical development from the addition of a superficial hydrophilic corona to improve their cargo pharmacokinetics. The most studied and used polymer for this purpose is poly(ethylene glycol), PEG. However, in spite of its wide use for over two decades now, there is no general consensus on the optimum PEG chain coverage-density and size required to escape from the mononuclear phagocyte system and to extend the circulation time. Moreover, cellular uptake and active targeting may have conflicting requirements in terms of surface properties of the nanocarriers which complicates even more the optimization process. These persistent issues can be largely attributed to the lack of straightforward characterization techniques to assess the coverage-density, the conformation or the thickness of a PEG layer grafted or adsorbed on a particulate drug carrier and is certainly one of the main reasons why so few clinical applications involving PEG coated particle-based drug delivery systems are under clinical trial so far. The objective of this review is to provide the reader with a brief description of the most relevant techniques used to assess qualitatively or quantitatively PEG chain coverage-density, conformation and layer thickness on polymeric nanoparticles. Emphasis has been made on polymeric particle (solid core) either made of copolymers containing PEG chains or modified after particle formation. Advantages and limitations of each technique are presented as well as methods to calculate PEG coverage-density and to investigate PEG chains conformation on the NP surface.

A Coupled 2 × 2D Babcock–Leighton Solar Dynamo Model. I. Surface Magnetic Flux Evolution

The need for reliable predictions of the solar activity cycle motivates the development of dynamo models incorporating a representation of surface processes sufficiently detailed to allow assimilation of magnetographic data. In this series of papers we present one such dynamo model, and document its behavior and properties. This first paper focuses on one of the model's key components, namely surface magnetic flux evolution. Using a genetic algorithm, we obtain best-fit parameters of the transport model by least-squares minimization of the differences between the associated synthetic synoptic magnetogram and real magnetographic data for activity cycle 21. Our fitting procedure also returns Monte Carlo-like error estimates. We show that the range of acceptable surface meridional flow profiles is in good agreement with Doppler measurements, even though the latter are not used in the fitting process. Using a synthetic database of bipolar magnetic region (BMR) emergences reproducing the statistical properties of observed emergences, we also ascertain the sensitivity of global cycle properties, such as the strength of the dipole moment and timing of polarity reversal, to distinct realizations of BMR emergence, and on this basis argue that this stochasticity represents a primary source of uncertainty for predicting solar cycle characteristics.

Metabolomics analysis in rats with thiamine deficiency identifies key metabolites in vulnerable brain regions and suggests neural stem progenitor cells play a role in ameliorating metabolic dysfunction

La documentation scientifique fait état de la présence, chez l’adulte, de cellules souches et progénitrices neurales (CSPN) endogènes dans les zones sous-ventriculaire et sous-granulaire du cerveau ainsi que dans le gyrus denté de l’hippocampe. De plus, un postulat selon lequel il serait également possible de retrouver ce type de cellules dans la moelle épinière et le néocortex des mammifères adultes a été énoncé. L’encéphalopathie de Wernicke, un trouble neurologique grave toutefois réversible qui entraîne un dysfonctionnement, voire une défaillance du cerveau, est causée principalement par une carence importante en thiamine (CT). Des observations récentes laissent envisager que les facteurs en cause dans la prolifération et la différenciation des CSPN pourraient également jouer un rôle important lors d’un épisode de CT. L’hypothèse, selon laquelle l’identification de nouveaux métabolites entrant dans le mécanisme ou la séquence de réactions se soldant en une CT pourraient en faciliter la compréhension, a été émise au moyen d'une démarche en cours permettant d’établir le profil des modifications métaboliques qui surviennent en de telles situations. Cette approche a été utilisée pour constater les changements métaboliques survenus au niveau du foyer cérébral dans un modèle de rats déficients en thiamine (rats DT), particulièrement au niveau du thalamus et du colliculus inférieur (CI). La greffe de CSPN a quant à elle été envisagée afin d’apporter de nouvelles informations sur la participation des CSPN lors d’un épisode de CT et de déterminer les bénéfices thérapeutiques potentiels offerts par cette intervention. Les sujets de l’étude étaient répartis en quatre groupes expérimentaux : un premier groupe constitué de rats dont la CT était induite par la pyrithiamine (rats DTiP), un deuxième groupe constitué de rats-contrôles nourris ensemble (« pair-fed control rats » ou rats PFC) ainsi que deux groupes de rats ayant subi une greffe de CSPN, soit un groupe de rats DTiP greffés et un dernier groupe constitué de rats-contrôles (rats PFC) greffés. Les échantillons de foyers cérébraux (thalamus et CI) des quatre groupes de rats ont été prélevés et soumis à des analyses métabolomiques non ciblées ainsi qu’à une analyse visuelle par microscopie à balayage électronique (SEM). Une variété de métabolites-clés a été observée chez les groupes de rats déficients en thiamine (rats DTiP) en plus de plusieurs métabolites dont la documentation ne faisait pas mention. On a notamment constaté la présence d’acides biliaires, d’acide cynurénique et d’acide 1,9— diméthylurique dans le thalamus, alors que la présence de taurine et de carnosine a été observée dans le colliculus inférieur. L’étude a de plus démontré une possible implication des CSPN endogènes dans les foyers cérébraux du thalamus et du colliculus inférieur en identifiant les métabolites-clés ciblant les CSPN. Enfin, les analyses par SEM ont montré une amélioration notable des tissus à la suite de la greffe de CSPN. Ces constatations suggèrent que l’utilisation de CSPN pourrait s’avérer une avenue thérapeutique intéressante pour soulager la dégénérescence symptomatique liée à une grave carence en thiamine chez l’humain.

Array pattern nulling by element position perturbations using a genetic algorithm

A genetic algorithm has been used for null steering in phased and adaptive arrays . It has been shown that it is possible to steer the array null s precisely to the required interference directions and to achieve any prescribed null depths . A comparison with the results obtained from the analytic solution shows the advantages of using the genetic algorithm for null steering in linear array patterns

A Cryptosystem Using the Concepts of Algebraic Geometric Code

Cryptosystem using linear codes was developed in 1978 by Mc-Eliece. Later in 1985 Niederreiter and others developed a modified version of cryptosystem using concepts of linear codes. But these systems were not used frequently because of its larger key size. In this study we were designing a cryptosystem using the concepts of algebraic geometric codes with smaller key size. Error detection and correction can be done efficiently by simple decoding methods using the cryptosystem developed. Approach: Algebraic geometric codes are codes, generated using curves. The cryptosystem use basic concepts of elliptic curves cryptography and generator matrix. Decrypted information takes the form of a repetition code. Due to this complexity of decoding procedure is reduced. Error detection and correction can be carried out efficiently by solving a simple system of linear equations, there by imposing the concepts of security along with error detection and correction. Results: Implementation of the algorithm is done on MATLAB and comparative analysis is also done on various parameters of the system. Attacks are common to all cryptosystems. But by securely choosing curve, field and representation of elements in field, we can overcome the attacks and a stable system can be generated. Conclusion: The algorithm defined here protects the information from an intruder and also from the error in communication channel by efficient error correction methods.

Analysis and Optimization of Machining Process Using Evolutionary Algorithms

To ensure quality of machined products at minimum machining costs and maximum machining effectiveness, it is very important to select optimum parameters when metal cutting machine tools are employed. Traditionally, the experience of the operator plays a major role in the selection of optimum metal cutting conditions. However, attaining optimum values each time by even a skilled operator is difficult. The non-linear nature of the machining process has compelled engineers to search for more effective methods to attain optimization. The design objective preceding most engineering design activities is simply to minimize the cost of production or to maximize the production efficiency. The main aim of research work reported here is to build robust optimization algorithms by exploiting ideas that nature has to offer from its backyard and using it to solve real world optimization problems in manufacturing processes.In this thesis, after conducting an exhaustive literature review, several optimization techniques used in various manufacturing processes have been identified. The selection of optimal cutting parameters, like depth of cut, feed and speed is a very important issue for every machining process. Experiments have been designed using Taguchi technique and dry turning of SS420 has been performed on Kirlosker turn master 35 lathe. Analysis using S/N and ANOVA were performed to find the optimum level and percentage of contribution of each parameter. By using S/N analysis the optimum machining parameters from the experimentation is obtained.Optimization algorithms begin with one or more design solutions supplied by the user and then iteratively check new design solutions, relative search spaces in order to achieve the true optimum solution. A mathematical model has been developed using response surface analysis for surface roughness and the model was validated using published results from literature.Methodologies in optimization such as Simulated annealing (SA), Particle Swarm Optimization (PSO), Conventional Genetic Algorithm (CGA) and Improved Genetic Algorithm (IGA) are applied to optimize machining parameters while dry turning of SS420 material. All the above algorithms were tested for their efficiency, robustness and accuracy and observe how they often outperform conventional optimization method applied to difficult real world problems. The SA, PSO, CGA and IGA codes were developed using MATLAB. For each evolutionary algorithmic method, optimum cutting conditions are provided to achieve better surface finish.The computational results using SA clearly demonstrated that the proposed solution procedure is quite capable in solving such complicated problems effectively and efficiently. Particle Swarm Optimization (PSO) is a relatively recent heuristic search method whose mechanics are inspired by the swarming or collaborative behavior of biological populations. From the results it has been observed that PSO provides better results and also more computationally efficient.Based on the results obtained using CGA and IGA for the optimization of machining process, the proposed IGA provides better results than the conventional GA. The improved genetic algorithm incorporating a stochastic crossover technique and an artificial initial population scheme is developed to provide a faster search mechanism. Finally, a comparison among these algorithms were made for the specific example of dry turning of SS 420 material and arriving at optimum machining parameters of feed, cutting speed, depth of cut and tool nose radius for minimum surface roughness as the criterion. To summarize, the research work fills in conspicuous gaps between research prototypes and industry requirements, by simulating evolutionary procedures seen in nature that optimize its own systems.

Recurrence Quantification Analysis of System Signals for Detecting Tool and Chatter in Turning

In this thesis, the applications of the recurrence quantification analysis in metal cutting operation in a lathe, with specific objective to detect tool wear and chatter, are presented.This study is based on the discovery that process dynamics in a lathe is low dimensional chaotic. It implies that the machine dynamics is controllable using principles of chaos theory. This understanding is to revolutionize the feature extraction methodologies used in condition monitoring systems as conventional linear methods or models are incapable of capturing the critical and strange behaviors associated with the metal cutting process.As sensor based approaches provide an automated and cost effective way to monitor and control, an efficient feature extraction methodology based on nonlinear time series analysis is much more demanding. The task here is more complex when the information has to be deduced solely from sensor signals since traditional methods do not address the issue of how to treat noise present in real-world processes and its non-stationarity. In an effort to get over these two issues to the maximum possible, this thesis adopts the recurrence quantification analysis methodology in the study since this feature extraction technique is found to be robust against noise and stationarity in the signals.The work consists of two different sets of experiments in a lathe; set-I and set-2. The experiment, set-I, study the influence of tool wear on the RQA variables whereas the set-2 is carried out to identify the sensitive RQA variables to machine tool chatter followed by its validation in actual cutting. To obtain the bounds of the spectrum of the significant RQA variable values, in set-i, a fresh tool and a worn tool are used for cutting. The first part of the set-2 experiments uses a stepped shaft in order to create chatter at a known location. And the second part uses a conical section having a uniform taper along the axis for creating chatter to onset at some distance from the smaller end by gradually increasing the depth of cut while keeping the spindle speed and feed rate constant.The study concludes by revealing the dependence of certain RQA variables; percent determinism, percent recurrence and entropy, to tool wear and chatter unambiguously. The performances of the results establish this methodology to be viable for detection of tool wear and chatter in metal cutting operation in a lathe. The key reason is that the dynamics of the system under study have been nonlinear and the recurrence quantification analysis can characterize them adequately.This work establishes that principles and practice of machining can be considerably benefited and advanced from using nonlinear dynamics and chaos theory.

Algebraic Geometric Codes and their relation to Cryptography using Elliptic Curves

Communication is the process of transmitting data across channel. Whenever data is transmitted across a channel, errors are likely to occur. Coding theory is a stream of science that deals with finding efficient ways to encode and decode data, so that any likely errors can be detected and corrected. There are many methods to achieve coding and decoding. One among them is Algebraic Geometric Codes that can be constructed from curves. Cryptography is the science ol‘ security of transmitting messages from a sender to a receiver. The objective is to encrypt message in such a way that an eavesdropper would not be able to read it. A eryptosystem is a set of algorithms for encrypting and decrypting for the purpose of the process of encryption and decryption. Public key eryptosystem such as RSA and DSS are traditionally being prel‘en‘ec| for the purpose of secure communication through the channel. llowever Elliptic Curve eryptosystem have become a viable altemative since they provide greater security and also because of their usage of key of smaller length compared to other existing crypto systems. Elliptic curve cryptography is based on group of points on an elliptic curve over a finite field. This thesis deals with Algebraic Geometric codes and their relation to Cryptography using elliptic curves. Here Goppa codes are used and the curves used are elliptic curve over a finite field. We are relating Algebraic Geometric code to Cryptography by developing a cryptographic algorithm, which includes the process of encryption and decryption of messages. We are making use of fundamental properties of Elliptic curve cryptography for generating the algorithm and is used here to relate both.

Role of social pressure as a key contributor of materialism and related status consumption

“At resale stores I have seen brand new clothes with original price tag still hanging from the sleeve. Some children have so many toys that they stay frustrated, not knowing which one to pick up for their next amusement. Presumably sensible adults trade in perfectly good cars just to have something shinier and newer. Didn’t us once live productive normal lives, without all these gadgets” [Cunningham (2005)]. During late eighties, nearly forty four percent of the participants, who took part in a consumer survey conducted in the US, responded positively to the question “My closets are filled with still 2 unopened items” [Faber and O’Guinn (1988)]. Reading such excerpts does not greatly surprise us anymore; as such reports have become common now. For many people shopping has moved beyond something that caters to their needs and wants and has become a hobby [Cunningham (2005)], an activity that they engage in to satisfy their hedonistic or pleasure-seeking goals [Ramnathan and Menon(2006), O’Cass and McEween (2004), Faber and O’Guinn (1989)]. Others look at their new possession as something that fills a void in their lives [Belk (1985), Diener et al. (1993)].

Multi-objective assembly job shop scheduling using genetic algorithm and tabu search

Assembly job shop scheduling problem (AJSP) is one of the most complicated combinatorial optimization problem that involves simultaneously scheduling the processing and assembly operations of complex structured products. The problem becomes even more complicated if a combination of two or more optimization criteria is considered. This thesis addresses an assembly job shop scheduling problem with multiple objectives. The objectives considered are to simultaneously minimizing makespan and total tardiness. In this thesis, two approaches viz., weighted approach and Pareto approach are used for solving the problem. However, it is quite difficult to achieve an optimal solution to this problem with traditional optimization approaches owing to the high computational complexity. Two metaheuristic techniques namely, genetic algorithm and tabu search are investigated in this thesis for solving the multiobjective assembly job shop scheduling problems. Three algorithms based on the two metaheuristic techniques for weighted approach and Pareto approach are proposed for the multi-objective assembly job shop scheduling problem (MOAJSP). A new pairing mechanism is developed for crossover operation in genetic algorithm which leads to improved solutions and faster convergence. The performances of the proposed algorithms are evaluated through a set of test problems and the results are reported. The results reveal that the proposed algorithms based on weighted approach are feasible and effective for solving MOAJSP instances according to the weight assigned to each objective criterion and the proposed algorithms based on Pareto approach are capable of producing a number of good Pareto optimal scheduling plans for MOAJSP instances.

Fixed Point Decimal Multiplication Using RPS Algorithm

Decimal multiplication is an integral part of financial, commercial, and internet-based computations. A novel design for single digit decimal multiplication that reduces the critical path delay and area for an iterative multiplier is proposed in this research. The partial products are generated using single digit multipliers, and are accumulated based on a novel RPS algorithm. This design uses n single digit multipliers for an n × n multiplication. The latency for the multiplication of two n-digit Binary Coded Decimal (BCD) operands is (n + 1) cycles and a new multiplication can begin every n cycle. The accumulation of final partial products and the first iteration of partial product generation for next set of inputs are done simultaneously. This iterative decimal multiplier offers low latency and high throughput, and can be extended for decimal floating-point multiplication.

Message Integrity in the World Wide Web: Use of Nested Hash Function and a Fast Stream Cipher

The focus of this work is to provide authentication and confidentiality of messages in a swift and cost effective manner to suit the fast growing Internet applications. A nested hash function with lower computational and storage demands is designed with a view to providing authentication as also to encrypt the message as well as the hash code using a fast stream cipher MAJE4 with a variable key size of 128-bit or 256-bit for achieving confidentiality. Both nested Hash function and MAJE4 stream cipher algorithm use primitive computational operators commonly found in microprocessors; this makes the method simple and fast to implement both in hardware and software. Since the memory requirement is less, it can be used for handheld devices for security purposes.