I am trying to implement the following problem using JACOP. Is it possible and if so how best to do it?
a subset of 50 x 50 x 20 = 50,000 boolean variables
should equal 1 and the remainder 0:
each selected[i][j][k] which is equal to 1
is associated with a utility value:
the goal is to maximize total utility:
maximize Σ(all i,j,k) (selected[i][j][k] * utility[i][j][k])
subject to the constraints that there is AT MOST one selection in
each row, column, and stack:
for each (i, j): Σ(all k) selected[i][j][k] <= 1
for each (j, k): Σ(all i) selected[i][j][k] <= 1
for each (i, k): Σ(all j) selected[i][j][k] <= 1
note, the usage
Σ(all x) K
means the sum of K evaluated at each value of x
You will have to experiment with few different models. I will give some tips. There are two types of tips (search and model). I can only hope you can decipher mine rumblings.
You have a challenging problem, thus the tips must touch on many advanced modelling techniques and aspects.
You need to be careful to avoid paying even linear complexity for large arity constraints.
What is the distribution of utility? Does it often have the same utility for different booleans? If yes, then you could simplify the computation of the maximal utility by grouping booleans with the same utility. Grouping by creating a sum var (int) that will be a sum of all booleans that have the same utility. Now, you will have array of int variables selectedSum[utility] that you could use in SumWeight constraint to compute the total utility. Even, if you do not have many booleans with the same utility you need to split the computation of total utility value across multiple constraints. Split the selected booleans and their utility into multiple groups with similar utility ( for example 200 groups where first group has the booleans with the highest utility, the last group has the booleans with the lowest utility and each group has 250 variables). Now compute the sum of utility for each group (using SumWeight). Now when you have utility of each group compute the total utility by simply summing them. This way of computing total utility combined with proper search will help you avoid iterating over long arrays.
AtMost constraint can be modeled by Sum, Count, Among. I will try them in this order.
The most important in this problem will be search. Order selected variables in such a way that the ones with the maximal utility are first. Use InputOrder with the search, so the ones with the highest utility are assigned first. Use IndomainMax so they are assigned first value 1.
Above, I suggested grouping selected variables into 200 groups. The search should help to minimize the number of constraints that are woken up to do the calculations.
More advanced model(s), discussions.
You can also look at your problem as
1) selecting k for all pairs of (i, j)
2) selecting i for all pairs of (j, k)
3) selecting j for all pairs of (i, k)
If we focus on 1) then what is the utility structure for each pair of (i, j)? The pairs of (i, j) may have very different cost structure, namely, it may have the minimum and maximum utility (depending on k) that varies a lot between pairs of ij. You could order pairs (i, j) starting with the ones that have the highest max regret (highest difference between maximum and minimum) and assign those in such a way that you get the highest utility).
How to compute the utility for a given pair (i, j) depending on k. You need to use an Element constraint that will give you way to know utility of pair(i,j) depending on the choice of k. Thus, utility of pair(i, j) will be a int var that will have its min and max. Thus use search that uses those utility[pair(i, j)] to decide about the value of the utility for a given pair first, followed by the choice of k, if multiple k have the same utility (SimpleMatrixSelect here, where utility variable is a pivot variable, the vector contains utility and k).
You could have a model where you take all pairs (i, j), (j, k), (i, k) and order them according to the MaxRegret criteria. Now, you select k, i, j based on the ones that have the highest MaxRegret.
This advanced approach is likely to work much better because it focuses better on the cost structure within search and it does not do the search on boolean variables but on int variables so the size of the search should be much smaller, but it requires usage of Element constraints, so there are some extra computational costs.
I will first work with a simple model 5x5x2 boolean variables to make sure that your constraints are properly setup. When you know that you constraint model is correct increase the problem size to 10x10x10 and experiment with different models/searches to see which one is the best one.
If my tips are too difficult to decipher and you have no clue what I am talking about
then I apologize and I recommend looking at advanced examples within JaCoP, for example NonTransitiveDice problem (sums, matrix), MUCA problem (among, complex searches), Parcel problem (TSP + sums), TSP problem (max regret, cost structure driven search), Queens (dual model).
If you understand half of what I said, then again I apologize, and propose the following deal, if you setup a github repository with your example and agree to add your code for your problem to JaCoPExamples then I can follow your work and give you more tips in the continuous manner.
Yes, it is possible but it might be not the best choice since it is a max-sat problem and you might look a specialized SAT solver for this.
Anyway, I made a simple model for your problem in minizinc and used JaCoP to solve it. The model is as follows.
array[1..50,1..50,1..20] of var 0..1: selected;
%array[1..50,1..50,1..20] of int: utility;
var int: cost;
forall (i in 1..50, j in 1..50) (sum(k in 1..20) (selected[i,j,k]) <= 1)
forall (j in 1..50, k in 1..20) (sum(i in 1..50) (selected[i,j,k]) <= 1)
forall (i in 1..50, k in 1..20) (sum(j in 1..50) (selected[i,j,k]) <= 1)
cost = sum(i in 1..50, j in 1..50, k in 1..20) (selected[i,j,k])
solve maximize cost;
I do not use utility since I do not know your values but JaCoP finds a solution with cost 4 but does not prove optimality in a reasonable time.
To make this model more efficient you should use AmongVar (minizinc among_var) constraint, I think. I do not have time to try it.
Thanks so much for your responses. I will set up a repository as you suggested and add my code to it.
As to your question about the structure of utility, it is almost always constant across the k dimension, that is, utility[i][j][k1] == utility[i][j][k2] for every k1 and k2, and all i, j (there are just a few exceptions.)
Thanks again for your tips, Radoslaw and Kris.
Log in to post a comment.