Variable splitting

In applied mathematics and computer science, variable splitting is a decomposition method that relaxes a set of constraints.^[1]

Details

When the variable ${\displaystyle x}$ appears in two sets of constraints, it is possible to substitute the new variables ${\displaystyle x_{1}}$ in the first constraints and ${\displaystyle x_{2}}$ in the second, and then join the two variables with a new "linking" constraint,^[2] which requires that

${\displaystyle x_{1}=x_{2}}$

This new linking constraint can be relaxed with a Lagrange multiplier; in many applications, a Lagrange multiplier can be interpreted as the price of equality between ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$ in the new constraint.

For many problems, relaxing the equality of split variables allows the system to be broken down, enabling each subsystem to be solved separately. This significantly reduces computation time and memory usage. Solving the relaxed problem with variable splitting can give an approximate solution to the initial problem. Using an approximate solution as a “warm start” facilitates the iterative solving of the original problem with only the variable ${\displaystyle x}$.

This was first introduced by Jörnsten, Näsberg, and Smeds in 1985.^[3] At the same time, M. Guignard and S. Kim introduced the same idea under the name "Lagrangean Decomposition" (their papers appeared in 1987).^[4]