# What is the dual of this LP?

Here is my simple LP problem for a constant symmetric positive matrix $$d$$ and continuous decision variables $$x$$:

\begin{align}\max&\quad\sum{x_i}\\\text{s.t.}&\quad x_i + x_j \leq d_{ij}\\&\quad x_i \geq 0\\&\quad i \in [0,n)\\&\quad j \in [i+1,n)\end{align}

What is the dual form of this? What's the general approach for finding a dual of this form?

The primal LP for $$n=3$$ looks like this:

$$\max 1^Tx\\ \text{s.t. } \left[\matrix{ 1 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 1\\ 0 & 0 & 1\\ }\right] \left[\matrix{ x_0\\x_1\\x_2 }\right] \leq \left[\matrix{ d_{01}\\ d_{02}\\ d_{11}\\ d_{22}\\ }\right]\\ x\geq 0$$

Note, that the definition is not well defined, as $$j\in[n,n)$$ makes not much sense, so I just removed the last constraint from the set of possible combinations of $$i$$ and $$j$$. If your definition is meant to be understood differently, just remove the corresponding constraints.

Applying the standard dualization rules results in this dual LP:

$$\min \left[\matrix{d_{01} & d_{02} & d_{11} & d_{22}}\right]^Ty\\ \text{s.t. } \left[\matrix{ 1 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 1\\ }\right] \left[\matrix{ y_0\\y_1\\y_2\\y_3 }\right] \geq \left[\matrix{ 1\\ 1\\ 1\\ }\right]\\ y\geq 0$$

The constraint matrix of the dual is simply $$A^T$$ so the general formulation is then:

$$\min d^Ty\\ \text{s.t. } y_j + y_i \geq 1, \; j\in[0,m-1], \; i\in[j+1,m-1]\\ y \geq 0$$

The size of $$m$$ is not completely clear as I am not sure about your initial formulation.

• To clarify, my $i$ and $j$ definitions were trying to show that I only care about the upper right triangle in my symmetric matrix $d$. Feb 22 at 14:52