In this final chapter, we return to the small problems outlined at the beginning of this book.
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 vi, which corresponds to the number of voters that he will bring in, and a cost mi. 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:
The last criterion ...