Metaheuristics for Logistics

12Solution to Problems

In this final chapter, we return to the small problems outlined at the beginning of this book.

12.1. The swing state problem

1. What kind of combinatorial optimization problem is the “swing state” problem in relation with?

The candidate has an overall budget of $ 500 k, comparable to a capacity C . He must, therefore, choose which states he must invest in, knowing that each state i ∈ I has a value v_i, which corresponds to the number of voters that he will bring in, and a cost m_i. The objective is to maximize the summation of the value of all the chosen states, without exceeding the capacity. We can recognize the knapsack problem.

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?

We will define as a saturated solution one for which it is not possible to add new states without violating the capacity constraint. The purpose of this question is to find a criterion that helps to sort states out. The order thus defined will allow determining which states will be selected through a greedy heuristic.

Three sorting criteria can be proposed:

1. – prioritizing states that require smaller investments (cost criterion);
2. – prioritizing states that give the most electoral votes (value criterion);
3. – prioritizing states where the investment per electoral vote obtained is the largest (ratio criterion).

The last criterion ...