The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational Study

The sample average approximation (SAA) method is an approach for solving stochastic optimization problems by using Monte Carlo simulation. In this technique the expected objective function of the stochastic problem is approximated by a sample average estimate derived from a random sample. The resulting sample average approximating problem is then solved by deterministic optimization techniques. The process is repeated with different samples to obtain candidate solutions along with statistical estimates of their optimality gaps.We present a detailed computational study of the application of the SAA method to solve three classes of stochastic routing problems. These stochastic problems involve an extremely large number of scenarios and first-stage integer variables. For each of the three problem classes, we use decomposition and branch-and-cut to solve the approximating problem within the SAA scheme. Our computational results indicate that the proposed method is successful in solving problems with up to 2¹⁶⁹⁴ scenarios to within an estimated 1.0% of optimality. Furthermore, a surprising observation is that the number of optimality cuts required to solve the approximating problem to optimality does not significantly increase with the size of the sample. Therefore, the observed computation times needed to find optimal solutions to the approximating problems grow only linearly with the sample size. As a result, we are able to find provably near-optimal solutions to these difficult stochastic programs using only a moderate amount of computation time.     

Jack van Lint (1932-2004): A survey of his scientific work

When Jack van Lint was appointed as full professor at the Eindhoven University of Technology at the age of 26 he combined a PhD in number theory with a very open scientific mind. It took a sabbatical visit to Bell Laboratories in 1966 to make him understand that a new and fascinating field of applied mathematics was emerging: discrete mathematics. It fascinated and inspired him for the rest of his life. When he passed away on September 28, 2004, he left behind a legacy of 18 books and 177 articles, covering many aspects of coding theory, combinatorics, and finite geometry.van Lint was also a strong international advocate of the role that discrete mathematics ought to play in modern applied mathematics curricula. Quite a few departments sought his advice. Years later, four different universities showed their appreciation by awarding him an honorary degree.This overview is an homage to van Lint's academic achievements and can serve as an introduction to his work for younger generations.     

Enolates de l'acetylacetate d'ethyle. Structure et reactivite du sel de potassium en presence d'ether couronne et de cryptand

It is shown that, through the addition of 18-crown-6 or cryptand (2.2.2) to potassium ethyl acetoacetate enolate solutions in tetrahydrofuran, 1:1 complexes are formed. A single crystal of the 1:1 potassium énolate-18-crown-6 complex has been obtained. Its structure has been determined by X-ray diffraction. The crystal includes entities formed from an enolate anion chelating a potassium cation externally complexed by the crown-ether. The vibrational spectrometry shows that the structure of the entity is kept in solution. In the species formed through the addition of cryptand (2.2.2), the enolate anion has a structure (IR spectroscopy) and a reactivity very close to that of the free anion, observed in a dissociating solvent (DMSO, HMPA). When crown ether is added, a contact ion pair is formed, in which the cation is externally solvated by the crown. On the other hand, the cation encapsulation by the cryptand leads to a released anion with an “ S-trans” or “W” structure. The reactivity and the orientation of the alkylation reactions of these entities have been measured in THF solutions. They are discussed in relation to the structure of the species present in the reaction medium.     

The determination of nickel, zinc, cobalt and manganese impurities in cadmium by pulse polarography

A pulse-polarographic method for the simultaneous determination of traces of nickel, zinc, cobalt and manganese in cadmium and its compounds is described. Interference from the reduction of the cadmium matrix was eliminated by a prior electrolytic deposition of cadmium on a mercury cathode at a controlled potential of –0.90 V vs. S.C.E. Iron in excess interfered with the determination of cobalt and was therefore extracted from the electrolysed solutions. The polarographic determination was performed in 0.1 M lithium acetate -0.025 M lithium thiocyanate as supporting electrolyte. A sample weight of 10 g and a final volume of 10 ml allowed the determination of about 0.08 p.p.m. nickel, 0.01 p.p.m. zinc, 0.02 p.p.m. cobalt and 0.003 p.p.m manganese. Less than 0.01 p.p.m. nickel could be determined with a 0.25 M pyridine 0.05 M potassium chloride supporting electrolyte. Several synthetic samples and commercially available cadmium products were analysed.     

The determination of traces of antimony,tin and arsenic in cadmium by pulse polarography

Traces of antimony, tin and arsenic in cadmium products were determined by pulse polarography. Arsenic was distilled, while antimony and tin were precipitated as hydroxides with manganese dioxide as carrier; some lead was coprecipitated with tin, hence these elements were further separated by distillation. In all cases quantitative recoveries were obtained. Antimony(III) was determined in a hydrochloric acid-sodium hypophosphite mixture, tin(IV) in a hydrochloric-hydrobromic acid mixture and arsenic(III) in sulphuric acid as supporting electrolytes; for arsenic(III), methylene blue had to be added. A sample weight of 10 g and an end volume of 10 ml allowed the determination down to about 0.004 p.p.m. antimony, 0.006 p.p.m. tin and 0.003 p.p.m. arsenic in cadmium. Several synthetic samples and commercially available cadmium products were analysed.     

Separation scheme for the determination of alkali metals (K, Rb, Cs), alkaline earths (Sr, Ba) and rare earths (Ce, Nd, Sm, Eu) in silicate materials by isotopic dilution analysis

A scheme is outlined for the separation of Li, K, Rb, Cs, Sr, Ba, Ce, Nd, Sm and Eu from silicate materials. The elements are separated by cation-exchange to provide groups suitable for mass spectrometric analysis, and are then further purified by anion-exchange. Results obtained by isotopic dilution analysis are reported for G-1, W-1, and the Harwell meteorite-in these measurements the alkali metals were determined separately from the other elements. Requirements are discussed for combining the procedures to form a more comprehensive method for use with a single sample.     

Electrochemical reduction of the lanthanide ions: Part II. Second reduction step of europium(III), ytterbium(III) and samarium(III) in acidic tetramethylammonium perchlorate solution

The second reduction step of Eu(III), Yb(III) and Sm(III) in 0.04 M tetramethylammonium perchlorate in the pH range 1.8–7 was investigated by cyclic voltammetry and d.c. polarography. The proposed reaction scheme at large hydrogen ion/lanthanide ion concentration ratios involves the reduction of the lanthanide(II) ion to the metallic state accompanied by a surface catalytic reaction in which the reactant is regenerated and also hydroxyl ions are formed which induces the precipitation of lanthanide(II) hydrous oxide on the electrode surface. This lanthanide(II) hydroxide is reduced at more negative potentials than the hydrated lanthanide(II) species. At lower hydrogen ion/lanthanide ion concentration ratios a preceding chemical reaction, probably involving hydrolyzed lanthanide(II) species, becomes rate determining.     

Organic Syntheses Without Solvent: Preparation of Alkoxyphthalimides and of Alkoxylamines

Alkoxyphthalimides are prepared by alkylation of N-hydroxyphthalimide under solid-liquid phase transfer catalysis without solvent. When conversion of alkoxyphthalimides into alkoxylamines is nearly complete, neat hydrazine hydrate is added at room temperature.