Can we have all reduced costs (strictly) positive?

Question

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.

Answer 1

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$.

Answer 2

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$.)