T is the number of time periods in the scheduling horizon System Parameters Rt is the system reserve requirement in time period t Bidder da M is the number of bidders participating in the CPP i=1,2,... M is the bidder inde Unit variables if the unit if the unit is shut do is the status of unit i in time period t is the real Ti, t is the reserve provided by unit i in time period t Ti, t is the downtime of unit i at the end of time period t an operating schedule for unit i and 2=u, p,r)is sche The CEMP is the determination of the opt system schedule >=yp, pop rop) that minimizes 如m +)A2D CEM cost. We denote by subject to n)4{∑∑=色里 satisfiesequation()4) ,Er}(a)=1,2,…M the set of feasible operating schedules for unit We can rewrite the Lagrangian relaxation as re function in equation (1)is the sum of th variable and the start-up prices. For each unit i, the CEM ost when unit i demand Pi, t in period t is given by bA (pi, t ) ui, t. CEM start-up costs arise if unit i is shut down in 1>∑()+(x)1--) time period t-1 and is operating in period t, i.e., if ui, t-1=0 and ui, t= 1. The downtime when started up is the downtime AePi t -uri, Jui +2d+FR as the length of the time period we express r, t recursively in subject to erms of ui, t, t= l,,T and Ti,o ;2r;eg)v=1,2,…M Ti, t=(Ti,t-1+Ar)(1-ui,t)Ti,o is given. (5) Here we removed the constant terms aD and AR from the The objective function is nonconvex. The state space minimand. The Lagrangian function complex minimum up and down time constraints and is 叭(AED,B)min ∑!(p:) is 78 half hour periods and the number of units can exceed 200, this is a large scale and complex nonlinear optimization +b(r-1)(1-wt-1)w+2D+出2 problem. in the solution of the CEMP may be effectively exploited. This approach leads ,2r}(g) the decomposition of the problem in terms of each bid- is separable in terms of bidders as there is no inter-unit er and results in the economic interpretation of the Lagrange pling in the constraints. This allows us to decompose the multipliers as prices. The Lagrangian relaxation technique in- problem into M subproblems. The subproblem for bidder i volves the construction and solution of modified problem in hich the system-wide constraints on demand and reserve con straints, which couple all bidders, are used to augment primal objective function with their associated Lagrange mul- p(,E) tipliers. The new problem does not enforce the demand and s:1>p+ reserve constraints and is therefore "relaxed ". All bidder con- traints,however, are enforced AePi, t -Her Jui,t:u,P,rJeni (a )J We define the T-dimensional vectors A=(A1, A2,,Ar]T r. Here A: and 420 are the La For given A and A, the M subproblems can be independ (o), for the demand and reserve constraints in time period t, of the CPP dispatcher problem can be solved efficiently for multipliers, which are non-negative for inequality constraint Ived in an efficient manner. Hence the Lagr particular values of A and u, giving the value (,E D, an be shown that the Lagrangian function中(Δ丛; B ∑∑)+(+---) P(DB)≥虮A;DR) 311