ISSN:
1436-4646
Schlagwort(e):
Set Packing
;
Integer Programming
;
Linear Programming
;
Simplex Method
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
Abstract This paper considers the set packing problem max{wx: Ax ⩽ b, x ⩾ 0 and integral}, whereA is anm × n 0–1 matrix,w is a 1 ×n weight vector of real numbers andb is anm × 1 vector of ones. In equality form, its linear programming relaxation is max{wx: (x, y) ∈P(A)} whereP(A) = {(x, y):Ax +I m y =b, x⩾0,y⩾0}. Letx 1 be any feasible solution to the set packing problem that is not optimal and lety 1 =b − Ax 1; then (x 1,y 1) is an integral extreme point ofP(A). We show that there exists a sequence of simplex pivots from (x 1,y 1) to (x*,y*), wherex* is an optimal solution to the set packing problem andy* =b − Ax*, that satisfies the following properties. Each pivot column has positive reduced weight and each pivot element equals plus one. The number of pivots equals the number of components ofx* that are nonbasic in (x 1,y 1).
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01582240
Permalink
