O'Reilly logo

Metaheuristics for Logistics by Laurent Deroussi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 iI 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:

  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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required