Premium
Cutting Plane Technique for the Set Covering Problem with Linear Fractional Functional
Author(s) -
Arora S. R.,
Swarup Kanti,
Puri M. C.
Publication year - 1977
Publication title -
zamm ‐ journal of applied mathematics and mechanics / zeitschrift für angewandte mathematik und mechanik
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.449
H-Index - 51
eISSN - 1521-4001
pISSN - 0044-2267
DOI - 10.1002/zamm.19770571006
Subject(s) - cover (algebra) , mathematics , cutting plane method , prime (order theory) , linear programming , covering problems , mathematical optimization , set cover problem , plane (geometry) , set (abstract data type) , linear fractional programming , solution set , linear form , integer programming , computer science , combinatorics , mathematical analysis , geometry , mechanical engineering , engineering , programming language
This paper develops an iterative cutting plane technique for finding an optimal cover solution of the set covering problem with linear fractional functional as its objective function which satisfies certain condition. The method determines a prime cover solution from the optimal solution of the linear fractional functional programming problem derived from the given problem, which is tested for optimality. If it is not an optimal prime cover solution, a linear cut is introduced and the process is continued till the optimal prime cover solution is reached. An example to illustrate the method is incorporated.