# Optimal partition

### From Glossary

Consider a primal-dual pair of linear programs:

Define primal surplus variables, and dual slack variables, For any non-negative vector, define its *support set* as those indexes for which the coordinate value is positive:
In an optimal solution, complementary slackness must hold, so that
implies
and
implies
Thus, the intersections,
and
are empty. If the solution is strictly complementary, these support sets yield partitions because then
and
A strictly complementary solution is an interior solution (and conversely), so each interior solution yields a partition of these index sets.

A key fact is that every LP with an optimal solution must have an optimal interior solution. Further, every optimal interior solution yields the *same* partition, so it is called *the* optimal partition.