Due to the inherent complexity of the associated problems, investigations of the basic principles of protein folding and evolution are usually restricted to simplified protein models. Our group has developed methods and programs for exact and complete solving of problems typical for studies using HP-like 3D lattice protein models. Addressed tasks are the prediction of globally optimal and listing of suboptimal structures, sequence design, neutral network exploration, and degeneracy computation. The used methods are based on fast and non-heuristic techniques (constraint programming) instead of following stochastic approaches, which are not capable of answering many fundamental questions. Thus, we are able to find optimal structure for HP-sequences of length greater than 200, including a proof of optimality. We have used these methods to find unique folding sequences, to investigate neutral nets and to design low-degenerated sequences for given structures.