Search code examples
or-toolsminizinc

Minimizing the sum of an array as exponent to the base 2

I have a problem that roughly does the following

set of int: SIZE = 1..3;
array[SIZE] of int: bound;
array[SIZE] of var int: cost;

constraint forall(i in SIZE) (cost[i] > bound[i]);

solve minimize sum(i in SIZE) (2^cost[i]);

I guess due to the way CP solver works, this is not possible. Or-tools throws the error

evaluation error: comprehension iterates over an infinite set

At the moment I opted for a hacky way to at least minimize the biggest exponent and how many times it occures with

solve minimize max(cost)*100+count(cost, max(cost));

Is there a nice and efficient way to take the elements of an array as exponent to the base 2, sum it and minimize the result?

Solution

  • The problem with you model stems from the fact that OR-Tools (and Gecode) do not have propagators for pow with variable exponents. They will instead rewrite the expression to work on each possible value that the exponent can take, and then choose the result based on the chosen value.

    However, when your expression is var int the set of possible value is infinite, and this is not possible. This is why MiniZinc will complain and throw an error. The fix is simply to provide both upper and lower bounds on your cost variables. For example, we could say that they have to be between 0 and 10, and the model will function as expected.

    set of int: SIZE = 1..3;
array[SIZE] of int: bound;
array[SIZE] of var 0..10: cost;

constraint forall(i in SIZE) (cost[i] > bound[i]);

solve minimize sum(i in SIZE) (2^cost[i]);

    (Alex' solution also is correct, but does some of the rewriting manually even though this is not necessary).