# Maximizing value of nodes visited in fixed time

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?

• Search for “orienteering problem” and “prize-collecting traveling salesman problem” Jul 31 at 16:50
• 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.?
– prubin
Jul 31 at 18:02
• @prubin Apologies, that was a typo, which I've corrected. Jul 31 at 18:38