1,721,015 research outputs found
Local search algorithms for political districting
No full textElectoral district planning plays an important role in a political election, especially when a majority voting rule is adopted, because it interferes in the translation of votes into seats. The practice of gerrymandering can easily take place if the shape of electoral districts is not controlled. In this paper we consider the following formulation of the political districting problem: given a connected graph (territory) with n nodes (territorial units), partition its set of nodes into k classes such that the subgraph induced by each class (district) is connected and a given vector of functions of the partition is minimized. The nonlinearity of such functions and the connectivity constraints make this network optimization problem a very hard one. Thus, the use of local search heuristics is justified. Experimentation on a sample of medium-large real-life instances has been carried out in order to compare the performance of four local search metaheuristics, i.e., Descent, Tabu Search, Simulated Annealing, and Old Bachelor Acceptance. Our experiments with Italian political districting provided strong evidence in favor of the use of automatic procedures. Actually, except for Descent, all local search algorithms showed a very good performance for this problem. In particular, in our sample of regions, Old Bachelor Acceptance produced the best results in the majority of the cases, especially when the objective function was compactness. Moreover, the district maps generated by this heuristic dominate the institutional district plan with respect to all the districting criteria under consideration. When properly designed, automatic procedures tend to be impartial and yield good districting alternatives. Moreover, they are remarkably fast, and thus they allow for the exploration of a large number of scenarios. (c) 2007 Elsevier B.V. All rights reserved
Political Districting: From classical models to recent approaches
No full textThe Political Districting problem has been studied since the 60's and many different models and techniques have been proposed with the aim of preventing districts' manipulation which may favor some specific political party (gerrymandering). A variety of Political Districting models and procedures was provided in the Operations Research literature, based on single- or multiple-objective optimization. Starting from the forerunning papers published in the 60's, this article reviews some selected optimization models and algorithms for Political Districting which gave rise to the main lines of research on this topic in the Operations Research literature of the last five decades. © 2012 Springer Science+Business Media New York
Computing sharp bounds for hard clustering problems on trees
No full textClustering problems with relational constraints in which the underlying graph is a tree arise in a variety of applications: hierarchical data base paging, communication and distribution networks, districting, biological taxonomy, and others. They are formulated here as optimal tree partitioning problems. In a previous paper, it was shown that their computational complexity strongly depends on the nature of the objective function and, in particular, that minimizing the total within-cluster dissimilarity or the diameter is computationally hard. We propose heuristics that find good partitions within a reasonable time, even for instances of relatively large size. Such heuristics are based on the solution of continuous relaxations of certain integer (or almost integer) linear programs. Experimental results on over 2000 randomly generated instances with up to 500 entities show that the values (total within-cluster dissimilarity or diameter) of the solutions provided by these heuristics are quite close to the minimum one. (C) 2008 Elsevier B.V. All rights reserved
The give-up problem for blocked regional lists with multi-winners
No full textThe current electoral law for the Italian Parliament prescribes blocked, linearly ordered lists of candidates for each party within each constituency. The peculiarity of the Italian electoral system is that a party can present the same candidate in different constituencies. There are several seats at stake in each constituency; these seats are allocated to the parties proportionally to the total number of votes they get. If the blocked list mechanism-which assigns the seats obtained by a party in a constituency to the first candidates of the corresponding ordered list-causes some candidates to win in more than one constituency, they may retain only one of the seats, giving up all the remaining ones. Thus, the problem arises for a party to find a suitable schedule of give-ups that produces the final set of winners for that party. In order to do this, we assume that such decision is centralized and based on some models of global (inter-regional) preferences over the set of candidates. In this paper, we introduce two classes of models to formulate the give-up problem, i.e., utility and ordinal models, and we show that for both of them some natural formulations of the problem can be efficiently solved by network flows techniques. © 2011 Elsevier B.V
Block linear majorants in quadratic 0-1 optimization
No full textAbstractA usual technique to generate upper bounds on the optimum of a quadratic 0–1 maximization problem is to consider a linear majorant (LM) of the quadratic objective function f and then solve the corresponding linear relaxation. Several papers have considered LMs obtained by termwise bounding, but the possibility of bounding groups of terms simultaneously does not appear to have been given much attention so far. In the present paper a broad and flexible computational framework is developed for implementing such a strategy. Here is a brief overview of our approach: in the first place, a suitable collection of “elementary” quadratic functions of few variables (typically, 3 or 4) is generated. All the coefficients of any such function (block) are either 1 or −1, and agree in sign with the corresponding coefficients of the given quadratic function. Next, for each block, a tightest LM (i.e., one having the same value as the block in as many points as possible), or a closest LM (i.e., one minimizing the sum of slacks) is computed. This can be accomplished through the solution of a small mixed-integer program, or a small linear program, respectively. Finally, the objective function is written as a weighted sum of blocks, with non-negative weights. Replacing in this expression each block by the corresponding LM yields an LM of f. We shall choose the weights in this process so that the maximum value of the resulting linear function is as small as possible. This amounts to a large-scale (but still polynomial-size) linear program, which may be solved exactly or, for larger instances, approximately by truncated column generation. The results of a set of 480 numerical tests with up to 200 variables are presented: the upper bounds on the quadratic optimum obtained by the above procedure are (provably) never worse, and often turn out to be substantially sharper, than those resulting from termwise bounding. Moreover, our bounds turn out to be close to the optimum in many (although not all) instances of some well-known benchmarks
Political districting: from classical models to recent approaches
No full textThe political districting problem has been studied since the 60's and many different models and techniques have been proposed with the aim of preventing districts' manipulation which may favor some specific political party (gerrymandering). A variety of political districting models and procedures was provided in the Operations Research literature, based on single- or multiple-objective optimization. Starting from the forerunning papers published in the 60's, this article reviews some selected optimization models and algorithms for political districting which gave rise to the main lines of research on this topic in the Operartions Research literature of the last five decades
- …
