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 PageLast modified: