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

• Thank you for all the help. I understand it now. I already simplified the primal the way you mentioned but forgot to upload the updated version here. However, I did not account for the dual variable corresponding to the upper bound of 'x'. Also, if it is not too much to ask, how can I calculate the reduced cost of a new column (pairing) with the addition of 'z' dual variable. Is it like this: red_cost(p_j) = c_j + z_j - \sum a_{ij} \times y_i? May 12, 2020 at 6:11
• If you are talking about adding a new primal column, making the associated changes to the dual, then solving the modified dual, after that yes, the reduced cost of the new primal column will be what you wrote. (Note that the y values will be different from what they were before adding the new primal column.)
– prubin
May 12, 2020 at 23:09
• Thank you for your reply. Moreover, I assumed the following, please correct me if I am wrong about it. In the LP-primal, I excluded the following condition: -x_j >= -1 for each pairing j. The rationale behind this assumption is that the minimization of primal-objective will lead to an optimal solution in which all 'x' will be less than 1. If it is correct, then I could simplify the respective dual by excluding the new dual variable 'z' corresponding to each pairing. May 13, 2020 at 12:26
• 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, 2020 at 15:57
• Yes, that would simplify the primal and the subsequent dual too. May 14, 2020 at 18:14