The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [column-generation]

Questions on algorithms that solve mathematical models by generating columns (variables) in the pricing step during solution on demand.

Filter by
Sorted by
Tagged with
10
votes
1answer
63 views

Stabilization techniques in column generation when subproblems are not solved optimally

Which stabilization techniques in column generation, like penalty function approaches and dual price smoothing, can be used when subproblems are not solved optimally? (I am particularly interested in ...
13
votes
3answers
422 views

Online Education for OR and Developing Decision Support Systems

I am looking for educational programmes which can be conducted online, such as full MSc., degree certificates, postgraduate courses/modules, MOOCs. Topics I am looking for are on advanced ...
10
votes
1answer
91 views

DOCplex adding columns

When using DOCplex to implement column generation, is it possible to add columns as an object, as opposed to creating a variable and then modifying the coefficients in the constraints? Edit: In ...
18
votes
1answer
105 views

Optimality in a simultaneous column and row generation procedure

What is the optimality argument in a simultaneous column and row generation procedure? By column and row generation procedure I mean a procedure in which every time a column in generated, several ...
21
votes
5answers
777 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 ...
18
votes
3answers
185 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} \] ...
15
votes
2answers
116 views

Automating the column generation decomposition process

When trying a decomposition technique such as column generation, most of the times my approach is to look at the problem and then: Decide what a column should represent Write the Master Problem Write ...
17
votes
6answers
189 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 ...
17
votes
3answers
370 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 ...