JuMP: constraint to use a value only `n` times

Specific Domains Optimization (Mathematical)
,
1

I am trying to solve a problem using ConstraintSolver.jl which uses JuMP. I want to define a constraint for a group of variables, such that certain values are only chosen certain times.

For eg: if the variables are 1 <= x[1:10] <= 3, I want it such that value 1 is only chosen 2 times, value 2 is only chosen 5 times and value 3 is chosen 2 times.

Can this be achieved using the constraints defined in JuMP and ConstraintSolver (listed here)?

2

This is generally achieved using a binary expansion:

model = Model()
n = [2, 5, 3]
@variable(model, y[1:10, 1:3], Bin)
@constraint(model, [i=1:10], sum(y[i, :]) == 1)
@constraint(model, [j=1:3], sum(y[:, j]) == n[j])
@expression(model, x[i=1:10], sum(j * y[i, j] for j in 1:3))
3 Likes
3

Thanks a lot! I have been looking for a solution for a very long time.

Just making sure, if my values are not in a range like instead of 1,2,3 which can be written as 1:3, if my possible values are 1,3,4 can I still make it work by using range 1:4 but not defining any constraint for value 2?

4

The standard name in the constraint programming community for this constraint is “Global Cardinality Count” (aka “GCC”). I have defined a decomposition for ConstraintSolver.jl in http://hakank.org/julia/constraints/constraints_utils.jl (as global_cardinality_count(model, a, gcc)), with a small example of the usage here: http://hakank.org/julia/constraints/clobal_cardinality_count.jl .

The arraya is the array of decision variables and gcc contains the occurrences for each value in a (including number of occurrences for the value of 0). It use another decomposition count_ctr for doing the counts.

If you want to constrain that one value in a should not be present, simply set the corresponding value in gcc to 0.

5 Likes
5

This is a very concise solution to define such a constraint. However, I think I will use the more performant solution for my use case; I think that the global_cardinality_count function will be slower because of the mutiple binary variables and sum constraints.

Based on my limited testing (gcc_vs_binexpr_test.jl) with some changed code, it seems that the original solution, though a bit more verbose, is faster (output.txt).

6

I definitely agree that your implementation is faster than mine. On my computer your approach is even more performant than mine than what the output.txt indicates.

A comment: My original implementation of global_cardinality_count also support cases when the gcc array (the count array) is an array of decision variables, which might be handy in some cases, for example if one want to add some constraints about the occurrences, such that the occurrences should be distinct.

But perhaps that variant is not relevant for your use case.

1 Like