Column generation when intractable variables appear in the objective function

Question

Is it possible to implement a column generation for a problem that the variables in the "complicating" constraint appear in the objective function?

Suppose the MIP is:

\begin{align} z = \min&\quad\sum_{ij} c_{ij} x_{ij} + \sum_i w_i\\ \text{s.t.}&\quad A(x) \leq a, \tag1 \\ &\quad w_i \geq c_{ij}x_{ij}, \quad \forall i, j\tag2 \\ &\quad x_{ij} \in \{0,1\},\\ &\quad w_{i} \geq 0. \end{align}

Where constraint set (2) are the complicating constraints. If we ignore (2), then what happens to the objective function?

P.S. I don't have the experience in implementing a column generation.

EDIT: I thank Rob for the great answer. For those unfamiliar with column generation, like me, there is additional information in the comments of his post as well.

Answer 1

Suppose $K$ is the set of columns, where the $k$th column $x^k \in \{0,1\}^n$ satisfies $A(x^k) \le a$. Now express $x$ as a convex combination of the columns $x^k$. Explicitly, substitute $x_{i,j} = \sum_{k\in K} \lambda_k x_{i,j}^k$, where $\sum_{k\in K} \lambda_k = 1$ and $\lambda_k \ge 0$ for all $k\in K$. You then obtain the following master problem over $\lambda$ and $w$, with dual variables in parentheses: \begin{align} &\text{minimize} &\sum_{k\in K} \left(\sum_{i,j} c_{i,j} x_{i,j}^k\right) \lambda_k + \sum_i w_i \\ &\text{subject to} &w_i - c_{i,j} \sum_{k\in K} x_{i,j}^k \lambda_k &\ge 0 &&\text{for all $i,j$} &&(\pi_{i,j} \ge 0)\\ &&\sum_{k\in K} \lambda_k &= 1 &&&&(\text{$\alpha$ free})\\ &&\lambda_k &\ge 0 &&\text{for all $k$} \\ &&w_i &\ge 0 &&\text{for all $i$} \end{align}

The column generation subproblem over $x$ is then to minimize the reduced cost of $\lambda_k$. That is, minimize $$\sum_{i,j} c_{i,j} (1+\pi_{i,j}) x_{i,j} - \alpha$$ subject to $A(x) \le a$ and $x \in\{0,1\}^n$.