# Warm start a simplex algorithm using a feasible solution

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.

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