The problem of stabilizing a linear discrete-time system with control constraints is considered. Necessary and sufficient conditions are given for the existence of a state feedback controller which drives the state to the origin asymptotically from every initial state in an assigned compact polyhedral set. These conditions can be checked via linear programming. It is shown that when the problem has a solution, a polyhedral function can be formed which turns out to be a Lyapunov function if a proper nonlinear feedback controller is applied. Two procedures are presented for the construction of the Lyapunov function. The first is based on the property that the stabilizing feedback compensator exists if and only if for every initial condition chosen on a vertex of the set there exists an open-loop control driving the state to its interior. The second procedure is based on the construction of the controllability regions to the given polyhedral set; this procedure can also be applied to systems with parameter uncertainties. The resulting compensator is obtained by solving on-line an optimization problem which can be efficiently implemented on a digital computer.