Narendra Karmarkar, Mauricio G.C. Resende, and K.G. Ramakrishnan

In Proceedings of the XV Latin American Conference of Computer Science, Santiago, Chile, vol. 1, pp. 241-260, 1989

ABSTRACT

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.

PostScript file of full paper

Go back

Mauricio G.C. Resende's Home Page

Copyright Notice