A model of a rigid-plastic rate-independent polycrystalline aggregate wherein sub-aggregates are represented as the nodes of a binary tree is proposed. The lowest nodes of the binary tree represent grains. Higher binary tree nodes represent increasingly larger sub-aggregates of grains, culminating with the root of the tree, which represents the entire polycrystalline aggregate. Planar interfaces are assumed to separate the sub-aggregates represented by nodes in the binary tree. Equivalence between the governing equations of the model and a standard linear program is established. The objective function of the linear program is given by the plastic power associated with polycrystal deformation and the linear constraints are given by compatibility requirements between the sub-aggregates represented by sibling nodes in the binary tree. The deviatoric part of the Cauchy stress in each sub-aggregate is deduced as linear combinations of the Lagrange multipliers associated with the constraints. It is shown that the present model allows a generalization of Taylor's principle to polycrystals. The proposed model is applied to simulate tensile, compressive, torsional, and plane-strain deformation of copper polycrystals. The predicted macroscopic response is in good agreement with published experimental data. The effect of the initial distribution of the planar interfaces separating the sub-aggregates represented by the binary tree on the predicted mechanical response in tension, compression and torsion is studied. Also, the role of constraints relaxation in simulations of plane strain compression is investigated in detail. © 2009 Elsevier Ltd. All rights reserved.