An important aspect of homology modeling and protein design algorithms is the correct positioning of protein side chains on a fixed backbone. Homology modeling methods are necessary to complement large scale structural genomics projects. Recently it has been shown that in automatic protein design it is of the uttermost importance to find the global solution to the side chain positioning problem [1]. If a suboptimal solution is found the difference in free energy between different sequences will be smaller than the error of the side chain positioning. Several different algorithms have been developed to solve this problem. The most successful methods use a discrete representation of the conformational space. Today, the best methods to solve this problem, are based on the dead end elimination theorem. Here we introduce an alternative method. The problem is formulated as a linear integer program. This programming problem can then be solved by efficient polynomial time methods, using linear programming relaxation. If the solution to the relaxed problem is integral it corresponds to the global minimum energy conformation (GMEC). In our experimental results, the solution to the relaxed problem has always been integral.