In applied mathematics and computer science, variable splitting is a decomposition method that relaxes a set of constraints.
Details
When the variable x {\displaystyle x} appears in two sets of constraints, it is possible to substitute the new variables x 1 {\displaystyle x_{1}} in the first constraints and x 2 {\displaystyle x_{2}} in the second, and then join the two variables with a new "linking" constraint,2 which requires that
x 1 = x 2 {\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 x 1 {\displaystyle x_{1}} and x 2 {\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 x {\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
Bibliography
- Adlers, Mikael; Björck, Åke (2000). "Matrix stretching for sparse least squares problems". Numerical Linear Algebra with Applications. 7 (2): 51–65. doi:10.1002/(sici)1099-1506(200003)7:2<51::aid-nla187>3.0.co;2-o. ISSN 1099-1506.
- Alvarado, Fernando (1997). "Matrix enlarging methods and their application". BIT Numerical Mathematics. 37 (3): 473–505. CiteSeerX 10.1.1.24.5976. doi:10.1007/BF02510237. S2CID 120358431.
- Grcar, Joseph (1990). Matrix stretching for linear equations (Technical report). Sandia National Laboratories. arXiv:1203.2377. Bibcode:2012arXiv1203.2377G. SAND90-8723.
- Vanderbei, Robert J. (July 1991). "Splitting dense columns in sparse linear systems". Linear Algebra and Its Applications. 152: 107–117. doi:10.1016/0024-3795(91)90269-3. ISSN 0024-3795.
- Jörnsten, Kurt O.; Näsberg, Mikael; Smeds, Per A. (1985). "Variable Splitting: A New Lagrangean Relaxation Approach to Some Mathematical Programming Models". LiTH MAT R. 84–85. University of Linköping, Department of Mathematics: 1–52.
- Guignard, Monique; Kim, Siwhan (1987). "Lagrangean Decomposition: A Model Yielding Stronger Bounds". Mathematical Programming. 39 (2): 215–228. doi:10.1007/BF02592948. hdl:2027.42/6740.
References
Pipatsrisawat, Knot; Palyan, Akop; Chavira, Mark; Choi, Arthur; Darwiche, Adnan (2008). "Solving Weighted Max-SAT Problems in a Reduced Search Space: A Performance Analysis". Journal on Satisfiability Boolean Modeling and Computation. 4(2008). UCLA: 4. Retrieved 18 April 2022. http://reasoning.cs.ucla.edu/fetch.php?id=86&type=pdf ↩
Vanderbei (1991) - Vanderbei, Robert J. (July 1991). "Splitting dense columns in sparse linear systems". Linear Algebra and Its Applications. 152: 107–117. doi:10.1016/0024-3795(91)90269-3. ISSN 0024-3795. https://doi.org/10.1016%2F0024-3795%2891%2990269-3 ↩
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. ↩