How can I remember the rules for taking the dual of a linear program (LP)?

Question

When taking the dual of a linear program (LP), is there a trick/easy way to remember the rules for the directions of the inequalities, signs of the variables, etc.? A trick with a catchy name, perhaps?

Answer 1

There sure is! It's called the SOB Method, originally proposed by A.T. Benjamin.

In the SOB method, we classify each variable and each constraint as either sensible, odd, or bizarre (hence the name SOB). For "usual" models, we expect variables to be non-negative (for example, lengths, times, etc.). Sometimes, a variable might be unrestricted (maybe like $xy$ coordinates in the plane), though this isn't as usual. It's even possible that the variable must be negative--weird! This intuition leads to:

1. $x\geq0$ $\leftarrow$ sensible
2. $x$ free $\leftarrow$ odd
3. $x\leq0$ $\leftarrow$ bizarre

Note that the classification of variables doesn't depend on whether we're minimizing or maximizing.

Constraints are also intuitive. Suppose we're maximizing something. Then we would expect that our constraints should bound $x$ from above (so we don't run off to infinity). That is, $Ax\leq{b}$ constraints are sensible. It's possible the constraints are equalities (somewhat weirder), or we might even have $Ax\geq{b}$ constraints--weird, because they look like a lower bound, even though we're maximizing.

Maximization

1. $Ax\leq{b}$ $\leftarrow$ sensible
2. $Ax=b$ $\leftarrow$ odd
3. $Ax\geq{b}$ $\leftarrow$ bizarre

Just the opposite reasoning holds for minimization:

Minimization

1. $Ax\geq{b}$ $\leftarrow$ sensible
2. $Ax=b$ $\leftarrow$ odd
3. $Ax\leq{b}$ $\leftarrow$ bizarre

Once everything is labeled, taking the dual is easy! A sensible primal variable matches up with a sensible dual constraint, etc. So if we're maximizing, and we have a variable $x_3\geq0$, say, then there will be a constraint in the dual with a $\geq$ sign (the dual is a minimization problem, and $\geq$ constraints are sensible in the minimization case).

Here's a full example from the linked paper:

$$ \begin{array}{rl} \text{Minimize} & 3x_1+5x_2+x_3\\ \text{subject to} & x_1+x_2+x_3=2\\ & 2x_1-3x_3\leq0\\ &x_1\geq0,x_2\geq0 \end{array} $$ The primal constraints tell us that our dual variables $y_1$ and $y_2$ will be, respectively, odd and bizarre. Likewise, the first two dual constraints will be sensible and the third one will be odd, resulting in the following LP: $$ \begin{array}{rl} \text{Maximize} & 2y_1\\ \text{subject to} & y_1+2y_2\leq3\\ & y_1\leq5\\ & y_1-3y_2=1\\ & y_2\leq0 \end{array} $$

Answer 2

I have always, for some reason, had troubles remembering those rules. In the book by Bertsimas and Tsitsiklis there is even a nice little table showing the conversion from a primal to a dual in a nice compact fashion. But as stated, I am not good at remembering these rules. Thus, I always write up the Lagrangean and identify for what values of the dual multipliers the Lagrangean function is unbounded; that gives me the constraints of the dual. For example, if we have a linear program of the form \begin{align} \min &\ cx\\ s.t.: &\ Ax\geq b\\ &\ Dx=d\\ &\ x\geq 0 \end{align} Then we can assign dual variables $ \mu\in\mathbb{R}^{m_b}_+ $ and $\pi\in\mathbb{R}^{m_d} $ to the two sets of constraints. The sign of the dual variables tend to come a little easier when you think of them as adding a penalty for violating the constraints. For example here, $\mu$ should be non-negative, as we want to add a positive amount to the objective function if $b_i< A_ix$ and $\pi$ should be able to take both positive and negative values, as any solution $x$ with $Dx\neq d$ should be discouraged. Hence we have the Lagrangean \[ L(\mu,\pi)=\min_{x\geq 0}⁡cx+\mu(b-Ax)+\pi(d-Dx) \] If the Lagrangean is rearranged a bit you get \[ L(\mu,\pi)=\mu b+\pi d + \min_{x≥0}⁡(c-\mu A-\pi D)x \] We should note, that as $x\geq 0$ we will have the following definition of the Lagrangean \begin{equation} L(\mu,\pi)=\begin{cases} -\infty,&\text{if } (c-\mu A-\pi D)_i<0 \text{ for some variable } x_i \\ \mu b+\pi d&\text{if } c-\mu A-\pi D\geq 0\end{cases} \end{equation} Thus, if the Lagrangean should be maximized, we want to avoid the cases where $(c-\mu A-\pi D)_i<0$. This means that the Lagrangean dual problem (and therefore also the linear programming dual) is given by \begin{align} \max_{\mu\geq 0,\pi\in\mathbb{R}^{m_d}}L(\mu,\pi) = \max&\ b\mu+d\pi\\ s.t.:&\ \mu A + \pi D\leq c\\ & \mu \geq 0,\pi \text{ free} \end{align} This helps me as I do not have to remember some conversion-rules (which I most definitely will screw up), and it also keeps it present for me why the dual looks as it does. This more "mechanical" (admitted, not "easy") way, has help many of my students too.

Answer 3

Here is a simple rule I use. Assume you are minimizing and

$$ A x \leq b $$

So the dual value $(y)$ tells you how the objective value change if you increase b. Now if you increase b, then you relax the problem and the objective value most go down. Therefore, the dual variables must satisfies

$$ y \leq 0. $$

Answer 4

I was having the same problem: I always had to look up the rules for taking LP duals. So I've built a small web page at https://lpdual.com that quickly gives the answer. It shows a sample primal program, and allows you to change the sense of the constraints and variables and to then see the effect on the dual.

Answer 5

We can present the canonical format for minimization and maximization problems as follows:

\begin{align} \min &\quad cx\\ \text{s.t.} &\quad Ax\geq b\\ &\quad x\geq 0 \end{align} and \begin{align} \max &\quad wb\\ \text{s.t.} &\quad wA\leq c\\ &\quad w\geq 0 \end{align} The second problem is dual of the first problem and vice versa.

$Ax=b$ in the first problem results in having free variable $w$ in the dual problem (vice versa) and $Ax\leq b$ results in $w\leq 0$ in dual problem (vice versa).

In the same fashion, $wA=c $ gives $x $ free (vice versa) ....