An exact algorithm for the capacitated shortest spanning arborescence

We are given a complete and loop-free digraphG=(V, A), whereV={1,...,n} is the vertex set,A={(i, j) :i, j V} the arc set, andr V is a distinguishedroot vertex. For each arc (i, j) A, letc _ij be the associatedcost, and for each vertexi, letq _i 0 be the associateddemand (withq _r =0). Moreover, a nonnegativebranch capacity, Q, is defined.A Capacitated Shortest Spanning Arborescence rooted at r (CSSA _r ) is a minimum cost partial digraph such that: (i) each vertexj r has exactly one entering arc; (ii) for each vertexj r, a path fromr toj exists; (iii) for each branch leaving vertexr, the total demand of the vertices does not exceed the branch capacity,Q. A variant of theCSSA _r problem (calledD-CSSA _r ) arises when the out-degree of the root vertex is constrained to be equal to a given valueD. These problems are strongly NP-hard, and find practical applications in routing and network design. We describe a new Lagrangian lower bound forCSSA _r andD-CSSA _r problems, strengthened in a cutting plane fashion by iteratively adding violated constraints to the Lagrangian problem. We also present a new lower bound based on projection leading to the solution of min-cost flow problems. The two lower bounds are then combined so as to obtain an overall additive lower bounding procedure. The additive procedure is then imbedded in a branch-and-bound algorithm whose performance is enhanced by means of reduction procedures, dominance criteria, feasibility checks and upper bounding. Computational tests on asymmetric and symmetric instances from the literature, involving up to 200 vertices, are given, showing the effectiveness of the proposed approach.     

A multi-start algorithm for a balanced real-world Open Vehicle Routing Problem

The aim of this paper is to solve a real-world problem proposed by an international company operating in Spain and modeled as a variant of the Open Vehicle Routing Problem in which the makespan, i.e., the maximum time spent on the vehicle by one person, must be minimized. A competitive multi-start algorithm, able to obtain high quality solutions within reasonable computing time is proposed. The effectiveness of the algorithm is analyzed through computational testing on a set of 19 school-bus routing benchmark problems from the literature, and on 9 hard real-world problem instances.     

Unambiguous Stereochemical Assignment of Cyclo(Phe-Pro), Cyclo(Leu-Pro), and Cyclo(Val-Pro) by Electronic Circular Dichroic Spectroscopy

2,5-diketopiperazines (DKPs) are cyclic dipeptides ubiquitously found in nature. In particular, cyclo(Phe-Pro), cyclo(Leu-Pro), and cyclo(Val-Pro) are frequently detected in many microbial cultures. Each of these DKPs has four possible stereoisomers due to the presence of two chirality centers. However, absolute configurations of natural DKPs are often ambiguous due to the lack of a simple, sensitive, and reproducible method for stereochemical assignment. This is an important problem because stereochemistry is a key determinant of biological activity. Here, we report a synthetic DKP library containing all stereoisomers of cyclo(Phe-Pro), cyclo(Leu-Pro), and cyclo(Val-Pro). The library was subjected to spectroscopic characterization using mass spectrometry, NMR, and electronic circular dichroism (ECD). It turned out that ECD can clearly differentiate DKP stereoisomers. Thus, our ECD dataset can serve as a reference for unambiguous stereochemical assignment of cyclo(Phe-Pro), cyclo(Leu-Pro), and cyclo(Val-Pro) samples from natural sources. The DKP library was also subjected to a biological screening using assays for E. coli growth and biofilm formation, which revealed distinct biological effects of cyclo(D-Phe-L-Pro).     

A Higher-Order Internal Wave Model Accounting for Large Bathymetric Variations

A higher-order strongly nonlinear model is derived to describe the evolution of large amplitude internal waves over arbitrary bathymetric variations in a two-layer system where the upper layer is shallow while the lower layer is comparable to the characteristic wavelength. The new system of nonlinear evolution equations with variable coefficients is a generalization of the deep configuration model proposed by Choi and Camassa [ 1 ] and accounts for both a higher-order approximation to pressure coupling between the two layers and the effects of rapidly varying bottom variation. Motivated by the work of Rosales and Papanicolaou [ 2 ], an averaging technique is applied to the system for weakly nonlinear long internal waves propagating over periodic bottom topography. It is shown that the system reduces to an effective Intermediate Long Wave (ILW) equation, in contrast to the Korteweg-de Vries (KdV) equation derived for the surface wave case.     

Magnesium hydroperoxyacetate (MHPA) and magnesium dihydroperoxide (MDHP): New antibacterial agents for fibrous substrates

Water-dispersable products have been prepared from the reaction of magnesium acetate tetrahydrate with hydrogen peroxide at mole ratios of 1 : 2 to 1 : 40 to produce compositions with active oxygen or peroxide contents of 1–30%. The products are believed to be stoichiometric mixtures of HOO Mg OAc and HOO Mg OOH that vary in composition with the molar ratios used. These new compounds are hydrolytically stable at ambient temperatures for extended periods (at least 60 days) and thermally stable below 300°C. Pad-cure processes are described for applying the above reaction products as a dispersion in water or aqueous hydrogen peroxide or as a foam in aqueous hydrogen peroxide to impart antibacterial activity to celulosics, synthetic fibers and fiber blends. The textiles are treated with dispersions or foam containing 10–17% of the reaction products derived from mole ratios of 1 : 2 to 1 : 40 magnesium acetate tetrahydrate: hydrogen peroxide. On subsequent heating for 2–4 min at 120–150°C, washing and drying, the modified textiles contain durably bound active oxygen or peroxide (0.1–1.7%) that has activity against representative gram-positive and gramnegative bacteria for up to 50 launderings.     

A tabu search algorithm for the Open Shop problem

In this paper we consider the minimum makespan Open Shop problem without preemption. It is well-known that the case with only two machines can be optimally solved in linear time, whereas the problem with an arbitrary number of machines is NP-hard in the strong sense. We propose a tabu search algorithm for the solution of the problem which uses simple list scheduling algorithms to build the starting solutions. The algorithm is extensively tested on randomly generated instances.     

Algorithms for railway crew management

Crew management is concerned with building the work schedules of crews needed to cover a planned timetable. This is a well-known problem in Operations Research and has been historically associated with airlines and mass-transit companies. More recently, railway applications have also come on the scene, especially in Europe. In practice, the overall crew management problem is decomposed into two subproblems, called crew scheduling and crew rostering. In this paper, we give an outline of different ways of modeling the two subproblems and possible solution methods. Two main solution approaches are illustrated for real-world applications. In particular we discuss in some detail the solution techniques currently adopted at the Italian railway company, Ferrovie dello Stato SpA, for solving crew scheduling and rostering problems.