Some Results on facets for linear inequality in 0-1 variables

Subject Areas : Data Envelopment Analysis

D.  Sashi Bhusan ¹ (Department of Mathematics, Balasore College of Engg . & Technology Teach. Sergarh, Balasore , Orissa , India)
B.  Bagaban ² (Ms.student of Mathematics, F. M. Autonomous College, Balasore, Orissa, India)
J.P.  Tripathy ³ (Department of Mathematics Gurukul Institute of Technology Bhubaneswar, Orissa, India)

Received: 2010-08-25 Accepted : 2010-08-25 Published : 2010-03-01

Keywords: Convex- hull, set-covering, set-partitioning, Matrodial-intersection, vertex-packing, cutting-planes,

Abstract :

The facet of Knapsack ploytope, i.e. convex hull of 0-1 points satisfying a givenlinear inequality has been presented in this current paper. Such type of facetsplays an important role in set covering set partitioning, matroidal-intersectionvertex- packing, generalized assignment and other combinatorial problems.Strong covers for facets of Knapsack ploytope has been developed in the first partof the present paper. Generating family of valid cutting planes that satisfyinequality with 0-1 variables through algorithms are the attraction of this paper.

References:

[1] Balas E., An Additive Algorithm for solving for linear program with 0-1 variable, operation research, Vol. 13, 517 -545, 1965.

[2] Balas E., Facets of the Knapsack Polytope, Mathematical programming, Vol. 8, 146-164, 1975.

[3] Balas E., and Jeroslow R., Canonical Cuts, on the unit Hypercube, SIAM Journal of Applied Mathematics Vol. 23, 61-69, 1972. 

[4] Balas E., Mazzola J.B., Non linear Zero – one programming | I, Linearisation Technique mathematical programming, Vol. 30, 1-21, 1984a.

[5] Wolfe P., The simplex Algorithm for Quadratic Programming.  Econometrical, Vol. 27, 382-398, 1959.

[6] Walsey LA., Facets for a linear inequality in zero- one variable mathematical programming, Vol. 8, 165 – 178, 1975.

[7] Walsey L.A., A resource decomposition algorithm for general mathematical programming study Vol. 14, 244 -257, 1981.