The robust linear constrained regulation problem for uncertain linear discrete-time systems (A,B) is investigated using the theory of positively invariant polyhedral sets. Closed and bounded polyhedral uncertain domains are considered, involving parameters of both A and B-matrices and polyhedral constraints on both state and control vectors. New sufficient conditions for the solvability of the regulation problem are presented. For computational solution of the regulation problem, a linear programming approach is proposed where the constraints are given by the solvability conditions and the performance index represents a guaranteed trade-off between the closed-loop stability margin and the level of control effort.