Applying distributed constraint optimization problem (DCOP) solution techniques to domains such as service-oriented agent networks can violate key limiting assumptions behind standard DCOP formulations. We extend the multi-constrained (MC-) DCOP to model problems where each agent controls multiple variables, calling this multi-variable (MV-) MC-DCOP. The MV-MC-DCOP formulation abstracts away some problem details including those about task ordering, so we have developed an ordered variation O-MV-MC-DCOP. We empirically show that the [O-]MV-MC-DCOP approach can fruitfully prune the space of joint policies that service-oriented agents would otherwise explore.