Novel and efficient linear formulations are developed for the problem of simultaneously performing an optimal synthesis of chromatographic protein purification processes, and the concomitant selection of peptide purification tags, that result in a maximal process improvement. To this end, two formulations are developed for the solution of this problem: (1) a model that minimizes both the number of chromatographic steps in the final purification process flow sheet and the composition of the tag, by use of weighted objectives, while satisfying minimal purity requirements for the final product; and (2) a model that attempts to find the maximal attainable purity under constraints on the maximum number of separation techniques and tag size. Both models are linearized using a previously developed strategy for obtaining optimal piecewise linear approximations of nonlinear functions. Proposed are models to two case studies based on protein mixtures with different numbers of proteins. Results show that the models are capable of solving to optimality all the implemented cases with computational time requirements of under I s, on average. The results obtained are further compared with previous nonlinear and linear models attempting to solve the same problem, and, thus, show that the approach represents significant gains in robustness and efficiency. (C) 2009 American Institute of Chemical Engineers AIChE J, 55: 2303-2317, 2009