# 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:

\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?

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