Questions tagged [column-generation]
Questions on algorithms that solve mathematical models by generating columns (variables) in the pricing step during solution on demand.
67
questions
2
votes
1
answer
103
views
General question regarding column generation
Assume one have an integer problem.
Is the master problem in the column generation algorithm the original integer problem, or its linear relaxation?
Thank you in advance.
4
votes
0
answers
85
views
Problem related to machine's performance while solving an LP-relaxation of a set-covering problem using the Column Generation
PS: I am familiar with performance variability encountered while solving large-scale MIPs. My question may not be explicitly related to it but maybe to the inefficiency of python packages.
I have ...
- 668
6
votes
1
answer
201
views
When using column generation, can I delete a node with negative reduced cost from my subproblem?
I am solving a minimization problem with a column generation procedure. The master problem is of the form
$$
\min \sum_{i\in \Omega}c_i \lambda_i
$$
subject to
$$
\sum_{i\in \Omega \mid v \in i } \...
- 12.9k
12
votes
1
answer
525
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 ...
- 12.9k
15
votes
2
answers
934
views
Column generation for TSP
For teaching purposes, I would like to solve the Travelling Salesman Problem with a column generation approach.
In the academic literature, an approach is proposed (for example here), where columns ...
- 12.9k
9
votes
0
answers
93
views
Adjusting duals heuristically
I am solving a scheduling problem-to find shifts and task schedules- using column generation. In essence, it is a set covering problem with additional constraints. The problem seems to be that the ...
14
votes
1
answer
597
views
Tools to implement branch-and-price algorithms
As far as I know, implementing a branch-and-price algorithm is a task far from trivial. However, there are tools such as SCIP or the BCP framework of COIN-OR that help implement such algorithms.
I ...
- 383
14
votes
2
answers
769
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
12
votes
1
answer
138
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 ...
14
votes
4
answers
585
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 ...
- 317
10
votes
1
answer
313
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 ...
- 1,345
18
votes
1
answer
260
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 ...
- 1,345
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.1k
20
votes
3
answers
433
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,133
19
votes
2
answers
399
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 ...
- 293
23
votes
9
answers
700
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,864
19
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,235