Consider the set covering problem \[ \begin{align} \min&\ \sum_{j=1}^nc_jx_j\\ s.t.:&\ \sum_{j=1}^na_{ij}x_j\geq 1,\quad \forall i=1,\dots,m\\ &\ 0\leq x_j \leq 1 \end{align} \] which, in my case, should be solved using column generation as $n$ is exponential in $m$. By letting $\pi_i$ be the dual multipliers of the set covering constraints, I can price out new variables by solving an optimization problem of the form \[ \min\{ c_j-\pi a(x) :x\in X\}. \] However, when doing this, I have not taken the dual variable of the constraint $x_j\leq 1$ into account. How do I do that? As the variable has not been added yet, I do not a have a dual variable for its bound.
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Assuming that the $a_{ij}$'s are either zero or one, and the $c_j$'s are positive, you do not need the upper bound on the variables. To see this, if $x_j=1$ for some $j$, then column $j$ covers all items, $i$, where $a_{ij}=1$ and it does not cover any other items. Increasing $x_j$ to $1+\varepsilon$, for some $\varepsilon>0$, will increase the cost, and cover no more items than having $x_j=1$. Thus, it will not be optimal to have $x_j>1$.
$\begingroup$
$\endgroup$
When pricing $x_j$, there are two possibilities:
- $x_j$ is not in the restricted master problem / $x_j$ has not been added before.
In this case, $x_j=0$ in the current solution. The constraint $x_j \le 1$ is not active, such that the associated multiplier is equal to 0. It is thus not a problem that the constraint was not added to the restricted master problem, and the dual can safely be ignored.
- $x_j$ is in the restricted master problem / $x_j$ has been added before.
In this case, you have already added the constraint $x_j \le 1$ earlier, such that the multiplier is available.
Note that the multiplier of $x_j \le 1$, say $\lambda_j$, should only be added for the variable $x_j$. This is needed to prevent finding variables that have been added before.
However, this may severely complicate the pricing problem. In vehicle routing, for example, you would have to add $\lambda_j$ for one specific route only.
As proposed by Sune, you can often avoid the upper bound on $x_j$ altogether, which is definitely preferred if possible.
answered Jun 20, 2019 at 21:19
$\begingroup$
$\endgroup$
Another understanding can be the following.
Denote $X = \{ x \in \Bbb R^n \mid 0 \leq x_j \leq 1, \forall j = 1,\dots, n\}$.
When solving the pricing problem successfully to optimal, all variable bound constraints will be satisfied. Therefore, you only need to track the dual variables $\pi$ of those 'hard' constraints which are $$\sum\limits_{j=1}^na_{ij}x_j\geq 1,\quad \forall i=1,\dots,m.$$
Good news for this model is that the pricing problem is a knapsack problem and you can solve it over given $X$ efficiently.
