On parallel computing for stochastic optimization models and algorithms

167 p.

MPI parallel programming of mixed integer optimization problems using CPLEX with COIN-OR

The aim of this technical report is to present some detailed explanations in order to help to understand and use the Message Passing Interface (MPI) parallel programming for solving several mixed integer optimization problems. We have developed a C++ experimental code that uses the IBM ILOG CPLEX optimizer within the COmputational INfrastructure for Operations Research (COIN-OR) and MPI parallel computing for solving the optimization models under UNIX-like systems. The computational experience illustrates how can we solve 44 optimization problems which are asymmetric with respect to the number of integer and continuous variables and the number of constraints. We also report a comparative with the speedup and efficiency of several strategies implemented for some available number of threads.

Scenario Cluster Lagrangian Decomposition in two stage stochastic mixed 0-1 optimization

In this paper we introduce four scenario Cluster based Lagrangian Decomposition (CLD) procedures for obtaining strong lower bounds to the (optimal) solution value of two-stage stochastic mixed 0-1 problems. At each iteration of the Lagrangian based procedures, the traditional aim consists of obtaining the solution value of the corresponding Lagrangian dual via solving scenario submodels once the nonanticipativity constraints have been dualized. Instead of considering a splitting variable representation over the set of scenarios, we propose to decompose the model into a set of scenario clusters. We compare the computational performance of the four Lagrange multiplier updating procedures, namely the Subgradient Method, the Volume Algorithm, the Progressive Hedging Algorithm and the Dynamic Constrained Cutting Plane scheme for different numbers of scenario clusters and different dimensions of the original problem. Our computational experience shows that the CLD bound and its computational effort depend on the number of scenario clusters to consider. In any case, our results show that the CLD procedures outperform the traditional LD scheme for single scenarios both in the quality of the bounds and computational effort. All the procedures have been implemented in a C++ experimental code. A broad computational experience is reported on a test of randomly generated instances by using the MIP solvers COIN-OR and CPLEX for the auxiliary mixed 0-1 cluster submodels, this last solver within the open source engine COIN-OR. We also give computational evidence of the model tightening effect that the preprocessing techniques, cut generation and appending and parallel computing tools have in stochastic integer optimization. Finally, we have observed that the plain use of both solvers does not provide the optimal solution of the instances included in the testbed with which we have experimented but for two toy instances in affordable elapsed time. On the other hand the proposed procedures provide strong lower bounds (or the same solution value) in a considerably shorter elapsed time for the quasi-optimal solution obtained by other means for the original stochastic problem.

Algorithms for colour image processing based on neurological models

373 p. : il., gráf., fot., tablas

Reference Points Based on Dynamic Optimisation: A Versatil Algorithm for Mixed Fishery Management with Bio-economic Agestructured Models

Single-species management objectives may not be consistent within mixed fisheries. They may lead species to unsafe situations, promote discarding of over-quota and/or misreporting of catches. We provide an algorithm for characterising bio-economic reference points for a mixed fishery as the steady-state solution of a dynamic optimal management problem. The optimisation problem takes into account: i) that species are fishing simultaneously in unselective fishing operations and ii)intertemporal discounting and fleet costs to relate reference points to discounted economic profits along optimal trajectories. We illustrate how the algorithm can be implemented by applying it to the European Northern Stock of Hake (Merluccius merluccius), where fleets also capture Northern megrim (Lepidorhombus whiffiagonis) and Northern anglerfish (Lophius piscatorius and Lophius budegassa). We find that optimal mixed management leads to a target reference point that is quite similar to the 2/3 of the Fmsy single-species (hake) target. Mixed management is superior to singlespecies management because it leads the fishery to higher discounted profits with higher long-term SSB for all species. We calculate that the losses due to the use of the Fmsy single-species (hake) target in this mixed fishery account for 11.4% of total discounted profits.

Study of an object recognition algorithm

This project introduces an improvement of the vision capacity of the robot Robotino operating under ROS platform. A method for recognizing object class using binary features has been developed. The proposed method performs a binary classification of the descriptors of each training image to characterize the appearance of the object class. It presents the use of the binary descriptor based on the difference of gray intensity of the pixels in the image. It shows that binary features are suitable to represent object class in spite of the low resolution and the weak information concerning details of the object in the image. It also introduces the use of a boosting method (Adaboost) of feature selection al- lowing to eliminate redundancies and noise in order to improve the performance of the classifier. Finally, a kernel classifier SVM (Support Vector Machine) is trained with the available database and applied for predictions on new images. One possible future work is to establish a visual servo-control that is to say the reac- tion of the robot to the detection of the object.

Cannabis use and involuntary admission may mediate long-term adherence in first-episode psychosis patients: a prospective longitudinal study

Background: This study aimed to examine factors associated with treatment adherence in first-episode psychosis (FEP) patients followed up over 8 years, especially involuntary first admission and stopping cannabis use. Methods: This prospective, longitudinal study of FEP patients collected data on symptoms, adherence, functioning,and substance use. Adherence to treatment was the main outcome variable and was categorized as ‘good’ or ‘bad’. Cannabis use during follow-up was stratified as continued use, stopped use, and never used. Bivariate and logistic regression models identified factors significantly associated with adherence and changes in adherence over the 8-year follow-up period. Results: Of the 98 FEP patients analyzed at baseline, 57.1% had involuntary first admission, 74.4% bad adherence,and 52% cannabis use. Good adherence at baseline was associated with Global Assessment of Functioning score (p = 0.019), Hamilton Depression Rating Scale score (p = 0.017) and voluntary admission (p < 0.001). Adherence patterns over 8 years included: 43.4% patients always bad, 26.1% always good, 25% improved from bad to good. Among the improved adherence group, 95.7% had involuntary first admission and 38.9% stopped cannabis use. In the subgroup of patients with bad adherence at baseline, involuntary first admission and quitting cannabis use during follow up were associated with improved adherence. Conclusions: The long-term association between treatment adherence and type of first admission and cannabis use in FEP patients suggest targets for intervention to improve clinical outcomes.

Genetics of Type III Bartter Syndrome in Spain, Proposed Diagnostic Algorithm

9 p.

Molecular diagnosis of distal renal tubular acidosis in Tunisian patients: proposed algorithm for Northern Africa populations for the ATP6V1B1, ATP6V0A4 and SCL4A1 genes

Background: Primary distal renal tubular acidosis (dRTA) caused by mutations in the genes that codify for the H+ -ATPase pump subunits is a heterogeneous disease with a poor phenotype-genotype correlation. Up to now, large cohorts of dRTA Tunisian patients have not been analyzed, and molecular defects may differ from those described in other ethnicities. We aim to identify molecular defects present in the ATP6V1B1, ATP6V0A4 and SLC4A1 genes in a Tunisian cohort, according to the following algorithm: first, ATP6V1B1 gene analysis in dRTA patients with sensorineural hearing loss (SNHL) or unknown hearing status. Afterwards, ATP6V0A4 gene study in dRTA patients with normal hearing, and in those without any structural mutation in the ATP6V1B1 gene despite presenting SNHL. Finally, analysis of the SLC4A1 gene in those patients with a negative result for the previous studies. Methods: 25 children (19 boys) with dRTA from 20 families of Tunisian origin were studied. DNAs were extracted by the standard phenol/chloroform method. Molecular analysis was performed by PCR amplification and direct sequencing. Results: In the index cases, ATP6V1B1 gene screening resulted in a mutation detection rate of 81.25%, which increased up to 95% after ATP6V0A4 gene analysis. Three ATP6V1B1 mutations were observed: one frameshift mutation (c.1155dupC; p.Ile386fs), in exon 12; a G to C single nucleotide substitution, on the acceptor splicing site (c.175-1G > C; p.?) in intron 2, and one novel missense mutation (c. 1102G > A; p. Glu368Lys), in exon 11. We also report four mutations in the ATP6V0A4 gene: one single nucleotide deletion in exon 13 (c.1221delG; p. Met408Cysfs* 10); the nonsense c.16C > T; p.Arg6*, in exon 3; and the missense changes c.1739 T > C; p.Met580Thr, in exon 17 and c.2035G > T; p.Asp679Tyr, in exon 19. Conclusion: Molecular diagnosis of ATP6V1B1 and ATP6V0A4 genes was performed in a large Tunisian cohort with dRTA. We identified three different ATP6V1B1 and four different ATP6V0A4 mutations in 25 Tunisian children. One of them, c.1102G > A; p.Glu368Lys in the ATP6V1B1 gene, had not previously been described. Among deaf since childhood patients, 75% had the ATP6V1B1 gene c. 1155dupC mutation in homozygosis. Based on the results, we propose a new diagnostic strategy to facilitate the genetic testing in North Africans with dRTA and SNHL.

Efficient learning of decomposable models with a bounded clique size

The learning of probability distributions from data is a ubiquitous problem in the fields of Statistics and Artificial Intelligence. During the last decades several learning algorithms have been proposed to learn probability distributions based on decomposable models due to their advantageous theoretical properties. Some of these algorithms can be used to search for a maximum likelihood decomposable model with a given maximum clique size, k, which controls the complexity of the model. Unfortunately, the problem of learning a maximum likelihood decomposable model given a maximum clique size is NP-hard for k > 2. In this work, we propose a family of algorithms which approximates this problem with a computational complexity of O(k · n^2 log n) in the worst case, where n is the number of implied random variables. The structures of the decomposable models that solve the maximum likelihood problem are called maximal k-order decomposable graphs. Our proposals, called fractal trees, construct a sequence of maximal i-order decomposable graphs, for i = 2, ..., k, in k − 1 steps. At each step, the algorithms follow a divide-and-conquer strategy based on the particular features of this type of structures. Additionally, we propose a prune-and-graft procedure which transforms a maximal k-order decomposable graph into another one, increasing its likelihood. We have implemented two particular fractal tree algorithms called parallel fractal tree and sequential fractal tree. These algorithms can be considered a natural extension of Chow and Liu’s algorithm, from k = 2 to arbitrary values of k. Both algorithms have been compared against other efficient approaches in artificial and real domains, and they have shown a competitive behavior to deal with the maximum likelihood problem. Due to their low computational complexity they are especially recommended to deal with high dimensional domains.