Is it possible to include an optimization algorithm's own running time in the cost?
Analyzing algorithms on real word machines is complicated but there has been some work done in this area in terms of how an algorithm behaves based on access to memory hierarchy. External Memory or memory hierarchy access based analysis are much more useful in understanding how an algorithm grows for large data-sets and in modern machines on most problems external memory access is the one which creates most latency AFAIK. You should check out work done on Cache Oblivious algorithms and algorithms for External Memory for understanding the run time cost of your problem.

I am not aware of work done on CPU cycles but someone who knows about this can pitch in.