Good morning!

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

x[10] integers

y[10] integers

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]]

any suggestion?

Thank you!