A country with 35 cities will be having an election with two candidates. As a strategist of one the candidates, you are responsible for developing an investment plan to win the election. The winner of the election is decided by number of cities that selects the candidate. There is also a council consisting of 7 seats. After the election is complete, the winner is allowed to divide the country into 7 connected regions. In each region the one who got the most votes obtain a seat in the council. Your first goal is to win the election, then obtain the highest number of seats. Figure 1. Position of Cities on 57 grid Part A. Win the Election You have to make investments in cities in order to win the election. Each of the city (i,j) has an expected investment amount E[i,j] so that you get vote from them. There are also other factors that effect if the city votes for you, which are; - For cities to not become suspicious of your investment, average investment to the neighborhood cities should be greater than T=15 million . - At least one of the neighboring cities should also vote for you. Q1. Formulate an integer linear program to find the optimal investment plan. You should find what is the minimum amount of investment so that you win the election. Q2. Implement your formulation in GUROBI and find the optimal solution. What are the investment amounts for each city and which cities voted for you? You can find the expectations of cities in exps.txt. Figure 2. Average investment on star cities should be greater than T for black square to vote and at least one of the stars should also vote for you. Part B. Region Partitioning After you won the election with the investment plan in Part A, you can now partition the regions. You will use the votes given by each city in part A to solve this part. For every region won, you will get a seat in the council. Each region must consist of 5 cities and there must be total of 7 regions. Due to international activities, the North, East and West border cities are part of the fixed regions as given in Figure 3 (Law of Border Regions). Remaining cities can be partitioned into 4 regions by you with additional conditions; I. 4 central (main) cities A, B, C, D should be part of different regions. II. The remaining (South) border cities cannot be in the same region with B or C. III. At least two South border cities should be in the same region with A. IV. The neighbor cities of B that are not part of fixed regions should be in the same region with B. Q1. Considering the conditions given above are there any cities whose region is predetermined? If so, write down which cities and which regions they are automatically assigned to. You can name the regions as A, B, C and D where the regions include the respective main cities. Q2. Formulate an integer linear program that maximizes the number of seats you will have in the council. Implement your formulation using GUROBI optimization software and find the optimal solution. What is the maximum number of seats you can have in the council? Give the optimal region partitions. Figure 3. Fixed Border Regions and Main Cities Part C. Region Partitioning II Suppose there is a change in law for region partitioning as they were found to be highly limiting. Now, Law of North Border Region and the constraints I, II, III, IV are lifted. Hence, the remaining requirements are; the East and West Regions are fixed. However, an additional law is implemented which states the cities in each region should be connected, there should be a direct neighbor. Write down the connectivity constraints for the remaining cities in 55 grid form. Formulate an integer linear program to find suitable partitioning to obtain the largest number of seats possible in the council. Implement your formulation using GUROBI optimization software and find the optimal solution. Hint: To formulate connectiveness constraint you have to force a direct neighbor around single cells and dominoes (connected two cells in the same region). Figure 4. Force a direct neighbor around single tiles and dominoes (consider vertical and horizontal dominoes separately) in 55 grid
