Phase 1 - Relaxation Sample Clauses

Phase 1 - Relaxation. (RL) ∈ The idea of the first phase consists in relaxing the duration of the contracts to a single period, that is, in assuming that He = 1 for all e E. Another way of looking at this relaxation is as follows. n=0 Replace each occurrence of the expression ΣHe−1 αt−n in the formulation (1)-(12) by a single binary variable βt, and add the constraints H −1e e e Σ αt−n = βt n=0 ∀ e ∈ E, t ∈ T. (18) e This obviously yields an equivalent formulation of MDPC, with the interpretation that βt = 1 if e and only if a contract with carrier e is in effect in period t. Now, remove all constraints (18). In this way, we obtain a relaxation of MDPC where the variables βt are not necessarily associated with contracts of duration He, but can be viewed as describing contracts of duration 1. Let us denote this relaxed problem as RL, and its optimal value as ZRL. Clearly, ZRL is a valid lower bound for MDPC: ZRL ≤ Zopt. Σ The formulation RL can be decomposed and solved independently for each period t ∈ T . Let RL(t) define the single-period problem at period t and let ZRL(t) be its optimal value. Then, ZRL = t∈T ZRL(t). In order to avoid confusion, we stress that each sub-problem RL(t) involves the binary decision vari- x xxxxx βt in its formulation. Thus, it differs from the single-period sub-problem SP (αˆt ) introduced e in Section 6.2.2, which is associated with fixed values of the variables αt . On the other hand, if βˆt denotes the optimal value of βt in the solution of RL(t), then, by definition, ZSP (βˆt) = ZRL(t). Algorithm 3: Relax-and-repair Heuristic: Phase 1 Input: An instance of MDPC.