Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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.
