Get dynamic submatrix and apply constraints

Question

I am really new to Constraint Programming and I am trying to solve a problem where from a two dimensional array, consisting of numbers, I need to take the least amount of sub arrays (2D) as possible, covering as much of the original 2D array as possible, obeying the following rules:

• Every sub array must be a rectangle part of the original
• The sum of numbers in each sub array must not exceed a specific number
• Every sub array must have at least 2 numbers in it

For example for the following matrix:

3 5 1 4
5 1 2 8
0 8 1 3
8 3 2 1

For a maximum sum of 10, a solution would be:

 3 -not picked 
{ 5 1 4 }
{ 5 1 }
{ 2 8 }
{ 0 8 }
{ 1 3 
  2 1 }
 8 -not picked

Right now I am using the diffn() equivalent of or-tools (MakeNonOverlappingBoxesConstraint()) to create the rectangles that are gonna cover the original array.

My problem is how to get the rectangles created by diffn() and split the original matrix based on the position and size of each one, so I can apply the Sum constraint.

If there is another way of achieving the same constraints without using the diffn() then I would try it out, but I can't think any other way.

Thank you!

Answer 1

The way to get a value from an array based on an IntVar, inside the solver, is by using the MakeElement() function and in this case the 2d version of it.

That way you can get a specific value from the matrix but not a range based on two IntVars (for example x - dx of rectangles). To accomplish the range part you can use a loop and a ConditionalExpression() to figure out if the specified value is in range.

For example in a 1d array, in order to get elements from data, positions x to x + dx would be as follows

int[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
IntVar x = solver.MakeIntVar(0, data.Length - 1);
IntVar dx = solver.MakeIntVar(1, data.Length);

solver.Add(x + dx <= data.Length);

IntVarVector range = new IntVarVector();
for (int i = 0; i < dx.Max(); i++)
{
    range.Add(solver.MakeConditionalExpression((x + i < x + dx).Var() , solver.MakeElement(data, (x + i).Var()), 0).Var());
}

solver.Add(range.ToArray().Sum() <= 10);

In Case of the 2d array (as in the question) then you just iterate through both dimensions. The only difference is that the 2d version of MakeElement() accepts an IndexEvaluator2 item (LongLongToLong in C#) so you have to make your own class that inherits LongLongToLong and override the Run() function.

class DataValues: LongLongToLong
{
    private int[,] _data;
    private int _rows;
    private int _cols;

    public DataValues(int[,] data, int rows, int cols)
    {
        _rows = rows;
        _cols = cols;
        _data = data;
    }

    public override long Run(long arg0, long arg1)
    {
        if (arg0 >= _rows || arg1 >= _cols)
            return 0;

        return _data[arg0, arg1];
    }
}

The only problem with this class is that it can ask for a value off the array, so we must handle it ourselves with if (arg0 >= _rows || arg1 >= _cols).

P.S. I dont know if this is the best method of accomplishing it, but it was the best I could think of, since I couldn't find anything similar online.