1
$\begingroup$

Consider the following linear program:
maximize $\sum\limits_{j = 1}^n {{p_j}{x_j}}$
subject to $\sum\limits_{j = 1}^n {{q_j}{x_j}} \le \beta$
$\begin{array}{*{20}{c}} {{x_j} \le 1}&{j = 1,2, \ldots ,n} \end{array}$
$\begin{array}{*{20}{c}} {{x_j} \ge 0}&{j = 1,2, \ldots ,n} \end{array}$
Here, the numbers ${p_j},j = 1,2, \ldots ,n$ are positive and sum to one. The same is true of the ${q_j}$ ’s:
$\sum\limits_{j = 1}^n {{q_j} = 1}$
${q_j} > 0$
Furthermore, assume that
$\frac{{{p_1}}}{{{q_1}}} < \frac{{{p_2}}}{{{q_2}}} < \cdots < \frac{{{p_n}}}{{{q_n}}}$
and that the parameter $\beta$ is a small positive number. Let $k = \min \{ j:{q_{j + 1}} + \cdots + {q_n} \le \beta \}$. Let ${y_0}$ denote the dual variable associated with the constraint involving $\beta$, and let ${y_j}$ denote the dual variable associated with the upper bound of 1 on variable ${x_j}$. Using duality theory, show that the optimal values of the primal and dual variables are given by
${x_j} = \left\{ {\begin{array}{*{20}{l}} 0&{j < k}\\ {\frac{{\beta - {q_{k + 1}} - \cdots - {q_n}}}{{{q_k}}}}&{j = k}\\ 1&{j > k} \end{array}} \right.$
${y_j} = \left\{ {\begin{array}{*{20}{l}} {\frac{{{p_k}}}{{{q_k}}}}&{j = 0}\\ 0&{0 < j \le k}\\ {{q_j}\left( {\frac{{{p_j}}}{{{q_j}}} - \frac{{{p_k}}}{{{q_k}}}} \right)}&{j > k} \end{array}} \right.$.

$\endgroup$
1
$\begingroup$

This is a fairly famous problem. It's the linear programming relaxation of the 0-1 knapsack problem. The problem here is to show that the greedy solution is optimal. Part of what makes that interesting is that the 0-1 knapsack problem itself is NP-complete: Not only is the greedy solution not guaranteed to be optimal for 0-1 knapsack, there's not even a known "fast" optimal algorithm for solving it!

To show what you're trying to show, first you have to construct the dual problem. This is

$$\begin{align} \text{minimize } &\beta y_0 + \sum_{j=1}^n y_j, \\ \text{subject to } &q_j y_0 + y_j \geq p_j, \ \ j = 1, 2, \ldots, n, \\ & y_j \geq 0. \end{align}$$

Then, verify that the primal solution given and the dual solution given have the same objective function value (by substituting them into their respective objective functions). The primal solution has objective function value $$p_k \frac{{\beta - {q_{k + 1}} - \cdots - {q_n}}}{{{q_k}}} + \sum_{j > k} p_j.$$ The dual solution has objective function value $$\beta \frac{p_k}{q_k} + \sum_{j > k} q_j \left(\frac{p_j}{q_j} - \frac{p_k}{q_k}\right).$$ A little algebra shows that they are equal.

Finally, verify that both the primal solution given and the dual solution given are feasible. I'll let you do that. By weak duality, then, the given primal and dual solutions are both optimal.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.