Insight Centre for Data Analytics - Conference Items

Permanent URI for this collection

Browse

Recent Submissions

Now showing 1 - 5 of 184
  • Item
    A constraint-based local search for designing tree networks with distance and disjoint constraints
    (Institute of Electrical and Electronics Engineers (IEEE), 2015-11-12) Arbelaez, Alejandro; Mehta, Deepak; O'Sullivan, Barry; Quesada, Luis; Seventh Framework Programme; Science Foundation Ireland
    In many network design problems clients are required to be connected to a facility under path-length constraints and budget limits. Each facility is associated with a tree network where the root is the facility itself and the remaining nodes of the tree are its clients. An inherent feature of these networks is that they are vulnerable to a failure. Therefore, it is often important to provide some resiliency in the network. We focus on a problem where we want to ensure that all clients are connected to two facilities so that if one facility fails then all clients can still be served by another facility. Optionally, one might require that each client is resilient to a single link or node failure by enforcing that the paths used to connect a client to its two facilities are either edge-disjoint or node-disjoint respectively. In this paper we use local search to evaluate the trade-off between cost versus resiliency and coverage versus resiliency for a real-world problem in the field of optical networks.
  • Item
    Learning a stopping criterion for local search
    (Springer Nature Ltd., 2016-12-01) Arbelaez, Alejandro; O’Sullivan, Barry; Festa, Paola; Sellmann, Meinolf; Vanschoren, Joaquin; Science Foundation Ireland; Seventh Framework Programme
    Local search is a very effective technique to tackle combinatorial problems in multiple areas ranging from telecommunications to transportations, and VLSI circuit design. A local search algorithm typically explores the space of solutions until a given stopping criterion is met. Ideally, the algorithm is executed until a target solution is reached (e.g., optimal or near-optimal). However, in many real-world problems such a target is unknown. In this work, our objective is to study the application of machine learning techniques to carefully craft a stopping criterion. More precisely, we exploit instance features to predict the expected quality of the solution for a given algorithm to solve a given problem instance, we then run the local search algorithm until the expected quality is reached. Our experiments indicate that the suggested method is able to reduce the average runtime up to 80% for real-world instances and up to 97% for randomly generated instances with a minor impact in the quality of the solutions.
  • Item
    Constraint programming and machine learning for interactive soccer analysis
    (Springer Nature Ltd., 2016-12-01) Duque, Robinson; Díaz, Juan Francisco; Arbelaez, Alejandro; Festa, Paola; Sellmann, Meinolf; Vanschoren, Joaquin
    A soccer competition consists of n teams playing against each other in a league or tournament system, according to a single or double round-robin schedule. These competitions offer an excellent opportunity to model interesting problems related to questions that soccer fans frequently ask about their favourite teams. For instance, at some stage of the competition, fans might be interested in determining whether a given team still has chances of winning the competition (i.e., finishing first in a league or being within the first k teams in a tournament to qualify to the playoff). This problem relates to the elimination problem, which is NP-complete for the actual FIFA pointing rule system (0, 1, 3), zero point to a loss, one point to a tie, and three points to a win. In this paper, we combine constraint programming with machine learning to model a general soccer scenario in a real-time application.
  • Item
    Parallelising the k-medoids clustering problem using space-partitioning
    (Association for the Advancement of Artificial Intelligence, 2013) Arbelaez, Alejandro; Quesada, Luis; Japan Society for the Promotion of Science; Science Foundation Ireland
    The k-medoids problem is a combinatorial optimisation problem with multiples applications in Resource Allocation, Mobile Computing, Sensor Networks and Telecommunications.Real instances of this problem involve hundreds of thousands of points and thousands of medoids.Despite the proliferation of parallel architectures, this problem has been mostly tackled using sequential approaches.In this paper, we study the impact of space-partitioning techniques on the performance of parallel local search algorithms to tackle the k-medoids clustering problem, and compare these results with the ones obtained using sampling.Our experiments suggest that approaches relying on partitioning scale more while preserving the quality of the solution.
  • Item
    SABIO: An implementation of MIP and CP for interactive soccer queries
    (Springer Nature Ltd., 2016-08-23) Duque, Robinson; Díaz, Juan Francisco; Arbelaez, Alejandro; Departamento Administrativo de Ciencia, Tecnología e Innovación (COLCIENCIAS); Science Foundation Ireland
    Soccer is one of the most popular sports in the world with millions of fans that usually raise interesting questions when the competition is partially completed. One interesting question relates to the elimination problem which consists in checking at some stage of the competition if a team i still has a theoretical chance to become the champion. Some other interesting problems from literature are the guaranteed qualification problem, the possible qualification problem, the score vector problem, promotion and relegation. These problems are NP-complete for the actual FIFA pointing rule system (0 points-loss, 1 point-tie, 3 points-win). SABIO is an online platform that helps users discover information related to soccer by letting them formulate questions in form of constraints and go beyond the classical soccer computational problems. In the paper we considerably improve the performance of an existing CP model and combine the use of MIP and CP to answer general soccer queries in a real-time application.