**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Heuristic (computer science)

Summary

In mathematical optimization and computer science, heuristic (from Greek εὑρίσκω "I find, discover") is a technique designed for problem solving more quickly when classic methods are too slow for finding an exact or approximate solution, or when classic methods fail to find any exact solution. This is achieved by trading optimality, completeness, accuracy, or precision for speed. In a way, it can be considered a shortcut.
A heuristic function, also simply called a heuristic, is a function that ranks alternatives in search algorithms at each branching step based on available information to decide which branch to follow. For example, it may approximate the exact solution.
Definition and motivation
The objective of a heuristic is to produce a solution in a reasonable time frame that is good enough for solving the problem at hand. This solution may not be the best of all the solutions to this problem, or it may simply approximate the exact solution. But it is still valua

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related people (9)

Related publications (100)

Loading

Loading

Loading

Related units (7)

Related concepts (22)

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algo

Artificial intelligence

Artificial intelligence (AI) is the intelligence of machines or software, as opposed to the intelligence of human beings or animals. AI applications include advanced web search engines (e.g., Google

Search algorithm

In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in th

Related courses (22)

Software agents are widely used to control physical, economic and financial processes. The course presents practical methods for implementing software agents and multi-agent systems, supported by programming exercises, and the theoretical underpinnings including computational game theory.

The goal of the lecture is to present and apply techniques for the modelling and the thermo-economic optimisation of industrial process and energy systems. The lecture covers the problem statement, the solving methods for the simulation and the single and multi-objective optimisation problems.

Students extend their knowledge on wireless communication systems to spread-spectrum communication and to multi-antenna systems. They also learn about the basic information theoretic concepts, about channel coding, and bit-interleaved coded modulation.

Constraint Satisfaction Problems (CSPs) are ubiquitous in computer science. Many problems, ranging from resource allocation and scheduling to fault diagnosis and design, involve constraint satisfaction as an essential component. A CSP is given by a set of variables and constraints on small subsets of these variables. It is solved by finding assignments of values to the variables such that all constraints are satisfied. In its most general form, a CSP is combinatorial and complex. In this thesis, we consider constraint satisfaction problems with variables in continuous, numerical domains. Contrary to most existing techniques, which focus on computing a single optimal solution, we address the problem of computing a compact representation of the space of all solutions that satisfy the constraints. This has the advantage that no optimization criterion has to be formulated beforehand, and that the space of possibilities can be explored systematically. In certain applications, such as diagnosis and design, these advantages are crucial. In consistency techniques, the solution space is represented by labels assigned to individual variables or combinations of variables. When the labeling is globally consistent, each label contains only those values or combinations of values which appear in at least one solution. This kind of labeling is a compact, sound and complete representation of the solution space, and can be combined with other reasoning methods. In practice, computing a globally consistent labeling is too complex. This is usually tackled in two ways. One way is to enforce consistencies locally, using propagation algorithms. This prunes the search space and hence reduces the subsequent search effort. The other way is to identify simplifying properties which guarantee that global consistency can be enforced tractably using local propagation algorithms. When constraints are represented by mathematical expressions, implementing local consistency algorithms is difficult because it requires tools for solving arbitrary systems of equations. In this thesis, we propose to approximate feasible solution regions by 2k-trees, thus providing a means of combining constraints logically rather than numerically. This representation, commonly used in computer vision and image processing, avoids using complex mathematical tools. We propose simple and stable algorithms for computing labels of arbitrary degrees of consistency using this representation. For binary constraints, it is known that simplifying convexity properties reduces the complexity of solving a CSP. These properties guarantee that local degrees of consistency are sufficient to ensure global consistency. We show how, in continuous domains, these results can be generalized to ternary and in fact arbitrary n-ary constraints. This leads to polynomial-time algorithms for computing globally consistent labels for a large class of constraint satisfaction problems with continuous variables. We describe and justify our representation of constraints and our consistency algorithms. We also give a complete analysis of the theoretical results we present. Finally, the developed techniques are illustrated using practical examples.

Related lectures (29)

Anastasia Ailamaki, Bikash Chandra, Riccardo Mancini, Srinivas Karthik Venkatesh

Modern data analytical workloads often need to run queries over a large number of tables. An optimal query plan for such queries is crucial for being able to run these queries within acceptable time bounds. However, with queries involving many tables, finding the optimal join order becomes a bottleneck in query optimization. Due to the exponential nature of join order optimization, optimizers resort to heuristic solutions after a threshold number of tables. Our objective is two fold: (a) reduce the optimization time for generating optimal plans; and (b) improve the quality of the heuristic solution. In this paper, we propose a new massively parallel algorithm, MPDP, that can efficiently prune the large search space (via a novel plan enumeration technique) while leveraging the massive parallelism offered by modern hardware (Eg: GPUs). When evaluated on real-world benchmark queries with PostgreSQL, MPDP is at least an order of magnitude faster compared to state-of-the-art techniques for large analytical queries. As a result, we are able to increase the heuristic-fall-back limit from 12 relations to 25 relations with same time budget in PostgreSQL. Also, in order to handle queries with even larger number of tables, we augment MPDP to a well known heuristic, IDP2 (iterative DP version 2) and a novel heuristic UnionDP. By systematically exploring a much larger search space, these heuristics provides query plans that are up to 7 times cheaper as compared to the state-of-the-art techniques while being faster to compute.

2022Anastasia Ailamaki, Bikash Chandra, Riccardo Mancini, Srinivas Karthik Venkatesh

Analytics on modern data analytic and data warehouse systems often need to run large complex queries on increasingly complex database schemas. A lot of progress has been made on executing such complex queries using techniques like scale out query processing, hardware accelerators like GPUs and code generation techniques. However, optimization of such queries remains a challenge. Existing optimal solutions either cannot be effectively parallelized, or are inefficient while doing a lot of unnecessary work. In this demonstration, we present our system, GPU-QO, which aims to demonstrate query optimization techniques for large analytical queries using GPUs. We first demonstrate Massively Parallel Dynamic Programming (MPDP) – a novel query optimization technique that can run on GPUs to generate optimal plans in a (massively) parallel and efficient manner. We then showcase IDP2-MPDP and UnionDP – two heuristic techniques, again using GPUs, that can even optimize queries containing 1000s of joins. Furthermore, we compare our techniques with current state-of-the-art solutions, and demonstrate how our techniques can reduce optimization time for optimal solutions by nearly two orders of magnitude and produce much better query plans for heuristics (up to 7x).