2

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?

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Brannon
  • 900
  • 2
  • 12
  • 1
    Have you tried to put the LP in a standard form for which you know the dual? For instance, look at https://en.wikipedia.org/wiki/Dual_linear_program#Vector_formulations . – Mark L. Stone Feb 18 '22 at 16:37
  • 1
    You may be able to find your answer by applying the rules in answers to this question https://or.stackexchange.com/q/292/278 – Sune Feb 18 '22 at 19:18

1 Answers1

2

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.

mattmilten
  • 1,633
  • 8
  • 12
  • 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$. – Brannon Feb 22 '22 at 14:52