# Questions tagged [column-generation]

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

17 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
102 views

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 ...
212 views

### Benders decomposition for a dense MILP

I am trying to solve a large MILP, but it seems like dense problems can be very difficult for moderns solvers. I tried to solve the problem described below considering only constraints (1) and (2) ...
• 109
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
77 views

### Linear programming approach to dynamic programming - an initial pair of state-decisions

I aim to solve the following Bellman equation: v(\vec{s}) = \min_{\vec{x} \in \Xi_{\vec{s}}} \big\{c(\vec{s}, \vec{x}) + \lambda \times \sum_{\vec{s}^{'}\in S} p(\vec{s}^{'} | \...
• 615
117 views

### Materials or sample code for column generation book (GERAD 25th Anniversary Series)

As far as I know, one of the interesting resources to learn the basic concept of the decomposition methods is column generation book (GERAD 25th Anniversary Series), which has been mentioned in some ...
• 8,940
87 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 ...
131 views

### How to find the vectors to be added as the columns in the master problem of Dantzig-Wolfe Decomposition?

I have a Dantzig-Wolfe decomposition question with the following questions \begin{align} &Maximize: 2x_1 +3x_2+4x_3+2x_4 \\ s.t. \quad & x_1 +x_2+2x_3+x_4 \le 15\\ & x_1 +x_2+2x_3+...
436 views

### On solving the Restricted Master Problem in Column Generation technique

I am working on developing a column generation (CG) based optimization framework for a large-scale airline crew pairing problem (a set-covering problem). First, I generate an initial feasible solution ...
151 views

### Why the column generation algorithm remains stuck at the same solution?

I was trying to solve a MILP by a column generation algorithm, and I noticed that the algorithm was stuck at the same solution, I tried to diversify the pool of initial columns, but the problem I ...
• 429
125 views

### Dantzig decomposition and Column Generation for equality constraints

I was trying to apply Dantzig Decomposition followed by Column Generation. The following is how I was taught. \begin{array}{l} \text { Minimize }-10 x_1-2 x_{2}-4 x_{3} \\ \text { subject to: } x_{1}+...
1 vote
317 views

### Set Covering and Column Generation

I need some set covering and column generation examples in OR-Tools python. If anyone can provide or direct me to some resources that would be great..!
• 137
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{...
52 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 \...
61 views

### Dual stabilization doesnt work properly

I am currently trying to speed up my column generation approach to reduce the tailing-off effect. I have modified my master problem as follows. For this I have introduced \$\phi_{ts}^+,\phi_{ts}^-,\...
75 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 ...