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

Lecture

The transhipment problem: Total unimodularity

Description

This lecture covers the transhipment problem in standard form, the incidence matrix, optimal solutions using Cramer's rule, and the concept of total unimodularity in matrices. It also includes examples and the integrality of basic solutions in polyhedrons.

In MOOC

Optimization: principles and algorithms - Network and discrete optimization

Official source

Related concepts (16)

Polyhedron

In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. A convex polyhedron is a polyhedron that bounds a convex set. Every convex polyhedron can be constructed as the convex hull of its vertices, and for every finite set of points, not all on the same plane, the convex hull is a convex polyhedron. Cubes and pyramids are examples of convex polyhedra. A polyhedron is a 3-dimensional example of a polytope, a more general concept in any number of dimensions.

Incidence matrix

In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y. The entry in row x and column y is 1 if x and y are related (called incident in this context) and 0 if they are not. There are variations; see below. Incidence matrix is a common graph representation in graph theory.

Dual polyhedron

In geometry, every polyhedron is associated with a second dual structure, where the vertices of one correspond to the faces of the other, and the edges between pairs of vertices of one correspond to the edges between pairs of faces of the other. Such dual figures remain combinatorial or abstract polyhedra, but not all can also be constructed as geometric polyhedra. Starting with any given polyhedron, the dual of its dual is the original polyhedron. Duality preserves the symmetries of a polyhedron.

Goldberg polyhedron

In mathematics, and more specifically in polyhedral combinatorics, a Goldberg polyhedron is a convex polyhedron made from hexagons and pentagons. They were first described in 1937 by Michael Goldberg (1902–1990). They are defined by three properties: each face is either a pentagon or hexagon, exactly three faces meet at each vertex, and they have rotational icosahedral symmetry. They are not necessarily mirror-symmetric; e.g. GP(5,3) and GP(3,5) are enantiomorphs of each other.

Flexible polyhedron

In geometry, a flexible polyhedron is a polyhedral surface without any boundary edges, whose shape can be continuously changed while keeping the shapes of all of its faces unchanged. The Cauchy rigidity theorem shows that in dimension 3 such a polyhedron cannot be convex (this is also true in higher dimensions). The first examples of flexible polyhedra, now called Bricard octahedra, were discovered by . They are self-intersecting surfaces isometric to an octahedron.

Related lectures (30)

Linear Constraints: Basic Solutions MOOC: Optimization: principles and algorithms - Linear optimization

Explores basic solutions in linear constraints and the equivalence with vertices.

Linear constraints, Degeneracy MOOC: Optimization: principles and algorithms - Linear optimization

Covers linear constraints and degeneracy in polyhedrons, focusing on basic solutions and degenerate cases.

Optimization: Classical Problems

Covers classical optimization problems, brute force algorithms, and integer linear optimization.

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

Explores the significance of vertices in optimization and outlines a method to identify them using linear algebra.

The Transhipment Problem: Total Unimodularity MOOC: Optimization: principles and algorithms - Network and discrete optimization