The use of sampling methods based on Monte Carlo approaches or of global optimization methods such as evolutionary algorithms have been available for years and applied quite successfully to determine the structure of supported metal or oxide clusters. Of particular interest to characterizing the oxidation states of supported metal clusters are approaches that combine global optimization of various stoichiometries with a subsequent thermodynamic analysis, or those that directly sample structure and stoichiometries under given conditions using grand canonical approaches. The resulting phase-diagrams allow to pinpoint which states are stable under which conditions, relying on well-defined and stable structural models.