Optimal Districting and Territory Design by Roger Z. Ríos-Mercado

Author:Roger Z. Ríos-Mercado
Language: eng
Format: epub
ISBN: 9783030343125
Publisher: Springer International Publishing

6.2 Mathematical Programming for Political Districting

The use of mathematical programming is a common practice in applications in which a quantitative approach is adopted to solve real-life problems. PD is one of these problems and the first models proposed in the literature for its solution are, in fact, mathematical programs (see Sect. 6.3). The success of mathematical programming resides in the fact that the formal model which represents the problem is easy-to-read (even if, of course, it is not as much easier to model the problem correctly). This is particularly important for PD in order to interact with politicians and lawmakers, who may feel comfortable with this kind of approach, also agreeing on the idea of solving the technical problem in a rigorous and efficient way, instead of proceeding by hands. In fact, this is what nowadays still happens in many countries, in spite of the extremely advanced and efficient technologies that are available for automated problem solving. Many criteria can be easily formulated through suitable algebraic constraints. But in real-life problems some conditions may require some additional effort to be modeled in this way, and it is possible that their correct formulation leads to a final model which is difficult to solve. This is the case of the contiguity constraints in PD, that we will discuss extensively in the following sections.

Relying on a correct and possibly concise model guarantees that in principle the problem can be solved exactly. Unfortunately, how much efficient is the solution process depends on the theoretical computational complexity of the problem. The typical situation in the general case is a computationally hard problem, but, if the size of the problem instance is not too large, the exact solution may be obtained. In the mathematics of electoral systems we already have examples. Problems related to seat allocation on the basis of the vote outcome of an election are of this type. For example, biproportional apportionment problems can be formulated as integer or mixed integer linear programs and can be solved efficiently at optimum even if the variables of the model are binary [19, 23, 25, 27]. For PD the difficulty is related to the integer decision variables and depends on the size of the territory under study. There are several cases in which the territory is small, i.e., after its discretization, the number of its territorial elementary units is small. In this case the problem can be solved easily. For medium size problems an efficient solution can be obtained using powerful computers that, thanks to the fast improvement of technology in the years, today allows solving in reasonable time problems that, for their size, were prohibitive 10 or 20 years ago. Some stratagems can be adopted to face large PD problems. One is to provide a first division of the territory into a set of subterritories, and then solve PD separately on these subterritories. This is, for example, the case of Italy, where the already existing division of the national territory into the Italian Administrative Regions is

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.