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!


1 Answer 1


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}

  • $\begingroup$ Thank you Sir, that helped me a lot. Just to make sure, I understood properly: In the minimization problem I want to switch signs of the primal (unequality) constraints by multiplying with (-1) in order for the dual variables to be nonnegative? Is that a general approach for problems like the one above? $\endgroup$ Commented Mar 29 at 13:32
  • 1
    $\begingroup$ Yes. You might find Arthur Benjamin's S-O-B method useful. $\endgroup$
    – RobPratt
    Commented Mar 29 at 13:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .