Manifold relaxations for integer programming

Zhiguo Feng; Ka-Fai Cedric Yiu

doi:10.3934/jimo.2014.10.557

Article Contents

2014, Volume 10, Issue 2: 557-566. Doi: 10.3934/jimo.2014.10.557

This issue Previous Article Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems Next Article Multimodal image registration by elastic matching of edge sketches via optimal control

Manifold relaxations for integer programming

Zhiguo Feng^1, and
Ka-Fai Cedric Yiu^2,

1.
College of Mathematics, Chongqing Normal University, Chongqing
2.
Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong

Received: September 30, 2012

Revised: July 31, 2013

Published: March 2014

Abstract Related Papers Cited by

Abstract

In this paper, the integer programming problem is studied. We introduce the notion of integer basis and show that a given integer set can be converted into a fixed number of linear combinations of the basis elements. By employing the Stiefel manifold and optimal control theory, the combinatorial optimization problem can be converted into a continuous optimization problem over the continuous Stiefel manifold. As a result, gradient descent methods can be applied to find the optimal integer solution. We demonstrate by numerical examples that this approach can obtain good solutions. Furthermore, this method gives new insights into continuous relaxation for solving integer programming problems.

Keywords:

Mathematics Subject Classification: Primary: 90C10, 90C57; Secondary: 58D10.

Citation:

Related Papers

Cited by

References

[1]	M. Borchardt, An exact penalty approach for solving a class of minimization problems with Boolean variables, Optimization, 19 (1988), 829-838.doi: 10.1080/02331938808843396.
[2]	Q. Chai, R. Loxton, K. L. Teo and C. H. Yang, A max-min control problem arising in gradient elution chromatography, Ind. Eng. Chem. Res., 51 (2012), 6137-6144.doi: 10.1021/ie202475p.
[3]	A. Edelman, T. A. Arias and S. Smith, The geometry of algorithms with orthogonality constraints, SIAM J. Matrix Anal. Appl., 20 (1998), 303-353.doi: 10.1137/S0895479895290954.
[4]	Z. G. Feng and K. L. Teo, A discrete filled function method for the design of FIR filters with signed-powers-of-two coefficients, IEEE Trans. on Signal Process., 56 (2008), 134-139.doi: 10.1109/TSP.2007.901164.
[5]	Z. G. Feng, K. L. Teo and Y. Zhao, Branch and bound method for sensor scheduling in discrete time, J. Ind. Manag. Optim., 1 (2005), 499-512.doi: 10.3934/jimo.2005.1.499.
[6]	R. Fletcher, Practical Methods of Optimization, 2nd edition, A Wiley-Interscience Publication, John Wiley & Sons, Ltd., Chichester, 1987.
[7]	C. Helmberg and F. Rendl, Solving quadratic (0,1)-problems by semidefinite programming and cutting planes, Math. Programming, 82 (1998), 291-315.doi: 10.1007/BF01580072.
[8]	M. Jünger, T. M. Liebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, Giovanni Rinaldi and L. A. Wolsey, eds., 50 Years of Integer Programming 1958-2008. From the Early Years to the State-of-the-Art, Papers from the 12th Combinatorial Optimization Workshop (AUSSOIS 2008) held in Aussois, January 7-11, 2008, Springer-Verlag, Berlin Heidelberg, 2010.doi: 10.1007/978-3-540-68279-0.
[9]	B. Kalantari and J. B. Rosen, Penalty formulation for zero-one nonlinear programming, Discrete Appl. Math., 16 (1987), 179-182.doi: 10.1016/0166-218X(87)90073-4.
[10]	W. Murray and K.-M. Ng, An algorithm for nonlinear optimization problems with binary variables, Comput. Optim. Appl., 47 (2010), 257-288.doi: 10.1007/s10589-008-9218-1.
[11]	C.-K. Ng, L.-S. Zhang, D. Li and W.-W. Tian, Discrete filled function method for discrete global optimization, Comput. Optim. Appl., 31 (2005), 87-115.doi: 10.1007/s10589-005-0985-7.
[12]	P. M. Pardalos, O. A. Prokopyev and S. Busygin, Continuous approaches for solving discrete optimization problems, in Handbook on Modelling for Discrete Optimization, International Series in Operations Research & Management Science, Vol. 88, Springer, 2006, 39-60.doi: 10.1007/0-387-32942-0_2.
[13]	J. Richstein, Verifying the Goldbach conjecture up to $4\cdot 10^{14}$, Math. Comp., 70 (2001), 1745-1749.doi: 10.1090/S0025-5718-00-01290-4.
[14]	K. Schittkowski, More Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems, 282, Springer-Verlag, Berlin, 1987.doi: 10.1007/978-3-642-61582-5.
[15]	R. A. Shandiz and N. Mahdavi-amiri, An exact penalty approach for mixed integer nonlinear programming problems, American Journal of Operations Research, 1 (2011), 185-189.
[16]	H. D. Sherali and W. P. Adams, A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems, Discrete Appl. Math., 52 (1994), 83-106.doi: 10.1016/0166-218X(92)00190-W.
[17]	S. Wang, K. L. Teo, H. W. J. Lee and L. Caccetta, Solving 0-1 programming problems by a penalty approach, Opsearch, 34 (1997), 196-206.
[18]	W.-Y. Yan and K. L. Teo, Optimal finite-precision approximation of FIR filters, Signal Processing, 82 (2002), 1695-1705.doi: 10.1016/S0165-1684(02)00331-6.
[19]	K. F. C Yiu, Y. Liu and K. L. Teo, A hybrid descent method for global optimization, J. Global Optim., 28 (2004), 229-238.doi: 10.1023/B:JOGO.0000015313.93974.b0.
[20]	K. F. C Yiu, W. Y. Yan, K. L. Teo and S. Y. Low, A new hybrid descent method with application to the optimal design of finite precision FIR filters, Optim. Methods Softw., 25 (2010), 725-735.doi: 10.1080/10556780903254104.
[21]	C. Yu, B. Li, R. Loxton and K. L. Teo, Optimal discrete-valued control computation, Journal of Global Optimization, 56 (2013), 503-518.doi: 10.1007/s10898-012-9858-7.
[22]	W. X. Zhu, Penalty parameter for linearly constrained 0-1 quadratic programming, J. Optim. Theory Appl., 116 (2003), 229-239.doi: 10.1023/A:1022174505886.