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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .