American Institute of Mathematical Sciences

Advanced
April  2014, 10(2): 557-566. doi: 10.3934/jimo.2014.10.557

Manifold relaxations for integer programming

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

1. 

College of Mathematics, Chongqing Normal University, Chongqing, China
2. 

Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong

Received  October 2012 Revised  August 2013 Published  October 2013

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: integer basis, optimal control, Integer programming, Stiefel manifold, permutation matrix..
Mathematics Subject Classification: Primary: 90C10, 90C57; Secondary: 58D1.
Citation: Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557
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.

show all references

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.

[1]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353
[2]

Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009
[3]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027
[4]

Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213
[5]

Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial and Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67
[6]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[7]

Mohamed A. Tawhid, Ahmed F. Ali. A simplex grey wolf optimizer for solving integer programming and minimax problems. Numerical Algebra, Control and Optimization, 2017, 7 (3) : 301-323. doi: 10.3934/naco.2017020
[8]

Mahmoud Ameri, Armin Jarrahi. An executive model for network-level pavement maintenance and rehabilitation planning based on linear integer programming. Journal of Industrial and Management Optimization, 2020, 16 (2) : 795-811. doi: 10.3934/jimo.2018179
[9]

René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363
[10]

Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115
[11]

Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks and Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783
[12]

Mahdi Roozbeh, Saman Babaie–Kafaki, Zohre Aminifard. Two penalized mixed–integer nonlinear programming approaches to tackle multicollinearity and outliers effects in linear regression models. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3475-3491. doi: 10.3934/jimo.2020128
[13]

Jayadev S. Athreya, Gregory A. Margulis. Values of random polynomials at integer points. Journal of Modern Dynamics, 2018, 12: 9-16. doi: 10.3934/jmd.2018002
[14]

Fanwen Meng, Kiok Liang Teow, Kelvin Wee Sheng Teo, Chee Kheong Ooi, Seow Yian Tay. Predicting 72-hour reattendance in emergency departments using discriminant analysis via mixed integer programming with electronic medical records. Journal of Industrial and Management Optimization, 2019, 15 (2) : 947-962. doi: 10.3934/jimo.2018079
[15]

Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial and Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431
[16]

Chaabane Djamal, Pirlot Marc. A method for optimizing over the integer efficient set. Journal of Industrial and Management Optimization, 2010, 6 (4) : 811-823. doi: 10.3934/jimo.2010.6.811
[17]

Luigi Ambrosio, Gianluca Crippa, Philippe G. Lefloch. Leaf superposition property for integer rectifiable currents. Networks and Heterogeneous Media, 2008, 3 (1) : 85-95. doi: 10.3934/nhm.2008.3.85
[18]

Rein Luus. Optimal control of oscillatory systems by iterative dynamic programming. Journal of Industrial and Management Optimization, 2008, 4 (1) : 1-15. doi: 10.3934/jimo.2008.4.1
[19]

Quyen Tran, Harbir Antil, Hugo Díaz. Optimal control of parameterized stationary Maxwell's system: Reduced basis, convergence analysis, and a posteriori error estimates. Mathematical Control and Related Fields, 2022  doi: 10.3934/mcrf.2022003
[20]

Oliver Junge, Alex Schreiber. Dynamic programming using radial basis functions. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4439-4453. doi: 10.3934/dcds.2015.35.4439

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (139)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy