A Linearization technique for solving the quadratic set covering problem

Abstract

In this paper, a linearization technique to find an optimal cover solution of a Quadratic Set Covering Problem is developed. The technique is based on the construction of linear programming problem associated to the given quadratic program such that the optimal solution of this linear program is also the optimal solution of the quadratic program. Using Gomory cuts and Dual Simplex method, an optimal integer basic feasible solution of the form 0-1 is obtained, which is an optimal cover solution of the given Quadratic Set Covering Problem. An algorithm is given in the end of this paper and an example is illustrated in support of the technique

Keywords:

• Quadratic Programming
• Set Covering Problem
• Integer Programming