# Research on Cloud Task Scheduling Algorithm with Conflict Constraints Based on Branch-and-Price
## 4 Model Decomposition  
Since the above problem is a generalization of the classical bin packing problem and graph coloring problem, its solution is quite difficult: when the conflict graph is an empty set, the problem can be transformed into a classic multidimensional bin packing problem,and when the capacity of each type of resource in each VM is zero, the problem can be transformed into a graph coloring problem. Both the bin packing problem and the graph coloring problem have been proven to be NP-hard problems [22]. The time complexity of solving such problems increases as the size of the problem increases. Therefore, this paper first relaxes the tightly coupled constraint condition (3) of the original model based on the Lagrange relaxation principle [23] to obtain the Lagrange relaxation problem of the original problem. Second, we decompose the relaxation problem based on the Dantzig-Wolfe decomposition principle [24]. Thus, we can obtain a main problem with a relatively simple structure and a multidimensional bin packing subproblem with conflict constraints. We introduce a Lagrange multiplier \(\mu=(\mu_{1},\mu_{2},\ldots,\mu_{n})\) to perform Lagrange relaxation on the constraint condition (3). \(z(\mu)\) is the optimal solution of the relaxation problem, and the model of the Lagrangian relaxation problem is as follows:  
\[z(\mu)=\min \sum\limits_{i\in\mathcal{M}}y_{i}-\sum\limits_{i\in\mathcal{M}} \sum\limits_{j\in\mathcal{J}}\mu_{j}\cdot x_{ij}+\sum\limits_{j\in\mathcal{J} }\mu_{j}\] s.t. \[: (2),(4),(5)\]  
The problem can be decomposed into \(m\) identical multidimensional bin packing problems with conflict constraints, that is, \(z=m:z_{i}(\mu)+\sum_{j\in\mathcal{J}}\mu_{j}\), which is called subproblem (SP). The model is as follows:  
\[\text{(SP)}\qquad z_{i}(\mu)=\min\ y-\sum\limits_{j\in\mathcal{J}}\mu_{j} \cdot x_{j} \tag{6}\]  
\[\text{s.t.}\ \ \sum\limits_{j\in\mathcal{J}}d_{j^{\prime}}\cdot x_{j}\leq c_{ r}\cdot y,\ \forall r\in\mathcal{R} \tag{7}\]  
\[x_{j}+x_{j^{\prime}}\leq 1,\ \forall(j,j^{\prime})\in E \tag{8}\]  
\[x_{j},y\in\{0,1\},\ \forall j\in\mathcal{J} \tag{9}\]  
Assuming that there are \(H\) feasible solutions that satisfy the constraint conditions (7)-(9), each feasible solution is represented by the vector \((x_{1}^{h},x_{2}^{h},\ldots x_{n}^{h},y^{h})_{h=1,2,\ldots,H}^{\text{T}}\). Therefore, \(z_{i}(\mu)=\min\limits_{h=1,2,\ldots,H}\ \left\{y^{h}-\sum_{j\in\mathcal{J}}\mu_{j} \cdot x_{j}^{h}\right\}\), and the optimal Lagrangian lower bound of the original problem is  
\[\max\limits_{\mu}\left\{m\cdot z_{i}(\mu)+\sum\limits_{j\in \mathcal{J}}\mu_{j}\right\}\] \[=\max\limits_{\mu}\left\{m\cdot\min\limits_{h=1,2,\ldots,H}\ \left\{y^{h}-\sum\limits_{j\in\mathcal{J}}\mu_{j}\cdot x_{j}^{h}\right\}+ \sum\limits_{j\in\mathcal{J}}\mu_{j}\right\}\]  
We define variable \(\theta=\min\limits_{h=1,2,\ldots,H}\ \left\{y^{h}-\sum_{j\in\mathcal{J}}\mu_{j} \cdot x_{j}^{h}\right\}.\) Since \((0,0,\ldots,0,0)^{\text{T}}\) is a feasible solution to the SP, \(\theta\leq 0\). We can obtain the following Lagrangian master problem (LMP):  
\[(\text{ LMP})\qquad\max(\sum\limits_{j\in\mathcal{J}}\mu_{j}+m \cdot\theta) \tag{10}\] \[\text{s.t.}\ \ \theta+\sum\limits_{j\in\mathcal{J}}\mu_{j}\cdot x_{j}^{h} \leq y^{h},h=1,2,\ldots,H\] (11) \[: (2),(4),(5)\]0  
We can obtain the Dantzig-Wolfe master problem (DMP) which is the dual solution of the previous LMP as follows:\[: (2),(4),(5)\]1 \[: (2),(4),(5)\]2 (14) \[: (2),(4),(5)\]3 (15) \[: (2),(4),(5)\]4  
From the above models, it can be seen that the optimal solution of SP provides a lower bound \(m\cdot z_{i}(\mu)+\sum_{j\in\mathcal{J}}\mu_{j}\) for \(z(\mu)\). The DMP is equivalent to the original relaxation problem, but due to the large number of DMP columns (coefficients) that cannot be enumerated one by one, we iteratively add effective columns through the column generation algorithm to obtain the restricted master problem (RMP). The optimal solution of RMP provides an upper bound for \(z(\mu)\).