**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.

Lecture# Integer Optimization: Theory and Applications

Description

This lecture covers the fundamentals of integer optimization, including integer programming, dynamic programming, approximation algorithms, and set-cover problems. The instructor discusses the complexity of integer programming, the linear programming relaxation, branch & bound, and the knapsack problem. The lecture also explores topics such as Steinitz Lemma, GCD, Euclidean Algorithm, lattices, Minkowski's Theorem, and transference bounds. Additionally, the lecture delves into the application of integer programming in fixed dimension and algorithms for the Shortest Vector Problem (SVP).

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.

Instructor

Related concepts (153)

In course

Set theory

Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concerned with those that are relevant to mathematics as a whole. The modern study of set theory was initiated by the German mathematicians Richard Dedekind and Georg Cantor in the 1870s. In particular, Georg Cantor is commonly considered the founder of set theory.

Integer programming

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear. Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems.

Set (mathematics)

A set is the mathematical model for a collection of different things; a set contains elements or members, which can be mathematical objects of any kind: numbers, symbols, points in space, lines, other geometrical shapes, variables, or even other sets. The set with no element is the empty set; a set with a single element is a singleton. A set may have a finite number of elements or be an infinite set. Two sets are equal if they have precisely the same elements. Sets are ubiquitous in modern mathematics.

Empty set

In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other theories, its existence can be deduced. Many possible properties of sets are vacuously true for the empty set. Any set other than the empty set is called non-empty. In some textbooks and popularizations, the empty set is referred to as the "null set".

Linear programming

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization). More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints.

MATH-504: Integer optimisation

The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer s

Related lectures (655)

Approximation AlgorithmsCS-450: Algorithms II

Covers approximation algorithms for optimization problems, LP relaxation, and randomized rounding techniques.

Recursive Algorithms: Induction & SortingCS-101: Advanced information, computation, communication I

Explores induction, recursion, and sorting algorithms, including merge sort and the proof of correctness for recursive algorithms.

Counterfactuals: SEM and D-SeparationMGT-416: Causal inference

Explores counterfactuals in SEMs and D-Separation in graphical models.

Complex Systems: Critical PhenomenaPHYS-435: Statistical physics III

Explores critical phenomena in complex systems, including stochastic objects, percolation, and combinatorial optimization.

Set Cover: Integrality GapCS-450: Algorithms II

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