More Web Proxy on the site http://driver.im/

research-article

An artificial neural network for solving quadratic zero-one programming problems

Authors:

S.M. MiriAuthors Info & Claims

Neurocomputing, Volume 235, Issue C

Pages 192 - 198

https://doi.org/10.1016/j.neucom.2016.12.064

Published: 26 April 2017 Publication History

Abstract

This paper presents an artificial neural network to solve the quadratic zero-one programming problems under linear constraints. In this paper, by using the connection between integer and nonlinear programming, the quadratic zero-one programming problem is transformed into the quadratic programming problem with nonlinear constraints. Then, by using the nonlinear complementarity problem (NCP) function and penalty method this problem is transformed into an unconstrained optimization problem. It is shown that the Hessian matrix of the associated function in the unconstrained optimization problem is positive definite in the optimal point. To solve the unconstrained optimization problem an artificial neural network is used. The proposed neural network has a simple structure and a low complexity of implementation. It is shown here that the proposed artificial neural network is stable in the sense of Lyapunov. Finally, some numerical examples are given to show that the proposed model finds the optimal solution of this problem in the low convergence time.

References

[1]

W.P. Adams, R. Forrester, F. Glower, Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs, Discret. Optim., 1 (2004) 99-120.

Digital Library

[2]

M. Aourid, X.D. Do, B. Kaminska, Penalty formulation for 0-1 linear programming problem: a neural network approach, IEEE Neural Netw., 2 (1993) 1092-1095.

[3]

M. Aourid, B. Kaminska, Neural networks for solving the quadratic 0-1 programming problem under linear constraints, IEEE Neural Netw., 4 (1995) 1690-1693.

[4]

A. Billionnet, M.C. Costa, A. Sutter, An efficient algorithm for a task allocation problem, J. Assoc. Comput. Mach., 39 (1992) 502-518.

Digital Library

[5]

A. Billionnet, S. Elloumi, M.C. Plateau, Improving the performance of standard solvers for quadratic 0-1 programs by atight convex reformulation: the QCR method, Discret. Appl. Math., 157 (2009) 1185-1197.

Digital Library

[6]

J.S. Chen, C.H. Ko, S. Pan, A neural network based on the generalized Fischer-Burmeister function for nonlinear complementarity problems, Inf. Sci., 180 (2010) 697-711.

Digital Library

[7]

J.S. Chen, S. Pan, A family of NCP functions and a descent method for the nonlinear complementarity problem, Comput. Optim., 40 (2008) 389-404.

Digital Library

[8]

S. Effati, M. Baymani, A new nonlinear neural network for solving convex nonlinear programming problems, Appl. Math. Comput., 168 (2005) 1370-1379.

Digital Library

[9]

S. Effati, A.R. Nazemi, Neural network and its application for solving linear and quadratic programming problems, Appl. Math. Comput., 172 (2006) 305-331.

[10]

S. Effati, M. Ranjbar, A novel recurrent nonlinear neural network for solving quadratic programming problems, Appl. Math. Model., 35 (2011) 1688-1695.

[11]

S. Effati, A. Mansoori, M. Eshaghnezhad, An efficient projection neural network for solving bilinear programming problems, Neurocomputing, 168 (2015) 1188-1197.

Digital Library

[12]

G. Finke, R.E. Burkard, F. Real, Quadratic assignment problem, Ann. Discret. Math., 31 (1987) 61-82.

[13]

A. Fischer, A special Newton-type optimization method, Optimization, 24 (1992) 269-284.

[14]

A. Fischer, Solution of the monotone complementarity problem with locally Lipschitzian functions, Math. Program., 76 (1997) 513-532.

Digital Library

[15]

X. He, A. Chen, W.A. Chaovalitwongse, H.X. Liu, An improved linearization technique for a class of quadratic 0-1 programming problems, Optim. Lett., 6 (2012) 31-41.

[16]

F.S. Hillier, G.J. Lieberman, Introduction to Operations Research, McGraw-Hill, 2008.

Digital Library

[17]

M.P. Kennedy, L.O. Chua, Neural networks for nonlinear programming, IEEE Trans. Curcuits Syst., 35 (1988) 554-562.

[18]

J. Krarup, D. Pisinger, F. Plastria, Discrete location problems with push-pull objectives, Discret. Appl. Math., 123 (2002) 365-378.

Digital Library

[19]

C. Lu, X. Guo, Convex reformulation for binary quadratic programming problems via average objective value maximization, Optim. Lett., 9 (2015) 523-535.

[20]

R.K. Miller, A.N. Michel, Ordinary Differential Equations, Academic Press, 1982.

[21]

A.R. Nazemi, A dynamic system model for solving convex nonlinear optimization problems, Commun. Nonlinear Sci. Numer Simula., 17 (2012) 1696-1705.

[22]

P.M. Pardalos, G.P. Rodgers, Computational aspect of a branch and bound algorithm for quadratic zero-one programming, Computing, 45 (1990) 131-144.

Digital Library

[23]

F.A. Pazos, A. Bhaya, Control Liapunov function design of neural networks that solve convex optimization and variational inequality problems, Neurocomputing, 72 (2009) 3863-3872.

Digital Library

[24]

A. Rodriguez-Vazquez, R. Domingues-Castro, A. Rueda, J.L. Huertas, E. Sanchez-Sinencio, Nonlinear switched-capacitor neural networks for optimization problems, IEEE Trans. Circuits Syst., 37 (1990) 384-397.

[25]

M.V. Rybashov, The gradient method of solve convex programming problems on electronic analog computers, Autom. Remote Control, 26 (1965) 1886-1898.

[26]

H.D. Sherali, W.P. Adams, A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, Kluwer Academic Publishers, Nowell, MA, 1999.

[27]

B. Simeone, Quadratic 0-1 Programming, Boolean Functions and Graphs. Waterloo, Ontario, 1979.

[28]

J.J.E. Slotin, W. Li, Applied Nonlinear Control, Prentice hall, 1991.

[29]

D.W. Tank, J.J. Hopfield, Simple neural optimization networks: an A/D converter, Signal decision network and a linear programming circuit, IEEE Trans., Curcuits Syst., 33 (1986) 533-541.

[30]

L.N. Trefethen, D. Bau, Numerical linear algebra, Soc. Ind. Appl. Math. (1997).

[31]

J. Wang, A deterministic annealing neural network for convex programming, Neural Netw., 7 (1994) 629-641.

Digital Library

[32]

Y. Xia, G. Feng, J. Wang, A novel recurrent neural network for solving nonlinear optimization problems with inequality constraints, IEEE Trans. Neural Netw., 19 (2008) 1340-1353.

Digital Library

[33]

Y. Xia, J. Wang, A recurrent neural network for solving linear projection equations, Neural Netw., 13 (2000) 337-350.

Digital Library

[34]

Y. Xia, J. Wang, A general projection neural network for solving monotone variational inequality and related optimization problems, IEEE Trans., Neural Netw., 15 (2004) 318-328.

Digital Library

[35]

Y. Xia, J. Wang, A recurrent neural network for solving nonlinear convex programs subject to linear constraints, IEEE Trans., Neural Netw., 16 (2005) 1045-1053.

Digital Library

Cited By

Ou YLin H(2021)A neurodynamic approach to zero-one quadratic programmingNumerical Algorithms10.1007/s11075-021-01075-z88:3(1251-1274)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1007/s11075-021-01075-z
Ranjbar MEffati SMiri S(2020)An efficient neural network for solving convex optimization problems with a nonlinear complementarity problem functionSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-019-04189-824:6(4233-4242)Online publication date: 1-Mar-2020
https://dl.acm.org/doi/10.1007/s00500-019-04189-8

An artificial neural network for solving quadratic zero-one programming problems

Recommendations

Numerical solution for linear and quadratic programming problems using a recurrent neural network

A recurrent neural network, is proposed in this paper for solving linear and quadratic programming problems. The main advantage of this network is that here we are not in need of parameters setting. Moreover, using this network we can solve primal ...
A neural network for solving a convex quadratic bilevel programming problem

A neural network is proposed for solving a convex quadratic bilevel programming problem. Based on Lyapunov and LaSalle theories, we prove strictly an important theoretical result that, for an arbitrary initial point, the trajectory of the proposed ...
A new neural network for solving linear and quadratic programming problems

A new neural network for solving linear and quadratic programming problems is presented and is shown to be globally convergent. The new neural network improves existing neural networks for solving these problems: it avoids the parameter turning problem, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Neurocomputing

Neurocomputing Volume 235, Issue C

April 2017

287 pages

ISSN:0925-2312

Issue’s Table of Contents

Copyright © Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 26 April 2017

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ou YLin H(2021)A neurodynamic approach to zero-one quadratic programmingNumerical Algorithms10.1007/s11075-021-01075-z88:3(1251-1274)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1007/s11075-021-01075-z
Ranjbar MEffati SMiri S(2020)An efficient neural network for solving convex optimization problems with a nonlinear complementarity problem functionSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-019-04189-824:6(4233-4242)Online publication date: 1-Mar-2020
https://dl.acm.org/doi/10.1007/s00500-019-04189-8

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents