1
$\begingroup$

Problem Statement

Let's run an election.

$i \in \text{voters}$

$j \in \text{candidates}$

$x_j \in \{ 0, 1 \}$ The candidate is chosen by setting this to 1. This is the election result.

$b_{i,j} \in [0,1]$ Ballot of voter i for candidate j. Voter gives bigger numbers if he likes the candidate. This is the input to the election.

Now, how do we choose $x_j$ so that the best group of candidates win? Here is one optimization.

edit 2: Actually this is a better problem.

Maximize $Z$ subject to

$\begin{array}{ll} \forall _{j } , & \sum_{i} f_i * b_{ij}^2 * x_j \geq Z * x_j & \text{ Minimum winning score is maximized.} \\ \forall _{i } , & \sum_{j} f_i * b_{ij} * x_j = 1 & \text{The weight of each voter is the same.} \leq \text{works too}\\ & \sum_{j } x_j = N & \text{ The number of seats is N.} \end{array} $ When I try this in Gurobi, it complains, "Q matrix is not positive semi-definite". However, I can set an upper bound on f and then it will work. Also, I can linearize something:

$ \forall _{j } , \quad N*(x_j-1)+\sum_{i} f_i * b_{ij}^2 \geq Z \quad \text{ Minimum winning score is maximized.} $

Gurobi does solve this, though it takes a lot of time. I wish I could linearize all the constraints so there is no $f*x$ term.

It is also possible to just say

$\text{Maximize} \quad {\displaystyle \min_j \sum_i \frac{b_{ij}^2}{\sum_j x_j*b_{ij}}}$

but I'm not sure this helps, though it does get rid of f.

Here's another related problem

$ \begin{array}{lll} \text{Minimize} & { \max_{i } \sum_{j } f_i * b_{ij} * x_j} & \text{The representation of each voter is fair.} \\ \text{Subject to} & {\forall \ j } \ \ \sum_{i } f_i * b_{ij}^2 *x_j \geq x_j \ \ \ & \text{The value of each winning seat is the same.} \end{array} $

old stuff below

edit 1: I realize a better problem to solve is this one:

Maximize $Z$ subject to

$\begin{array}{ll} \forall _{j } , & \sum_{i} f_i * b_{ij} * x_j \geq Z * x_j & \text{ Minimum winning score is maximized.} \\ \forall _{i } , & \sum_{j} f_i * b_{ij} * x_j = 1 & \text{The weight of each voter is the same.} \leq \text{works too}\\ & \sum_{j } x_j = N & \text{ The number of seats is N.} \end{array} $

When I try this in Gurobi, it complains, "Q matrix is not positive semi-definite".

The model and explanation below is old but helpful in understanding the problem above.

$\begin{array}{ll} \text{maximize } \text{ } \text{ } \sum_{i} & \sum_{j} f_i * b_{ij} * x_j \text{ } \text{ } \text{ } &\text{Total score is maximized.} \\ \text{ subject to } \text{ } \text{ } \forall _{i } , & \sum_{j} f_i * b_{ij} * x_j \leq 1 & \text{The weight of each voter is the same, basically.}\\ \text{ and subject to} & \sum_{j } x_j = N & \text{The number of seats is N.} \end{array} $

What is this $f_i$? It lets you vote for multiple candidates. So if two of your candidates that you like end up winning, half your vote went to one and half to the other. Basically, $f_i$ is a way to divide but using multiplication.

$f_i \in (0,1]$

How to Help

I'm glad Gurobi will do this problem. I was able to implement it. And it is too slow and I want it to go faster. I want to know what gurobi is doing. I have gurobi's log file but it is hard to interpret. I also have my code. In the example I am running, I have 216 voters, 10 candidates, and 5 winners. It takes 42 seconds.

What is this problem related to and are there different forms to implement it?

It is a kind of load balancing where the loading is factorized to $f_i * x_j$ instead of $x_{i,j}$. It is a binary problem in $x_j$ and it is also continuous in $f_i$. This is a committee selection problem. It's also almost a binary quadratic problem except it has this additional $f_i$, which is continuous.

There could be a simplification of $f_i$ because it is either 1 or $\frac{1}{\sum_{j} b_{ij} * x_j}$. Maybe this quadratic constraint can be simplified.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.