Optimization of a matrix with integers and constraints for a car park

Hello,

I have a question about an optimization of a matrix.

I want to simulate with the matrix A a path, which a vehicle can drive. The integers have the following meaning:

1: Start/end area

2: Road

3: parking area

0: free area

A first initial matrix would be e.g.

A=

[ 0 0 1 0 0;

3 2 2 2 3;

0 0 2 0 0;

0 0 3 0 0 ]

So a start/end area, which is connected to 3 parking areas via the roads.

Now a possible objective function would be to increase the capacity of this infrastructure (matrix). The capacities result from the parking spaces and start area

Cstart = (tw/tstart) * nstart

Cpark = (tw/tpark) * npark

Where nstart and npark are the number of respective areas and represent the variables. In this case nstart = 1 and npark = 3. The total capacity would be

Call = min (Cstart, Cpark)

The objective function would be

Maximize Call.

The boundary conditions would be

- Each start area must be connected to a street

- Each parking area must be connected to a street

- There must be at least one start surface

- There must be at least one parking space

- A starting area must not be directly next to a parking area

- There must be no dead end for the streets, means that each street must be connected to two other spaces, which are not 0 (free areas).

With the objective function and the boundary conditions a matrix should then be output, which has a maximum capacity. E.g. like this:

A =

[ 3 2 1 2 3;

3 2 2 2 3;

3 2 2 2 3;

3 2 1 2 3 ]

Now, unfortunately, I don't know how to quantify these qualitative conditions. Moreover, I also don't know how, given these conditions, to derive from the objective function and the boundary conditions to the matrix A and arrange the integers.

The question now would be is there an algorithm with which one could do something like this?

[Bruno Luong]

What is "obtimate a matrix".

Your description of the problem seems incomplete. For instant why not juts select

A = [1 1 1 1 1 1 1 1 1 1 1]?

There are many 1s and few 2s?

[b999]

The point is that the individual values in the matrix represent certain areas. This means that I want to have as many as possible of area type 1 and as few as possible of area type 2. In addition, certain areas should always lie next to each other. This does not mean that I only want to have the areas with 1, there should still be some of the other areas. The goal would be, for example, that the twos are replaced with another surface type (in this case best 1).

[Bruno Luong]

Why not replace all 2s by 1s? What exactly the "rule" that prevents to do that replacement? You have NOT explain cleatly what is the "rule".

[b999]

I apologize for the not precise description. I'll try to describe the whole problem again in more detail.

I would like to get a matrix as a target, which contains intergers, which stand for a certain surface type. For this I have thought that the user enters a matrix, which should then be optimized.

The optimization is to run in such a way that after an objective function the arrangement of the Intergers is made. In this point I do not know exactly whether the objective function must be a mathematical formulation or, for example, a formulation such as "minimize the number of cells with the value 2".

To the objective functions I have boundary conditions, which must be kept. These consist mostly of specifications which integers or cells may lie next to each other (e.g. Integer 3 must always be adjacent to Integer 4 in the matrix). For checking the boundary conditions I already have a function, which outputs 1 or 0, depending on whether the boundary condition is met by the given matrix.

Now I don't know how to implement the whole thing. Depending on whether the boundary conditions (0 or 1) must be taken as the objective function, either a multi-objective optimization results or not. I would be already grateful if I could get an approach how to implement something like this.

Your question about the rule that prevents the matrix from being filled should be done by a definition of the integers that are needed. I would like to eventually allow a selection of integers and their arrangement based on the target functions.

Since I'm new to matlab, I'm looking at what algorithm and structure is generally the best way to solve such a problem.

[Bruno Luong]

OK so you refuse to give any useful details, the best I can do is to direct you to read the doc starting with a keyword in the question

https://www.mathworks.com/help/optim/ug/multiobjective-optimization-algorithms.html

https://www.mathworks.com/help/gads/gamultiobj.html

I can't be more helpful with the such generic "question" (no description of target objective function, no description of constraints) all we know is you want the maximums of 1s and with the less 2s as much as possible, which is useless information for me.

[John D'Errico]

@a9v9

You are being too vague about the problem here, so that nobody can really give help. That usually means you have not yourself quantified what the exact requirements are in your mind. Until you manage to formulate a problem in terms of mathematics, you cannot start to write code to solve that problem.

But this does not seem to be an optimization problem, at least not yet. It is certainly not something that GA would handle as you have described it, since you want to start with a starting point, that is, an array a user would provide. Tools like GA do not use an initial point.

You also talk about GAMULTIOBJ, but you have said nothing about why this is a problem involving multiple criteria to be optimized. Again, I think either you have not really formulated what you want to do yet, or you have been far too vague in explaining the problem.

Possibly you might be wanting to view this as some sort of a perturbation process, wherein most of the array remains the same, and you want to find a minimal change in some way that satisfies some set of constraints. Viewed in that way, now GA might again be an option. But you need to decide what it is that you are minimizing.

[b999]

@John D'Errico

Okay, I see the problem. The quantification of my problem is also exactly the difficulty which I have current.

I'll try to illustrate the whole thing with a simple example:

I want to simulate with the matrix A a path, which a vehicle can drive. The integers have the following meaning:

1: Start/end area

2: Road

3: parking area

0: free area

A first initial matrix would be e.g.

A=

[ 0 0 1 0 0;

3 2 2 2 3;

0 0 2 0 0;

0 0 3 0 0 ]

So a start/end area, which is connected to 3 parking areas via the roads.

Now a possible objective function would be to increase the capacity of this infrastructure (matrix). The capacities result from the parking spaces and start area

Cstart = (tw/tstart) * nstart

Cpark = (tw/tpark) * npark

Where nstart and npark are the number of respective areas and represent the variables. In this case nstart = 1 and npark = 3. The total capacity would be

Call = min (Cstart, Cpark)

The objective function would be

Maximize Call.

The boundary conditions would be

- Each start area must be connected to a street

- Each parking area must be connected to a street

- There must be at least one start surface

- There must be at least one parking space

- A starting area must not be connected to a parking area

- There must be no dead end for the streets, means that each street must be connected to two other spaces, which are not 0 (free areas).

With the objective function and the boundary conditions a matrix should then be output, which has a maximum capacity. E.g. like this:

A =

[ 3 2 1 2 3;

3 2 2 2 3;

3 2 2 2 3;

3 2 1 2 3 ]

Now, unfortunately, I don't know how to quantify these qualitative conditions. Moreover, I also don't know how, given these conditions, to derive from the objective function and the boundary conditions to the matrix A and arrange the integers.

I hope that made the whole thing a little clearer?

The question now would be is there an algorithm with which one could do something like this?

I am sorry for my explainations. I am new to matlab and don't really know how to handle this problem...

[Sam Chak]

Hi @a9v9,

Could you please edit the question and update both the title and the contents with details about the optimization of car parks? This would be helpful because people often don't want to scroll down and read unrelated comments in order to understand the context and the technical aspects of the integer-based optimization problem.

[Bruno Luong]

"- A starting area must not be connected to a parking area"

But then the first row of A given as example

A = [3 2 1 2 3;
    ...
    ]

I see 1 (starting area) connects to 3 (parking) via 2 (road). So I don't understand your constraint

[b999]

@Bruno Luong

Yes, that is a little bit misleading.

Maybe this is a better expression:

A starting area must not be directly next to a parking area (so A = [ 3 1 ...] is not aceptable. A= [3 2 1 ...] is okay)

[Bruno Luong]

This matrix meet all your constraints and minimizes Call = min (Cstart, Cpark) = 1

A=[ 1 2 3 0 0
    0 0 0 0 0
    0 0 0 0 0
    0 0 0 0 0]

If not you have to explain me why.

[b999]

But i want to maximize Call.

So the objective function would be: max Call = min (Cstar,Cpark)

[Sam Chak]

@a9v9, I'm trying visualize the your matrix A on this parking lot map.

[b999]

@Sam Chak

I don't quite understand what you are trying to say with this picture.

My goal is first to find an algorithm that can arrange the matrix based on the boundary conditions and objective function. At the very end you can visualize this matrix.

[Sam Chak]

No worries, @a9v9, I was just trying understand your optimization problem, and associate the numbers {0, 1, 2, 3} with physical objects that I understand such as {free lot, starting location, asphalt road, occupied lot, no parking area}.

[b999]

@Sam Chak

Okay, no in this case 0 means that there ist "nothing". So an area with no function. 3 means a parking lot/area, it doens't define wherether there is a car in it or not.

I am interested in optimizing the topology with respect to the boundary conditions and target functions, not in where a car is located. I have used the example with the cars in order to make the situation more understandable.

[Sam Chak]

@a9v9. Alright I see it now, thanks for your clarification. I'm bad at algebraic topology.

[Bruno Luong]

OK maximize Call so is this pattern is valid?

A = [3 2 3 2
     0 1 0 1
     3 2 3 2
     0 1 0 1]

[Harald]

Hi,

In case you are not familiar with optimization problems in general, I recommend taking the Optimization Onramp as a first step.

As others have noted, it is difficult to understand your verbal descriptions, let alone convert them to formulas.

In particular, I don't see the multi-objective nature of this. If you want to maximize capacity (and capacity is a scalar), this is a single objective.

As a first step, I suppose the dimensions of the matrix are fixed and you "only" want to rearrange the numbers within the matrix?

Best wishes,

Harald

[b999]

@Bruno Luong

Yes, with the given boundary conditions this should be valid.

One could consider that the starting surfaces (1) may only lie at the edge of the matrix A (n x m), i.e. at n=1 or n=4 or m = 1 or m = 5, in order to ensure accessibility. But the addition of boundary conditions should still be possible in the implementation.

@Bruno Luong did you rearrange it using an algorithm or was it just a general question?

[b999]

Hi @Harald,

yes, you are right. The dimension of the matrix should first be taken as given. The integers should then be arranged according to the objective function and the boundary conditions.

And yes, you are right. With only the objective function of the capacity it would not be a multiobjective optimization. Perhaps in a further step several objective functions with weighting could be considered. But not necessarily relevant for the first step.

I agree that understanding the problem would be easier with mathematical formulations. I just don't know how to formulate the problem matahmatically, unfortunately. Therefore, among other things, the question here in the forum :)

[Bruno Luong]

If you want to solve with numerical method (seem not smart to me, since I thinh this problem can be solve with a repeat pattern) then just consider you matrix as a long vector with integer 0, ..., 3. Then program the constraints even if you have difficulty to express in math formulation (afterall an algorithm can defined in place of the formula) then use GA to solve it. It will be messy to program what is the path in 2D. You can use tools such as graph class to assist you for verification of various constraints.

[Bruno Luong]

"did you rearrange it using an algorithm or was it just a general question?"

No this pattern is sipmply from just deduction.

[b999]

@Bruno Luong

I first thought of the numerical algorithms from what I read on the internet. But in principle I am open-minded about the solution of the problem.

Could you briefly explain the procedure with the "repeat pattern"? That would be very nice. I have never heard of it. Is there also some kind of toolbox in Matlab for this?

[Harald]

@Bruno Luong: the problem-based approach allows for direct optimization of matrices. I find this quite helpful.

@a9v9: the least you would need is a function that returns the number of constraint violations for any input matrix. It could then be an option to use that as penalty term for the objective function rather than as an actual constraint, i.e.

max (capacity - c*[# of violations]) with a sufficiently large number c.

Depending on the size of the matrix, it could be an alternative to try all combinations in a loop. Perhaps, this is what Bruno refers to as the repeat pattern. It will of course help if you can rule out a large number of combinations to begin with.

If you combine several objectives with weights, it is still considered a single objective.

[Bruno Luong]

When I wrote "repeat pattern"I mean just repeat the 2 x 2 pattern block

[3 2;
 0 1]

ans = 2×2

3 2 0 1

as I give as example for A of size( m x n) m = 4 n=4.

If m or n is odd, then truncate the last row/column then replace 1 with 3 or vice versa so that the number of 1 == number of 3.

It seems to me this simple "repeat pattern" returns the optimal solution. I don't see the need of using optimization tool for the problem stated here. But if the problem statement is different and more compliated then optimization might need to sove it.

Try with 10 x 10, I bet that the optimization would not find solution in reasonable time.

I'm curious to see if any optimization formulation can lead to finding reliable solution, and eventually beat my repeat pattern solution (or not).

m = 11;
n = 11;

A = repmat([3 2; 0 1], ceil(m/2), ceil(n/2));
A = A(1:m, 1:n);

d=floor((nnz(A==3)-nnz(A==1))/2);
i = find(A==3 & ((1:m)'==m | (1:n)==n));
A(i(1:d)) = 1

A = 11×11

3 2 3 2 3 2 3 2 3 2 3 0 1 0 1 0 1 0 1 0 1 0 3 2 3 2 3 2 3 2 3 2 3 0 1 0 1 0 1 0 1 0 1 0 3 2 3 2 3 2 3 2 3 2 3 0 1 0 1 0 1 0 1 0 1 0 3 2 3 2 3 2 3 2 3 2 3 0 1 0 1 0 1 0 1 0 1 0 3 2 3 2 3 2 3 2 3 2 3 0 1 0 1 0 1 0 1 0 1 0

nusefulplace = min(nnz(A==3),nnz(A==1))

nusefulplace = 30

Answer 1

[Bruno Luong]

Here is formalization with intlinprog (solver base)

m = 4;
n = 5;

% Bruno repeat pattern solution
A0 = repmat([3 2; 0 1], ceil(m/2), ceil(n/2));
A0 = A0(1:m, 1:n);
d=floor((nnz(A0==3)-nnz(A0==1))/2);
i = find(A0==3 & ((1:m)'==m | (1:n)==n));
A0(i(1:d)) = 1;
b0 = A0 == reshape(0:3,1,1,4);
b0 = double(b0(:));
efficientcy0 = min([nnz(A0==3) nnz(A0==1)])

efficientcy0 = 5

% Maximize the umber of 1 and 3
z = zeros(m,n,4);
f = z; f(:,:,[2 4]) = -1;

N = numel(f);
Aeq = [];
beq = [];
lb = zeros(N,1);
ub = 1+zeros(N,1);
A1 = z; A1(:,:,2) = -1; b1 = -1;
A3 = z; A3(:,:,4) = -1; b3 = -1;
A = [A1(:)'; A3(:)'];
b = [b1; b3];
for i=1:m
    for j=1:n
        % There is exactly one ID by position
        k = sub2ind([m n 4], i+zeros(1,4), j+zeros(1,4), 1:4);
        Ak = accumarray(k(:), 1, [N,1]);
        Aeq(end+1,:) = Ak;
        beq(end+1) = 1;

        % 4-connected neighbor
        in = [i-1, i+1, i,    i];
        jn = [j,   j,   j-1, j+1];
        keep = in>=1 & in<=m & jn>=1 & jn<=n;
        in = in(keep);
        jn = jn(keep);

        % 1 must be connected to 2
        k = sub2ind([m n 4], i, j, 2);
        kn = sub2ind([m n 4], in, jn, 3+zeros(size(in)));
        Ak = -accumarray(kn(:), 1, [N,1]) + accumarray(k(:), 1, [N,1]);
        A(end+1,:) = Ak;
        b(end+1) = 0;

        % 3 must be connected to 2
        k = sub2ind([m n 4], i, j, 4);
        kn = sub2ind([m n 4], in, jn, 3+zeros(size(in)));
        Ak = -accumarray(kn(:), 1, [N,1]) + accumarray(k(:), 1, [N,1]);
        A(end+1,:) = Ak;
        b(end+1) = 0;

        % 2 must be connected to 1, 2, or 3
        k = sub2ind([m n 4], i, j, 3);
        kn1 = sub2ind([m n 4], in, jn, 2+zeros(size(in)));
        kn2 = sub2ind([m n 4], in, jn, 3+zeros(size(in)));
        kn3 = sub2ind([m n 4], in, jn, 4+zeros(size(in)));
        kn = [kn1, kn2, kn3];
        Ak = -accumarray(kn(:), 1, [N,1]) + accumarray(k(:), 1, [N,1]);
        A(end+1,:) = Ak;
        b(end+1) = 0;

        % 1 must not be connected to 3
        k = sub2ind([m n 4], i, j, 2);
        for l=1:length(in)
            kn = sub2ind([m n 4], in(l), jn(l), 4);
            Ak = accumarray(kn(:), 1, [N,1]) + accumarray(k(:), 1, [N,1]);
            A(end+1,:) = Ak;
            b(end+1) = 1;
        end
    end
end
% Balance between 1 and 3
Ak = repmat(reshape([0 1 0 -1],1,1,4),m,n,1);
A(end+1,:) = +Ak(:); b(end+1) = 1;
A(end+1,:) = -Ak(:); b(end+1) = 1;

bin = intlinprog(f, 1:N, A, b(:), Aeq, beq(:), lb, ub, b0);

LP:                Optimal objective value is -17.055556.                                           

Cut Generation:    Applied 6 Gomory cuts,                                                           
                   and 8 zero-half cuts.                                                            
                   Lower bound is -15.000000.                                                       
                   Relative gap is 45.45%.                                                         

Heuristics:        Found 2 solutions using diving.                                                  
                   Upper bound is -13.000000.                                                       
                   Relative gap is 14.29%.                                                         

Cut Generation:    Applied 2 strong CG cuts,                                                        
                   and 12 zero-half cuts.                                                           
                   Lower bound is -14.000000.                                                       
                   Relative gap is 7.14%.                                                          

Branch and Bound:

   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
      29      0.18         3  -1.300000e+01   0.000000e+00                                          

Optimal solution found.

Intlinprog stopped because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0. The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05.

bin = reshape(round(bin), [m,n,4]);
A = sum(bin.*reshape(0:3,1,1,4),3)

A = 4×5

2 3 3 2 3 3 3 2 1 2 3 2 1 1 1 3 2 1 2 1

efficientcy = min([nnz(A==3) nnz(A==1)])

efficientcy = 6

[b999]

@Bruno Luong Thanks for helping me. I will check the code and try to understand it. Due to my knowledge in optimization and matlab it could take some time...i am not familiar with many operations you use in this code.

Is it possible in general to add some more integers to the Matrix, e.g. that you have 0,1,2,3,4,5,6? Or do you have to rewrite the whole code in this case?

One small question at first: why aren't you defining A2 in this part?

A1 = z; A1(:,:,2) = -1; b1 = -1;
A3 = z; A3(:,:,4) = -1; b3 = -1;
A = [A1(:)'; A3(:)'];

[Bruno Luong]

Because your constraints include these

• There must be at least one start surface
• There must be at least one parking space

But you do not tell "There must be at least one road"