1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

The 1979 publication Combinatorial Optimization with Rational Objective Functions of Nimrod Megiddo answers my question sufficiently well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.