Minimizing the power dissipation in scan-based testing is an im portant problem. We provide for the first time an optimal formulation for the problem of simultaneously compacting, ordering, and X-filling a set of test patterns such that the fault coverage is maintained but the (overall or peak) power dissipation is minimized. We model the problem as a sequence of Pseudo-Boolean optimization problems. We give a scalable implementation of the optimization problem based on window-based local search. In contrast to the traditional technique of sequentially optimizing for compaction, ordering, and X-filling, we experimentally demonstrate that our simultaneous optimization can reduce power dissipation by 47% on a set of benchmark circuits.