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?