Standard Monte Carlo cluster algorithms have proven to be very effecti
ve for many different spin models. However, they fail for frustrated s
pin systems. Recently, a generalized cluster algorithm was introduced
that works extremely well for the fully frustrated Ising model on a sq
uare lattice by placing bonds between sites based on information from
plaquettes rather than links of the lattice. Here we study some proper
ties of this algorithm and some variants of it. We introduce a practic
al methodology for constructing a generalized cluster algorithm for a
given spin model, and apply this method to some other frustrated Ising
models. We find that such algorithms work well for simple fully frust
rated Ising models in two dimensions, but appear to work poorly or not
at all for more complex models such as spin glasses.