Unit commitment (UC) is one of the most important power system operation problems. To integrate higher penetration of wind power into power systems, more compressed air energy storage (CAES) plants are being built. Existing cavern models for the CAES used in power system optimization problems are not accurate, which may lead to infeasible solutions, e.g., the air pressure in the cavern is outside its operating range. In this regard, an accurate CAES model is proposed for the UC problem based on the accurate bi-linear cavern model proposed in the first paper of this two-part series. The minimum switch time between the charging and discharging processes of CAES is considered. The whole model, i.e., the UC model with an accurate CAES model, is a large-scale mixed integer bi-linear programming problem. To reduce the complexity of the whole model, three strategies are proposed to reduce the number of bi-linear terms without sacrificing accuracy. McCormick relaxation and piecewise linearization are then used to linearize the whole model. To decrease the solution time, a method to obtain an initial solution of the linearized model is proposed. A modified RTS-79 system is used to verify the effectiveness of the whole model and the solution methodology.