1
$\begingroup$

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).

$\endgroup$
5
  • $\begingroup$ ok, but why tho $\endgroup$ Apr 12, 2021 at 22:09
  • $\begingroup$ 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. $\endgroup$
    – Samuel
    Apr 13, 2021 at 1:11
  • $\begingroup$ 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)\}$ $\endgroup$ Apr 14, 2021 at 4:11
  • $\begingroup$ 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? $\endgroup$
    – Samuel
    Apr 16, 2021 at 18:58
  • $\begingroup$ Have you tried looking at a possible asymmetric dual formulation of your LP? $\endgroup$
    – ms_
    Apr 16, 2021 at 20:37

0

You must log in to answer this question.