Bandwidth and Separator Problems are in general NP-complete. A natural mathematical formulation of these problems leads to quadratic problems in binary variables. This leads naturally to SDP relaxations, and also to eigenvalue based relaxations. We consider relaxations based on eigenvalues. These are improved by redistributing the edge weights, leading to eigenvalue optimization problems. We present some preliminary computational results which indicate that this approach is feasible also for large scale problems.