# Variable bounds in column generation

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.

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

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.

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.