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

**Mathematical Programming**, vol.
52, pp. 597-618, 1991

**ABSTRACT**

We present an interior point approach to the zero-one
integer programming feasibility problem based on the minimization of a
nonconvex 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 set
covering problems that arise from computing the 1-width of the incidence
matrix of Steiner triple systems.

PostScript file of full paper

Go back

Mauricio G.C. Resende's Home PageLast modified: