ILP Part 45 — Deadline 24 2017 Election

This is the forty fifth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we solve Election task from Deadline 24 2017 using ILP. You can read it here or short description below:

Looks like perfect task for ILP.


For every candidate we create a binary variable saying whether this candidate is included in Tribunal. Next, for each voter we create conjunction of variable of candidate which voter wants to enter the Tribunal and binary negation of variable of candidate which this voter doesn’t want to enter. Next, we simply maximize the sum of all voter variables.

Code below solves the problem:

This solution received AC during the contest.