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, and the total unimodularity theorem. It explains how the incidence matrix of a network is totally unimodular, leading to integer optimal solutions for the transhipment problem when the supply vector is integer.

In MOOC

Optimization: principles and algorithms - Network and discrete optimization

Official source

Ontological neighbourhood

Theoretical computer science

Algorithms and data structures: Combinatorial optimization

Related concepts (19)

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.

Unimodular matrix

In mathematics, a unimodular matrix M is a square integer matrix having determinant +1 or −1. Equivalently, it is an integer matrix that is invertible over the integers: there is an integer matrix N that is its inverse (these are equivalent under Cramer's rule). Thus every equation Mx = b, where M and b both have integer components and M is unimodular, has an integer solution. The n × n unimodular matrices form a group called the n × n general linear group over , which is denoted .

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.

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.

Incidence structure

In mathematics, an incidence structure is an abstract system consisting of two types of objects and a single relationship between these types of objects. Consider the points and lines of the Euclidean plane as the two types of objects and ignore all the properties of this geometry except for the relation of which points are on which lines for all points and lines. What is left is the incidence structure of the Euclidean plane.

Related lectures (50)

Linear Programming: Weighted Bipartite Matching

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

The Transhipment Problem: Standard Form MOOC: Optimization: principles and algorithms - Network and discrete optimization

Covers the linear optimization problem of the transhipment model.

Exact methods: Branch and Bound MOOC: Optimization: principles and algorithms - Network and discrete optimization

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

Approximation Algorithms

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

Discrete Optimization: Relaxation MOOC: Optimization: principles and algorithms - Network and discrete optimization