An interior point algorithm to solve computationally difficult set covering problems

An interior point algorithm to solve computationally difficult set covering problems

0.00 Avg rating0 Votes
Article ID: iaor19921502
Country: Netherlands
Volume: 52
Issue: 3
Start Page Number: 597
End Page Number: 618
Publication Date: Dec 1991
Journal: Mathematical Programming
Authors: , ,
Keywords: sets
Abstract:

The authors 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. They 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.

Reviews

Required fields are marked *. Your email address will not be published.