# On dual-formulation of a given primal for a set-covering problem

I need to solve an LP-relaxation of an airline crew pairing optimization problem (CPOP). The problem formulation is a modified SCP and is as follows:

Primal of the CPOP:

$$min \left(\sum_{j=1}^{P} c_j x_j +\left(\sum_{i=1}^{F}\left(\sum_{j=1}^{P} a_{ij} x_{j} - 1 \right) \right) \times P_{Dhd}\right)$$,

subject to,

$$\sum_{j=1}^{P} a_{ij} x_{j} \geq 1,~~~~\forall i \in \{1,2,...,F\}$$

$$x_j \in [0, 1],~~~~~~\forall j \in \{1,2,...,P\}$$

where,

$$P$$: size of $$\mathcal{P}$$, i.e., $$|\mathcal{P}|$$,

$$F$$: size of $$\mathcal{F}$$, i.e., $$|\mathcal{F}|$$,

$$c_j$$: cost of a pairing $$p_j$$,

$$P_{Dhd}$$: pre-defined parameter which penalizes the number of deadhead flights in the solution,

$$a_{ij}$$ is 1 if flight $$f_i$$ is covered in pairing $$p_j$$ & is 0 otherwise,

$$x_j$$ is a relaxed binary decision variable which represents the fractional-contribution of a pairing $$p_j$$ in the corresponding LP-solution

I have formulated the following dual for the above primal:

$$max \left(\sum_{i=1}^{F} y_i \right),$$

subject to,

$$\sum_{i=1}^{F} a_{ij} y_i \leq c_j + P_{Dhd} \times \left( \sum_{i=1}^{F} \left(a_{ij} - nd_{ij}\right) \right),~~~~\forall j \in \{1,2,...,P\}$$

$$\sum_{j=1}^{P} nd_{ij} = 1,~~~~~~~~\forall i \in \{1,2,...,F\}$$

$$y_i \in \mathbb{R}_{\geq 0},~~~\forall i \in \{1,2,...,F\}$$

where,

$$nd_{ij}$$: binary auxiliary variable which is 1 if flight $$f_i$$ is not a deadhead flight in pairing $$p_j$$ & is 0 otherwise

$$y_i$$: dual variable which represents a shadow price to cover flight $$f_i$$ in the respective manner

Is the above dual correct? Is it right to introduce new binary variables (such as $$nd_{ij}$$ in this case) and constraints for them while formulating dual from primal?

It does not look correct, and in particular the dual of an LP is an LP, so it makes no sense to have a binary variable in the dual. I suspect what led you astray was a misunderstanding of the penalty portion of the primal objective. You can rewrite the primal objective as $$\begin{gather*} \sum_{j=1}^{P}c_{j}x_{j}+P_{Dhd}\left[\sum_{i=1}^{F}\sum_{j=1}^{P}a_{ij}x_{j}-\sum_{i=1}^{F}1\right]\\ =\sum_{j=1}^{P}\left(c_{j}+P_{Dhd}\sum_{i=1}^{F}a_{ij}\right)x_{j}-F\times P_{Dhd}. \end{gather*}$$The last term is a constant term and can be ignored.
Meanwhile, you need to account for the dual variable (call it $$z_j$$) of the upper bound (1) for $$x_j$$. If you rewrite the primal to include $$-x_j \ge -1 \, \forall j$$ and make the domain of $$x$$ just $$x\ge 0$$, you'll see that the dual constraints should be $$\sum_{i=1}^F a_{ij} y_i - z_j \le c_j + P_{Dhd} \sum_{i=1}^F a_{ij} \quad \forall j$$and the dual objective is $$\max \left(\sum_{i=1}^F y_i - \sum_{j=1}^P z_j\right).$$
• You had $x_j\in [0,1]$ in the primal, which implies $-x_j \ge -1$. Are you saying you now intend to change the primal to $x_j \ge 0$? That seems reasonable to me. – prubin May 14 '20 at 15:57