Cheapest path through populated matrix

1 view (last 30 days)
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
Sebastian Holmqvist
Sebastian Holmqvist on 10 Jul 2012
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.

Sign in to comment.

Answers (0)

Categories

Find more on Get Started with Optimization Toolbox in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!