Question 1: The "swing states" problem

In the United States of America, during the presidential elections, there are certain states called "swing states", which are liable to swing from the Democratic Party towards the Republican or vice versa. It is these states that both parties pay most attention to, especially when the results day is drawing near. Table 1.1 shows the list of these states and the figures of their Electoral College.

The advisers of one of two candidates (you are free to choose either side) ask you to help them make the most of their last week of campaigning. You are also provided with, in Table 1.1, an estimate of the sum that needs to be invested in every state in order to have a chance to command a majority. There is a $500,000 global budget left to invest. The question is simple: which states should you choose in order to win the greatest number of electors?

Table 1.1. List of "swing states" and estimate of the investment necessary to obtain a majority

1) What kind of combinatorial optimization problem is the "swing state" problem in relation with?

2) Determine a criterion according to which the states can be ranked from most interesting to least interesting. Deduce a construction heuristic from this and give its principle. What solution do you find?

3) Remove the most expensive state from the last solution. Can you then complete your solution by choosing some other states, thus improving it?

Question 2: Adel and his camels

Your favorite Operations Research professor (we will call him Mr L.), having barely arrived in Douz1, meets Adel, a professional camel driver. Mr L., after introducing Adel to Operations Research, works out a deal for a free excursion to the Sahara. In exchange, Mr L. has to show Adel that his knowledge in optimization can help him conduct his business more proficiently. Adel reveals to Mr L. that he has two problems. Before we tackle these, let us examine in detail our camel driver's activity.

Adel owns 12 camels. Every morning the camels need gearing up before being able to carry tourists. Two procedures are required and they have to be carried out in this order. First of all, a veterinary check-up is performed in order to make sure that the animals are in good health. Afterwards, the camels are saddled up in the Bedouin way. The time it takes to perform these two tasks varies according to the age of the animal and the kind of saddle that needs to be placed on it. These times are shown in Table 1.2. For the sake of confidentiality, we cannot tell you the names of the camels, which we will then refer to as numbers (from 1 to 12). Adel has two workers. The first one deals with the veterinary check-up. The second is an expert in Bedouin traditions and only saddles up the camels.

Table 1.2. Time necessary to gear up the camels (in minutes)

1) A group of 12 tourists arrives at 10 o'clock for a camelback ride. Adel wants to fully satisfy his prestigious customers. Thus, he asks Mr L. to help him reduce their waiting time as much as possible. All the camels will have to be ready as soon as possible, given that they will start working at 8 o'clock. Mr L. offers to determine the order in which the camels will have to be geared up in order to minimize the tourists' waiting time. The problem seems so easy to him that he exults:
- What kind of optimization problem has Mr L. recognized and why does he seem so happy?
- What solving technique is Mr L. going to employ?
- What will the tourists' waiting time be?

Question 3: Sauron's forges

Scary Sauron has employed you, one of his most faithful lieutenants, as his chief engineer. Your role consists of supervising the various Mordor forges and in making sure of their constant supply of iron ores so that they can produce weapons at their full capacity. Given the strategic role played by these forges in the upcoming war, there is no need to point out that your life will be inextricably linked to your productivity!

Figure 1.2 represents the map of Mordor and the locations of the different forges (numbered 1-11). The only iron mine of the whole kingdom, which is where you are located with your team and constitutes the source of supply for all the forges, is also represented on this map (as the letter M). You will also find on the map the different paths between these locations as well as the time - in hours - it takes to cover them

Figure 1.2. Map of Mordor

Problem 1: The inspection of the forges Recently appointed, you decide to walk all over Mordor in order to supervise the set of forges:

1) Fill out the distance in Table 1.4. For each non-gray case, you will give the shortest distance from the first location (shown across the rows) to the second (shown in the columns). Why is it not necessary to provide information about every case presented in this table?

2) Your aim is to visit all the forges in Mordor. Even if you completely trust your partner (who will stand in for you at the mine during your absence), it is clear that you would like your absence to be as short as possible. Thus, you try to minimize the travel time (the time spent at the locations remaining constant).

What is the name of the problem you have to solve? What solution do you obtain when you apply the "nearest neighbor" heuristic upon leaving the mine? (If several forges are equidistant, you will choose the one corresponding to the smallest number). Can you hope to obtain a better result if you apply the same technique but with a different starting point?

Table 1.4. Distance between the mine and the forges

3) Propose the best solution possible.