0
$\begingroup$

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.

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer, $d_i$ and 0 are supposed to be lower and upper bounds for the optimization variables. What should be the sign of the reduced cost associated to a variable 'non-basic at upper bound'? $\endgroup$ Commented Jun 23, 2019 at 10:52
  • $\begingroup$ The reduced cost remains $\sigma_j = c_j - A_j^T \pi$. The optimality conditions change. Assume minimization. For an optimal variable non-basic at lower we have $\sigma_j \ge 0$. For an optimal variable non-basic at upper this is $\sigma_j \le 0$. $\endgroup$ Commented Jun 23, 2019 at 17:37
0
$\begingroup$

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

Regardless if your problem is in (non-)standard form, the non-basic components are equal to zero.

Can the simplex method be used in such scenario without transforming the problem in a standard one ?

Well no, you have to transform your problem by adding slack and artificial variables to lift your inequalities to equality ones. Simplex does not operate on inequality constraints. For more information, you can watch this tutorial.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer, however in this case wouldn't it be possible for the non-basic variables to be either 0 or $d_i$ since a constraint would be active anyway? $\endgroup$ Commented Jun 21, 2019 at 13:18
  • $\begingroup$ The non-basic ones are the ones that deactivate constraints, that's why they're non-basic. $\endgroup$ Commented Jun 21, 2019 at 13:51

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.