Total dual integrality information

In mathematical optimization, total dual integrality is a sufficient condition for the integrality of a polyhedron. Thus, the optimization of a linear objective over the integral points of such a polyhedron can be done using techniques from linear programming.

A linear system $Ax\leq b$ , where $A$ and $b$ are rational, is called totally dual integral (TDI) if for any $c\in \mathbb {Z} ^{n}$ such that there is a feasible, bounded solution to the linear program

{\begin{aligned}&&\max c^{\mathrm {T} }x\\&&Ax\leq b,\end{aligned}}

there is an integer optimal dual solution.^[1]^[2]^[3]

Edmonds and Giles^[2] showed that if a polyhedron $P$ is the solution set of a TDI system $Ax\leq b$ , where $b$ has all integer entries, then every vertex of $P$ is integer-valued. Thus, if a linear program as above is solved by the simplex algorithm, the optimal solution returned will be integer. Further, Giles and Pulleyblank^[1] showed that if $P$ is a polytope whose vertices are all integer valued, then $P$ is the solution set of some TDI system $Ax\leq b$ , where $b$ is integer valued.

Note that TDI is a weaker sufficient condition for integrality than total unimodularity.^[4]

^ ^a ^b Giles, F.R.; W.R. Pulleyblank (1979). "Total Dual Integrality and Integer Polyhedra". Linear Algebra and its Applications. 25: 191–196. doi:10.1016/0024-3795(79)90018-1.
^ ^a ^b Edmonds, J.; R. Giles (1977). "A min-max relation for submodular functions on graphs". Annals of Discrete Mathematics. 1: 185–204.
^ Schrijver, A. (1981). "On Total Dual Integrality". Linear Algebra and its Applications. 38: 27–32. doi:10.1016/0024-3795(81)90005-7.
^ Chekuri, C. "Combinatorial Optimization Lecture Notes" (PDF).

[gilesPulleyblank-1] Giles, F.R.; W.R. Pulleyblank (1979). "Total Dual Integrality and Integer Polyhedra". Linear Algebra and its Applications. 25: 191–196. doi:10.1016/0024-3795(79)90018-1.

[EdmondsGiles-2] Edmonds, J.; R. Giles (1977). "A min-max relation for submodular functions on graphs". Annals of Discrete Mathematics. 1: 185–204.

[3] Schrijver, A. (1981). "On Total Dual Integrality". Linear Algebra and its Applications. 38: 27–32. doi:10.1016/0024-3795(81)90005-7.

[4] Chekuri, C. "Combinatorial Optimization Lecture Notes" (PDF).

Total dual integrality information

and 20 Related for: Total dual integrality information

Total dual integrality

TDI

Unimodular matrix

Linear programming

List of numerical analysis topics

Configuration linear program

Integral linear operator

Surface integral

Pontryagin duality

Hodge star operator

Fractional coloring

Integral probability metric

Ba space

IISER Aptitude Test

Total variation denoising

Polytope

Calculus

Bushmaster III

Wasserstein metric

Wikipedia