Linked Questions
10 questions linked to/from How to modify master problem and individual sub problems in column generation?
20
votes
3
answers
573
views
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}
\]
...
- 1,143
14
votes
2
answers
825
views
Obtaining optimality gaps when using hybrid exact-heuristic approaches to vehicle routing problems
I'm starting to read about column generation-based approaches to vehicle routing problems (VRP). Let's say that I want to solve very large instances of an intricate VRP, I'm not looking to always ...
- 383
10
votes
1
answer
470
views
Integer column generation without branch & price
Consider the following situation. I have an integer program which I want to solve using column generation. After a suitable decomposition, the master problem has decision variables that select the ...
- 123
2
votes
1
answer
162
views
How to improve a column generation algorithm
I have been busy the last few weeks implementing this model with Column Generation in Gurobi and then solving it. The whole thing is now working quite well and I have also run a few calculation ...
- 139
1
vote
1
answer
137
views
Help with formulating the objective function of my subproblem
i have a pretty basic question regarding column generation. I have the following scheduling problem i would like to solve with column generation:
\begin{align}
&\min\sum_{t}^{}\sum_{s}^{}slack_{ts}...
- 139
1
vote
2
answers
173
views
Best approach to initialize column generation
I was wondering what the typical approaches are for generating an initial solution for the first column in a COlumn Generation approach and which usually work best and are easiest to implement (Gurobi)...
- 139
0
votes
1
answer
132
views
Gurobi - Problem with adding a non-linear constraint to a column object
I have implemented the following Column Generation model in Gurobi. Unfortunately, I currently have the problem that the constraint in the master problem is not linear and therefore I cannot add the ...
- 139
0
votes
1
answer
42
views
Implementing column generation in SAS
I am currently trying to implement this model in SAS. Unfortunately, I always get this error. How can I solve this and finally get the final roster $x$ and the total value of $slack_{ts}$ (preferably ...
- 139
1
vote
0
answers
50
views
How to decompose a specific constraint in the sub-problem?
Suppose there is a specific constraint as follows to impose the precedence relation between the tasks:
$$ \sum_{m \in M} m.x_{j,m} \leq \sum_{m \in M} m.x_{k,m} \quad \forall (j,k) \in T $$
I want to ...
- 9,456
0
votes
1
answer
54
views
Adding additional coordinating constraint to a decomposed model
As suggested by @RobPratt, here is the new opened question. I have these decomposed master and subproblems:
\begin{align}
&\text{minimize} &\sum_t \sum_s \text{slack}_{ts} \\
&\text{...
- 139