Premium
A nonlinear approach to a class of combinatorial optimization problems[Note 1. Supported by the Dutch Organization for Scientific Research (NWO/SION) ...]
Author(s) -
Warners J. P.
Publication year - 1998
Publication title -
statistica neerlandica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.52
H-Index - 39
eISSN - 1467-9574
pISSN - 0039-0402
DOI - 10.1111/1467-9574.00076
Subject(s) - mathematical optimization , optimization problem , mathematics , class (philosophy) , combinatorial optimization , reduction (mathematics) , computation , nonlinear programming , quadratic equation , quadratic assignment problem , nonlinear system , quadratic unconstrained binary optimization , quadratic programming , l reduction , function (biology) , computer science , algorithm , continuous optimization , artificial intelligence , physics , geometry , quantum mechanics , evolutionary biology , quantum computer , quantum , biology , multi swarm optimization
A special class of combinatorial optimization problems is considered. We develop a compact nonconvex quadratic model for these problems that incorporates all inequality constraints in the objective function, and discuss two approximation algorithms for solving this model. One is inspired by Karmarkar's potential reduction algorithm for solving combinatorial optimization problems; the other is a variant of the reduced gradient method. The paper concludes with computational experiences with both real‐life and randomly generated instances of the frequency assignment problem. Large problems are satisfactorily solved in reasonable computation times.