Concept

Discrete optimization

Related lectures (25)

Discrete Optimization: Set Covering

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

The Backpack Problem

Introduces the backpack problem, a discrete optimization problem with constraints and algorithms to solve it.

Discrete Optimization: Traveling Salesman Problem

Covers the traveling salesman problem, modeling, constraints, additional constraints, and network representation.

Traveling Salesman Problem: Introduction and Approximation Methods

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

Metropolis Algorithm: Optimization and Probabilistic Approach

Covers the Metropolis algorithm for approximate optimization using lazy chains and exploring state space efficiently.

Discrete Optimization: The Curse of Dimensionality

Delves into the curse of dimensionality in discrete optimization, highlighting the challenges of exponential computational time growth with problem size.

Exact methods: Branch and Bound

Explores the Branch and Bound algorithm in discrete optimization, efficiently finding optimal solutions by calculating lower bounds on subsets.

Optimal Decision Making: Applications of Discrete Optimization

Explores optimal decision making through discrete optimization, emphasizing binary variables and practical applications.

Optimal Decision Making: Integer Programming

Covers integer programming, convex hulls, Gomory cutting planes, and branch and bound methods.

Knapsack Problem: Optimization and Traveling Salesman

Explores the knapsack problem and the traveling salesman problem with a focus on optimization algorithms.

Introduction to Optimization

Introduces linear algebra, calculus, and optimization basics in Euclidean spaces, emphasizing the power of optimization as a modeling tool.

Statistical Physics: Spin Glasses & Optimization

Explores the Curie-Weiss model, spin glasses, and optimization problems in statistical physics.

Random Walk and Diffusion

Explores binomial distribution, random walk, and diffusion concepts in a continuous context.

Discrete variables: Geometric properties

Covers geometric properties of discrete variables in GIS, including location, size, and shape.

Discrete Optimization: Relaxation

Explores solving discrete optimization problems by relaxing integrality constraints.

Introduction to Optimization and Operations Research

Covers fundamental concepts of optimization and operations research, exploring real-world examples and key topics over a semester.

Estimating Stability and Quality

Covers the process of estimating stability and quality in numerical methods, focusing on discrete problems and algebraic identities.

Discrete Variables: Spatial Arrangement and Neighbourhood

Covers geometric properties, spatial arrangement, autocorrelation, and neighbourhood analysis in geographic information systems.

Discrete Optimization: Modeling

Covers logical operations and constraints in discrete optimization modeling.

Discrete Optimization: Definitions

Covers definitions and concepts in discrete optimization, including binary linear problems and combinatorial optimization.