International Journal of Nonlinear Analysis and Applications

Solving binary semidefinite programming problems and binary linear programming problems via multi-objective programming

Document Type : Research Paper

Authors

Faculty of Mathematics, Statistics and Computer Science, Semnan University, Semnan, Iran

Abstract

‎In recent years the binary quadratic program has grown in‎ ‎combinatorial optimization‎. ‎Quadratic programming can‎ ‎be formulated as a semidefinite programming problem‎. ‎In this paper‎, ‎we consider the general form of‎ ‎binary semidefinite programming problems (BSDP)‎.‎ ‎We show the optimal solutions of the BSDP belong to the efficient set of a semidefinite multiobjective programming problem (SDMOP)‎. ‎Although‎ ‎finding all efficient points for multiobjective is not an easy problem‎, ‎but‎
‎solving a continuous problem would be easier than a discrete variable problem‎. ‎In this paper‎, ‎we solve an SDMOP‎, ‎as an auxiliary‎, ‎instead of BSDP‎. We show the performance of our method by generating and solving random problems.

Keywords

[1] B. Alidaee, A.G. Kochenberger and A. Ahmadian, 0-1 quadratic programming approach for optimum solutions of two scheduling problems, Int. J. Syst. Sci. 25.2 (1994) 401-408.
[2] X. Bao, N.V. Sahinidis and M. Tawarmalani, Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons, Math. Prog. 129(1) (2011) 129.
[3] H.P. Benson, A finite, nonadjacent extreme-point search algorithm for optimization over the efficient set, J. Opt. Theory Appl. 73(1) (1992) 47–64.
[4] H.P. Benson and E. Sun, New closedness results for efficient sets in multiple objective mathematical programming, Journal of mathematical analysis and applications, 238(1) (1999) 277–296.
[5] S. Burer, D.M. Renato and Y. Zhang, Rank-two relaxation heuristics for max-cut and other binary quadratic programs, SIAM J. Opt. 12(2) (2002) 503–521.
[6] F. Glover, B. Alidaee, C. Rego and G. Kochenberger, One-pass heuristics for large-scale unconstrained binary quadratic problems, European J. Oper. Res. 137(2) (2002) 272–287.
[7] G.A. Kochenberger,F. Glover, B. Alidaee and C. Rego, A unified modeling and solution framework for combinatorial optimization problems, OR Spect. 26(2) (2004) 237–250.
[8] D.G. Luenberger and Y. Yinyu, Linear and Nonlinear Programming, Springer, 2016.
[9] J. Luo, K.R. Pattipati, P.K. Willett and F. Hasegawa, Near-optimal multiuser detection in synchronous CDMA using probabilistic data association IEEE Commun. Lett. 5(9) (2001) 361–363.
[10] P. Merz and B. Freisleben, Genetic algorithms for binary quadratic programming, Proc. 1st Ann. Conf. Gen. Evolut. Comput. Volume 1. Morgan Kaufmann Publishers Inc., 1999.
[11] O. Ozpeynirci and M. Koksalan, An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs, Manag. Sci. 56(12) (2010) 2302–2315.
[12] P.M. Pardalos and G.R. Rodgers, A branch and bound algorithm for maximum clique problem Comput. Oper. Res. 19 (1992) 363—375.
[13] A.T. Phillips and J.B. Rosen, A quadratic assignment formulation of the molecular conformation problem Journal of Global Optimization, 4.2 (1994) 229-241.
[14] S. Poljak and H. Wolkowicz, Convex relaxations of (0, 1)-quadratic programming Mathematics of Operations Research, 20.3 (1995) 550-561.
[15] H. Wolkowicz, and M.F. Anjos, Semidefinite programming for discrete optimization and matrix completion problems, Discrete Appl. Math. 123(1-3) (2002) 513–577.
[16] H. Wolkowicz, R. Saigal and L. Vandenberghe, Handbook of semidefinite programming: theory, algorithms, and applications, Springer Science and Business Media, 2012.
[17] Z. Xu, M. Hong and Z.Q. Luo, Semidefinite approximation for mixed binary quadratically constrained quadratic programs, SIAM J. Opt. 24(3) (2014) 1265–1293.
International Journal of Nonlinear Analysis and Applications
Volume 13, Issue 1
March 2022
Pages 297-304
  • Receive Date: 02 February 2018
  • Revise Date: 21 July 2018
  • Accept Date: 13 February 2019