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 & 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.  doi: 10.1080/02331938808843396.  Google Scholar

[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.  doi: 10.1021/ie202475p.  Google Scholar

[3]

A. Edelman, T. A. Arias and S. Smith, The geometry of algorithms with orthogonality constraints,, SIAM J. Matrix Anal. Appl., 20 (1998), 303.  doi: 10.1137/S0895479895290954.  Google Scholar

[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.  doi: 10.1109/TSP.2007.901164.  Google Scholar

[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.  doi: 10.3934/jimo.2005.1.499.  Google Scholar

[6]

R. Fletcher, Practical Methods of Optimization,, 2nd edition, (1987).   Google Scholar

[7]

C. Helmberg and F. Rendl, Solving quadratic (0,1)-problems by semidefinite programming and cutting planes,, Math. Programming, 82 (1998), 291.  doi: 10.1007/BF01580072.  Google Scholar

[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, (2008), 7.  doi: 10.1007/978-3-540-68279-0.  Google Scholar

[9]

B. Kalantari and J. B. Rosen, Penalty formulation for zero-one nonlinear programming,, Discrete Appl. Math., 16 (1987), 179.  doi: 10.1016/0166-218X(87)90073-4.  Google Scholar

[10]

W. Murray and K.-M. Ng, An algorithm for nonlinear optimization problems with binary variables,, Comput. Optim. Appl., 47 (2010), 257.  doi: 10.1007/s10589-008-9218-1.  Google Scholar

[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.  doi: 10.1007/s10589-005-0985-7.  Google Scholar

[12]

P. M. Pardalos, O. A. Prokopyev and S. Busygin, Continuous approaches for solving discrete optimization problems,, in Handbook on Modelling for Discrete Optimization, (2006), 39.  doi: 10.1007/0-387-32942-0_2.  Google Scholar

[13]

J. Richstein, Verifying the Goldbach conjecture up to $4\cdot 10^{14}$,, Math. Comp., 70 (2001), 1745.  doi: 10.1090/S0025-5718-00-01290-4.  Google Scholar

[14]

K. Schittkowski, More Test Examples for Nonlinear Programming Codes,, Lecture Notes in Economics and Mathematical Systems, (1987).  doi: 10.1007/978-3-642-61582-5.  Google Scholar

[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.   Google Scholar

[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.  doi: 10.1016/0166-218X(92)00190-W.  Google Scholar

[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.   Google Scholar

[18]

W.-Y. Yan and K. L. Teo, Optimal finite-precision approximation of FIR filters,, Signal Processing, 82 (2002), 1695.  doi: 10.1016/S0165-1684(02)00331-6.  Google Scholar

[19]

K. F. C Yiu, Y. Liu and K. L. Teo, A hybrid descent method for global optimization,, J. Global Optim., 28 (2004), 229.  doi: 10.1023/B:JOGO.0000015313.93974.b0.  Google Scholar

[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.  doi: 10.1080/10556780903254104.  Google Scholar

[21]

C. Yu, B. Li, R. Loxton and K. L. Teo, Optimal discrete-valued control computation,, Journal of Global Optimization, 56 (2013), 503.  doi: 10.1007/s10898-012-9858-7.  Google Scholar

[22]

W. X. Zhu, Penalty parameter for linearly constrained 0-1 quadratic programming,, J. Optim. Theory Appl., 116 (2003), 229.  doi: 10.1023/A:1022174505886.  Google Scholar

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.  doi: 10.1080/02331938808843396.  Google Scholar

[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.  doi: 10.1021/ie202475p.  Google Scholar

[3]

A. Edelman, T. A. Arias and S. Smith, The geometry of algorithms with orthogonality constraints,, SIAM J. Matrix Anal. Appl., 20 (1998), 303.  doi: 10.1137/S0895479895290954.  Google Scholar

[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.  doi: 10.1109/TSP.2007.901164.  Google Scholar

[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.  doi: 10.3934/jimo.2005.1.499.  Google Scholar

[6]

R. Fletcher, Practical Methods of Optimization,, 2nd edition, (1987).   Google Scholar

[7]

C. Helmberg and F. Rendl, Solving quadratic (0,1)-problems by semidefinite programming and cutting planes,, Math. Programming, 82 (1998), 291.  doi: 10.1007/BF01580072.  Google Scholar

[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, (2008), 7.  doi: 10.1007/978-3-540-68279-0.  Google Scholar

[9]

B. Kalantari and J. B. Rosen, Penalty formulation for zero-one nonlinear programming,, Discrete Appl. Math., 16 (1987), 179.  doi: 10.1016/0166-218X(87)90073-4.  Google Scholar

[10]

W. Murray and K.-M. Ng, An algorithm for nonlinear optimization problems with binary variables,, Comput. Optim. Appl., 47 (2010), 257.  doi: 10.1007/s10589-008-9218-1.  Google Scholar

[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.  doi: 10.1007/s10589-005-0985-7.  Google Scholar

[12]

P. M. Pardalos, O. A. Prokopyev and S. Busygin, Continuous approaches for solving discrete optimization problems,, in Handbook on Modelling for Discrete Optimization, (2006), 39.  doi: 10.1007/0-387-32942-0_2.  Google Scholar

[13]

J. Richstein, Verifying the Goldbach conjecture up to $4\cdot 10^{14}$,, Math. Comp., 70 (2001), 1745.  doi: 10.1090/S0025-5718-00-01290-4.  Google Scholar

[14]

K. Schittkowski, More Test Examples for Nonlinear Programming Codes,, Lecture Notes in Economics and Mathematical Systems, (1987).  doi: 10.1007/978-3-642-61582-5.  Google Scholar

[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.   Google Scholar

[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.  doi: 10.1016/0166-218X(92)00190-W.  Google Scholar

[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.   Google Scholar

[18]

W.-Y. Yan and K. L. Teo, Optimal finite-precision approximation of FIR filters,, Signal Processing, 82 (2002), 1695.  doi: 10.1016/S0165-1684(02)00331-6.  Google Scholar

[19]

K. F. C Yiu, Y. Liu and K. L. Teo, A hybrid descent method for global optimization,, J. Global Optim., 28 (2004), 229.  doi: 10.1023/B:JOGO.0000015313.93974.b0.  Google Scholar

[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.  doi: 10.1080/10556780903254104.  Google Scholar

[21]

C. Yu, B. Li, R. Loxton and K. L. Teo, Optimal discrete-valued control computation,, Journal of Global Optimization, 56 (2013), 503.  doi: 10.1007/s10898-012-9858-7.  Google Scholar

[22]

W. X. Zhu, Penalty parameter for linearly constrained 0-1 quadratic programming,, J. Optim. Theory Appl., 116 (2003), 229.  doi: 10.1023/A:1022174505886.  Google Scholar

[1]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[2]

Tobias Geiger, Daniel Wachsmuth, Gerd Wachsmuth. Optimal control of ODEs with state suprema. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021012
[3]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437
[4]

Lorenzo Freddi. Optimal control of the transmission rate in compartmental epidemics. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021007
[5]

Marzia Bisi, Maria Groppi, Giorgio Martalò, Romina Travaglini. Optimal control of leachate recirculation for anaerobic processes in landfills. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 2957-2976. doi: 10.3934/dcdsb.2020215
[6]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183
[7]

Xiaohong Li, Mingxin Sun, Zhaohua Gong, Enmin Feng. Multistage optimal control for microbial fed-batch fermentation process. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021040
[8]

John T. Betts, Stephen Campbell, Claire Digirolamo. Examination of solving optimal control problems with delays using GPOPS-Ⅱ. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 283-305. doi: 10.3934/naco.2020026
[9]

Livia Betz, Irwin Yousept. Optimal control of elliptic variational inequalities with bounded and unbounded operators. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021009
[10]

Shanjian Tang, Fu Zhang. Path-dependent optimal stochastic control and viscosity solution of associated Bellman equations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (11) : 5521-5553. doi: 10.3934/dcds.2015.35.5521
[11]

Marita Holtmannspötter, Arnd Rösch, Boris Vexler. A priori error estimates for the space-time finite element discretization of an optimal control problem governed by a coupled linear PDE-ODE system. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021014
[12]

M. Phani Sudheer, Ravi S. Nanjundiah, A. S. Vasudeva Murthy. Revisiting the slow manifold of the Lorenz-Krishnamurthy quintet. Discrete & Continuous Dynamical Systems - B, 2006, 6 (6) : 1403-1416. doi: 10.3934/dcdsb.2006.6.1403
[13]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[14]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[15]

Marian Gidea, Rafael de la Llave, Tere M. Seara. A general mechanism of instability in Hamiltonian systems: Skipping along a normally hyperbolic invariant manifold. Discrete & Continuous Dynamical Systems - A, 2020, 40 (12) : 6795-6813. doi: 10.3934/dcds.2020166
[16]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247
[17]

Yves Dumont, Frederic Chiroleu. Vector control for the Chikungunya disease. Mathematical Biosciences & Engineering, 2010, 7 (2) : 313-345. doi: 10.3934/mbe.2010.7.313
[18]

Y. Latushkin, B. Layton. The optimal gap condition for invariant manifolds. Discrete & Continuous Dynamical Systems - A, 1999, 5 (2) : 233-268. doi: 10.3934/dcds.1999.5.233
[19]

Martin Bohner, Sabrina Streipert. Optimal harvesting policy for the Beverton--Holt model. Mathematical Biosciences & Engineering, 2016, 13 (4) : 673-695. doi: 10.3934/mbe.2016014
[20]

Xingchun Wang, Yongjin Wang. Variance-optimal hedging for target volatility options. Journal of Industrial & Management Optimization, 2014, 10 (1) : 207-218. doi: 10.3934/jimo.2014.10.207

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences