ILP Part 70 — Elements reordering

This is the seventieth 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 solving the following problem: we have a set of elements with ranks (higher rank is better) and want to reorder them to maximize the revenue. However, some elements are pinned to positions and can be moved at most one slot away. Only eight top elements are considered for the cost function (they fit in the UI element), also, elements closer to the beginning are worth more.

Sounds simple:

var ranks = new int[]{1, 2, 5, 11, 20, 30, 60, 65, 70, 71, 73, 90, 110};
var positions = new int[] {-1, -1, 4, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1};
int count = ranks.Length;
int premiumPositions = 8;

var variables = Enumerable.Range(0, count).Select(i => solver.CreateAnonymous(Domain.PositiveOrZeroInteger)).ToArray();

solver.Set<AllDifferent>(variables[0], variables.Skip(1).ToArray());

for(int i=0;i<count;++i){
	variables[i].Set<LessOrEqual>(solver.FromConstant(count)).Set<GreaterOrEqual>(solver.FromConstant(1));
	
	if(positions[i] != -1){
		variables[i].Set<LessOrEqual>(solver.FromConstant(positions[i]+1)).Set<GreaterOrEqual>(solver.FromConstant(positions[i]-1));
	}
}

var goal = solver.Operation<Addition>(Enumerable.Range(0, count).Select(i => solver.Operation<Condition>(variables[i].Operation<IsLessOrEqual>(solver.FromConstant(premiumPositions)), solver.FromConstant(premiumPositions + 1).Operation<Subtraction>(variables[i]).Operation<Multiplication>(solver.FromConstant(ranks[i])), solver.FromConstant(0))).ToArray());

solver.AddGoal("g", goal);
solver.Solve();

var ranks = new int[]{1, 2, 5, 11, 20, 30, 60, 65, 70, 71, 73, 90, 110};

var positions = new int[] {-1, -1, 4, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1};

int count = ranks.Length;

int premiumPositions = 8;

var variables = Enumerable.Range(0, count).Select(i => solver.CreateAnonymous(Domain.PositiveOrZeroInteger)).ToArray();

solver.Set<AllDifferent>(variables[0], variables.Skip(1).ToArray());

for(int i=0;i<count;++i){

variables[i].Set<LessOrEqual>(solver.FromConstant(count)).Set<GreaterOrEqual>(solver.FromConstant(1));

if(positions[i] != -1){

variables[i].Set<LessOrEqual>(solver.FromConstant(positions[i]+1)).Set<GreaterOrEqual>(solver.FromConstant(positions[i]-1));

}

var goal = solver.Operation<Addition>(Enumerable.Range(0, count).Select(i => solver.Operation<Condition>(variables[i].Operation<IsLessOrEqual>(solver.FromConstant(premiumPositions)), solver.FromConstant(premiumPositions + 1).Operation<Subtraction>(variables[i]).Operation<Multiplication>(solver.FromConstant(ranks[i])), solver.FromConstant(0))).ToArray());

solver.AddGoal("g", goal);

solver.Solve();

We start with ranks and pinned positions. We create variables and make sure positions are different. Next, we add ranges for each element and pin elements if possible.

Finally, the goal. We use the simple if condition: if an element is in first 8 slots then its rank is multiplied by the position with simple linear scaling (first element is worth eight times more than the eighth element), otherwise the item doesn’t change the goal function.

Output:

Total (root+branch&cut) =   93.52 sec. (32346.81 ticks)
Goal: 2441
13
12
5
4
11
10
9
8
7
6
3
2
1

Total (root+branch&cut) = 93.52 sec. (32346.81 ticks)

Goal: 2441

So it took 1,5 minutes to find the solution. Can we do better?

Hard part here is we use the condition which can be represented in ILP but is pretty heavy operation. However, we can use simple math to make it faster:

var goal = solver.Operation<Addition>(Enumerable.Range(0, count).Select(i => variables[i].Operation<Negation>().Operation<Addition>(solver.FromConstant(premiumPositions + 1)).Operation<Maximum>(solver.FromConstant(0)).Operation<Multiplication>(solver.FromConstant(ranks[i]))).ToArray());

1	var goal = solver.Operation<Addition>(Enumerable.Range(0, count).Select(i => variables[i].Operation<Negation>().Operation<Addition>(solver.FromConstant(premiumPositions + 1)).Operation<Maximum>(solver.FromConstant(0)).Operation<Multiplication>(solver.FromConstant(ranks[i]))).ToArray());

We take element $i$ in position $k$ . We first negate the position and get $-k$ , we then increase it by $8+1$ so we get $-k + 9$ and then take the maximum $\max(0, -k + 9)$ . Notice what happens: if the element was in first 8 positions then this value is transformed into proper ordering (first element is worth eight times more than the eighth element). Otherwise we get zero. We then multiply the value by the element’s rank.

Output:

Total (root+branch&cut) =   41.69 sec. (15158.95 ticks)
Goal: 2441.00000002328
12
11
5
4
13
9
10
8
7
6
3
1.99999999988359
0.999999999883586

Total (root+branch&cut) = 41.69 sec. (15158.95 ticks)

Goal: 2441.00000002328

1.99999999988359

0.999999999883586

Notice we get some rounding errors but at the end of the day it’s the same solution calculation in 40 seconds (almost twice as fast as previous approach). Can we do better?

Instead of having general integer variables let’s use binaries:

var variables = Enumerable.Range(0, count).Select(i => Enumerable.Range(0, count).Select(j => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray()).ToArray();

for(int i=0;i<count;++i){
	if(positions[i] != -1){
		for(int j = 0; j< count; ++j){
			if(j < positions[i] - 2 || j > positions[i]){
				solver.Set<Equal>(variables[i][j], solver.FromConstant(0));
			}
		}
	}
}

for(int j=0;j<count;++j){
	solver.Operation<Addition>(Enumerable.Range(0, count).Select(i => variables[i][j]).ToArray()).Set<Equal>(solver.FromConstant(1));
}

for(int i=0;i<count;++i){
	solver.Operation<Addition>(variables[i]).Set<Equal>(solver.FromConstant(1));
}

var goal = solver.FromConstant(0);
for(int j=0;j<premiumPositions;++j){
	for(int i=0;i<count;++i){
		goal = goal.Operation<Addition>(variables[i][j].Operation<Multiplication>(solver.FromConstant(ranks[i])).Operation<Multiplication>(solver.FromConstant(8 - j)));
	}
}

solver.AddGoal("g", goal);
solver.Solve();

var variables = Enumerable.Range(0, count).Select(i => Enumerable.Range(0, count).Select(j => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray()).ToArray();

for(int i=0;i<count;++i){

if(positions[i] != -1){

for(int j = 0; j< count; ++j){

if(j < positions[i] - 2 || j > positions[i]){

solver.Set<Equal>(variables[i][j], solver.FromConstant(0));

}

for(int j=0;j<count;++j){

solver.Operation<Addition>(Enumerable.Range(0, count).Select(i => variables[i][j]).ToArray()).Set<Equal>(solver.FromConstant(1));

}

for(int i=0;i<count;++i){

solver.Operation<Addition>(variables[i]).Set<Equal>(solver.FromConstant(1));

}

var goal = solver.FromConstant(0);

for(int j=0;j<premiumPositions;++j){

for(int i=0;i<count;++i){

goal = goal.Operation<Addition>(variables[i][j].Operation<Multiplication>(solver.FromConstant(ranks[i])).Operation<Multiplication>(solver.FromConstant(8 - j)));

}

solver.AddGoal("g", goal);

solver.Solve();

We use two dimensional array of binaries, first dimension is element number, second dimension is element position. Binary variable indicates whether i-th element can be assigned to j-th position.

First we block positions for pinned elements. Next, we make sure there is one element in given position. Finally, we make sure element is in one position only.

For goal we define calculations much easier: we iterate over premium positions and can precaculate the factor. We then multiply it by the binary variable. Result:

Total (root+branch&cut) =    0.02 sec. (1.17 ticks)

1	Total (root+branch&cut) = 0.02 sec. (1.17 ticks)

Looks like manual “variable unrolling” is way better. Generally, avoid using comparisons and prefer binary flags (especially if you can precalculate them outside of the ILP model).