9
$\begingroup$

I had a number of students claim on their homework that "All $z_j-c_j$ values are positive, therefore the solution is optimal." Of course, I noted that they should say "non-negative" instead of "positive" or restrict their statement to just the non-basic variables, but this started me thinking: could we have a case where all $z_j -c_j$ values are (strictly) positive?

Consider a linear program $$\begin{align*} \min &\quad \mathbf{cx} \\ \textrm{s.t. } &\quad A\mathbf{x} \geq \mathbf{b}, \end{align*}$$ where $A \in \mathbb{R}^{m \times n}$ has full row-rank, and $\mathbf{b}$, $\mathbf{c}$, and $\mathbf{x}$ are of corresponding dimensions. In most cases, we have $\mathbf{w}B^{-1}\mathbf{a}_j - c_j = z_j - c_j = 0$ for all basic columns due to complementary slackness. At a degenerate optimal solution, where a variable $x_j$ corresponds to constraint $i$, so that $a_{ij}x_j = b_i$, we might conceivably have $z_j - c_j \neq 0$ and still maintain complementary slackness. Of course, in this case the dual problem has alternative optimal solutions. I conjecture that in this degenerate case, we might obtain a non-basic dual solution such that all $z_j - c_j \neq 0$, but even then, we will be attracted to some basis. However, I can't seem to build a proof for this. On the flip side, we know there are cases of cycling in higher dimensions; could the case where all reduced costs are positive be an example of "anti-cycling" (rather than cycling between attractive directions, we cycle between unattractive ones)?

I can think of three possible answers to my question:

  1. Prove that $z_j - c_j \neq 0$ for all $j=1,\ldots,n$ is impossible at optimality.
  2. Prove that if $z_j - c_j \neq 0$ for all $j=1,\ldots,n$ then there must exist some $z_j - c_j < 0$.
  3. Find a counter example, where $z_j - c_j > 0$ for all $j = 1,\ldots,n$ at an optimal solution.
$\endgroup$
6
$\begingroup$

This may depend on how you define "reduced costs". If you mean reduced costs as computed by the simplex algorithm, then no, it is not possible that all are strictly positive due to the mechanics of the algorithm. If you mean $c^\prime - y^{*\prime}A$ for the original variables and $y^{*\prime} I$ for the surplus variables, where $y^*$ is any optimal dual solution, then I think it is possible.

Suppose that $c$ is strictly positive in all components ($c \gg 0$) and that $b=0$. By inspection, $x^*=0$ is an optimal solution to the primal problem. (I'm assuming $x\ge 0$ in the primal.) The dual problem is$$\begin{align*} \max &\quad b^\prime y \\ \textrm{s.t. } &\quad A^\prime y \le c, \\ & \quad y \ge 0\end{align*}$$wherein, since $b=0$, any feasible $y$ is optimal. Now let $y^*\gg 0$ be any feasible (hence optimal) dual solution and let $\bar{y} = \frac{1}{2} y^* \gg 0$. By fixing $A$ and cranking up $c$, you should be able to guarantee the existence of a strictly positive feasible $y^*$. It is easy to verify that (a) $\bar{y}$ is feasible (hence optimal) and (b) $A^\prime y^* \le c \implies A^\prime \bar{y} \ll c$. So $c^\prime - \bar{y}^\prime A \gg 0$ and $\bar{y}^\prime I \gg 0$.

$\endgroup$
  • $\begingroup$ Prubin, thank you for this response. I agree this depends on the definition of "reduced costs." In my question, I allow for non-basic solutions, so I do not restrict this to the Simplex Algorithm. In fact, it was because of this ambiguity that in my question I specifically asked for $z_j - c_j > 0$. In your response, you show a case where each $c_j - z_j > 0$. Thus, you have an example of all non-zero reduced costs (ruling out Case 1 in my question). However, your solution does not answer the question of whether it is possible to have all $z_j - c_j > 0$. $\endgroup$ – Tim Mar 6 at 17:10
  • $\begingroup$ Just to be clear, are you referring to a max problem or a min problem? You posed the question in terms of $z_j - c_j$ being nonnegative at optimum. That's the negative of the reduced cost, and nonpositive reduced costs at optimum would imply a max problem; but your question contains a min problem. $\endgroup$ – prubin Mar 7 at 23:02
0
$\begingroup$

Based on Wikipedia:

In linear programming, reduced cost, or opportunity cost, is the amount by which an objective function coefficient would have to improve (so increase for maximization problem, decrease for minimization problem) before it would be possible for a corresponding variable to assume a positive value in the optimal solution. Given a system as follows: \begin{align*} \min &\quad \mathbf{cx} \\ \textrm{s.t. } &\quad A\mathbf{x} \leq \mathbf{b}, \end{align*}

For maximization problem in the optimality, all non-basic variables have $z_j - c_j \geq 0$, whereas in minimization problem all non-basic variables in the optimality have $z_j - c_j \leq 0$. (All basic variables have $z_j - c_j = 0$.)

$\endgroup$
  • 1
    $\begingroup$ A. Omidi, thank you for taking the time to put this answer together. Your response is correct in most cases, because we are looking for a basic dual solution. However, my question points to a particular case where the primal solution is degenerate and the dual solution has alternative optimal solutions, including non-basic ones. Can you expand your answer to show that even when the dual has alternative optimal solutions, we must always have all reduced costs equal to zero? $\endgroup$ – Tim Jan 30 at 17:04

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.