A Tight Linearization Strategy for Zero-One Quadratic Programming Problems
In this paper, we present a new approach to linearizing zero-one quadratic minimization problem which has many applications in computer science and communications. Our algorithm is based on the observation that the quadratic term of zero-one variables has two equivalent piece-wise formulations, convex and concave cases. The convex piece-wise objective function and/or constraints play a great role in deducing small linearization. Further tight strategies are also discussed.
Keywords: Integer programming, quadratic programming, linearization.
Download Full-Text
ABOUT THE AUTHORS
Wajeb Gharibi
1 Dept. of Computer Science, College of Computer Science & Information Systems, Jazan University, Jazan 82822-6694, KSA.
Yong Xia
School of Mathematics and System Sciences, Beihang University Beijing, 100191, P. R. China
Wajeb Gharibi
1 Dept. of Computer Science, College of Computer Science & Information Systems, Jazan University, Jazan 82822-6694, KSA.
Yong Xia
School of Mathematics and System Sciences, Beihang University Beijing, 100191, P. R. China