\documentclass[a4paper]{article}
%\usepackage{hyperref}
\usepackage{amsmath,amsthm,amssymb}
\usepackage[T1,T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,bulgarian]{babel}
%\usepackage{setspace}
%\usepackage{color}
\usepackage{verbatim}
\usepackage{latexsym}

\begin{document}

\title{Едномандатни райони и поток в мрежа}
\author{Георги Георгиев (Скелета), Мартин Георгиев}
%\address{Faculty of Mathematics and Informatics, Sofia University, Sofia, Bulgaria}
%\ead{skelet@fmi.uni-sofia.bg}

\maketitle

\section{Задача} \mbox{}

Дадена е област, населена с избиратели и разделена на $n$ по-малки административни единици (общини).
Знаем броят избиратели $e_i$ във всяка община и кои общини са съседни (имат обща граница).

Известен е броят $k$ представители (депутати), които областта ще изпрати в парламента.

Търсим разделяне на областта на мажоритарни (едномандатни) избирателни райони (ЕИР).
Всеки ЕИР ще избира един представител (депутат), искаме всички ЕИР да имат приблизително равен брой избиратели.
Нека приемем, че $E_{all}=\sum_{i=1}^n e_i$ е кратно на $k$, искаме всеки ЕИР да има $C=E_{all}/k$ избиратели.

При разделянето искаме да запазим максимално географската обособеност на общините,
тоест всеки ЕИР да е от избиратели от една община или (при малки общини) от няколко съседни общини.

За да осигурим равенството на избирателите, ще се наложи да местим избиратели от една община към друга.
Търсим решение с минимален брой на преместени избиратели.

\section{Пример} %\mbox{}

\begin{verbatim}
Област Стара Загора, номерирани общини и избиратели в тях:

1 Братя Даскалови – 5691
2 Гурково – 4247
3 Гълъбово – 10913
4 Николаево – 3646
5 Казанлък – 68949
6 Мъглиж – 9444
7 Опан – 1892
8 Павел Баня – 13602
9 Раднево – 16918
10 Стара Загора – 147433
11 Чирпан  – 18585

общо 301320 избиратели, един мандат има C=30132 избиратели
\end{verbatim}
 
Търсим такова минимално разместване на избиратели от община към съседна община, 
при което след разместването всяка община ще има брой избиратели, кратен на $C=30132$.

Кои общини са съседни определяме от административната карта на България.
За конкретния пример съседствата, зададени като двойки номера на общини са:
\begin{verbatim}
(1,5), (1,8), (1,10), (1,11)
(2,6), (2,4), (2,10)
(3,7), (3,9)
(4,6), (4,10)
(5,6), (5,8), (5,10)
(6,10)
(7,9), (7,10)
(9,10)
(10,11)
\end{verbatim}

\begin{comment}
община Стара Загора граничи с всички общини 
       с изключение на Гълъбово и Павел Баня
община Братя Даскалови граничи с общини 
       Павел Баня, Казанлък, Стара Загора и Чирпан
община Гурково граничи с общини Мъглиж, Николаево и Стара Загора
община Гълъбово граничи с общини Опан и Раднево
община Николаево граничи с общини Гурково, Мъглиж и Стара Загора
община Казанлък граничи с общини
       Братя Даскалови, Мъглиж, Павел Баня и Стара Загора
община Мъглиж граничи с общини
       Гурково, Казанлък, Николаево и Стара Загора
община Опан граничи с общини Гълъбово, Раднево и Стара Загора
община Павел Баня граничи с общини Братя Даскалови и Казанлък
община Раднево граничи с общини Гълъбово, Опан и Стара Загора
община Чирпан граничи с общини Братя Даскалови и Стара Загора
\end{comment}

\section{Математически модел} \mbox{}

Нека $G(V,E)$ е неориентиран граф с върхове общините и ребра съседствата между общини.
Нека $V=\{1,2\ldots n\}$.

Преди разместването на избиратели община $i$ има $e_i$ избиратели, 
нека след разместването в нея има $Cx_i$ избиратели, $x_i$-целочислено
($x_i$ е броят ЕИР с център $i$-тата община след разместването).

Да означим с $f_{ij}, (i,j)\in E$ броят на избирателите, 
които преместваме от община $i$ към съседна община $j$.  

В сила е следния баланс на потока избиратели за $i$-тата община:
\begin{equation}
e_i+\sum_{j, (i,j)\in E}(f_{ji}-f_{ij})=Cx_i
\end{equation}
  
Формулираме задачата за намиране на минимално разместване като задача 
на целочисленото линейно програмиране (ЦЛП):
\begin{equation}\label{obj}
\min \sum_{(i,j)\in E} {f_{ij}}
\end{equation}

%subject to  constraints:
при ограничения:

\begin{equation}\label{const1}
\begin{array}{l}
\displaystyle \sum_{j, (i,j)\in E}(f_{ij}-f_{ji})+Cx_i=e_i, \ \forall i \\
\displaystyle x_{i}\geq 0, x_{i}\in \mathbb{Z} \\
\displaystyle f_{ij}\geq 0, f_{ij}\in \mathbb{Z} 
\end{array}
\end{equation}
 
Хипотеза 1: Описаната задача е $\mathbf{NP}$-трудна.

Хипотеза 2: Условието $f_{ij}\in \mathbb{Z}$ е излишно. 
Основание е за тази хипотеза е факта, че при фиксирани $x_{i}$ задачата става потокова и 
матрицата (\ref{const1}), задаваща ограниченията в линейния модел е напълно унимодулярна.

Точно решение може да се получи с някой от известните пакети за ЦЛП, примерно lp\_solve.

\section{Приближено решаване с жаден алгоритъм} \mbox{}

Свеждаме до потокова задача -- добавяме 2 нови върха $s$ и $t$ в графа $G$.
Нека $s$ има номер 0, а $t$ -- номер $n+1$.

Добавяме ориентирани ребра от $s$ до всички общини с пропускна способност (капацитет) $c_{s,i}=e_i$.

Неориентираните ребра в $G$ представяме като двойка ориентирани с безкрайна пропускна способност.

Добавяме ориентирани ребра от всички общини до $t$ с пропускна способност $c_{i,t}=0$.
Инициираме масив $x_i=0, \; 0<i\leq n$.

В така получения граф максималния поток от $s$ до $t$ е $0$.
Инициираме нулев поток $f_{ij}=0$ за $0\leq i,j \leq n+1,\; (i,j) \in E$ и изпълняваме жаден алгоритъм, 
който модифицира графа и потока:

\vspace{10pt}

[1] Избираме изходящо от $s$ ребро с максимална стойност на $\vartriangle=e_i-f_{s,i}$ 
-- броят избиратели в община $i$, които не са разпределени в никой ЕИР.
Това е жадната стъпка в алгоритъма.

[2] Ако $\vartriangle=0$ спираме (всички избиратели са разпределени).
Нека $\vartriangle>0$ и $i$ е номера на общината за която се достига.  
Увеличаваме $x_i$ с единица, също пропускната способност на реброто $(i,t), \; c_{i,t}=Cx_i$.
Смисълът на тази стъпка е, че добавяме нов ЕИР с център община $i$. 

[3] Насищаме потока, докато запълним увеличения капацитет $c_{i,t}$ така:

[3a] Търсим най-кратък увеличаващ път от $s$ до $t$ в смисъла на метода на Форд-Фалкерсон.
Ползваме BFS.

[3b] Увеличаваме потока по намерения път и отиваме на стъпка [3].

[4] Отиваме на стъпка [1].

\vspace{10pt}

След приключване на алгоритъма правим нормировка за всяка двойка съседни общини $(i,j)$.
Нека $f_{min}=min(f_{ij},f_{ji})$, намаляме потока и по двете ребра с $f_{min}$.

Ненулевите стойности на потока $f_{ij},  \; 0<i,j\leq n$ 
задават разместването на избирателите между съседни общини,
а стойностите на масива $x_i$ -- броя ЕИР с центрове съответните общини.

\vspace{10pt}

\emph{Пример за неоптималност на жадния алгоритъм} 
Нека имаме 6 общини, една централна с 10 избиратели, останалите 5 имат по 8 избиратели и са наредени около централната. 
Броят на мандатите е 5 ($k=5, C=10$).
Ако централната има номер 1, неориентираните ребра в $E$ са:

(1,2) (1,3) (1,4) (1,5) (1,6)
(2,3) (3,4) (4,5) (5,6) (6,2) 

Жадният алгоритъм ще даде мандат на централната община, 
а оптималното решение дава по един мандат на
всяка от периферните общини и прехвърля по 2-ма избиратели 
от централната към всяка периферна община.

\vspace{10pt}

Направените експерименти %от студента Мартин Георгиев 
показаха, че с насищане 
на най-късите пътища по схемата Форд-Фалкерсън не се получава поток с минимална сума на прехвърлянията.
В този смисъл жадния алгоритъм може да е полезен само при големи размери на задачата 
за намиране на приближени стойности на комбинаторните променливи $x_i$.

Не помага и двукратно пускане на жадния алгоритъм, при което първо търсим комбинаторните променливи $x_i$,
а при второто пускане ги фиксираме и търсим потоковите променливи $f_{ij}$. Полученото решение не минимизира сумата \`{и}м.

\section{Детайлизация на разместването} \mbox{}

Пакетът lp\_solve намира бързо решението на (\ref{obj},\ref{const1}) при малки размери, 
като в примера за област Стара Загора.

Проблемът е, че променливите $f_{ij}$ дават броя избиратели, които ще местим от една община в съседна,
но не дават информация кои точно, отчитайки по-фината административна и географска структура на 
общините. 

От условието за минимална цена на потока (\ref{obj}) тривиално следва, 
че графът от разместванията (с ребра $f_{ij}>0$) не съдържа цикли.
Нека го сортираме топологично и списъкът на наредба на върховете е $(v_1,v_2 \ldots v_n)$.

В сортирания граф всички ребра ще са насочени отляво на дясно и 
можем итеративно да декомпозираме и детайлизираме разместването.
Детайлизацията ще започне от връх $v_1$ и ще завърши в $v_n$.
На $i$-тата стъпка сме прехвърлили избиратели от върховете наляво от $v_i$,
а във връх $v_i$ има натрупани $e'_i$ избиратели, 
които са оригиналните $e_i$ избиратели във върха плюс преместените от вече обработените върхове.

Нека графът $G_i(V_i,E_i)$ е детайлизация на структурата на община $v_i$ 
след извършените до момента размествания.
Върховете $V_i$ могат да бъдат най-ниско ниво на детайлизация (секции) 
или по-малки административни единици (населени места, квартали и пр.).
Нека всеки от върховете има $y_j$ избиратели, $\sum_{j\in V_i}{y_j}=e'_i$.
Ребрата в този граф отразяват съседство или разстояние.

   

\end{document}


