2. Problem Encoding and Local Search (20 points) Recall that the Pigeonhole problem concerns putting n + 1 pigeons into n holes. The con- straints on this problem are: (1) each pigeon is assigned a hole and (2) each hole can acco- modate at most one pigeon. (a) (9 pts) Assuming that the binary variable Xij is True if and only if pigeon i is in hole j, give the clauses that encode the constraints of the problem. Make sure that each set of clauses is accompanied by an English description. (b) (4 pts) How many clauses do you need? Express your answer in big-O notation. (c) (7 pts) Describe how local search can be applied to the Pigeonhole problem, using a direct formulation (i.e., not using the Boolean encoding of part (a)). Discuss a way of improving the local search strategy. (Note: Since there is no solution to the Pigeonhole problem, any local search strategy will not return a solution, but that doesn't mean we cannot apply local search to it.) 2. Problem Encoding and Local Search (20 points) Recall that the Pigeonhole problem concerns putting n + 1 pigeons into n holes. The con- straints on this problem are: (1) each pigeon is assigned a hole and (2) each hole can acco- modate at most one pigeon. (a) (9 pts) Assuming that the binary variable Xij is True if and only if pigeon i is in hole j, give the clauses that encode the constraints of the problem. Make sure that each set of clauses is accompanied by an English description. (b) (4 pts) How many clauses do you need? Express your answer in big-O notation. (c) (7 pts) Describe how local search can be applied to the Pigeonhole problem, using a direct formulation (i.e., not using the Boolean encoding of part (a)). Discuss a way of improving the local search strategy. (Note: Since there is no solution to the Pigeonhole problem, any local search strategy will not return a solution, but that doesn't mean we cannot apply local search to it.)