On Wednesday, a businessman has to be at his his office in Ataehir for a meeting...

Transcribed Image Text:

On Wednesday, a businessman has to be at his his office in Ataşehir for a meeting then he has to visit his customers located in Levent, Kavacık and Kadıköy and turn back to his office. The distances in kilometers between the locations are given in the following table: Ataşehir Ataşehir Levent Kavacık Kadıköy B 15 11 13 If he is to visit each location only once: Levent 18 - 10 16 Kavacık 10 9 H 22 Kadıköy 12 17 24 M a) Does this problem correspond to a linear programming (LP), mixed integer programming (MIP) or integer programming (IP) problem? Explain. b) Formulate the objective function and degree constraints in open form. c) Write the sub-circuit elimination constraint for the subset Ataşehir, Levent, Kavacık) in open form. d) Write the connectivity constraint for the subset Ataşehir, Kadıköy) in open form. e) If you model the problem by writing all sub-circuit elimination constraints instead of connectivity constraints how many constraints should you write in total (including degree constraints, sub-circuit elimination constraints, and binary constraints) f) In order to find a lower bound for the solution, which constraint types should be removed from the whole model? Is the lower bound you find always feasible? Explain. Minus u etki On Wednesday, a businessman has to be at his his office in Ataşehir for a meeting then he has to visit his customers located in Levent, Kavacık and Kadıköy and turn back to his office. The distances in kilometers between the locations are given in the following table: Ataşehir Ataşehir Levent Kavacık Kadıköy B 15 11 13 If he is to visit each location only once: Levent 18 - 10 16 Kavacık 10 9 H 22 Kadıköy 12 17 24 M a) Does this problem correspond to a linear programming (LP), mixed integer programming (MIP) or integer programming (IP) problem? Explain. b) Formulate the objective function and degree constraints in open form. c) Write the sub-circuit elimination constraint for the subset Ataşehir, Levent, Kavacık) in open form. d) Write the connectivity constraint for the subset Ataşehir, Kadıköy) in open form. e) If you model the problem by writing all sub-circuit elimination constraints instead of connectivity constraints how many constraints should you write in total (including degree constraints, sub-circuit elimination constraints, and binary constraints) f) In order to find a lower bound for the solution, which constraint types should be removed from the whole model? Is the lower bound you find always feasible? Explain. Minus u etki