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:

Introduction
Today is an important day at the Supreme Chamber of the Beetle Parliament. It is today that
the Members of the Beetle Parliament (MBPs) are electing the members of the Jumping Tribunal.
Both parliamentary groups – the Civil Faction and the Military Faction – submitted their nominations.
The Jumping Tribunal will be selected from those candidates in a voting that is quite atypical by today’s
standards. Each MBP has exactly two votes. One of them says which candidate the MBP would want
in the Tribunal, the other – the candidate the MBP is vehemently opposed to. When all votes are
gathered – in compliance with the Beetle Constitution – the Jumping Tribunal will be elected in such
a manner that both votes of as many MBPs as possible corresponds to the selected Tribunal members.
Problem
The Civil Faction submitted A nominations, the Military Faction – B nominations. Each MBP submitted
precisely two votes in the manner described above. Because of a strict party discipline, MBPs
of each faction vote in favor of one of the nominees of their own faction and against one of the nominees
of the opposing faction. A total of N MBPs are entitled to vote.
The two votes (one favorable and one negative) cast by each MBP are considered as two requests:
“please include this candidate in the Tribunal” and “under no circumstances may the candidate be included
in the Tribunal”. An MBP is content with the voting results only if both of his requests have been fulfilled
simultaneously. The elected representation of the Tribunal must ensure the maximum number of MBPs
who are happy with the voting results.
Having all granted votes at your disposal propose the final (and compliant with the Beetle Constitution!)
composition of the Jumping Tribunal. The Tribunal may be composed of any number of candidates.

Introduction

Today is an important day at the Supreme Chamber of the Beetle Parliament. It is today that

the Members of the Beetle Parliament (MBPs) are electing the members of the Jumping Tribunal.

Both parliamentary groups – the Civil Faction and the Military Faction – submitted their nominations.

The Jumping Tribunal will be selected from those candidates in a voting that is quite atypical by today’s

standards. Each MBP has exactly two votes. One of them says which candidate the MBP would want

in the Tribunal, the other – the candidate the MBP is vehemently opposed to. When all votes are

gathered – in compliance with the Beetle Constitution – the Jumping Tribunal will be elected in such

a manner that both votes of as many MBPs as possible corresponds to the selected Tribunal members.

Problem

The Civil Faction submitted A nominations, the Military Faction – B nominations. Each MBP submitted

precisely two votes in the manner described above. Because of a strict party discipline, MBPs

of each faction vote in favor of one of the nominees of their own faction and against one of the nominees

of the opposing faction. A total of N MBPs are entitled to vote.

The two votes (one favorable and one negative) cast by each MBP are considered as two requests:

“please include this candidate in the Tribunal” and “under no circumstances may the candidate be included

in the Tribunal”. An MBP is content with the voting results only if both of his requests have been fulfilled

simultaneously. The elected representation of the Tribunal must ensure the maximum number of MBPs

who are happy with the voting results.

Having all granted votes at your disposal propose the final (and compliant with the Beetle Constitution!)

composition of the Jumping Tribunal. The Tribunal may be composed of any number of candidates.

Looks like perfect task for ILP.

Solution

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:

var solver = new CplexMilpSolver(5);

solver.Cplex.SetOut(null);

var header = Console.ReadLine().Split(new[] {" "}, StringSplitOptions.RemoveEmptyEntries).Select(c => Convert.ToInt32(c)).ToArray();

int N = header[0];
int A = header[1];
int B = header[2];

var isA = Enumerable.Range(0, A).Select(a => solver.Create($"A_{a}", Domain.BinaryInteger)).ToArray();
var isB = Enumerable.Range(0, B).Select(b => solver.Create($"B_{b}", Domain.BinaryInteger)).ToArray();

var goal = solver.FromConstant(0);

for (int i = 0; i < N; ++i)
{
	IVariable isIHappy;

	var ballot = Console.ReadLine().Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries).Select(c => Convert.ToInt32(c)).ToArray();

	int yesF = ballot[0];
	int yesId = ballot[1] - 1;

	int noF = ballot[2];
	int noId = ballot[3] - 1;

	if (yesF == 1)
	{
		isIHappy = isA[yesId];
	}
	else
	{
		isIHappy = isB[yesId];
	}

	if (noF == 1)
	{
		isIHappy = isIHappy.Operation(OperationType.Conjunction, isA[noId].Operation(OperationType.BinaryNegation));
	}
	else
	{
		isIHappy = isIHappy.Operation(OperationType.Conjunction, isB[noId].Operation(OperationType.BinaryNegation));
	}


	goal = goal.Operation(OperationType.Addition, isIHappy);
}

solver.AddGoal("goal", goal);

solver.Solve();

var aChosen = isA.Select(v => (int) v.GetValue()).ToArray();
var bChosen = isB.Select(v => (int) v.GetValue()).ToArray();

Console.WriteLine(aChosen.Count(v => v == 1));

for (int i = 0; i < A; ++i)
{
	if (aChosen[i] == 1)
	{
		Console.Write($"{i+1} ");
	}
}
Console.WriteLine();

Console.WriteLine(bChosen.Count(v => v == 1));

for (int i = 0; i < B; ++i)
{
	if (bChosen[i] == 1)
	{
		Console.Write($"{i + 1} ");
	}
}
Console.WriteLine();

var solver = new CplexMilpSolver(5);

solver.Cplex.SetOut(null);

var header = Console.ReadLine().Split(new[] {" "}, StringSplitOptions.RemoveEmptyEntries).Select(c => Convert.ToInt32(c)).ToArray();

int N = header[0];

int A = header[1];

int B = header[2];

var isA = Enumerable.Range(0, A).Select(a => solver.Create($"A_{a}", Domain.BinaryInteger)).ToArray();

var isB = Enumerable.Range(0, B).Select(b => solver.Create($"B_{b}", Domain.BinaryInteger)).ToArray();

var goal = solver.FromConstant(0);

for (int i = 0; i < N; ++i)

{

IVariable isIHappy;

var ballot = Console.ReadLine().Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries).Select(c => Convert.ToInt32(c)).ToArray();

int yesF = ballot[0];

int yesId = ballot[1] - 1;

int noF = ballot[2];

int noId = ballot[3] - 1;

if (yesF == 1)

{

isIHappy = isA[yesId];

}

else

{

isIHappy = isB[yesId];

}

if (noF == 1)

{

isIHappy = isIHappy.Operation(OperationType.Conjunction, isA[noId].Operation(OperationType.BinaryNegation));

}

else

{

isIHappy = isIHappy.Operation(OperationType.Conjunction, isB[noId].Operation(OperationType.BinaryNegation));

}

goal = goal.Operation(OperationType.Addition, isIHappy);

}

solver.AddGoal("goal", goal);

solver.Solve();

var aChosen = isA.Select(v => (int) v.GetValue()).ToArray();

var bChosen = isB.Select(v => (int) v.GetValue()).ToArray();

Console.WriteLine(aChosen.Count(v => v == 1));

for (int i = 0; i < A; ++i)

{

if (aChosen[i] == 1)

{

Console.Write($"{i+1} ");

}

Console.WriteLine();

Console.WriteLine(bChosen.Count(v => v == 1));

for (int i = 0; i < B; ++i)

{

if (bChosen[i] == 1)

{

Console.Write($"{i + 1} ");

}

Console.WriteLine();

This solution received AC during the contest.