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:
\begin{align}\min&\quad\sum_{j=1}^{P} c_j x_j +\sum_{i=1}^{F}\left(\sum_{j=1}^{P} a_{ij} x_{j} - 1 \right)\times P_{Dhd}\\\text{s.t.}&\quad \sum_{j=1}^{P} a_{ij} x_{j} \geq 1,~~~~\forall i \in \{1,2,...,F\}\\&\quad x_j \in [0, 1],~~~~~~\forall j \in \{1,2,...,P\}\end{align}
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$ and 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:
\begin{align}\max&\quad\sum_{i=1}^{F} y_i\\\text{s.t.}&\quad\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\}\\&\quad\sum_{j=1}^{P} nd_{ij} = 1,~~~~~~~~\forall i \in \{1,2,...,F\}\\&\quad y_i \in \mathbb{R}_{\geq 0},~~~\forall i \in \{1,2,...,F\}\end{align}
where
$nd_{ij}$: binary auxiliary variable which is $1$ if flight $f_i$ is not a deadhead flight in pairing $p_j$ and 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?