Handling Free Variables via Variable Splitting

When converting a linear program to standard form, every decision variable must be non-negative. A free (unrestricted) variable is rewritten as the difference of two non-negative variables — a technique called variable splitting. This lesson covers the splitting substitution, applying it throughout the objective and constraints, handling multiple free variables, and recovering original variable values after solving.

Step 1 of 157%

Tutorial

Free Variables and the Splitting Substitution

A linear program is in standard form when every decision variable is required to be non-negative. A decision variable that has no sign restriction — one allowed to take any real value (positive, negative, or zero) — is called a free variable (or unrestricted variable).

To handle a free variable when converting an LP to standard form, we use variable splitting. We replace each free variable $x$ with the difference of two new non-negative variables:

x = x^+ - x^-, \quad x^+ \geq 0, \quad x^- \geq 0.

This substitution is valid because every real number is expressible as the difference of two non-negative reals. For instance, if the optimal value of $x$ turns out to be $7$ , the optimizer can choose $x^+ = 7$ and $x^- = 0$ ; if it turns out to be $-4$ , the optimizer can choose $x^+ = 0$ and $x^- = 4$ .

The representation is not unique (we could also write $7 = 10 - 3$ ), but the LP solver will pick whichever values of $x^+$ and $x^-$ are best for the objective.