Preconditioning 2D integer data for fast convex hull computations

In order to accelerate computing the convex hull on a set of n points, a heuristic procedure is often applied to reduce the number of points to a set of s points, s ≤ n, which also contains the same hull. We present an algorithm to precondition 2D data with integer coordinates bounded by a box of size p × q before building a 2D convex hull, with three distinct advantages. First, we prove that under the condition min(p, q) ≤ n the algorithm executes in time within O(n); second, no explicit sorting of data is required; and third, the reduced set of s points forms a simple polygonal chain and thus can be directly pipelined into an O(n) time convex hull algorithm. This paper empirically evaluates and quantifies the speed up gained by preconditioning a set of points by a method based on the proposed algorithm before using common convex hull algorithms to build the final hull. A speedup factor of at least four is consistently found from experiments on various datasets when the condition min(p, q) ≤ n holds; the smaller the ratio min(p, q)/n is in the dataset, the greater the speedup factor achieved.

The multiple team formation problem using sociometry

The Team Formation problem (TFP) has become a well-known problem in the OR literature over the last few years. In this problem, the allocation of multiple individuals that match a required set of skills as a group must be chosen to maximise one or several social positive attributes. Speci�cally, the aim of the current research is two-fold. First, two new dimensions of the TFP are added by considering multiple projects and fractions of people's dedication. This new problem is named the Multiple Team Formation Problem (MTFP). Second, an optimization model consisting in a quadratic objective function, linear constraints and integer variables is proposed for the problem. The optimization model is solved by three algorithms: a Constraint Programming approach provided by a commercial solver, a Local Search heuristic and a Variable Neighbourhood Search metaheuristic. These three algorithms constitute the first attempt to solve the MTFP, being a variable neighbourhood local search metaheuristic the most effi�cient in almost all cases. Applications of this problem commonly appear in real-life situations, particularly with the current and ongoing development of social network analysis. Therefore, this work opens multiple paths for future research.

Precession and nutation in the eta Carinae binary system: evidence from the X-ray light curve

It is believed that eta Carinae is actually a massive binary system, with the wind-wind interaction responsible for the strong X-ray emission. Although the overall shape of the X-ray light curve can be explained by the high eccentricity of the binary orbit, other features like the asymmetry near periastron passage and the short quasi-periodic oscillations seen at those epochs have not yet been accounted for. In this paper we explain these features assuming that the rotation axis of eta Carinae is not perpendicular to the orbital plane of the binary system. As a consequence, the companion star will face eta Carinae on the orbital plane at different latitudes for different orbital phases and, since both the mass-loss rate and the wind velocity are latitude dependent, they would produce the observed asymmetries in the X-ray flux. We were able to reproduce the main features of the X-ray light curve assuming that the rotation axis of eta Carinae forms an angle of 29 degrees +/- 4 degrees with the axis of the binary orbit. We also explained the short quasi-periodic oscillations by assuming nutation of the rotation axis, with an amplitude of about 5 degrees and a period of about 22 days. The nutation parameters, as well as the precession of the apsis, with a period of about 274 years, are consistent with what is expected from the torques induced by the companion star.

Perinatal salt restriction: A new pathway to programming adiposity indices in adult female Wistar rats

Low birth weight has been associated with increased obesity in adulthood. It has been shown that dietary salt restriction during intrauterine life induces low birth weight and insulin resistance in adult Wistar rats. The present study had a two-fold objective: to evaluate the effects that low salt intake during pregnancy and lactation has on the amount and distribution of adipose tissue; and to determine whether the phenotypic changes in fat mass in this model are associated with alterations in the activity of the renin-angiotensin system. Maternal salt restriction was found to reduce birth weight in male and female offspring. In adulthood, the female offspring of dams fed the low-salt diet presented higher adiposity indices than those seen in the offspring of dams fed a normal-salt diet. This was attributed to the fact that adipose tissue mass (retroperitoneal but not gonadal, mesenteric or inguinal) was greater in those rats than in the offspring of dams fed a normal diet. The adult offspring of dams fed the low-salt diet, compared to those dams fed a normal-salt diet, presented the following: plasma leptin levels higher in males and lower in females; plasma renin activity higher in males but not in females; and no differences in body weight, mean arterial blood pressure or serum angiotensin-converting enzyme activity. Therefore, low salt intake during pregnancy might lead to the programming of obesity in adult female offspring. (c) 2009 Elsevier Inc. All rights reserved.

Building binary-tree-based multiclass classifiers using separability measures

Various popular machine learning techniques, like support vector machines, are originally conceived for the solution of two-class (binary) classification problems. However, a large number of real problems present more than two classes. A common approach to generalize binary learning techniques to solve problems with more than two classes, also known as multiclass classification problems, consists of hierarchically decomposing the multiclass problem into multiple binary sub-problems, whose outputs are combined to define the predicted class. This strategy results in a tree of binary classifiers, where each internal node corresponds to a binary classifier distinguishing two groups of classes and the leaf nodes correspond to the problem classes. This paper investigates how measures of the separability between classes can be employed in the construction of binary-tree-based multiclass classifiers, adapting the decompositions performed to each particular multiclass problem. (C) 2010 Elsevier B.V. All rights reserved.

A review on the combination of binary classifiers in multiclass problems

Several real problems involve the classification of data into categories or classes. Given a data set containing data whose classes are known, Machine Learning algorithms can be employed for the induction of a classifier able to predict the class of new data from the same domain, performing the desired discrimination. Some learning techniques are originally conceived for the solution of problems with only two classes, also named binary classification problems. However, many problems require the discrimination of examples into more than two categories or classes. This paper presents a survey on the main strategies for the generalization of binary classifiers to problems with more than two classes, known as multiclass classification problems. The focus is on strategies that decompose the original multiclass problem into multiple binary subtasks, whose outputs are combined to obtain the final prediction.

The constrained compartmentalized knapsack problem: mathematical models and solution methods

The constrained compartmentalized knapsack problem can be seen as an extension of the constrained knapsack problem. However, the items are grouped into different classes so that the overall knapsack has to be divided into compartments, and each compartment is loaded with items from the same class. Moreover, building a compartment incurs a fixed cost and a fixed loss of the capacity in the original knapsack, and the compartments are lower and upper bounded. The objective is to maximize the total value of the items loaded in the overall knapsack minus the cost of the compartments. This problem has been formulated as an integer non-linear program, and in this paper, we reformulate the non-linear model as an integer linear master problem with a large number of variables. Some heuristics based on the solution of the restricted master problem are investigated. A new and more compact integer linear model is also presented, which can be solved by a branch-and-bound commercial solver that found most of the optimal solutions for the constrained compartmentalized knapsack problem. On the other hand, heuristics provide good solutions with low computational effort. (C) 2011 Elsevier BM. All rights reserved.

Crop rotation scheduling with adjacency constraints

In this article we propose a 0-1 optimization model to determine a crop rotation schedule for each plot in a cropping area. The rotations have the same duration in all the plots and the crops are selected to maximize plot occupation. The crops may have different production times and planting dates. The problem includes planting constraints for adjacent plots and also for sequences of crops in the rotations. Moreover, cultivating crops for green manuring and fallow periods are scheduled into each plot. As the model has, in general, a great number of constraints and variables, we propose a heuristics based on column generation. To evaluate the performance of the model and the method, computational experiments using real-world data were performed. The solutions obtained indicate that the method generates good results.

Job rotation in assembly lines employing disabled workers

In this paper we consider the programming of job rotation in the assembly line worker assignment and balancing problem. The motivation for this study comes from the designing of assembly lines in sheltered work centers for the disabled, where workers have different task execution times. In this context, the well-known training aspects associated with job rotation are particularly desired. We propose a metric along with a mixed integer linear model and a heuristic decomposition method to solve this new job rotation problem. Computational results show the efficacy of the proposed heuristics. (C) 2009 Elsevier B.V. All rights reserved.

Invariants of binary differential equations

In this paper, we study binary differential equations a(x, y)dy (2) + 2b(x, y) dx dy + c(x, y)dx (2) = 0, where a, b, and c are real analytic functions. Following the geometric approach of Bruce and Tari in their work on multiplicity of implicit differential equations, we introduce a definition of the index for this class of equations that coincides with the classical Hopf`s definition for positive binary differential equations. Our results also apply to implicit differential equations F(x, y, p) = 0, where F is an analytic function, p = dy/dx, F (p) = 0, and F (pp) not equal aEuro parts per thousand 0 at the singular point. For these equations, we relate the index of the equation at the singular point with the index of the gradient of F and index of the 1-form omega = dy -aEuro parts per thousand pdx defined on the singular surface F = 0.

Structural Characterization of Photopolymerizable Binary Liposomes Containing Diacetylenic and Saturated Phospholipids

The use of liposomes to encapsulate materials has received widespread attention for drug delivery, transfection, diagnostic reagent, and as immunoadjuvants. Phospholipid polymers form a new class of biomaterials with many potential applications in medicine and research. Of interest are polymeric phospholipids containing a diacetylene moiety along their acyl chain since these kinds of lipids can be polymerized by Ultra-Violet (UV) irradiation to form chains of covalently linked lipids in the bilayer. In particular the diacetylenic phosphatidylcholine 1,2-bis(10,12-tricosadiynoyl)- sn-glycero-3-phosphocholine (DC8,9PC) can form intermolecular cross-linking through the diacetylenic group to produce a conjugated polymer within the hydrocarbon region of the bilayer. As knowledge of liposome structures is certainly fundamental for system design improvement for new and better applications, this work focuses on the structural properties of polymerized DC8,9PC:1,2-dimyristoyl-sn-glycero-3-phusphocholine (DMPC) liposomes. Liposomes containing mixtures of DC8,9PC and DMPC, at different molar ratios, and exposed to different polymerization cycles, were studied through the analysis of the electron spin resonance (ESR) spectra of a spin label incorporated into the bilayer, and the calorimetric data obtained from differential scanning calorimetry (DSC) studies. Upon irradiation, if all lipids had been polymerized, no gel-fluid transition would be expected. However, even samples that went through 20 cycles of UV irradiation presented a DSC band, showing that around 80% of the DC8,9PC molecules were not polymerized. Both DSC and ESR indicated that the two different lipids scarcely mix at low temperatures, however few molecules of DMPC are present in DC8,9PC rich domains and vice versa. UV irradiation was found to affect the gel fluid transition of both DMPC and DC8,9PC rich regions, indicating the presence of polymeric units of DC8,9PC in both areas, A model explaining lipids rearrangement is proposed for this partially polymerized system.

Integer and fractional microwave induced resistance oscillations in a 2D system with moderate mobility

We report on integer and fractional microwave-induced resistance oscillations in a 2D electron system with high density and moderate mobility, and present results of measurements at high microwave intensity and temperature. Fractional microwave-induced resistance oscillations occur up to fractional denominator 8 and are quenched independently of their fractional order. We discuss our results and compare them with existing theoretical models. (C) 2009 Elsevier B.V. All rights reserved.

Scheduling Grid Applications with Software Requirements

The aim of task scheduling is to minimize the makespan of applications, exploiting the best possible way to use shared resources. Applications have requirements which call for customized environments for their execution. One way to provide such environments is to use virtualization on demand. This paper presents two schedulers based on integer linear programming which schedule virtual machines (VMs) in grid resources and tasks on these VMs. The schedulers differ from previous work by the joint scheduling of tasks and VMs and by considering the impact of the available bandwidth on the quality of the schedule. Experiments show the efficacy of the schedulers in scenarios with different network configurations.

Orthogonal packing of identical rectangles within isotropic convex regions

A mixed integer continuous nonlinear model and a solution method for the problem of orthogonally packing identical rectangles within an arbitrary convex region are introduced in the present work. The convex region is assumed to be made of an isotropic material in such a way that arbitrary rotations of the items, preserving the orthogonality constraint, are allowed. The solution method is based on a combination of branch and bound and active-set strategies for bound-constrained minimization of smooth functions. Numerical results show the reliability of the presented approach. (C) 2010 Elsevier Ltd. All rights reserved.

Proximal methods for nonlinear programming: double regularization and inexact subproblems

This paper describes the first phase of a project attempting to construct an efficient general-purpose nonlinear optimizer using an augmented Lagrangian outer loop with a relative error criterion, and an inner loop employing a state-of-the art conjugate gradient solver. The outer loop can also employ double regularized proximal kernels, a fairly recent theoretical development that leads to fully smooth subproblems. We first enhance the existing theory to show that our approach is globally convergent in both the primal and dual spaces when applied to convex problems. We then present an extensive computational evaluation using the CUTE test set, showing that some aspects of our approach are promising, but some are not. These conclusions in turn lead to additional computational experiments suggesting where to next focus our theoretical and computational efforts.