When thinking up a new TSP heuristic, I encountered the following rational combinatorial optimization problem: $$\min_{\alpha \in \lbrace0,1\rbrace^n}\frac{\alpha^T w}{\alpha^T m},\quad w \in \mathbb{R}^n, \ m\in\mathbb{N}^n,\ \|\alpha\|\ne 0 $$ and must admit, that I don't have any good idea of how to go about solving it to optimality besides using brute force; I am not even sure, how a branch-and-bound method would have to be formulated.
Questions:
- can the above problem be converted to a non-rational one, from which the optimal solution to the original problem can be efficiently (i.e. in polynomial time) be reconstructed?
- what algorithms can be recommended for practical problems, where good solutions are sufficient?
Edit:
I just saw, that Nimrod Megiddo had published a paper on that subject already in 1979.
If the question is considered pointless now, please vote to close.
