We suggest the Distributed Branch and Bound Algorithm intended for solving problems with exponential complexity e.g. coalition planning. This technique consists of three parts: the state space distribution, effective search algorithm and partial solution expansion. We will describe CPlanT - an OOTW (operations other than war) coalition planning multi-agent system where this approach has been exploited.