A nonlinear approach to a class of combinatorial optimization problems

被引:3
作者
Warners, JP [1 ]
机构
[1] Delft Univ Technol, Fac Tech Math & Informat, NL-2628 CD Delft, Netherlands
关键词
nonlinear optimization; interior point methods; gradient descent; frequency assignment;
D O I
10.1111/1467-9574.00076
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
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.
引用
收藏
页码:162 / 184
页数:23
相关论文
共 19 条
[1]  
Bazaraa MS., 1993, NONLINEAR PROGRAMMIN
[2]  
CHVATAL V, DISCRETE MATH, V4, P305
[3]  
DIKIN II, 1967, DOKL AKAD NAUK SSSR+, V174, P747
[4]   GLOBAL OPTIMIZATION FOR SATISFIABILITY (SAT) PROBLEM [J].
GU, J .
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 1994, 6 (03) :361-381
[5]  
Kamath A. P., 1990, Annals of Operations Research, V25, P43, DOI 10.1007/BF02283686
[6]   A NEW POLYNOMIAL-TIME ALGORITHM FOR LINEAR-PROGRAMMING [J].
KARMARKAR, N .
COMBINATORICA, 1984, 4 (04) :373-395
[7]   AN INTERIOR POINT ALGORITHM TO SOLVE COMPUTATIONALLY DIFFICULT SET COVERING PROBLEMS [J].
KARMARKAR, N ;
RESENDE, MGC ;
RAMAKRISHNAN, KG .
MATHEMATICAL PROGRAMMING, 1991, 52 (03) :597-618
[8]  
KARMARKAR N., 1990, CONTEMPORARY MATH, V114, P297
[9]   CONES OF MATRICES AND SET-FUNCTIONS AND 0-1 OPTIMIZATION [J].
Lovasz, L. ;
Schrijver, A. .
SIAM JOURNAL ON OPTIMIZATION, 1991, 1 (02) :166-190
[10]  
Schrijver A., 1986, THEORY LINEAR INTEGE