The advent of portable and high-density devices has made power consumption a critical design concern.In this paper, we address the problem of reducing power consumption via gate-level voltage scaling for those designs that are not under the strictest timing budget.We first use a maximum-weighted independent set formulation for voltage reduction on non-critical part of the circuit.Then, we use a minimum-weighted separator set formulation to do gate sizing and integrate the sizing procedure with a voltage scaling procedure to enhance power saving on the whole circuit.The proposed methods are evaluated using the MCNC benchmark circuits.and an average of 19.12% power reduction over the circuits having only one supply voltage has been achieved.