variable splitting

In applied mathematics and computer science, variable splitting is a decomposition method that relaxes a set of constraints.{{cite journal |last1=Pipatsrisawat |first1=Knot |last2=Palyan |first2=Akop |last3=Chavira |first3=Mark |last4=Choi |first4=Arthur |last5=Darwiche |first5=Adnan |title=Solving Weighted Max-SAT Problems in a Reduced Search Space: A Performance Analysis |journal=Journal on Satisfiability Boolean Modeling and Computation |date=2008 |volume=4(2008) |page=4 |url=http://reasoning.cs.ucla.edu/fetch.php?id=86&type=pdf |access-date=18 April 2022 |publisher=UCLA}}

Details

When the variable $x$ appears in two sets of constraints, it is possible to substitute the new variables $x_1$ in the first constraints and $x_2$ in the second, and then join the two variables with a new "linking" constraint,{{harvtxt|Vanderbei|1991}} which requires that

: $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 $x_1$ and $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 $x$ .

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

References

{{reflist|refs=

Kurt O. Jörnsten, Mikael Näsberg, Per A. Smeds. (1985) "Variable Splitting: A New Lagrangean Relaxation Approach to Some Mathematical Programming Models"

Volumes 84-85 of LiTH MAT R.: Matematiska Institutionen Publisher - University of Linköping, Department of Mathematics,

Monique Guignard and Siwhan Kim. (1987) "Lagrangean Decomposition: A Model Yielding Stronger Bounds", Authors Mathematical Programming, 39(2), pp. 215-228.

}}

Bibliography

{{cite journal|last1=Adlers|first1=Mikael|last2=Björck|first2=Åke|authorlink2=Åke Björck|title=Matrix stretching for sparse least squares problems|year=2000|pages=51–65|journal=Numerical Linear Algebra with Applications|volume=7|issue=2|issn=1099-1506|doi=10.1002/(sici)1099-1506(200003)7:2<51::aid-nla187>3.0.co;2-o}}
{{cite journal|last=Alvarado|first=Fernando|title=Matrix enlarging methods and their application|journal=BIT Numerical Mathematics|year=1997|pages=473–505|volume=37|issue=3|

doi=10.1007/BF02510237|citeseerx=10.1.1.24.5976|s2cid=120358431}}

{{cite tech report |first=Joseph |last=Grcar |title=Matrix stretching for linear equations |institution=Sandia National Laboratories |number=SAND90-8723 |arxiv=1203.2377 |year=1990|bibcode=2012arXiv1203.2377G }}
{{cite journal|first=Robert J.|last=Vanderbei|authorlink=Robert J. Vanderbei|title=Splitting dense columns in sparse linear systems|journal=Linear Algebra and Its Applications|volume=152|date=July 1991|pages=107–117|issn=0024-3795

|doi= 10.1016/0024-3795(91)90269-3

|doi-access=free}}

{{cite journal |last1=Jörnsten |first1=Kurt O. |last2=Näsberg |first2=Mikael |last3=Smeds |first3=Per A. |title=Variable Splitting: A New Lagrangean Relaxation Approach to Some Mathematical Programming Models |journal=LiTH MAT R |volume=84–85 |year=1985 |publisher=University of Linköping, Department of Mathematics |pages=1–52 }}
{{cite journal |last1=Guignard |first1=Monique |last2=Kim |first2=Siwhan |title=Lagrangean Decomposition: A Model Yielding Stronger Bounds |journal=Mathematical Programming |volume=39 |issue=2 |year=1987 |pages=215–228 |doi=10.1007/BF02592948 |hdl=2027.42/6740 |hdl-access=free }}

Category:Decomposition methods