A typical problem requiring us to select a subset from a set of objects that meets some criteria and optimize some objective functions. This kind of problem is likely to be represented as an array of 0/1 variables, or an array of boolean variables. Or in MiniZinc, we can use set variables.
Set Variables
Modeling with sets is common for combinatorial problems. Set variables in MiniZinc choose a set from a given fixed superset, e.g.:
var set of {1, 2, 3}: x;
% x could be {}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}You may imagine set values are represented using an array:
array[1..3] of var 0..1: x;
set value possible representation value
{} [0,0,0]
{1} [1,0,0]
{2} [0,1,0]
{3} [0,0,1]
{1,2} [1,1,0]
{2,3} [0,1,1]
{1,3} [1,0,1]
{1,2,3} [1,1,1]Below is an example of well-known 0/1 knapsack problem, there are at least 3 modeling approaches:
- Array of indicator variables 0 or 1
- Array of boolean variables
- Native set variables
In the example below, the variable occur could be implemented as either an array or a set. Both are equivalent.
enum MOVES;
int: timeBound;
array[MOVES] of int: power;
array[MOVES] of int: duration;
var set of MOVES: occur;
% if use array
% array[MOVES] of var bool: occur;
constraint (sum(i in MOVES)(duration[i] * (i in occur))) <= timeBound;
% if use array
% constraint (sum(i in MOVES)(duration[i] * bool2int(occur[i]))) <= timeBound;
solve maximize sum(i in MOVES)(power[i] * (i in occur));
% if use array
% solve maximize sum(i in MOVES)(power[i] * bool2int(occur[i]));We can further simplify the code in the sum functions, which is more straight forward:
% more straight forward
constraint (sum(i in occur)(duration[i])) <= timeBound;
solve maximize sum(i in occur)(power[i]);Array variable or set variable? Which is better? Most solvers treat both the same. But Constraint Programming solvers may treat the last set variable better since they can combine cardinality reasoning with other set reasoning.
Fixed Cardinality Sets
When we’re modeling decisions in our problem, they are not necessarily the decisions we have to make in our model. We usually have to add constraints to our model to make sure that the only answers that come out of the model are valid decisions to the problem:
- Ensure each solution to the model is a solution of the problem
- Try to ensure each solution of the problem only has one solution in the model
In the historical novel Romance of the Three Kingdoms, an army wanted to attack a few spots, each of which is protected by some Bagua properties. If a spot is under attack, any other spots shared the same Bagua properties will be unbreakable. We can only choose a few spots to attach, and the objective is to max the damage. The problem can be modeled as below:
% data
int: nSpots = 10;
set of int: SPOT = 1..nSpots;
array[SPOT] of int: damage = [10, 8, 4, 2, 6, 9, 5, 3, 8, 10];
enum PROP = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};
array[PROP] of set of SPOT: group = [{1,4,6}, {1,2,6,7}, {1,3,6,8}, {1,2,3}, {2,9,10}, {5,6,8,10}, {7,8,10}, {1,3,5}];
% decision variables
var set of SPOT: attacks;
% constraints
% for every property, we can only attack one spot associated with that property
constraint forall(p in PROP) (card(attacks intersect group[p]) <= 1);
% objective
var int: totalDamages = sum(att in attacks)(damage[att]);
solve maximize (totalDamages)Run the model, we get optimal result:
Running untitled_model.mzn
100msec
attacks = {1,9};
----------
attacks = {1,10};
----------
attacks = {4,5,7,9};
----------
==========
Finished in 100msec.However, if we only are allowed to attack 3 spots, we can improve the model by simply adding one more constraint:
constraint card(attacks) = 3;Run the model again, we get optimal result:
Running untitled_model.mzn
102msec
attacks = {2,4,5};
----------
attacks = {3,7,9};
----------
attacks = {5,7,9};
----------
==========
Finished in 102msec.Bounded Cardinality Sets
Further if we are allowed to attack AT MOST 3 spots, i.e. the cardinality is bounded, it is as simple as change the constraint as below:
constraint card(attacks) <= 3;Run the model again, we get optimal result:
Running untitled_model.mzn
82msec
attacks = {1,9};
----------
attacks = {1,10};
----------
==========
Finished in 82msec.Fixed Cardinality Sets – Use Array
There are multiple ways to represent fixed cardinality sets:
- Use
var set ofobjects and cardinality constraint- Good if the solver natively supports sets
- Good when objects are not too big
- Use
array[1..u] of varobjects- Good when
uis small
- Good when
The example above showed that once we’ve known the size (cardinality) of the set, we can actually model the set differently.
var set of SPOT: attacks;
constraint card(attacks) = size;
% is remodeled to
array[1..size] of var SPOT: attacks;Why we do this? If the cardinality of set is much larger than the size of array, this can help decrease the number of variables in the model dramatically. However there is another problem, consider:
% array x has 3 elements, each is from 1 to 10
% There are 10 * 10 * 10 = 1000 possible values: [1,1,1] ... [10,10,10]
array[1..3] of var 1..10: x;
% set x actually has 10 * 9 * 8 / (3 * 2 * 1) = 120 possible values
var set of 1..10: x;
constraint card(x) = 3;The problem is there are lots of more array values (1000) than there are possible subsets (120). Some of these 1000 array values don’t represent the subsets. How to solve this problem? The first thing we need to do is ensure that all the values in this array are different, otherwise it won’t represent a set of cardinality specified.
% array x still has 10 * 9 * 8 = 720 possible values
array[1..3] of var 1..10: x;
forall(i,j in 1..3 where i < j)
(x[i] != x[j]);There are still multiple array representations for the same set, for example: {1, 6, 10} has 6 representations:
[1, 6, 10]
[1, 10, 6]
[6, 10, 1]
[6, 1, 10]
[10, 1, 6]
[10, 6, 1]Further, we need to ensure 1 of these orders appear, that is [1, 6, 10]
% array x still has 10 * 9 * 8 = 720 possible values
array[1..3] of var 1..10: x;
forall(i in 1..3-1)
(x[i] < x[i+1]);Now, putting everything together, our Bagua army problem is improved:
% data
int: nSpots = 10;
set of int: SPOT = 1..nSpots;
array[SPOT] of int: damage = [10, 8, 4, 2, 6, 9, 5, 3, 8, 10];
enum PROP = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};
array[PROP] of set of SPOT: group = [{1,4,6}, {1,2,6,7}, {1,3,6,8}, {1,2,3}, {2,9,10}, {5,6,8,10}, {7,8,10}, {1,3,5}];
% decision variables
int: size = 3;
array[1..size] of var SPOT: attacks;
% constraints
% force there is only 1 array representation for a set value
constraint forall(i in 1..size-1)(attacks[i] < attacks[i+1]);
% constraints
% for every property, we can only attack one spot associated with that property
constraint forall(p in PROP) (sum(i in 1..size)(attacks[i] in group[p]) <= 1);
% objective
var int: totalDamages = sum(att in attacks)(damage[att]);
solve maximize (totalDamages)Run the model, we get the optimal result again:
Running untitled_model.mzn
413msec
attacks = [2, 4, 5];
----------
attacks = [3, 7, 9];
----------
attacks = [5, 7, 9];
----------
==========
Finished in 413msec.Bounded Cardinality Sets – Use Array
The sets of bounded cardinality can be also implemented using array, but with extra work. The set SPOT of the array attacks itself is not enough, we need to extend the set SPOT by introducing an extra value. This extra value stands for no element, meaning the army won’t attack a spot, that is going to allow us to get a set of smaller (bounded) cardinality.
SPOTx = SPOT union {extra-value};
array[1..size] of var SPOTx: attacks;
% for instance extra-value = 0
% SPOT = 1..nSpots
% SPOTx = 0..nSpotsAfter introducing this extra-value 0, let’s recall the two critical issues when modeling decisions:
- Ensure each solution to the model is a solution of the problem
- Model solution [3, 0, 3] does not represent a problem solution, because we are not allowed to attack the same spot for twice.
- Model solution [0, 2, 0] represents a problem solution, because repeated extra-value 0s are OK.
- Try to ensure each solution of the problem only has one solution in the model
- Suppose {2} is a problem solution, it should have only one solution in the model. Multiple solutions like [0, 2, 0], [2, 0, 0], [0, 0, 2] are not allowed.
Again, we need to add constraint to fix these issues:
% now only repeats of extra-value 0s are allowed
constraint forall(i in 1..size-1)
(attacks[i] >= (attacks[i] != 0) + attacks[i+1]);
% when (attacks[i] != 0), attacks[i] >= 1+attacks[i+1];
% when (attacks[i] = 0), attacks[i] >= attacks[i+1];
% this is an combination of
% strict ordering (attacks[i] > attacks[i+1]), which does not work for repeated extra-values [2, 0, 0]
% and non-strict ordering (attacks[i] >= attacks[i+1]), which does not work for repeated spot values [3, 2, 2]The extra-value 0 in the attacks also affect the calculation of objective variable totalDamages. Because there is no element 0 in the array damage, if we try to look up damage[0], we won’t be allowed by constraints, so there can not be a 0 in the attacks array. So basically the definition of the totalDamages will force that there is no 0 in the attacks array. To fix this problem, we only want to sum up damages which are not at position 0. We add where att > 0 to the objective variable.
Finally the complete model is:
% data
int: nSpots = 10;
set of int: SPOT = 1..nSpots;
array[SPOT] of int: damage = [10, 8, 4, 2, 6, 9, 5, 3, 8, 10];
enum PROP = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};
array[PROP] of set of SPOT: group = [{1,4,6}, {1,2,6,7}, {1,3,6,8}, {1,2,3}, {2,9,10}, {5,6,8,10}, {7,8,10}, {1,3,5}];
% decision variables
int: size = 3;
set of int: SPOTx = {0} union SPOT;
array[1..size] of var SPOTx: attacks;
% constraints
% force there is only 1 array representation for a set value
constraint forall(i in 1..size-1)(attacks[i] >= (attacks[i] != 0) + attacks[i+1]);
% constraints
% for every property, we can only attack one spot associated with that property
constraint forall(p in PROP) (sum(i in 1..size)(attacks[i] in group[p]) <= 1);
% objective
var int: totalDamages = sum(att in attacks where att > 0)(damage[att]);
solve maximize (totalDamages)Run the model, we get the new optimal result:
Running untitled_model.mzn
109msec
attacks = [0, 0, 0];
----------
attacks = [1, 0, 0];
----------
attacks = [9, 1, 0];
----------
attacks = [10, 1, 0];
----------
==========
Finished in 109msec.For more on MiniZinc: Modeling with Sets, please refer to the wonderful course here https://www.coursera.org/learn/basic-modeling
Related Quick Recap
I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at https://KZHU.ai
Don't forget to sign up newsletter, don't miss any chance to learn.
Or share what you've learned with friends!
Tweet
