Matrix wrapper

[jcoupey]

Currently the input class contains all the data to model the problem (jobs, vehicles) and is responsible for computing and storing the matrix.

Yet, a copy of the matrix is made at

vroom/src/problems/tsp/tsp.cpp

Line 17 in 9c138af

_matrix(_input._matrix), // TODO avoid this copy!

for a tsp instance. This copy is currently mandatory as we don't want to mess the original and as the matrix is modified to handle the forced start and end cases. This comes at a cost on performance and memory requirements, especially for big instances.

We should avoid this copy while still allowing the tsp class to use a customized version of the matrix, and several different adaptations should be possible (think creating several tsp instances to solve sub-problems with different start/end, without copying or modifying the initial matrix).

There is probably a good way to do this by designing a wrapper around the current matrix structure. It could hold a reference to the one and only initial matrix and return its values except when start/end adjustments related to a vehicle are to be made.

[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.