
Integer Programming
1.Let P is s subset of Rn be a nonempty polyhedron. For c belonging to Rn, define
z(c) := max{c (transpose)x : x belongs to P}..... (1)
Show that the following statements are equivalent.
(i) P = conv(P intersection Zn).
(ii) Let F subset of P be any face. Then, F intersection Zn not = to null set;.
(iii) The optimal value z(c) of the linear program (1) is attained at some point in P intersection Zn,for all c belonging to Rn such that z(c) is infinite.
2.Let Pi = Qi + Ci, i = 1; 2 be polyhedra in Rn (here, Qi are polytopes and Ci are polyhedral
cones).
(a) Let R subset of Rn be a polyhedron. show that R is a closed set. Now Let
R1 subset of R^2 be a line, and R2 subset of R^2 be a singleton point not lying on R1. Then, show that conv(R1 U R2) is not a closed set.
(b) Show that Q := conv(Q1 U Q2) is a polytope and C := conv(C1 U C2) is a
polyhedral cone.
(c) Let P := conv(P1 U P2). Show that P Q+C, where Q and C are as defined
in (b).