  We consider an extension of the rollout algorithm that applies to constrained
deterministic dynamic programming, including challenging combinatorial
optimization problems. The algorithm relies on a suboptimal policy, called base
heuristic. Under suitable assumptions, we show that if the base heuristic
produces a feasible solution, the rollout algorithm has a cost improvement
property: it produces a feasible solution, whose cost is no worse than the base
heuristic's cost.
  We then focus on multiagent problems, where the control at each stage
consists of multiple components (one per agent), which are coupled either
through the cost function or the constraints or both. We show that the cost
improvement property is maintained with an alternative implementation that has
greatly reduced computational requirements, and makes possible the use of
rollout in problems with many agents. We demonstrate this alternative algorithm
by applying it to layered graph problems that involve both a spatial and a
temporal structure. We consider in some detail a prominent example of such
problems: multidimensional assignment, where we use the auction algorithm for
2-dimensional assignment as a base heuristic. This auction algorithm is
particularly well-suited for our context, because through the use of prices, it
can advantageously use the solution of an assignment problem as a starting
point for solving other related assignment problems, and this can greatly speed
up the execution of the rollout algorithm.
