To solve an NP-hard optimization problem optimally, we can use mathematical programming or brute force techniques. I would like to know if it is possible to solve the problem in an online fashion optimally? Is there any mathematical tool that can perform this task? I can design an online algorithm to solve the problem but I cannot say it gives the best possible online solution. However, with brute force methods, I can guarantee for sure that the solution produced is the best possible offline solution.
This question comes to my head when trying to compare my online algorithm to something; an online optimal algorithm, to see how well my online algorithm is performing. In the offline case, it is easy for me to compare. Once I have my offline algorithm, I implement a brute force or a mathematical program and I do the comparison. How to do the comparison for the online case?
EDIT: An online algorithm should make decisions in an irrevocable way.