0000000000082360
AUTHOR
Anna Martínez-gavara
Cost-effective Multiresolution schemes for Shock Computations
Harten's Multiresolution framework has provided a fruitful environment for the development of adaptive codes for hyperbolic PDEs. The so-called cost-effective alternative [4,8,21] seeks to achieve savings in the computational cost of the underlying numerical technique, but not in the overall memory requirements of the code. Since the data structure of the basic algorithm does not need to be modified, it provides a set of tools that can be easily implemented into existing codes and that can be very useful in order to speed up the numerical simulations involved in the testing process that is associated to the development of new numerical schemes. In this paper we present two different applica…
Randomized heuristics for the Capacitated Clustering Problem
In this paper, we investigate the adaptation of the Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Greedy methodologies to the Capacitated Clustering Problem (CCP). In particular, we focus on the effect of the balance between randomization and greediness on the performance of these multi-start heuristic search methods when solving this NP-hard problem. The former is a memory-less approach that constructs independent solutions, while the latter is a memory-based method that constructs linked solutions, obtained by partially rebuilding previous ones. Both are based on the combination of greediness and randomization in the constructive process, and coupled with a subsequent l…
Tabu search for min-max edge crossing in graphs
Abstract Graph drawing is a key issue in the field of data analysis, given the ever-growing amount of information available today that require the use of automatic tools to represent it. Graph Drawing Problems (GDP) are hard combinatorial problems whose applications have been widely relevant in fields such as social network analysis and project management. While classically in GDPs the main aesthetic concern is related to the minimization of the total sum of crossing in the graph (min-sum), in this paper we focus on a particular variant of the problem, the Min-Max GDP, consisting in the minimization of the maximum crossing among all egdes. Recently proposed in scientific literature, the Min…
A Hybrid Strategic Oscillation with Path Relinking Algorithm for the Multiobjective k-Balanced Center Location Problem
This paper presents a hybridization of Strategic Oscillation with Path Relinking to provide a set of high-quality nondominated solutions for the Multiobjective k-Balanced Center Location problem. The considered location problem seeks to locate k out of m facilities in order to serve n demand points, minimizing the maximum distance between any demand point and its closest facility while balancing the workload among the facilities. An extensive computational experimentation is carried out to compare the performance of our proposal, including the best method found in the state-of-the-art as well as traditional multiobjective evolutionary algorithms.
A numerical treatment of wet/dry zones in well-balanced hybrid schemes for shallow water flow
The flux-limiting technology that leads to hybrid, high resolution shock capturing schemes for homogeneous conservation laws has been successfully adapted to the non-homogeneous case by the second and third authors. In dealing with balance laws, a key issue is that of well-balancing, which can be achieved in a rather systematic way by considering the 'homogeneous form' of the balance law.The application of these techniques to the shallow water system requires also an appropriate numerical treatment for the wetting/drying interfaces that appear initially or as a result of the flow evolution. In this paper we propose a numerical treatment for wet/dry interfaces that is specifically designed f…
Heuristics for the Constrained Incremental Graph Drawing Problem
Abstract Visualization of information is a relevant topic in Computer Science, where graphs have become a standard representation model, and graph drawing is now a well-established area. Within this context, edge crossing minimization is a widely studied problem given its importance in obtaining readable representations of graphs. In this paper, we focus on the so-called incremental graph drawing problem, in which we try to preserve the user’s mental map when obtaining successive drawings of the same graph. In particular, we minimize the number of edge crossings while satisfying some constraints required to preserve the position of vertices with respect to previous drawings. We propose heur…
Well-Balanced Adaptive Mesh Refinement for shallow water flows
Well-balanced shock capturing (WBSC) schemes constitute nowadays the state of the art in the numerical simulation of shallow water flows. They allow to accurately represent discontinuous behavior, known to occur due to the non-linear hyperbolic nature of the shallow water system, and, at the same time, numerically maintain stationary solutions. In situations of practical interest, these schemes often need to be combined with some kind of adaptivity, in order to speed up computing times. In this paper we discuss what ingredients need to be modified in a block-structured AMR technique in order to ensure that, when combined with a WBSC scheme, the so-called 'water at rest' stationary solutions…
Tabu search for the dynamic Bipartite Drawing Problem
Abstract Drawings of graphs have many applications and they are nowadays well-established tools in computer science in general, and optimization in particular. Project scheduling is one of the many areas in which representation of graphs constitutes an important instrument. The experience shows that the main quality desired for drawings of graphs is readability, and crossing reduction is a fundamental aesthetic criterion to achieve it. Incremental or dynamic graph drawing is an emerging topic in this context, where we seek to preserve the layout of a graph over successive drawings. In this paper, we target the edge crossing reduction in the context of incremental graph drawing. Specifically…
Some Theoretical Results About Stability for IMEX Schemes Applied to Hyperbolic Equations with Stiff Reaction Terms
In this work we are concerned with certain numerical difficulties associated to the use of high order Implicit–Explicit Runge–Kutta (IMEX-RK) schemes in a direct discretization of balance laws with stiff source terms. We consider a simple model problem, introduced by LeVeque and Yee in [J. Comput. Phys 86 (1990)], as the basic test case to explore the ability of IMEX-RK schemes to produce and maintain non-oscillatory reaction fronts.
On stability issues for IMEX schemes applied to 1D scalar hyperbolic equations with stiff reaction terms
The application of a Method of Lines to a hyperbolic PDE with source terms gives rise to a system of ODEs containing terms that may have very different stiffness properties. In this case, Implicit-Explicit Runge-Kutta (IMEX-RK) schemes are particularly useful as high order time integrators because they allow an explicit handling of the convective terms, which can be discretized using the highly developed shock capturing technology, together with an implicit treatment of the source terms, necessary for stability reasons. Motivated by the structure of the source term in a model problem introduced by LeVeque and Yee in [J. Comput. Phys. 86 (1990)], in this paper we study the preservation of ce…
A review on discrete diversity and dispersion maximization from an OR perspective
Abstract The problem of maximizing diversity or dispersion deals with selecting a subset of elements from a given set in such a way that the distance among the selected elements is maximized. The definition of distance between elements is customized to specific applications, and the way that the overall diversity of the selected elements is computed results in different mathematical models. Maximizing diversity by means of combinatorial optimization models has gained prominence in Operations Research (OR) over the last two decades, and constitutes nowadays an important area. In this paper, we review the milestones in the development of this area, starting in the late eighties when the first…
Selecting Genetic Operators to Maximise Preference Satisfaction in a Workforce Scheduling and Routing Problem
The Workforce Scheduling and Routing Problem (WSRP) is a combinatorial optimisation problem that involves scheduling and routing of workforce. Tackling this type of problem often requires handling a considerable number of requirements, including customers and workers preferences while minimising both operational costs and travelling distance. This study seeks to determine effective combinations of genetic operators combined with heuristics that help to find good solutions for this constrained combinatorial optimisation problem. In particular, it aims to identify the best set of operators that help to maximise customers and workers preferences satisfaction. This paper advances the understand…
Adaptation based on interpolation errors for high order mesh refinement methods applied to conservation laws
Adaptive mesh refinement is nowadays a widely used tool in the numerical solution of hyperbolic partial differential equations. The algorithm is based on the numerical approximation of the solution of the equations on a hierarchical set of meshes with different resolutions. Among the different parts that compose an adaptive mesh refinement algorithm, the decision of which level of resolution is adequate for each part of the domain, i.e., the design of a refinement criterion, is crucial for the performance of the algorithm. In this work we analyze a refinement strategy based on interpolation errors, as a building block of a high order adaptive mesh refinement algorithm. We show that this tec…
Variable neighborhood descent for the incremental graph drawing
Abstract Graphs are used to represent reality in several areas of knowledge. Drawings of graphs have many applications, from project scheduling to software diagrams. The main quality desired for drawings of graphs is readability, and crossing reduction is a fundamental aesthetic criterion for a good representation of a graph. In this paper we target the edge crossing reduction in the context of incremental graph drawing, in which we want to preserve the layout of a graph over successive drawings. We propose a hybrid method based on the GRASP (Greedy Randomized Adaptive Search Procedure) and VND (Variable Neighborhood Descent) methodologies and compare it with previous methods via simulation.
GRASP and tabu search for the generalized dispersion problem
Abstract The problem of maximizing dispersion requires the selection of a specific number of elements from a given set, in such a way that the minimum distance between the pairs of selected elements is maximized. In recent years, this problem has received a lot of attention and has been solved with many complex heuristics. However, there is a recent variant in which the selected elements have to satisfy two realistic constraints, a minimum capacity limit and a maximum budget, which in spite of its practical significance in facility location, has received little attention. In this paper, we first propose mathematical models to obtain the optimal solution of small- and medium-size instances, …