# Given the primal, turn it into the dual (LP)

Given the primal resource allocation: $$\min_{x} \text{ costs} = \sum_{i} c_i x_i$$

$$\sum_{i} x_i = D \\ (p)$$

$$x_i \leq \text{CAP}_i \quad \forall i \text{ (}\lambda_i\text{)} \\$$

$$x_i \geq 0 \quad \forall i \\$$

Now the solution of the dual is also given:

$$\max_{(p, \lambda_i)} \text{Value} = pD - \sum_{i} (\lambda_i \cdot \text{CAP}_i) \quad$$

$$c_i + \lambda_i \geq p \quad \forall i \text{ (Xi)} \quad$$

$$\lambda_i \geq 0 \quad \forall i \quad$$

$$p \geq 0 \quad$$

Now what I did so far is the following: I wanted to see whether this solution is correct for the simple case in which we have $$x_1$$ and $$x_2$$ and thus restated:

$$\min \text{costs} = c_1 x_1 + c_2 x_2$$

$$x_1 + x_2 = D \\ (p)$$

$$x_1 \leq \text{CAP}_1 \quad (\lambda_1)$$ $$x_2 \leq \text{CAP}_2 \quad (\lambda_2)$$

$$x_1 \geq 0$$ $$x_2 \geq 0$$

$$p (x_1 + x_2) + \lambda_1 x_1 + \lambda_2 x_2 \leq pD + \lambda_1 \text{CAP}_1 + \lambda_2 \text{CAP}_2$$

$$x_1 (p+\lambda_1) + x_2 (p+\lambda_2) \leq pD + \sum_{i} \lambda_i \cdot \text{CAP}_i$$

which yields:

$$\max_{(p, \lambda_i)} \text{Value} = pD + \sum_{i} \lambda_i \cdot \text{CAP}_i$$ $$p + \lambda_i \geq c_i \quad \forall i$$

$$\lambda_i \geq 0 \quad \forall i$$ $$p \geq 0$$

Thus neither the objective function nor the constraints are correct. Can somebody tell me what went wrong in my approach? Thanks!

The dual variable $$p$$ should be free because the corresponding primal constraint is an equality. If you want the dual variable $$\lambda_i$$ to be nonnegative, you need to rewrite the corresponding primal constraint as $$-x_i \ge -\text{CAP}_i$$ because the primal objective is minimization. The resulting dual problem is then to maximize $$D p - \sum_i \text{CAP}_i \lambda_i$$ subject to \begin{align} p - \lambda_i &\le c_i &&\text{for all i} \\ p &\text{ free} \\ \lambda_i &\ge 0 &&\text{for all i} \end{align}