An interior point algorithm to solve computationally difficult set covering problems (Q1181917)

The authors consider the following integer programming problem: Find \(w\in R^ n\) such that \(B^ T w\leq b\), \(w_ i=\{-1,1\}\) \((i=1,\dots,m)\), \(B\in R^{m\times n}\), \(b\in R^ n\). The paper proposes an inner point method to achieve feasible points through an optimization problem for nonconvex potentials. This nonconvex optimization procedure is made on an ellipsoid. Experience with several large test problems is also reported in detail in the paper.