# Optimal partition

$LaTeX: \min \left \{cx: x \ge 0, Ax \ge b \right \} \mbox{ and } \max \left \{yb: y \ge 0, yA \le c \right \}.$
Define primal surplus variables, $LaTeX: s = Ax - b,$ and dual slack variables, $LaTeX: d = c - yA.$ For any non-negative vector, $LaTeX: v,$ define its support set as those indexes for which the coordinate value is positive: $LaTeX: \textstyle I(v)= \left \{j: v_j > 0 \right \}.$ In an optimal solution, complementary slackness must hold, so that $LaTeX: \textstyle j \in I(x)$ implies $LaTeX: j \notin I(d),$ and $LaTeX: \textstyle i \in I(s)$ implies $LaTeX: i \notin I(y).$ Thus, the intersections, $LaTeX: \textstyle I(x) \land I(d)$ and $LaTeX: \textstyle I(s) \land I(y),$ are empty. If the solution is strictly complementary, these support sets yield partitions because then $LaTeX: \textstyle I(x) \lor I(d) = \left \{1, \dots, n \right \}$ and $LaTeX: \textstyle I(s) \lor I(y) = \left \{1, \dots, m \right \}.$ A strictly complementary solution is an interior solution (and conversely), so each interior solution yields a partition of these index sets.