# Alternative method of converting a linear problem into standard form LP

The problem we are given is:

\begin{align} & \text{Find a vector} && \mathbf{x} \\ & \text{that maximizes} && \mathbf{D}^T \mathbf{x}\\ & \text{subject to} && W \mathbf{x} = \mathbf{\pi} \\ & \text{and} && \mathbf{x} \ge \mathbf{0}. \end{align} Where $$W$$ is an $$N$$ by $$M$$ matrix.

And we want to convert it into a standard LP (linear program)

\begin{align} & \text{Find a vector} && \mathbf{x} \\ & \text{that maximizes} && \mathbf{c}^T \mathbf{x}\\ & \text{subject to} && A \mathbf{x} \leq \mathbf{b} \\ & \text{and} && \mathbf{x} \ge \mathbf{0}. \end{align}

The textbook way of doing this would be replacing the contraint $$W \mathbf{x} = \mathbf{\pi}$$, by the constraints $$W \mathbf{x} \leq \mathbf{\pi}$$ and $$-W \mathbf{x} \leq -\mathbf{\pi}$$, and stacking these two inequalities on top of each other.

Question: Is there a way of converting this problem into an LP without using this trick?

My attempt: Replace the constraint $$W \mathbf{x} = \mathbf{\pi}$$, by the constraint $$W \mathbf{x} \leq \mathbf{\pi}$$ and the additional maximization condition $$\text{max}(W\mathbf{q})$$. Unfortunately, these are now $$N+1$$ maximization problems, instead of one (because $$W$$ is a matrix).

• ok, but why tho Apr 12, 2021 at 22:09
• Excellent question @KaragounisZ, I am developing an algorithm that will run on quantum computers. Using the conventional textbook method makes it computationally unstable, unfortunately, so I need to find another way. Apr 13, 2021 at 1:11
• what if you put the equality constraint into the objective function as in the Lagrangian relaxation? For instance, your optimization problem has value equal to $\max_{x \geq 0} \min_\lambda \{D'x - \lambda \cdot (Wx - \pi)\}$ Apr 14, 2021 at 4:11
• Thank you @KaragounisZ. The solution that you provided isn't a standard LP form? Is there an easy way of converting this into a standard LP form? Apr 16, 2021 at 18:58
• Have you tried looking at a possible asymmetric dual formulation of your LP?
– ms_
Apr 16, 2021 at 20:37