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

Lecture

Discrete Optimization: Traveling Salesman Problem

Description

This lecture introduces the traveling salesman problem, where the goal is to find the shortest itinerary visiting all cities exactly once. The instructor covers modeling the problem with decision variables and constraints, including additional constraints and a network representation. The lecture concludes with the formulation of the problem and a summary.

In MOOC

Optimization: principles and algorithms - Network and discrete optimization

Official source

Related concepts (14)

Discrete optimization

Discrete optimization is a branch of optimization in applied mathematics and computer science. As opposed to continuous optimization, some or all of the variables used in a discrete mathematical program are restricted to be discrete variables—that is, to assume only a discrete set of values, such as the integers. Three notable branches of discrete optimization are: combinatorial optimization, which refers to problems on graphs, matroids and other discrete structures integer programming constraint programming These branches are all closely intertwined however since many combinatorial optimization problems can be modeled as integer programs (e.

Combinatorial optimization

Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.

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.

Optimization problem

In mathematics, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables are continuous or discrete: An optimization problem with discrete variables is known as a discrete optimization, in which an object such as an integer, permutation or graph must be found from a countable set.

Travelling salesman problem

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research. The travelling purchaser problem and the vehicle routing problem are both generalizations of TSP.

Related lectures (37)

Discrete Optimization: Set Covering MOOC: Optimization: principles and algorithms - Network and discrete optimization

Explores the set covering problem through the example of completing a sticker collection at a minimum cost.

Optimization with Constraints: KKT Conditions

Covers the KKT conditions for optimization with constraints, essential for solving constrained optimization problems efficiently.

Traveling Salesman Problem: Introduction and Approximation Methods

Introduces the Traveling Salesman Problem and explores approximation methods using Markov chains.

Optimization Methods: Theory Discussion

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

The Backpack Problem MOOC: Information, Computation, Communication: Introduction to computational thinking