Consider the following three problems. The first is intended to be a simplification of the second that might be amenable to solution methods the second is not amenable to.

First problem: Assume we have an undirected graph, each vertex of which has a payout associated with visiting it (e.g. five dollars). Each edge has an associated travel duration (e.g. fifteen minutes). Given a time limit (e.g. eight hours), find the route that takes less than this time limit to traverse that maximizes the payout.

Second problem: In this variant, the payout is not a scalar in dollars, but a vector of apples, oranges, and plums. Instead of a single payout value associated with each vertex, there are multiple payouts (e.g. visiting a certain vertex comes with a payout of one apple, two oranges, and a plum). Which route, under the time limit, maximizes the number of fruit paid out in the smallest component (e.g. {two apples, two oranges, one plum} is preferable to {one apple, two oranges, zero plums}) (EDITED to correct earlier mistake pointed out by prubin).

Third problem: The same as the second problem, but instead of looking for a single optimal solution, we are looking for a description of the non-dominated set. So if one path gets {one apple, two oranges, one plum} and another gets {two apples, one orange, one plum}, both are returned because neither is better in all dimensions.

Can all three problems be formulated as mixed integer linear programs? Are any in a named class of optimization problems? Are there known optimal algorithms for these problems?

  • 2
    $\begingroup$ Search for “orienteering problem” and “prize-collecting traveling salesman problem” $\endgroup$
    – RobPratt
    Jul 31 at 16:50
  • $\begingroup$ If your second problem maximizes the smallest component in the payout vector, wouldn't (2, 2, 1) and (1, 2, 1) be tied (both have minimum component value 1)? Are you implying a tie-breaking method based on second smallest, then third smallest, etc.? $\endgroup$
    – prubin
    Jul 31 at 18:02
  • $\begingroup$ @prubin Apologies, that was a typo, which I've corrected. $\endgroup$ Jul 31 at 18:38


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.