Search

This work focuses on the capacitated dispersion problem for which we study several mathematical formulations in different spaces using variables associated with nodes, edges, and costs. The relationships among the presented formulations are investigated by comparing the projections of the feasible sets of the LP relaxations onto the subspace of natural variables. These formulations are then strengthened with families of valid inequalities and variable-fixing procedures. The separation problems associated with the valid inequalities that are exponential in number are shown to be polynomially solvable by reducing them to longest path problems in acyclic graphs. The dual bounds obtained from stronger but larger formulations are used to improve the strength of weaker but smaller formulations. Several sets of computational experiments are conducted to illustrate the usefulness of the findings, as well as the aptness of the formulations for different types of instances.

In this work, we propose a heuristic procedure for a stochastic version of the uncapacitated r-allocation p-hub median problem with nonstop services. In particular, we assume that the number of hubs to which a terminal can be allocated is bounded from above by r. Additionally, we consider the possibility of shipping traffic directly between terminals (nonstop services). Uncertainty is associated with the traffic to be shipped between nodes and with the transportation costs. If we assume that such uncertainty can be captured by a finite set of scenarios, each of which with a probability known in advance, it is possible to develop a compact formulation for the deterministic equivalent problem. However, even for small instances of the problem, the model becomes too large to be tackled by a general solver. This fact motivates the development of a heuristic procedure, whose starting point is the determination of a feasible solution to every (deterministic) single-scenario problem. These solutions are then embedded into a process based on the path relinking methodology: gradually an initial solution to the overall problem is transformed by the incorporation of attributes from some guiding solutions. In our case, the guiding solutions are those found for the single-scenario problems. We report and discuss the results of the numerical experiments performed using instances randomly generated for the new problem from the well-known CAB and AP data sets.

Introduction In clinical practice, celiac disease (CD) is monitored through anti-transglutaminase (TGA-IgA) antibody levels. The normalization of serum levels in successive periodic measurements indicates good response and adherence to dietary treatment. Objectives To evaluate the factors associated with the evolution of TGA-IgA antibodies and their association with dietary non-compliance and diseases related to CD. Methods This prospective observational study was carried out in 254 participants, who were recruited from patients from a hospital in southern Spain. Information about sex, age, serological test results, HLA DQ2/DQ8 haplotypes, mucosal atrophy, gastrointestinal and extra-intestinal symptoms, as well as diagnosis of diseases related to CD, was collected. Results Clinical manifestations, such as diarrhoea, abdominal pain and weight loss, showed differences according to sex and age. Children under 18 years of age presented a degree of total or severe atrophy of the intestinal villi. TGA-IgA antibodies concentrations were directly associated with the number of digestive disorders manifested by the patient and the record of dietary non-compliance and inversely related to the number of extra-digestive disorders. Conclusions Adolescents between 12 and 18 years old were the least monitored as well as the group with more extra-intestinal symptoms reported. Therefore, it is necessary to develop strategies in clinical practice aimed at this population group and continuous monitoring should be implemented to improve life quality and reduce complications that may arise in the long term., Celiac disease, TGA-IgA antibodies, Diet, Dietary non-compliance

In this paper, we study the visualization of complex structures in the context of automatic graph drawing. Constructing geometric representations of combinatorial structures, such as networks or graphs, is a difficult task that requires an expert system. The automatic generation of drawings of graphs finds many applications from software engineering to social media. The objective of graph drawing expert systems is to generate layouts that are easy to read and understand. This main objective is achieved by solving several optimization problems. In this paper we focus on the most important one: reducing the number of arc crossings in the graph. This hard optimization problem has been studied extensively in the last decade, proposing many exact and heuristic methods to minimize the total number of arc crossings. However, despite its practical significance, the min–max variant in which the maximum number of crossings over all edges is minimized, has received very little attention. We propose new heuristic methods based on the strategic oscillation methodology to solve this NP-hard optimization problem. Our experimentation shows that the new method compares favorably with the existing ones, implemented in current graph drawing expert systems. Therefore, a direct application of our findings will improve these functionality (i.e., crossing reduction) of drawing systems.

In this paper, a districting problem with stochastic demands is investigated. The goal is to divide a geographic area into p contiguous districts such that, with some given probability, the districts are balanced with respect to some given lower and upper thresholds. The problem is cast as a p -median problem with contiguity constraints that is further enhanced with chance-constrained balancing requirements. The total assignment cost of the territorial units to the representatives of the corresponding districts is used as a surrogate compactness measure to be optimized. Due to the tantalizing purpose of deriving a deterministic equivalent for the problem, a two-phase heuristic is developed. In the first phase, the chance-constraints are ignored and a feasible solution is constructed for the relaxed problem; in the second phase, the solution is corrected if it does not meet the chance-constraints. In this case, a simulation procedure is proposed for estimating the probability of a given solution to yield a balanced districting. That procedure also provides information for guiding the changes to make in the solution. The results of a series of computational tests performed are discussed based upon a set of testbed instances randomly generated. Different families of probability distributions for the demands are also investigated, namely: Uniform, Log-normal, Exponential, and Poisson.

In this paper we study the hub location problem, where the goal is to identify an optimal subset of facilities (hubs) to minimize the transportation cost while satisfying certain capacity constraints. In particular, we target the single assignment version, in which each node in the transportation network is assigned to only one hub to route its traffic. We consider here a realistic variant introduced previously, in which the capacity of edges between hubs is increased in a modular way. This reflects the practical situation in air traffic where the number of flights between two locations implies a capacity in terms of number of passengers. Then, the capacity can be increased in a modular way, as a factor of the number of flights. We propose heuristic methods to obtain high-quality solutions in short computing times. Specifically, we implement memory structures to create advanced search methods and compare them with previous heuristics on a set of benchmark instances. Memory structures have been widely implemented in the context of the tabu search methodology, usually embedded in local search algorithms. In this paper we explore an alternative design in which the constructive method is enhanced with frequency information and the local search is coupled with a path relinking post-processing. Statistical tests confirm the superiority of our proposal with respect to previous developments.

The capacitated single assignment hub location problem with modular link capacities is a variant of the classical hub location problem in which the cost of using edges is not linear but stepwise, and the hubs are restricted in terms of transit capacity rather than in the incoming traffic. We propose a metaheuristic algorithm based on strategic oscillation, a methodology originally introduced in the context of tabu search. Our method incorporates several designs for constructive and destructive algorithms, together with associated local search procedures, to balance diversification and intensification for an efficient search. Computational results on a large set of instances show that, in contrast to exact methods that can only solve small instances optimally, our metaheuristic is able to find high-quality solutions on larger instances in short computing times. In addition, the new method, which joins tabu search strategies with strategic oscillation, outperforms the previous tabu search implementation.

Multidisciplinary research in public health is approached using methods from many scientific disciplines. One of the main characteristics of this type of research is dealing with large data sets. Classic statistical variable selection methods, known as “screen and clean”, and used in a single-step, select the variables with greater explanatory weight in the model. These methods, commonly used in public health research, may induce masking and multicollinearity, excluding relevant variables for the experts in each discipline and skewing the result. Some specific techniques are used to solve this problem, such as penalized regressions and Bayesian statistics, they offer more balanced results among subsets of variables, but with less restrictive selection thresholds. Using a combination of classical methods, a three-step procedure is proposed in this manuscript, capturing the relevant variables of each scientific discipline, minimizing the selection of variables in each of them and obtaining a balanced distribution that explains most of the variability. This procedure was applied on a dataset from a public health research. Comparing the results with the single-step methods, the proposed method shows a greater reduction in the number of variables, as well as a balanced distribution among the scientific disciplines associated with the response variable. We propose an innovative procedure for variable selection and apply it to our dataset. Furthermore, we compare the new method with the classic single-step procedures. La investigación multidisciplinaria en salud pública se enfoca usando métodos de muchas disciplinas científicas. Una de las principales características de este tipo de investigación es lidiar con conjuntos voluminosos de datos. Los métodos clásicos estadísticos de selección de variables, conocidos como “screen and clean”, y utilizados en un solo paso, seleccionan las variables con mayor peso explicativo en su modelo. Estos métodos, comúnmente usados en investigación pública en salud, pueden inducir a enmascarar la multicolinealidad, excluyendo variables relevantes para los expertos en cada disciplina y sesgando el resultado. Se usan algunas técnicas específicas para resolver este problema, como las regresiones penalizadas y estadísticas bayesianas, que ofrecen resultados más equilibrados entre subconjuntos de variables, pero con umbrales menos restrictivos de selección. Usando la combinación de métodos clásicos, se propone en este trabajo un tercer paso en el procedimiento, recogiendo variables relevantes de cada disciplina científica, minimizando la selección de variables en cada una de ellas y obteniendo una distribución equilibrada que explica la mayor parte de la variabilidad. Este procedimiento fue aplicado en un conjunto de datos de una investigación en salud pública. Comparando los resultados con los métodos de un solo paso, el método propuesto expone una gran reducción en el número de variables, así como la distribución equilibrada entre las disciplinas científicas asociadas con la variable de respuesta. Proponemos un procedimiento innovador para la selección de variables y aplicarlo a nuestro conjunto de datos. Asimismo, comparamos el nuevo método con los procedimientos clásicos de un solo paso. A pesquisa multidisciplinar em saúde pública emprega métodos provenientes de diversas disciplinas científicas. Uma das principais características desse tipo de pesquisa é o fato de lidar com conjuntos de dados grandes. Os métodos clássicos de seleção de variáveis estatísticas, conhecidos como “screen and clean” (filtrar e limpar), e aplicados a partir de um passo único, selecionam as variáveis com o maior peso explanatório no modelo. Esses métodos, amplamente disseminados na pesquisa em saúde pública, podem induzir ao mascaramento e à multi-colinearidade, excluindo variáveis que seriam relevantes para os especialistas em cada disciplina e enviesando os resultados. Algumas técnicas específicas usadas para resolver esse problema, como regressões penalizadas e estatísticas Bayesianas, oferecem resultados mais equilibrados entre subconjuntos de variáveis, porém com limiares de seleção menos restritivos. O artigo propõe um procedimento com três passos, usando uma combinação de métodos clássicos, captando as variáveis relevantes de cada disciplina científica, minimizando a seleção de variáveis em cada disciplina e obtendo uma distribuição equilibrada que explica a maior parte da variabilidade. O procedimento foi aplicado a um conjunto de dados de uma pesquisa em saúde pública. Ao comparar os resultados com os métodos que utilizam um único passo, o método proposto demonstra maior redução no número de variáveis, assim como, uma distribuição equilibrada entre as disciplinas científicas relacionadas à variável dependente. Propomos um procedimento inovador para a seleção de variáveis, que aplicamos depois ao nosso conjunto de dados. Além disso, comparamos o método novo com os procedimentos clássicos de apenas um estágio.

Scatter search is a population-based method that has been shown to yield high-quality outcomes for combinatorial optimization problems. It uses strategies for combining solution vectors that have proved effective in a variety of problem settings. In this paper, we present a scatter search implementation for an NP -hard variant of the classic p-hub median problem. Specifically, we tackle the uncapacitated r-allocation p-hub median problem, which consists of minimizing the cost of transporting the traffics between nodes of a network through special facilities that act as transshipment points. This problem has a significant number of applications in practice, such as the design of transportation and telecommunications networks.As it is customary in metaheuristic implementations, we design specific methods to create an efficient solving procedure based on the scatter search methodology. In particular, we propose mechanisms to generate, combine, and improve solutions for this problem. Special mention deserves the use of path-relinking as an extension of the classical combination method. Extensive computational experiments establish the effectiveness of our procedure in relation to approaches previously identified to be best.

In this paper we propose a heuristic for the Uncapacitated r-Allocation p-Hub Median Problem. In the classical p-hub location problem, given a set of nodes with pairwise traffic demands, we must select p of them as hub locations and route all traffics through them at a minimum cost. We target here an extension, called the r-allocation p-hub median problem, recently proposed by Yaman [19], in which every node is assigned to r of the p selected hubs (r@?p) and we are restricted to route the traffic of the nodes through their associated r hubs. As it is usual in this type of problems, our method has three phases: location, assignment and routing. Specifically, we propose a heuristic based on the GRASP methodology in which we consider three local search procedures. The combinatorial nature of this problem makes them time-consuming. We therefore propose a filtering mechanism to discard low-quality constructions and skip its improvement, saving its associated running time. We perform several experiments to first determine the values of the key-search parameters of our method and then to compare with previous algorithms. Computational results on 465 instances show that while only small instances can be optimally solved with exact methods, the heuristic is able to find high-quality solutions on larger instances in short computing times. Moreover, when targeting the classical p-hub versions (with r=1 or r=p), our heuristic is competitive with the state of the art methods.