0
$\begingroup$

Suppose I have an LP formulation as such:

$\min\ \ \sum\limits_{i,j,t}\ w_{ij}x_{ijt} (\frac{t-r_j}{p_{ij}}+0.5)$

$\sum\limits_{i,t}\frac{x_{ijt}}{p_{ij}}=1\,\forall\ j$

$\sum\limits_{j}x_{ijt}\leq 1\,\forall \ i,t$

$x_{ijt}\geq 0\ \forall\ i,j,t\geq r_j$

For understanding the context of its formulation, please refer here.

My question is how to proceed to compute its dual problem. Now for standard notation like

$\min\ p'x$

$Ax\geq b, x\geq 0$

The dual is simply

$\max\ b'u$

$A'u\leq p, u\geq 0$

But the primal problem of interest has inequalities of the less than ($\leq$) form as well as equality constraints. So how do we proceed with this kind of non-standard form?

$\endgroup$
1
$\begingroup$

Two alternative approaches:

  1. Rewrite the primal problem in standard form by replacing equality with two inequalities and multiplying both sides of $\le$ inequalities by $-1$ to reverse the sense to $\ge$.
  2. For equality constraints in the primal, use free variables in the dual, and for $\le$ constraints in the primal, use $\le 0$ variables. The second approach is simpler. See this paper.
$\endgroup$
1
  • $\begingroup$ could you please cite an illustrative solved example for approach 2? $\endgroup$ – user_1_1_1 Sep 14 '19 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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