19
$\begingroup$

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.

$\endgroup$

3 Answers 3

18
$\begingroup$

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

$\endgroup$
9
$\begingroup$

When pricing $x_j$, there are two possibilities:

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

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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