Questions tagged [column-generation]
Questions on algorithms that solve mathematical models by generating columns (variables) in the pricing step during solution on demand.
11
questions
20
votes
3
answers
546
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
23
votes
11
answers
853
views
Reference for column generation applications
When talking about column generation algorithms, the main example is the cutting stock problem. I'm aware that variations of vehicle routing problem (VRP) can be solved using a column generation ...
- 5,894
3
votes
1
answer
486
views
How to modify master problem and individual sub problems in column generation?
This is a follow-up post regarding this one. I deleted this new post once before, as I was unhappy with the formulation. I have the following basic nurse scheduling MILP, which tries to cover the ...
- 139
12
votes
1
answer
584
views
When using column generation, can a sub-problem be ignored once and for all once it fails to generate a new column?
Suppose you are solving a minimization problem with a column generation procedure, and that you have $2$ sub-problems. At some point, one of the $2$ sub-problems is no longer able to generate a column ...
- 13.7k
26
votes
5
answers
2k
views
Solving pricing problem heuristically in column generation algorithm for VRP
In the set covering/column generation approach for the VRP (Balinski and Quandt (1964), or e.g. this tutorial), the basic idea is:
Generate some routes.
Solve the set covering problem using those ...
- 13.2k
20
votes
3
answers
1k
views
Column generation stabilisation
Has anyone performed a benchmark of the various stabilisation techniques in column generation? Which ones perform better for set pack/partition/cover problems like VRP? And are there theoretical ...
- 1,245
6
votes
2
answers
630
views
Branch and Price Algorithm
Can branch and price be a good solution approach for a routing problem with min-max objective function? For example, minimizing the max length of any vehicle route in a VRP.
In the literature, I haven'...
- 455
6
votes
1
answer
571
views
Column Generation algorithm for vehicle routing problem
I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. In more detail, I want to minimize the arrival time of the last vehicle in the depot. I ...
- 455
4
votes
1
answer
275
views
Column Generation algorithm
I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. but there is a point in calculating the arrival time of the vehicle in each node. the ...
- 455
1
vote
1
answer
125
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
0
votes
2
answers
62
views
Modification of subproblem objective function
I have the following decomposed compact model with the following master problem:
\begin{align}
&\text{minimize} &\sum_t \sum_s \text{slack}_{ts} \\
&\text{subject to} &\sum_i \sum_r \...
- 139