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

Question

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?

Answer 1

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).$$