I've been searching a lot for relevant answers to my question. However, I was unable to find a problem formulation with satisfactory answers that would help for my problem.

In a nutshell, I would like to find an initial feasible basis, $\mathcal{B}$, to start my simplex algorithm. And I would like to find this initial basis using an initial feasible basic solution, $x_0$, that satisfies $Ax_0=b$. Note that $A$ and $x_0$ already contain the necessary slack and surplus variables such that the problem is in the following form:

$$min\ \ c^Tx \\ Ax = b\\ x\geq 0$$

A more detailed explanation that might help in finding an initial basis in this specific scenario:

The problem I am solving requires that two linear programming problems that are solved in an alternating fashion. In standard form these problems are formulated as:

$$min\ \ c^T\begin{bmatrix}v \\ s\end{bmatrix}\\ \begin{bmatrix}Gw_1 & \pm I & 0 \\ Gw_2 & 0 & \pm I\end{bmatrix}\begin{bmatrix}v \\ s\end{bmatrix} = b\\ v\geq 0,\ s\geq 0$$ and,

$$min\ \ d^T\begin{bmatrix}w_1 \\w_2\\ s\end{bmatrix}\\ \begin{bmatrix}I_2\otimes (Gv) & \pm I\end{bmatrix}\begin{bmatrix}w_1 \\ w_2 \\ s\end{bmatrix} = b\\ w_i\geq 0,\ s\geq 0$$

Here, vector $v$, and scalars $w_i$, denote the two sets of structural variables and $s$ denotes the shared slack and surplus variables as the equality constraints are equivalent. (They are derived from: $Gvw_1 \leq b$, and $Gvw_2 \leq b$).

Now suppose ($v^*$, $s^*$) is the minimizer for a given $\bar{w}$. Note that $(\bar{w},\ s^*)$ is still a basic feasible solution as the equality constraints are equivalent between the two problems. Now I'd like to start from the feasible basic solution $(\bar{w},\ s^*)$, and find the corresponding basis to start the simplex algorithm.

The trivial columns that must be included in the basis are all entries where, $\begin{bmatrix}\bar{w}\\ s^*\end{bmatrix}>0$. However, this does not necessarily yield a complete basis. And I am not able to find a solution on how to complete this basis besides trail and error.

I hope the problem is sufficiently explained and if there are any question regarding this problem I'd be happy to clarify / elaborate.

  • $\begingroup$ I suspect this is like a crossover algorithm. Cplex has SetStart which looks like what you are after. You may need to provide duals. $\endgroup$ – Erwin Kalvelagen Jun 20 at 8:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.