10
$\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?

The homework problem originally was for a maximization problem, but here I'll pose it for a minimization problem, so now we want $c_j - z_j > 0$. 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 $c_j - \mathbf{c}_B B^{-1}\mathbf{a}_j = c_j - z_j = 0$ for all basic columns due to complementary slackness.

Edit 2: Prubin's answer points out that using the above formula cannot give strictly positive reduced costs, since the dual variables in the Simplex algorithm are always basic: $\mathbf{w} = \mathbf{c}_B B^{-1}$.

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

| improve this answer | |
$\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
  • $\begingroup$ I am referring to a min problem. As you point out, $z_j - c_j$ is the negative reduced cost (I amended the question title to match this definition). Normally, in a minimization problem, we have optimality when all the negative reduced costs are all non-negative. My question asks for a standard LP minimization problem that has an optimal solution where all the all the negative reduced costs are (strictly) positive, or a proof that this cannot happen. $\endgroup$ – Tim Apr 23 at 15:01
  • $\begingroup$ In a minimization problem, the condition for optimality is that all the reduced costs (not negated reduced costs) are nonnegative. $\endgroup$ – prubin Apr 23 at 18:59
  • $\begingroup$ I see where you're going. I apologize: the homework problem had been a maximization, and in posing my question here I was making the switch to minimization without making the proper adjustments. I will fix the question. Again, I apologize and thank you for setting me straight. $\endgroup$ – Tim Apr 24 at 13:36
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$.)

| improve this answer | |
$\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.