Graphic summary
  • Show / hide key
  • Information


Scientific and technological production
  •  

1 to 20 of 20 results
  • Risk-neutral bounded max-sum for distributed constraint optimization

     Larrosa Bondia, Francisco Javier; Rollon Rico, Emma
    ACM Symposium on Applied Computing
    Presentation's date: 2013-03
    Presentation of work at congresses

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    Bounded Max-Sum is a message-passing algorithm for solving Distributed Constraint Optimization Problems able to compute solutions with a guaranteed approximation ratio. Although its approximate solutions were empirically proved to be within a small percentage of the optimal solution on low and moderate dense problems, in this paper we show that a simple modification systematically provides even better solutions. This is especially relevant in critical applications (e.g. disaster response scenarios) where the accuracy of solutions is of vital importance.

  • Decomposing utility functions in bounded max-sum for distributed constraint optimization

     Rollon Rico, Emma; Larrosa Bondia, Francisco Javier
    Congrés Global sobre sistemes intelligents
    Presentation's date: 2013-03-03
    Presentation of work at congresses

    Read the abstract Read the abstract  Share Reference managers Reference managers Open in new window

    Bounded Max-Sum is a message-passing algorithm for solving Distributes Constraint Optimization Problems (DCOP) able to compute solutions with a guaranteed approximation ratio. In this paper we show that the introduction of an intermediate step that decomposes functions may significantly improve its accuracy. This is especially relevant in critical applications (e.g. automatic surveillance, disaster response scenarios) where the accuracy of solutions is of vital importance.

  • Semiring-based mini-bucket partitioning schemes

     Rollon Rico, Emma; Larrosa Bondia, Francisco Javier; Dechter, Rina
    International Joint Conference on Artificial Intelligence
    Presentation's date: 2013-08-03
    Presentation of work at congresses

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    Graphical models are one of the most prominent frameworks to model complex systems and efficiently query them. Their underlying algebraic properties are captured by a valuation structure that, most usually, is a semiring. Depending on the semiring of choice, we can capture probabilistic models, constraint networks, cost networks, etc. In this paper we address the partitioning problem which occurs in many approximation techniques such as mini-bucket elimination and join- graph propagation algorithms. Roghly speaking, subject to complexity bounds, the algorithm needs to find a partition of a set of factors such that best approximates the whole set. While this problem has been addressed in the past in a particular case, we present here a general description. Furthermore, we also propose a general partitioning scheme. Our proposal is general in the sense that it is presented in terms of a generic semiring with the only additional requirements of a division operation and a refinement of its order. The proposed algorithm instantiates to the particular task of computing the probability of evidence, but also applies directly to other important reasoning tasks. We demonstrate its good empirical behaviour on the problem of computing the most probable explanation.

  • Improved bounded max-sum for distributed constraint optimization

     Rollon Rico, Emma; Larrosa Bondia, Francisco Javier
    International Conference on Principles and Practice of Constraint Programming
    Presentation's date: 2012
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Local arc consistency for non-invertible semirings, with an application to multi-objective optimization

     Bistarelli, Stefano; Gadducci, Fabio; Larrosa Bondia, Francisco Javier; Rollon Rico, Emma; Santini, Francesco
    Expert systems with applications
    Date of publication: 2012-02-01
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • On mini-buckets and the min-fill elimination ordering

     Rollon Rico, Emma; Larrosa Bondia, Francisco Javier
    International Conference on Principles and Practice of Constraint Programming
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Bucket and mini-bucket schemes for M best solutions over graphical models

     Flerova, Natalia; Rollon Rico, Emma; Dechter, Rina
    Workshop on Graph Structures for Knowledge Representation and Reasoning
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Access to the full text
    New mini-bucket partitioning heuristics for bounding the probability of evidence  Open access

     Rollon Rico, Emma; Dechter, Rina
    AAAI Conference on Artificial Intelligence
    Presentation's date: 2010
    Presentation of work at congresses

    Read the abstract Read the abstract Access to the full text Access to the full text Open in new window  Share Reference managers Reference managers Open in new window

    Mini-Bucket Elimination (MBE) is a well-known approximation algorithm deriving lower and upper bounds on quantities of interest over graphical models. It relies on a procedure that partitions a set of functions, called bucket, into smaller subsets, called mini-buckets. The method has been used with a single partitioning heuristic throughout, so the impact of the partitioning algorithm on the quality of the generated bound has never been investigated. This paper addresses this issue by presenting a framework within which partitioning strategies can be described, analyzed and compared. We derive a new class of partitioning heuristics from first-principles geared for likelihood queries, demonstrate their impact on a number of benchmarks for probabilistic reasoning and show that the results are competitive (often superior) to state-ofthe-art bounding schemes.

  • Extending soft arc consistency algorithms to non-invertible semirings

     Bistarelli, Stefano; Gadducci, Fabio; Larrosa Bondia, Francisco Javier; Rollon Rico, Emma; Santini, Francesco
    Date of publication: 2010-07-03
    Book chapter

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • RESTRICCIONES BLANDAS CON PESOS: CASOS CENTRALIZADO Y DISTRIBUIDO

     Rollon Rico, Emma; Vila Grabulosa, Lluis; Larrosa Bondia, Francisco Javier
    Participation in a competitive project

     Share

  • Active tuples-based scheme for bounding posterior beliefs

     Bidyuk, Bozhena; Dechter, Rina; Rollon Rico, Emma
    Journal of artificial intelligence research
    Date of publication: 2010
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Enabling local computation for partially ordered preferences

     Fargier, Helene; Rollon Rico, Emma; Wilson, Nic
    Constraints
    Date of publication: 2010-10
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • MILTI-OBJECTIVE OPTIMIZATION IN GRAPHICAL MODELS  Open access

     Rollon Rico, Emma
    Defense's date: 2008-11-03
    Department of Software, Universitat Politècnica de Catalunya
    Theses

    Read the abstract Read the abstract Access to the full text Access to the full text Open in new window  Share Reference managers Reference managers Open in new window

    Many real-life optimization problems are combinatorial, i.e. they concern a choice of the best solution from a finite but exponentially large set of alternatives. Besides, the solution quality of many of these problems can often be evaluated from several points of view (a.k.a. criteria). In that case, each criterion may be described by a different objective function. Some important and well-known multicriteria scenarios are: · In investment optimization one wants to minimize risk and maximize benefits. · In travel scheduling one wants to minimize time and cost. · In circuit design one wants to minimize circuit area, energy consumption and maximize speed. · In knapsack problems one wants to minimize load weight and/or volume and maximize its economical value. The previous examples illustrate that, in many cases, these multiple criteria are incommensurate (i.e., it is difficult or impossible to combine them into a single criterion) and conflicting (i.e., solutions that are good with respect one criterion are likely to be bad with respect to another). Taking into account simultaneously the different criteria is not trivial and several notions of optimality have been proposed. Independently of the chosen notion of optimality, computing optimal solutions represents an important current research challenge. Graphical models are a knowledge representation tool widely used in the Artificial Intelligence field. They seem to be specially suitable for combinatorial problems. Roughly, graphical models are graphs in which nodes represent variables and the (lack of) arcs represent conditional independence assumptions. In addition to the graph structure, it is necessary to specify its micro-structure which tells how particular combinations of instantiations of interdependent variables interact. The graphical model framework provides a unifying way to model a broad spectrum of systems and a collection of general algorithms to efficiently solve them. In this Thesis we integrate multi-objective optimization problems into the graphical model paradigm and study how algorithmic techniques developed in the graphical model context can be extended to multi-objective optimization problems. As we show, multiobjective optimization problems can be formalized as a particular case of graphical models using the semiring-based framework. It is, to the best of our knowledge, the first time that graphical models in general, and semiring-based problems in particular are used to model an optimization problem in which the objective function is partially ordered. Moreover, we show that most of the solving techniques for mono-objective optimization problems can be naturally extended to the multi-objective context. The result of our work is the mathematical formalization of multi-objective optimization problems and the development of a set of multiobjective solving algorithms that have been proved to be efficient in a number of benchmarks.

    Muchos problemas reales de optimización son combinatorios, es decir, requieren de la elección de la mejor solución (o solución óptima) dentro de un conjunto finito pero exponencialmente grande de alternativas. Además, la mejor solución de muchos de estos problemas es, a menudo, evaluada desde varios puntos de vista (también llamados criterios). Es este caso, cada criterio puede ser descrito por una función objetivo. Algunos escenarios multi-objetivo importantes y bien conocidos son los siguientes: · En optimización de inversiones se pretende minimizar los riesgos y maximizar los beneficios. · En la programación de viajes se quiere reducir el tiempo de viaje y los costes. · En el diseño de circuitos se quiere reducir al mínimo la zona ocupada del circuito, el consumo de energía y maximizar la velocidad. · En los problemas de la mochila se quiere minimizar el peso de la carga y/o el volumen y maximizar su valor económico. Los ejemplos anteriores muestran que, en muchos casos, estos criterios son inconmensurables (es decir, es difícil o imposible combinar todos ellos en un único criterio) y están en conflicto (es decir, soluciones que son buenas con respecto a un criterio es probable que sean malas con respecto a otra). Tener en cuenta de forma simultánea todos estos criterios no es trivial y para ello se han propuesto diferentes nociones de optimalidad. Independientemente del concepto de optimalidad elegido, el cómputo de soluciones óptimas representa un importante desafío para la investigación actual. Los modelos gráficos son una herramienta para la represetanción del conocimiento ampliamente utilizados en el campo de la Inteligencia Artificial que parecen especialmente indicados en problemas combinatorios. A grandes rasgos, los modelos gráficos son grafos en los que los nodos representan variables y la (falta de) arcos representa la interdepencia entre variables. Además de la estructura gráfica, es necesario especificar su (micro-estructura) que indica cómo interactúan instanciaciones concretas de variables interdependientes. Los modelos gráficos proporcionan un marco capaz de unificar el modelado de un espectro amplio de sistemas y un conjunto de algoritmos generales capaces de resolverlos eficientemente. En esta tesis integramos problemas de optimización multi-objetivo en el contexto de los modelos gráficos y estudiamos cómo diversas técnicas algorítmicas desarrolladas dentro del marco de los modelos gráficos se pueden extender a problemas de optimización multi-objetivo. Como mostramos, este tipo de problemas se pueden formalizar como un caso particular de modelo gráfico usando el paradigma basado en semi-anillos (SCSP). Desde nuestro conocimiento, ésta es la primera vez que los modelos gráficos en general, y el paradigma basado en semi-anillos en particular, se usan para modelar un problema de optimización cuya función objetivo está parcialmente ordenada. Además, mostramos que la mayoría de técnicas para resolver problemas monoobjetivo se pueden extender de forma natural al contexto multi-objetivo. El resultado de nuestro trabajo es la formalización matemática de problemas de optimización multi-objetivo y el desarrollo de un conjunto de algoritmos capaces de resolver este tipo de problemas. Además, demostramos que estos algoritmos son eficientes en un conjunto determinado de benchmarks.

  • Database Design and Administration

     Abello Gamazo, Alberto; Rollon Rico, Emma; Rodriguez Gonzalez, M. Elena
    Date of publication: 2007-09
    Book

     Share Reference managers Reference managers Open in new window

  • Multi-objective Russian doll search

     Rollon Rico, Emma; Larrosa Bondia, Francisco Javier
    22nd AAAI conference on Artificial Intelligence
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Multi-objective propagation in constraint programming

     Rollon Rico, Emma; Larrosa Bondia, Francisco Javier
    European Conference on Artificial Intelligence
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Diseño y administración de bases de datos

     Abello Gamazo, Alberto; Rollon Rico, Emma; Rodriguez Gonzalez, M. Elena
    Date of publication: 2006-09
    Book

     Share Reference managers Reference managers Open in new window

  • Bucket elimination for multiobjective optimization

     Rollon Rico, Emma; Larrosa Bondia, Francisco Javier
    Journal of heuristics
    Date of publication: 2006-09
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Mini-bucket elimination with bucket propagation

     Rollon Rico, Emma; Larrosa Bondia, Francisco Javier
    Lecture notes in computer science
    Date of publication: 2006-09
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Depth-first mini-bucket elimination

     Rollon Rico, Emma; Larrosa Bondia, Francisco Javier
    Lecture notes in computer science
    Date of publication: 2005-10
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window