Structure-based computational protein design (CPD) plays a critical role in advancing the field of protein engineering and accelerating the delivery of fine-tuned proteins displaying high specificity, efficiency and stability. Using an energy function and a reliable search method, CPD tries to identify amino acid sequences that fold into a target structure and ultimately perform a desired function. Because of the vastness of the search space and the intractable combination of many degrees of freedom , the most usual CPD approaches consider a single rigid protein backbone, and usually ignore protein flexibility. This traditional Single State Protein Design (SSD) contrasts with the increasing evidence that proteins do not remain fixed in a unique conformational state but rather sample conformational ensembles. Large-scale protein motions ranging from local flexibility to large conformational rearrangements may play key roles on protein properties and functions. By exploiting and extending our efficient AI-based CPD methods [1-4], we developed innovative MultiState Design (MSD) methods aiming to alleviate SSD limitation by considering several conformational states simultaneously [5]. These methods seek to identify a sequence that optimizes a function of its optimal energies on the different considered states. We introduce efficient reductions of positive MSD problems to Cost Function Networks with two different fitness definitions and implement them in the POMPd (Positive Multistate Protein design) software. POMPd is able to identify guaranteed optimal sequences of positive multistate full protein redesign problems and exhaustively enumerate sub-optimal sequences close to the MSD optimum which is convenient for sequence library design. On various positive MSD problems we show that it is possible to identify an optimal MSD sequence and observe that the average energy fitness provides the best sequence recovery. Our method outperforms state-of-the-art guaranteed computational design approaches by several orders of magnitudes and can solve MSD problems with sizes previously unreachable with guaranteed algorithms. [1-4] Viricel et al. 2018 Bioinformatics ; Traoré et al. 2016 J Comput Chem. ; Simoncini, et al. 2015 J Chem Theory Comput. ; Traore et al. 2013 Bioinformatics. [5] Vucinic et al. Bioinformatics, submitted