Linear programming – value of non-basic variables for the solution of a non-standard linear program

linear algebralinear programmingoptimization

Considering this non-standard linear program:

\begin{equation}
\begin{matrix}
\displaystyle \min_x & c^T x \\
\textrm{s.t.} & A x & = & b \\
& x_i & \geq & 0 & & \forall i \\
& x_i & \leq & d_i & & \forall i
\end{matrix}
\end{equation}

Where $x_i$ denotes the i-th component of vector $x$.

Regarding the solution $x^*$, what are the values of its non-basic components?

For a standard form LP they would be 0 but in this case the constraints $x_i\leq d_i$ make such statement not valid.

Can the simplex method be used in such scenario without transforming the problem in a standard one and if yes, what is the formulation for the reduced costs?

I apologize for the possible incorrect notation but I'm pretty new to linear programming.

Best Answer

Real world Simplex codes allow variables to have a lower and upper bound. A non-basic variable can be at lower bound or at upper bound but usually not in between (there are some exceptions to this rule, sometimes these are called superbasic).

Solvers typically will tell you in their solution not only "this variable is non-basic", but more precisely "this variable is non-basic at upper bound". Otherwise you can also deduce this from the sign of the corresponding reduced cost.

Now, it depends what $x_i \le d_i$ means. Is this a constraint or a bound? If it is constraint, $x_i\ge 0$ has no finite upper bound. When solved, $x_i$ will never be "nonbasic at upper bound" but only "nonbasic at lower bound". If $x_i \le d_i$ is formulated as a bound, $x_i$ can be either NB at lower or NB at upper bound.

Also notice that presolvers typically would convert a constraint like $x_i \le d_i$ into a bound. That would make the model smaller (and reduces the size of the basis). The postsolve would report a solution that would look like the solver worked on an explicit constraint while actually, behind the scenes, it converted this to a bound.

Related Question