I'm trying to solve this problem in linear programming. The task is to build a model with the minimum amount of constraints and variables (it has to be run on AMPL students version, 300 variables and 300 constraints).
I got a 8x8 matrix with a probability in each cell, I have to find a 10-cell path (diagonal directions are allowed) which maximize the sum of the probabilities of the cells.
I understand that a "classical approach" to find a path into a graph will require an huge amount of variables and constraints.
I tried (with success) to make a model which have those variables
which represents the coordinates of the 10 chosen cells, in the assigned order.
But now I have no idea of how to write the objective function! Since I cannot write something like
max sum(i in 1..10) p[x[i],y[i]]