SET COVERING, SET PARTITIONING AND SET PACKING PROBLEM WITH LINEAR FRACTIONAL OBJECTIVE FUNCTION

 

Ratnesh Rajan Saxena, Rashmi Gupta

 

Abstract

 

Set Covering, Set Partitioning and Set Packing problems be-long to the class of 0-1 integer programming problems that are NP-complete. In this paper an enumerative technique using Combinotorics is developed to solve these problems with non-linear objective function, in particular the fractional objective function. Most of the existing procedures such as cutting plane technique or branch and bound technique for solving these problems have their basis in simplex algorithm. The well known Breadth First Search (BFS) and Depth First Search (DFS) techniques of graph theory form the basis of the proposed algorithms. The enumeration procedure developed in the proposed algorithms is a modification of these techniques. The algorithms developed in this paper are supported by numerical examples.

 

Lecture Notes in Management Science (2011) Vol. 3: 107-120

3rd International Conference on Applied Operational Research, Proceedings

© Tadbir Operational Research Group Ltd. All rights reserved.

www.tadbir.ca

 

ISSN 2008-0050 (Print)

ISSN 1927-0097 (Online)

 

ARTICLE OUTLINE

 

·         Introduction

·         Theoretical Development

·         Set Covering Problems

·         Definitions

·         Results Used

·         Algorithm

·         Numerical Example

·         Set Partitioning Problems

·         Numerical Example

·         Set Packing Problems

·         Algorithm

·         Numerical Example

·         Concluding Remarks

·         References

 

Full Text PDF