Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Optimization Techniques: Local Search, VNS, Simulated Annealing

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.

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.

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.

Iterated local search

Iterated Local Search (ILS) is a term in applied mathematics and computer science defining a modification of local search or hill climbing methods for solving discrete optimization problems. Local search methods can get stuck in a local minimum, where no improving neighbors are available. A simple modification consists of iterating calls to the local search routine, each time starting from a different initial configuration. This is called repeated local search, and implies that the knowledge obtained during the previous local search phases is not used.

Metaheuristic

In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, tune, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimization problem or a machine learning problem, especially with incomplete or imperfect information or limited computation capacity. Metaheuristics sample a subset of solutions which is otherwise too large to be completely enumerated or otherwise explored.

Related lectures (32)

Constraint Satisfaction: Formulation and Algorithms

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

Optimisation in Energy Systems

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

Optimization Methods: Theory Discussion

Explores optimization methods, including unconstrained problems, linear programming, and heuristic approaches.

Search Algorithms: Abductive Reasoning

Covers search algorithms, focusing on abductive reasoning and heuristic search strategies.

Optimization and Simulation: Heuristics and Neighborhoods