Nonlinear Approach to a Class of Combinatorial Optimization Problems

摘要

A special class of combinatorial optimization problems is considered. The authorsdevelop a compact nonconvex quadratic model for these problems that incorporates all inequality constraints in the objective function, and discuss two 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 results on both real-life and randomly generated instances of the frequency assignment problem. Large problems are satisfactorily solved in reasonable time.