Applying retention registers is one of the most effective and efficient approaches to keep flip-flop states in power-gated circuits during the sleep mode. Instead of replacing each flip-flop in a power-gated circuit with a single-bit retention register (SBRR), recent research has shown that applying multi-bit retention registers (MBRRs) can effectively reduce the storage size, and hence save more chip area and leakage power. However, the previous work simply adopted greedy heuristics for power-gated circuit optimization with MBRRs, which first break feedback paths and then iteratively replace a flip-flop covering the maximum number of (k-1)-link paths with a k-bit retention register. Different from the previous work, this paper presents an even more effective approach based on integer-linear-programming (ILP) formulation with simultaneous consideration of all feedback paths. Experimental results show that the proposed approach can further reduce up to 46% storage size compared with the previous work.