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

[answerhappygod]

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 1 (73.62 KiB) Viewed 42 times

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).