6
$\begingroup$

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

$\endgroup$
13
  • $\begingroup$ Welcome to OR.SE! It is recommended that you use MathJax for your equations rather than posting an image. So, please consider editting your question with MathJax as outlined here. $\endgroup$
    – EhsanK
    Sep 15 at 16:22
  • $\begingroup$ Your first constraint has a summation over $s$, but no subscript $s$ in the terms being summed. $\endgroup$
    – prubin
    Sep 15 at 17:17
  • $\begingroup$ Also, you should not be using $\lambda$ for all three sets of dual variables. $\endgroup$
    – prubin
    Sep 15 at 17:18
  • $\begingroup$ Another (important) problem: the dual constraints should not contain primal variable $y_{br}$. $\endgroup$
    – prubin
    Sep 15 at 17:19
  • 1
    $\begingroup$ Do you have all the candidates already generated or not? If yes, then you can just loop through them, compute their reduced cost and add the ones with negative reduced costs. Otherwise, solving the pricing problem will give you a candidate of minimum reduced cost that you can add if its reduced cost is negative. In this case, you need a dedicated algorithm to solve the pricing subproblem $\endgroup$
    – fontanf
    Sep 21 at 15:55
2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Given the additional details, I not sure if column generation would be applicable. Your column generator would be looking for a new candidate route for a particular courier in a particular shift the courier was willing to work, but why would that route not already be known? If the number of courier/shift/route combos (i.e., the number of $(b,r)$ pairs) is too large to let you have all columns present, then you could use the duals to evaluate existing routes for a particular courier/shift combo and see if any should be added to the model for that courier in that shift. $\endgroup$
    – prubin
    Sep 17 at 16:00
  • $\begingroup$ Thanks a lot again! I explained above what I understood from your comment . Am I on the right track? $\endgroup$
    – pozyavas
    Sep 21 at 15:40
  • $\begingroup$ Given what you say about the routing subproblem, I think it looks correct. $\endgroup$
    – prubin
    Sep 21 at 20:18
  • $\begingroup$ Thank you so much! I really appreciate your taking the time to help me! $\endgroup$
    – pozyavas
    Sep 24 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.