MATLAB Answers


Cheapest path through populated matrix

Asked by Sebastian Holmqvist on 9 Jul 2012

I'm attempting to calculate an "optimal" (if possible) path through a data set matrix (position over time). Each "cell" has a cost and I also need to introduce a derivative cost (between each second/column) and preferably other general constraints/costs (i.e spanning over several seconds/columns) e.g number of max number of row changes. As I need to lookup each position in the matrix in order to calculate the total path cost I've run into problems. So far I've tried;

  • Dynamic Programming - Works good, but I'm not able to set general constraints (i.e spanning several seconds). Also, it only handles derivative costs, not constraints.
  • fmincon - Would work if it weren't for the fact that it minimizes the variables in real numbers. As I calculate my cost by matrix lookup all indexes must therefore be integer. Rounding in the object function only breaks the optimization. The alternative bintprog only handles binary :/
  • Dijkstra's algorithm - First off I need to convert my matrix to a graph (not a fix size). But even if I would sort that out I'm stuck on the fact that it doesn't handle general constraints.
  • Mixed Integer Linear Programming - Minimizes on cTx <= b where c is a vector. I am not able to extract a vector from my data set prior knowing x. Also, I think intercepting x would potentially break the LP theory.

Any bright ideas or comments?

  1 Comment

I kind of "solved it" by going with fmincon. I bypassed my earlier issue with indexing by doing interp2 lookup on my table. That way fmincon can do it's thing with real numbers, not caring about any indexing.

When it's finished, I round off the numbers to integers making them fit my application. I know that doing so might break one or more constraints, but it's something I'm aware of.

0 Answers

Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

MATLAB Academy

New to MATLAB?

Learn MATLAB today!