I implemented a method to solve a large integer program but am not sure how its called. The idea is the same as column generation, just less explicit.
Take the following problem as a simple example (optimal solution [1,0,0]):
(1)
min $\sum_n n x_n$
s.t.
$\sum_n x_n = 1$
$x_n \in \{0,1\}, \forall n$
Let n be a vector [1,2,3].
Now, using column generation I would generate all permutations $[a_1, a_2, a_3]_{1...k}$, such that $\sum_n a_{n,k} = 1, \forall k \land a_{n,k} \in \{0,1\}, \forall n,k$ and add them iteratively. Variable $y_k$ now denotes whether a permutation $k$ is selected. This yields:
min $\sum_n n x_n$
s.t.
$a_k \circ y_k = x, \forall k$
$\sum_k y_k = 1$
$y_k \in \{0,1\}^{k}, \forall n$
(2) It can be proven computationally that a solution is a global minimum by generating and evaluating all permutations.
But I can expect first improvements quite fast (usually).
To decrease computational cost I am only interested in a subset of all permutations. However, I don't want to generate all permutations manually but let the solver do it. Hence, I change this algorithm described in (2) by utilising model (1).
Assume I know a solution $x'$.
During the first iteration, I then solve:
min $n_1 x_1 + \sum_2^n n x'_n$
s.t.
$x_1 + \sum_2^n x'_n = 1$
$x_1 \in \{0,1\}$
During the second iteration I solve:
min $n_1 x_1 + n_2 x_2 + \sum_3^n n x'_n$
s.t.
$x_1 + x_2 + \sum_3^n x'_n = 1$
$x_1, x_2 \in \{0,1\}$
and so forth.
Eventually I will solve model 1 entirely and be able obtain an optimal solution - given enough time. Does this classify as column-and-constraint generation? I start from a fixed solution and reintruduce integer variables, eventually recovering the full problem.
Thanks a lot in advance!!