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 appears in two sets of constraints, it is possible to substitute the new variables in the first constraints and in the second, and then join the two variables with a new "linking" constraint,[2] which requires that
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 and 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 .
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]
References
- ^ Page Module:Citation/CS1/styles.css has no content.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.
- ^ Lua error in package.lua at line 80: module 'Module:Footnotes/anchor_id_list' not found.
- ^ 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
- Page Module:Citation/CS1/styles.css has no content.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.
- Page Module:Citation/CS1/styles.css has no content.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.
- Page Module:Citation/CS1/styles.css has no content.Grcar, Joseph (1990). Matrix stretching for linear equations (Technical report). Sandia National Laboratories. arXiv:1203.2377. Bibcode:2012arXiv1203.2377G. SAND90-8723.
- Page Module:Citation/CS1/styles.css has no content.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.
- Page Module:Citation/CS1/styles.css has no content.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.
- Page Module:Citation/CS1/styles.css has no content.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.
