Election Problem

election_problem.py

#!/usr/bin/env python3

import sys
from pyscipopt import Model, quicksum
import pdb
import random

def generate_votes(row=10, col=10):
    votes = {}

    for x in range(row):
        for y in range(col):
            democrats = random.randint(0, 50)
            republicans = random.randint(0, 50) * 2
            votes[x, y] = {'d': democrats, 'r': republicans}
    return votes


def main():
    model = Model("Election")
    row = 10
    col = 10
    constituency = 10
    s = {}
    wd = {}
    wr = {}
    winner = {}
    votes = generate_votes(row, col)

    # Winner vars for the 10 constituency
    for i in range(constituency):
        # Total number of democrats in this constituency
        wd[i] = model.addVar(vtype="I", name="wd{}".format(i))

        # Total number of republicans in this constituency
        wr[i] = model.addVar(vtype="I", name="wr{}".format(i))

        # If democrats have more votes than republicans set to 1 else 0
        winner[i] = model.addVar(vtype="B", name="winner{}".format(i))

    # Vars for the induvidual states
    for x in range(row):
        for y in range(col):
            for w in range(constituency):
                s[x, y, w] = model.addVar(vtype="B", name="{}-{}-{}".format(x, y, w))

    # Constraints
    # Every state can only be in one constituency
    for x in range(row):
        for y in range(col):
            model.addCons(quicksum(s[x, y, w] for w in range(constituency)) == 1)  # Nur 1 Bezirk

    # Every constituency has 10 states
    for w in range(constituency):
        model.addCons(quicksum(s[x, y, w] for x in range(col) for y in range(row)) == 10,
                      name="Bezirk_{}".format(w))

    # Sum up the total number of votes for this constituency for democrats wd and republicans wr
    for w in range(constituency):
        model.addCons(wd[w] == quicksum(s[x, y, w] * votes[x, y]['d']  for x in range(col) for y in range(row)))
        model.addCons(wr[w] == quicksum(s[x, y, w] * votes[x, y]['r']  for x in range(col) for y in range(row)))

    # Set the winner[w] to 1 if democrats have more votes else 0
    for w in range(constituency):
        model.addCons(wd[w] - wr[w] <= 500 * winner[w])
        model.addCons(winner[w] <= (wd[w] - wr[w]) * winner[w])
        
    conshdlr = ElectionHdlr(s, logger=logger)
    model.setBoolParam("misc/allowdualreds", False)
    model.includeConshdlr(conshdlr, "election",
                         "Election", chckpriority=-10,
                         needscons=False)

    # Set the target: As many 1 in winner[w] (democrats wins)
    model.setObjective(quicksum(winner[w] for w in range(constituency)), "maximize")

    model.hideOutput()
    model.optimize()

    if model.getStatus() != 'optimal':
        print('No solution found!') 
        sys.exit(1)
    print("Solution found")

    # Print solution
    solution = {}
    for x in range(row):
        out = ''
        for y in range(col):
            for w in range(10):
                if model.getVal(s[x, y, w]) >= 0.5:
                    # print(w+1)
                    solution[x, y] = w + 1
            out += str(solution[x, y]) + ' '
        print(out)


if __name__ == "__main__":
    main()

electionHandler.py

#!/usr/bin/env python3

from pyscipopt import Model, Conshdlr, SCIP_RESULT
import pdb
import logging


EPS = 1.e-6
class ElectionHdlr(Conshdlr):

    def __init__(self, variables, row=10, col=10, cons=10, logger=None):
        self.row = row
        self.col = col
        self.constituency = cons
        self.variables = variables
        self.logger = logger or logging.getLogger(__name__)



    def deepSearch(self, solution, pos_x, pos_y):
      """Check if the next states has the same value
      """
        fields = [{'x': pos_x, 'y': pos_y}]
        value = solution[pos_x, pos_y]['value']
        while len(fields) > 0:
            field = fields.pop(0)
            x = field['x']
            y = field['y']

            solution[x, y]['visited'] = True
            # Check right:
            if y < 9 and not solution[x, y+1 ]['visited'] and solution[x, y+1 ]['value'] == value:
                fields.append({'x': x, 'y': y+1})

            # Check down
            if x < 9 and not solution[x+1, y ]['visited'] and solution[x+1, y ]['value'] == value:
                fields.append({'x': x+1, 'y': y})

            # Check vertical
            if x < 9 and y < 9 and not solution[x+1, y+1 ]['visited'] and solution[x+1, y+1 ]['value'] == value:
                fields.append({'x': x+1, 'y': y+1})


    def checkNeighbour(self, sol=None):
        """self.model.getSolVal(solution, x[i,j]) > EPS:
        """
        # Build the solution to work with solution[x,y]
        solution = {}
        var = self.variables
        for x in range(self.row):
            for y in range(self.col):
                for w in range(self.constituency):
                    if self.model.getSolVal(sol, var[x, y, w]) > EPS:
                        solution[x, y] = {'visited': False, 'value': w}

        if not solution:
            return {'solution': False}

        # Check constrain that the constituency are aside
        visited_constituency = set()
        for x in range(self.row):
            for y in range(self.col):

                # Check if this value already is visited
                if solution[x, y]['visited']:
                    continue
                # Check if this constituency is in our list
                if solution[x, y]['value'] in visited_constituency:
                    self.logger.info("Value: {} was already searched".format(solution[x, y]['value']))
                    return {'solution': False, 'x': x, 'y': y, 'w': solution[x, y]['value']}

                # Set visited flag for
                visited_constituency.add(solution[x, y]['value'])
                self.logger.info("Deep search from x: {}, y: {} for element {}".format(x, y, solution[x, y]['value']))
                self.deepSearch(solution, x, y)


        return {'solution': True}


    def conscheck(self, constraints, solution, checkintegrality,
                  checklprows, printreason, completely):
        self.logger.info("Check one solution")
        self.logger.info("-"*20)
        sol = self.checkNeighbour(solution)
        if sol['solution']:
            self.logger.info("Solution seems OK")
            return {"result": SCIP_RESULT.FEASIBLE} 
        else:
            self.logger.info("Solution is not OK")
            return {"result": SCIP_RESULT.INFEASIBLE}


    def consenfolp(self, constraints, n_useful_conss, sol_infeasible):
        self.logger.info("Check CONSENS")
        self.logger.info("="*20)
        var = self.variables
        sol = self.checkNeighbour()
        if sol['solution']:
            {"result": SCIP_RESULT.FEASIBLE}
        else:
            return {"result": SCIP_RESULT.CUTOFF}

    def conslock(self, constraint, nlockspos, nlocksneg):
        pass