Lecture

Optimization Techniques: Local Search, VNS, Simulated Annealing

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture covers optimization techniques such as local search, variable neighborhood search (VNS), and simulated annealing. It explains concepts like 2-OPT neighborhood, lexicographic rules, dominance, and weighted sum. The instructor demonstrates how to transform multi-objective optimization problems into single-objective ones and discusses heuristics for optimization. Practical examples and algorithms are provided to illustrate the application of these techniques.

Official source

Ontological neighbourhood

Mathematics

Mathematical optimization: Metaheuristics

Related concepts (32)

Local search (optimization)

In computer science, local search is a heuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions. Local search algorithms move from solution to solution in the space of candidate solutions (the search space) by applying local changes, until a solution deemed optimal is found or a time bound is elapsed.

Mathematical optimization

Mathematical optimization (alternatively spelled optimisation) or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

Tabu search

Tabu search (TS) is a metaheuristic search method employing local search methods used for mathematical optimization. It was created by Fred W. Glover in 1986 and formalized in 1989. Local (neighborhood) searches take a potential solution to a problem and check its immediate neighbors (that is, solutions that are similar except for very few minor details) in the hope of finding an improved solution. Local search methods have a tendency to become stuck in suboptimal regions or on plateaus where many solutions are equally fit.

Multi-objective optimization

Multi-objective optimization or Pareto optimization (also known as multi-objective programming, vector optimization, multicriteria optimization, or multiattribute optimization) is an area of multiple-criteria decision making that is concerned with mathematical optimization problems involving more than one objective function to be optimized simultaneously. Multi-objective is a type of vector optimization that has been applied in many fields of science, including engineering, economics and logistics where optimal decisions need to be taken in the presence of trade-offs between two or more conflicting objectives.

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 the search space of a problem domain, with either discrete or continuous values. Although search engines use search algorithms, they belong to the study of information retrieval, not algorithmics. The appropriate search algorithm to use often depends on the data structure being searched, and may also include prior knowledge about the data.

Related lectures (64)

Constraint Satisfaction: Formulation and Algorithms

Covers the formulation of constraint satisfaction problems and systematic algorithms for solving them efficiently.

Set Cover: Integrality Gap

Explores the integrality gap concept in set cover and multiplicative weights algorithms.

Optimisation in Energy Systems

Explores optimization in energy system modeling, covering decision variables, objective functions, and different strategies with their pros and cons.

Distributed Intelligent Systems: General Logistics and Course Overview

Covers the general logistics, course rationale, prerequisites, organization, credits, workload, grading, and course content, including swarm intelligence, foraging strategies, and collective phenomena.

Optimization Methods: Theory Discussion