Equivalence of piecewise-linear approximation and Lagrangian relaxation for network revenue management

The network revenue management (RM) problem arises in airline, hotel, media,and other industries where the sale products use multiple resources. It can be formulatedas a stochastic dynamic program but the dynamic program is computationallyintractable because of an exponentially large state space, and a number of heuristicshave been proposed to approximate it. Notable amongst these -both for their revenueperformance, as well as their theoretically sound basis- are approximate dynamic programmingmethods that approximate the value function by basis functions (both affinefunctions as well as piecewise-linear functions have been proposed for network RM)and decomposition methods that relax the constraints of the dynamic program to solvesimpler dynamic programs (such as the Lagrangian relaxation methods). In this paperwe show that these two seemingly distinct approaches coincide for the network RMdynamic program, i.e., the piecewise-linear approximation method and the Lagrangianrelaxation method are one and the same.

Relaxation methods for solving linear inequality systems: Converging results

The problem of finding a feasible solution to a linear inequality system arises in numerous contexts. In [12] an algorithm, called extended relaxation method, that solves the feasibility problem, has been proposed by the authors. Convergence of the algorithm has been proven. In this paper, we onsider a class of extended relaxation methods depending on a parameter and prove their convergence. Numerical experiments have been provided, as well.

A Lagrangian relaxation approach to a coupled lot-sizing and cutting stock problem

Industrial production processes involving both lot-sizing and cutting stock problems are common in many industrial settings. However, they are usually treated in a separate way, which could lead to costly production plans. In this paper, a coupled mathematical model is formulated and a heuristic method based on Lagrangian relaxation is proposed. Computational results prove its effectiveness. (C) 2009 Elsevier B.V. All rights reserved.

A Lagrangian relaxation approach to a coupled lot-sizing and cutting stock problem

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

An active/reactive predispatch model incorporating ramp rate constraints solved by dual decomposition/lagrangian relaxation

The Predispatch model (PD) calculates a short-term generation policy for power systems. In this work a PD model is proposed that improves two modeling aspects generally neglected in the literature: voltage/reactive power constraints and ramp rate constraints for generating units. Reactive power constraints turn the PD into a non-linear problem and the ramp rate constraints couple the problem dynamically in time domain. The solution of the PD is turned into a harder task when such constraints are introduced. The dual decomposition/ lagrangian relaxation technique is used in the solution approach for handing dynamic constraints. As a result the PD is decomposed into a series of independent Optimal Power Flow (FPO) sub problems, in which the reactive power is represented in detail. The solution of the independent FPO is coordinated by means of Lagrange multipliers, so that dynamic constraints are iteratively satisfied. Comparisons between dispatch policies calculated with and without the representation of ramp rate constraints are performed, using the IEEE 30 bus test system. The results point-out the importance of representing such constraints in the generation dispatch policy. © 2004 IEEE.

Oxygen mobility in Bi:Sr:Ca:Cu:O ceramic measured using anelastic relaxation methods

Since the discovery of YBaCuO, experiments have shown that its superconducting properties are strongly affected by the oxygen content. More recently, anelastic relaxation measurements in La2CuO4+δ, showed that the decrease in the oxygen content can be related to two events. One is the decrease in mobility between two adjacent CuO planes, and the other is the increase in the number of tilting patterns of the CuO6 octahedra. In the case of the bismuth-based ceramic, it is known that the oxygen content, within some limits, does not affect its superconducting properties. In order to evaluate the mobility and the effect of the oxygen content on this material we have prepared BSCCO ceramic and tested regarding its internal friction and electrical resistivity as a function of the temperature while the oxygen content was being reduced by a sequence of vacuum annelaing at 620 K. The samples were prepared in the Bi:Sr:Ca:Cu = 2212 and 2223 proportion, using powder obtained by the sol-gel route and conventional solid state reaction. The anelastic relaxation measurements were performed using a torsion pendulum operating with frequency about 15-35 Hz between 77 to 700 K. The diffraction pattern of the as sintered and the vacuum annealed material were also presented. The results have shown complex anelastic relaxation structures that were associated to the jump of interstitial oxygen atoms between two adjacent CuO planes. The vacuum annealing showed to be deleterious to the critical temperature of the superconducting ceramic.

Long-Range Pollution Transport: Trans-Atlantic Mechanisms and Lagrangian Modeling Methods

Over the past several decades, it has become apparent that anthropogenic activities have resulted in the large-scale enhancement of the levels of many trace gases throughout the troposphere. More recently, attention has been given to the transport pathway taken by these emissions as they are dispersed throughout the atmosphere. The transport pathway determines the physical characteristics of emissions plumes and therefore plays an important role in the chemical transformations that can occur downwind of source regions. For example, the production of ozone (O3) is strongly dependent upon the transport its precursors undergo. O3 can initially be formed within air masses while still over polluted source regions. These polluted air masses can experience continued O3 production or O3 destruction downwind, depending on the air mass's chemical and transport characteristics. At present, however, there are a number of uncertainties in the relationships between transport and O3 production in the North Atlantic lower free troposphere. The first phase of the study presented here used measurements made at the Pico Mountain observatory and model simulations to determine transport pathways for US emissions to the observatory. The Pico Mountain observatory was established in the summer of 2001 in order to address the need to understand the relationships between transport and O3 production. Measurements from the observatory were analyzed in conjunction with model simulations from the Lagrangian particle dispersion model (LPDM), FLEX-PART, in order to determine the transport pathway for events observed at the Pico Mountain observatory during July 2003. A total of 16 events were observed, 4 of which were analyzed in detail. The transport time for these 16 events varied from 4.5 to 7 days, while the transport altitudes over the ocean ranged from 2-8 km, but were typically less than 3 km. In three of the case studies, eastward advection and transport in a weak warm conveyor belt (WCB) airflow was responsible for the export of North American emissions into the FT, while transport in the FT was governed by easterly winds driven by the Azores/Bermuda High (ABH) and transient northerly lows. In the fourth case study, North American emissions were lofted to 6-8 km in a WCB before being entrained in the same cyclone's dry airstream and transported down to the observatory. The results of this study show that the lower marine FT may provide an important transport environment where O3 production may continue, in contrast to transport in the marine boundary layer, where O3 destruction is believed to dominate. The second phase of the study presented here focused on improving the analysis methods that are available with LPDMs. While LPDMs are popular and useful for the analysis of atmospheric trace gas measurements, identifying the transport pathway of emissions from their source to a receptor (the Pico Mountain observatory in our case) using the standard gridded model output, particularly during complex meteorological scenarios can be difficult can be difficult or impossible. The transport study in phase 1 was limited to only 1 month out of more than 3 years of available data and included only 4 case studies out of the 16 events specifically due to this confounding factor. The second phase of this study addressed this difficulty by presenting a method to clearly and easily identify the pathway taken by only those emissions that arrive at a receptor at a particular time, by combining the standard gridded output from forward (i.e., concentrations) and backward (i.e., residence time) LPDM simulations, greatly simplifying similar analyses. The ability of the method to successfully determine the source-to-receptor pathway, restoring this Lagrangian information that is lost when the data are gridded, is proven by comparing the pathway determined from this method with the particle trajectories from both the forward and backward models. A sample analysis is also presented, demonstrating that this method is more accurate and easier to use than existing methods using standard LPDM products. Finally, we discuss potential future work that would be possible by combining the backward LPDM simulation with gridded data from other sources (e.g., chemical transport models) to obtain a Lagrangian sampling of the air that will eventually arrive at a receptor.

The approximate numerical solution of boundary value problems by relaxation methods,

"Contract N7 onr-358, T. O. I., NR-041-032."

Lagrangian-informed mixed integer programming reformulations

La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques.

Hybrid methods for lot sizing on parallel machines

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Activation of beta(2)-adrenergic receptors hastens relaxation and mediates phosphorylation of phospholamban, troponin I, and C-protein in ventricular myocardium from patients with terminal heart failure

Background-Catecholamines hasten cardiac relaxation through beta-adrenergic receptors, presumably by phosphorylation of several proteins, but it is unknown which receptor subtypes are involved in human ventricle. We assessed the role of beta(1)- and beta(2)-adrenergic receptors in phosphorylating proteins implicated in ventricular relaxation. Methods and Results-Right ventricular trabeculae, obtained from freshly explanted hearts of patients with dilated cardiomyopathy (n=5) or ischemic cardiomyopathy (n=5), were paced at 60 bpm. After measurement of the contractile and relaxant effects of epinephrine (10 mu mol/L) or zinterol (10 mu mol/L), mediated through beta(2)-adrenergic receptors, and of norepinephrine (10 mu mol/L), mediated through beta(1)-adrenergic receptors, tissues were freeze clamped. We assessed phosphorylation of phospholamban, troponin I, and C-protein, as well as specific phosphorylation of phospholamban at serine 16 and threonine 17, Data did not differ between the 2 disease groups and were therefore pooled. Epinephrine, zinterol, and norepinephrine increased contractile force to approximately the same extent, hastened the onset of relaxation by 15+/-3%, 5+/-2%, and 20+/-3%, respectively, and reduced the time to half-relaxation by 26+/-3%, 21+/-3%, and 37+/-3%. These effects of epinephrine, zinterol, and norepinephrine were associated with phosphorylation (pmol phosphate/mg protein) of phospholamban 14+/-3, 12+/-4, and 12+/-3, troponin I 40+/-7, 33+/-7, and 31+/-6; and C-protein 7.2+/-1.9, 9.3 +/- 1.4, and 7.5 +/- 2.0. Phosphorylation of phospholamban occurred at both Ser16 and Thr17 residues through both beta(1)- and beta(2)-adrenergic receptors. Conclusions-Norepinephrine and epinephrine hasten human ventricular relaxation and promote phosphorylation of implicated proteins through both beta(1)- and beta(2)-adrenergic receptors, thereby potentially improving diastolic function.

Endothelium-dependent relaxation in response to poly-L-arginine in canine coronary arteries: implications about hyperpolarization as a mechanism of vasodilatation

OBJECTIVE: To study the mechanism by which poly-L-arginine mediates endothelium-dependent relaxation. METHODS: Vascular segments with and without endothelium were suspended in organ chambers filled with control solution maintained at 37ºC and bubbled with 95% O2 / 5% CO2. Used drugs: indomethacin, acetycholine, EGTA, glybenclamide, ouabain, poly-L-arginine, methylene blue, N G-nitro-L-arginine, and verapamil and N G-monomethyl-L-arginine. Prostaglandin F2á and potassium chloride were used to contract the vascular rings. RESULTS: Poly-L-arginine (10-11 to 10-7 M) induced concentration-dependent relaxation in coronary artery segments with endothelium. The relaxation to poly-L-arginine was attenuated by ouabain, but was unaffected by glybenclamide. L-NOARG and oxyhemoglobin caused attenuation, but did not abolish this relaxation. Also, the relaxations was unaffected by methylene blue, verapamil, or the presence of a calcium-free bathing medium. The endothelium-dependent to poly-L-arginine relaxation was abolished only in vessels contracted with potassium chloride (40 mM) in the presence of L-NOARG and indomethacin. CONCLUSION: These experiments indicate that poly-L-arginine induces relaxation independent of nitric oxide.

On bounds for network revenue management

The Network Revenue Management problem can be formulated as a stochastic dynamic programming problem (DP or the\optimal" solution V *) whose exact solution is computationally intractable. Consequently, a number of heuristics have been proposed in the literature, the most popular of which are the deterministic linear programming (DLP) model, and a simulation based method, the randomized linear programming (RLP) model. Both methods give upper bounds on the optimal solution value (DLP and PHLP respectively). These bounds are used to provide control values that can be used in practice to make accept/deny decisions for booking requests. Recently Adelman [1] and Topaloglu [18] have proposed alternate upper bounds, the affine relaxation (AR) bound and the Lagrangian relaxation (LR) bound respectively, and showed that their bounds are tighter than the DLP bound. Tight bounds are of great interest as it appears from empirical studies and practical experience that models that give tighter bounds also lead to better controls (better in the sense that they lead to more revenue). In this paper we give tightened versions of three bounds, calling themsAR (strong Affine Relaxation), sLR (strong Lagrangian Relaxation) and sPHLP (strong Perfect Hindsight LP), and show relations between them. Speciffically, we show that the sPHLP bound is tighter than sLR bound and sAR bound is tighter than the LR bound. The techniques for deriving the sLR and sPHLP bounds can potentially be applied to other instances of weakly-coupled dynamic programming.

Dynamic Facility Location with Modular Capacities : Models, Algorithms and Applications in Forestry

Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable.

A coupling cutting stock-lot sizing problem in the paper industry

An important production programming problem arises in paper industries coupling multiple machine scheduling with cutting stocks. Concerning machine scheduling: how can the production of the quantity of large rolls of paper of different types be determined. These rolls are cut to meet demand of items. Scheduling that minimizes setups and production costs may produce rolls which may increase waste in the cutting process. On the other hand, the best number of rolls in the point of view of minimizing waste may lead to high setup costs. In this paper, coupled modeling and heuristic methods are proposed. Computational experiments are presented.