Dual of a model to obtain reduced costs

Question

I have the following model which I am going to solve with column generation.

\begin{align} \max & \sum_{b \in B} \sum_{s \in S} \sum_{r \in \Omega_s}\beta_{bs}p_r y_{br}\label{objective-set1}\\ \text{s.t.} & \sum_{b \in B} \sum_{s \in S} \sum_{r \in \Omega_s} a_{ir}y_{br} \leq 1 & i \in P \label{c1-set1}\\ &\sum_{s \in S}\sum_{r \in \Omega_{s}} \beta_{bs}y_{br} \leq 1 & b \in B \label{c2-set1}\\ &\sum_{b \in B}\sum_{r \in \Omega_{s}} \beta_{bs} y_{br} \leq V_s & s \in S \label{c3-set1}\\ & y_{br} \in \{0,1\} & b \in B, s \in S, r \in \Omega_s \label{c5-set1} \end{align}

I try to obtain the reduced costs of the variables by taking the dual of this model. I want to add new columns to the set $\Omega_s$ using the pricing problem. So, I assume that the problem is decomposable into a set of pricing subproblems —one for each $s$. Based on this, I tried to write the reduced costs by forming the constraint of the dual problem. This is what I came up with. \begin{align} \sum_{i \in P} a_{ir}\lambda_i + \beta_{bs} \gamma_b + \beta_{bs} \theta_s \geq p_r\beta_{bs} \quad b \in B, r \in \Omega_s \end{align} Using this equation, I can write the pricing subproblems in minimization form for each $b \in B$ and for each $s \in S$ as follows: \begin{align} &\min \Bigg\{ \sum_{i \in P} a_{ir}\lambda_i + \beta_{bs} \gamma_b + \beta_{bs} \theta_s - p_r\beta_{bs}\Bigg\} = & \min \Bigg\{ \sum_{i \in P} a_{ir}(\lambda_i - p_i \beta_{bs}) + \beta_{bs} \gamma_b + \beta_{bs} \theta_s\Bigg\} \end{align} I can say that there is a pricing subproblem corresponding to $b \in B$ and each $s \in S$.

Answer 1

It's a bit tricky to sort out what is going on here. Given a dual solution ($\lambda,\gamma,\theta$) to the LP relaxation of the master problem, your subproblem will need to solve for $a_{ir}$ and $\beta_{bs}$ (or not; see below) so as to maximize the expression on the left side of your dual constraint, subject to whatever constraints there are for $a_{ir}$ and $\beta_{bs}$ (about which I have no idea, since the question provides no context for what columns represent). If the maximum value of the column generator objective exceeds the right side of your dual constraint, you'll add the new column to the master problem.

You'll have to solve the column generation subproblem for a specific $b\in B$, which likely means iterating over $B$ until a subproblem succeeds in generating a new column. That leaves the question of which $\Omega_s$ gets the new column. Since $\beta_{bs}$ is the same for all $r\in\Omega_s$, I can see two possibilities. If currently $\Omega_s = \emptyset$, you column generator will treat both $a_{ir}$ and $\beta_{bs}$ as variables. If not, the $\beta_{bs}$ are fixed and only the $a_{ir}$ are variables.

At this point, I'm not sure whether you want to pick the $s\in S$ that will get the new column up front, or iterate overall combinations of $b$ and $s$ until you get a new column, or let the column generation problem pick $s$ by introducing binary variables to select an $s\in S$ (making the column generation problem a MIP if it wasn't already one).