An Interior Point Approach to the Maximum Independent Set Problem in Dense Random Graphs
Narendra K. Karmarkar, Maurício G. C. Resende, K. G. Ramakrishnan · 1999
We present an interior point approach to the zero-one integer programming feasibility problem based on the minimization of an appropriate potential function. Given a polytope defined by a set of linear inequalities, this procedure generates a sequence of strict interior points of this polytope, such that each consecutive point reduces the value of the potential function. An integer solution (not necessarily feasible) is generated at each iteration by a rounding scheme. The direction used to determine the new iterate is computed by solving a nonconvex quadratic program on an ellipsoid. We illustrate the approach by considering a class of difficult NP-complete problems: finding a maximum independent set of a dense random graph. Some implementation details are discussed and preliminary computational results are presented. We solve several large independent set problems in graphs having up to 1000 vertices and over 250,000 edges. Key words: Integer programming, interior point method, maxim...