Improved Solutions for the Steiner Triple Covering Problem

摘要

In, Fulkerson et al. describe a set covering problem that arises from computing the 1-width of incidence matrices of Steiner triple systems. The resulting 0-1 integer linear programming problem is widely recognized as a particularly difficult problem, witness a result from Avis in which he shows that any branch and bound algorithm with linear programming relaxation and/or elimination by dominance requires that a super polynomial number of partial solutions must be inspected.The Steiner triple covering problem is of particular interest for bench marking purposes (see e.g. Karmarkar et al.) because the problem is hard and has yet a relatively low number of variables and, moreover, some instances can be simply generated.