2
$\begingroup$

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?

$\endgroup$
2

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – Brannon
    Feb 22, 2022 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.