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

Lecture

Integer Programming: Doignon's Theorem

In course

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 science and cryptography during the past 30 years. ...

Description

This lecture discusses Doignon's theorem in integer programming, which states that a set is minimally infeasible if the removal of any constraint makes it feasible. The theorem, introduced by Doignon in 1973, is explained with mathematical notation and a proof. The lecture also covers the concept of convex hull and the conditions for a set to be considered infeasible.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Official source

Related concepts (17)

Convex hull

In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset. Convex hulls of open sets are open, and convex hulls of compact sets are compact.

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.

Convex set

In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex region is a subset that intersects every line into a single line segment (possibly empty). For example, a solid cube is a convex set, but anything that is hollow or has an indent, for example, a crescent shape, is not convex. The boundary of a convex set is always a convex curve.

Carathéodory's theorem (convex hull)

Carathéodory's theorem is a theorem in convex geometry. It states that if a point lies in the convex hull of a set , then can be written as the convex combination of at most points in . More sharply, can be written as the convex combination of at most extremal points in , as non-extremal points can be removed from without changing the membership of in the convex hull. Its equivalent theorem for conical combinations states that if a point lies in the conical hull of a set , then can be written as the conical combination of at most points in .

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.

Related lectures (34)

Optimization with Constraints: KKT Conditions

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

Linear Programming: Weighted Bipartite Matching

Covers linear programming, weighted bipartite matching, and vertex cover problems in optimization.

Optimisation Problem: Solving by FM

Covers the modelling and optimization of energy systems, focusing on solving optimization problems with constraints and variables.

Linear Constraints: Polyhedron MOOC: Optimization: principles and algorithms - Linear optimization

Explains linear constraints and the concept of a polyhedron in optimization problems.

Optimization Methods: Theory Discussion