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](http://theory.stanford.edu/~megiddo/pdf/rational.pdf) had published a paper on that subject already in 1979.  

If the question is considered pointless now, please vote to close.



Unconstrained Rational Combinatorial Optimization
The 1979 publication [Combinatorial Optimization with Rational Objective Functions](http://theory.stanford.edu/~megiddo/pdf/rational.pdf) of Nimrod Megiddo answers my question sufficiently well.


