Linear programming: path in a grid

Linear spaces and subspaces, linear transformations, bases, etc.

Linear programming: path in a grid

Postby francesco.paduano on Mon Jun 30, 2014 2:52 pm

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!
francesco.paduano
 
Posts: 1
Joined: Mon Jun 30, 2014 2:42 pm

Sponsor

Sponsor
 

Return to Matrix (Linear) Algebra

cron