ILP Part 57 – SPOJ Wpłaty – Random IT Utensils

This is the fifty seventh 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 are going to solve RNR_01_04 – Wpłaty from SPOJ. The history is as follows.
We want to get some money for charity. We go from door to door and ask each homeowner to donate. Each person can either donate automatically if at least $d_i$ persons donated already. We can either convince the person explicitly (if that’s needed) or move on. The task is to get at least $m$ donations and to convince as few people as possible. We are given number of people, $m$ , and next line with $d$ values.

Example:

8 5
10 5 1 4 2 3 10 4

1 2	8 5 10 5 1 4 2 3 10 4

Output:

1

Solution:

var solver = new CplexMilpSolver(10);

var requiredPayments = 5;
IVariable[] paymentsToNotRequireConvincing = new int[] {10, 5, 1, 4, 2, 3, 10, 4}.Select(w => solver.FromConstant(w)).ToArray();

IVariable[] isExplicitlyConvinced = paymentsToNotRequireConvincing.Select(w => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray();
List<IVariable> isConvinced = new List<IVariable>();

for(int i=0;i<paymentsToNotRequireConvincing.Length; ++i){
	var currentConvinced = i > 0 
		? solver.Operation(OperationType.Addition, isConvinced.Take(i).ToArray()).Operation(OperationType.IsGreaterOrEqual, paymentsToNotRequireConvincing[i]).Operation(OperationType.Disjunction, isExplicitlyConvinced[i]) 
		: solver.FromConstant(0).Operation(OperationType.IsGreaterOrEqual, paymentsToNotRequireConvincing[i]).Operation(OperationType.Disjunction, isExplicitlyConvinced[i]);
	isConvinced.Add(currentConvinced);
}

solver.Operation(OperationType.Addition, isConvinced.ToArray()).Set(ConstraintType.GreaterOrEqual, solver.FromConstant(requiredPayments));

var goal = solver.Operation(OperationType.Addition, isExplicitlyConvinced.ToArray());

solver.AddGoal("Goal", goal.Operation(OperationType.Negation));
solver.Solve();

Console.WriteLine("To convince: " + solver.GetValue(goal));
foreach(var c in isExplicitlyConvinced) {
	Console.WriteLine("Explicitly convinced: " + solver.GetValue(c));
}

var solver = new CplexMilpSolver(10);

var requiredPayments = 5;

IVariable[] paymentsToNotRequireConvincing = new int[] {10, 5, 1, 4, 2, 3, 10, 4}.Select(w => solver.FromConstant(w)).ToArray();

IVariable[] isExplicitlyConvinced = paymentsToNotRequireConvincing.Select(w => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray();

List<IVariable> isConvinced = new List<IVariable>();

for(int i=0;i<paymentsToNotRequireConvincing.Length; ++i){

var currentConvinced = i > 0

? solver.Operation(OperationType.Addition, isConvinced.Take(i).ToArray()).Operation(OperationType.IsGreaterOrEqual, paymentsToNotRequireConvincing[i]).Operation(OperationType.Disjunction, isExplicitlyConvinced[i])

: solver.FromConstant(0).Operation(OperationType.IsGreaterOrEqual, paymentsToNotRequireConvincing[i]).Operation(OperationType.Disjunction, isExplicitlyConvinced[i]);

isConvinced.Add(currentConvinced);

}

solver.Operation(OperationType.Addition, isConvinced.ToArray()).Set(ConstraintType.GreaterOrEqual, solver.FromConstant(requiredPayments));

var goal = solver.Operation(OperationType.Addition, isExplicitlyConvinced.ToArray());

solver.AddGoal("Goal", goal.Operation(OperationType.Negation));

solver.Solve();

Console.WriteLine("To convince: " + solver.GetValue(goal));

foreach(var c in isExplicitlyConvinced) {

Console.WriteLine("Explicitly convinced: " + solver.GetValue(c));

}

We create binary variables in line 6 to indicate whether we had to convince person explicitly. Then in loop in line 9 we calculate whether person is convinced – either automatically or explicitly.
In line 16 we add constraint to have at least $m$ payments.
Then in line 18 we want to count people we had to convince explicitly and then minimize the value.

Bonus chatter: Do you know how to solve this in $O(n)$ time and $O(n)$ memory?