Answer Happy

3. Consider the following mixed integer set: n P= {(x, y) € {0,1}" x R" : yi sd, 0 si 5 Uili, Vi = 1, ... ,n}, i=1 u > 0. which may occur as a substructure of network design problems. Assume that d > 0, U; > 0) for i = 1, ... , n and d= Li-i ui – where (a) (10pts) Fix variables x; to 1 for i = 1, ... , n, i.e., consider P(N) = {(x, y) EP: Xi = 1, Vi = 1, ... ,n}. What is the dimension of P(N)? Identify a nontrivial facet-defining inequality in P(N) and prove it is facet-defining for P(N). (b) (10pts) Sequentially lift the variables x; for i = 1, in to obtain a closed-form lifted valid inequality for conv(P). (c) (bonus) Argue that this lifted inequality is facet-defining for conv(P).