Matrix wrapper

[vroom-project]

Matrix wrapper

[PattyDePuh]

Maybe just a hash will do inside the matrix-wrapper class:

• hash-function made out of the combination of the column and row, that should be altered.
• for retriving: checking if combination "number-row/number-column" exist in hash,
  => then take the edited value,
  => else take the value from the original matrix.

At least thats, what has been on my mind for quite some time ...

[jcoupey]

Thanks for the input, I guess choosing the way to do it will mostly come down to efficiency. Maybe a simpler filtering might also be sufficient as we "only" want zeros on whole line/columns (https://github.com/VROOM-Project/vroom/blob/master/src/problems/tsp/tsp.cpp#L32-L49).

[PattyDePuh]

If it is only about the zeroes in the diagonal, then yes thats easy to achive: Simply look, if column equal row.
But there were also some other alterations made in the matrix to force the solver to determined start-endpoints. Thats why I was there maybe thinking to general, that it should be able to "overwrite" any value from the Matrix inside the wrapper.

[jcoupey]

Now this comes down to not creating a new matrix using get_sub_matrix at

vroom/src/problems/tsp/tsp.cpp

Line 19 in 897ba57

_matrix(_input._matrix.get_sub_matrix(_tsp_index_to_global)),

Costs could be retrieved from the original matrix without a copy by using the indexes matching in _tsp_index_to_global to add a level of indirection.

Potential concern: I wonder what would be the impact of accessing the original matrix from different threads solving TSP sub-problems in parallel.

[PattyDePuh]

Since the algorithm do not care how the matrix is accessed in the background, i come up with the idea to make matrix a virtual class, which got only the virtual methods size() and operator[] for the access.
The original matrix class becomes the content_matrix and inherits from matrix.
The sub_matrix_wrapper inherits from matrix also, and gets the address to the rows/entries of a content_matrix.

The content_matrix then can create those wrappers with the get_sub_matrix() method.

I'm currently implementing the described structure on this branch.

[jcoupey]

@PattyDePuh Using get_sub_matrix to populate the content will leave the same amount of copying around.

I was thinking of just having an object holding a const ref to the original matrix and the list of indices for the sub-problem, as transmitted in the tsp constructor here:

vroom/src/problems/tsp/tsp.cpp

Lines 18 to 19 in 87c3091

	_tsp_index_to_global(std::move(problem_indices)),
	_matrix(_input._matrix.get_sub_matrix(_tsp_index_to_global)),

Then wrapper[i][j] would just return original_matrix[indices[i]][indices[j]].

On second though this would not be enough to cover the matrix modifications in the workaround for fixed start/end.

After all, I actually wonder if this is worth the trouble for now as it would only impact the TSP code. And we are far from hitting memory/computing times bounds right now, even with big instances.

[PattyDePuh]

The wrapper solution could be implemented easily, if we would abonden the idea to access the matrix with double operator[] and instead using a normal 'two arguments between parantheses' call:
wrapper::get(i,j)
Your concern about the modification: Here we could also have a variety of wrappers, which all inherit from the basic wrapper and alter the output according to the demand.
And i think they will become useful in the future.
Right after we decided which attribute of the verhicle routing problem we are going to handle next.

[jcoupey]

Now that the object model is in place, job and vehicle descriptions hold all relevant information to remove the need for hacky workarounds when handling other variants.
The TSP code situation is a bit special as it was written in the first place, therefore not using the current model, but only relying on a matrix for problem description.

[jcoupey]

Closing here as I don't think this is worth the trouble for now, especially in the light of the recent code changes introduced by the CVRP approach.