# Questions tagged [column-generation]

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

88 questions
Filter by
Sorted by
Tagged with
1 vote
38 views

### Multi-Commodity Flow with "group edges"

I'm currently working on a special variation of the Multi-Commodity flow problem. My goal is to solve this variation via column generation, because the graph can become very large. Description Given......
• 13
1 vote
45 views

### How to set up the master and subproblem

I have the following question. I have a classical scheduling model with the following constraints: Demand coverage One shift per day Minimum and maximum number of consecutive working days Forward ...
1 vote
67 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)...
41 views

### Column Generation for non/single capacitated routing problems

Introduction The strategy here documented was applied before for the TSP: Column generation for TSP https://coin-or.github.io/jorlib/manual/manual.pdf (Section 4, page 18); And https://www.jstor.org/...
28 views

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{...
53 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 \...
71 views

### How to implement self-adjusting smoothing in column generation?

I am currently trying to implement the "Smoothing with a Self-Adjusting Parameter" methodology (on the right in Table 1) from Pessoa et. al (2018) in my MILP. Unfortunately, I am not quite ...
54 views

### Branch-and-Price for VRPs: Enforcing branching on arcs

The following is based on my understanding, which may have flaws, so please correct me if I claim something wrong. When solving VRPs with Branch-and-Price, one can enforce integrality by branching on ...
• 676
61 views

• 113
1 vote
72 views

### Termination criterion for the Phase 1 algorithm in column generation

To initialize column generation, I obtain a feasible set of columns via the following Phase 1 algorithm. The restricted master problem for this algorithm is formulated as follows. min ...
• 615
73 views

### In column generation is it possible that a new column from sub problem doesn't enter master's base? [duplicate]

In some iterations, when a new column is added to the master, it does not enter the base and a stop condition occurs, or a new column with a better objective function is found. is it correct?
1 vote
81 views

### Partially modify LHS of a constraint set?

I have implemented a column generation algorithm in Gurobi in Python. The most computationally expensive aspect of this algorithm is the reconstruction of the master problem when a column is added (or ...
• 615
98 views

### Is there existing code for the set partitioning formulation of routing problems?

The set partitioning formulation of routing problems is pretty well-accepted as perhaps the best exact method to solve routing problems. However, these methods are difficult to implement as many ...
330 views

### Column generation: set partitioning vs set covering

I am working with a column generation algorithm and have noticed that convergence is much faster when my master is a set covering problem ($Ax\ge 1$) compared to when it is a set partitioning problem (...
• 41
1 vote
75 views

439 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
542 views

### Metaheuristics vs Column generation for VRP

I am solving a vrp and its variants (pick up drop off, milk-run problem) using genetic algorithms. The issue that I am getting with the genetic algorithm is the randomness associated with the ...
• 629
110 views

### Dual instability, degeneracy, tailing off effect - Which are the causes and which are the effects?

Dual instability, degeneracy, and the tailing off effect are often mentioned together in papers. However, I cannot seem to find a clear explanation on which of these cause the other and vice versa? ...
• 676
276 views

### Why is the tailing off effect only a problem in column generation?

Why is the tailing off effect only a problem in column generation? If all columns were pregenerated, and one used the simplex method, wouldn't one see the tailing off effect? Is it simply not an issue ...
• 676
312 views

### Odd behavior in the branch bound and price algorithm with column generation

I have two questions on branch-bound-and-price. Why does it sometimes fail? For instance, the paper by Dabia et al shows results where the proposed algorithm fails for some cases. The paper does not ...