Skip to main content

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
1 vote
1 answer
35 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......
jatsqi's user avatar
  • 13
1 vote
0 answers
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 ...
marvelfab12's user avatar
1 vote
2 answers
66 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)...
nflgreaternba's user avatar
0 votes
1 answer
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/...
Matheus Diógenes Andrade's user avatar
0 votes
1 answer
28 views

Adding additional coordinating constraint to a decomposed model

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{...
nflgreaternba's user avatar
0 votes
2 answers
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 \...
nflgreaternba's user avatar
2 votes
1 answer
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 ...
marvelfab12's user avatar
0 votes
1 answer
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 ...
gmn's user avatar
  • 676
0 votes
0 answers
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}^-,\...
nflgreaternba's user avatar
2 votes
1 answer
122 views

Determine whether column generation heuristic is optimal?

I am currently working on a machine scheduling problem formulated as MILP and trying to solve it with Column Generation. Since I do not use Branch-n-Price, but only Column Generation as heuristic, it ...
ORNoob's user avatar
  • 21
2 votes
1 answer
127 views

How to improve a column generation algorithm

I have been busy the last few weeks implementing this model with Column Generation in Gurobi and then solving it. The whole thing is now working quite well and I have also run a few calculation ...
nflgreaternba's user avatar
5 votes
1 answer
348 views

What is delayed column generation?

I came across the term "Delayed Column Generation" yesterday and am wondering how this differs from classic Column Generation, or whether the terms are used synonymously.
marvelfab12's user avatar
2 votes
1 answer
74 views

Add multiple columns to the Master Problem in a column generation approach

I have read several times now that with a column generation approach in the subproblem you do not necessarily have to look for the column with the lowest negative reduced cost, but only one with ...
manofthousandnames's user avatar
0 votes
1 answer
35 views

Implementing column generation in SAS

I am currently trying to implement this model in SAS. Unfortunately, I always get this error. How can I solve this and finally get the final roster $x$ and the total value of $slack_{ts}$ (preferably ...
nflgreaternba's user avatar
0 votes
1 answer
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 ...
nflgreaternba's user avatar
0 votes
1 answer
89 views

How can I add columns from the subproblem to the master problem in my column generation model?

I have one last question about my column generation model. I am currently trying to implement it in code, and I am successfully solving the subproblem. So I can solve the dual values of the master ...
nflgreaternba's user avatar
0 votes
1 answer
127 views

Exploiting identical subproblems in column generation

As suggested, this is a new post. I have the following column generation model. The notation is as follows: $i\in I$ refers to the nurses, $t\in T$ to the days and $s\in S$ for the shifts. With the ...
nflgreaternba's user avatar
3 votes
1 answer
457 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 ...
nflgreaternba's user avatar
1 vote
1 answer
117 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}...
nflgreaternba's user avatar
2 votes
1 answer
191 views

How to evaluate the quality of a solution obtained using the price-and-branch method for an IP problem?

I have solved an integer programming problem using the price-and-branch (not branch-and-price) approach exactly as same as described in this question and obtained a feasible solution. As this approach ...
Sina_Alef's user avatar
1 vote
1 answer
145 views

Column generation for solving minimum cost multicommodity flow problem with additional edge disjoint constraints

I'm working on an integer programming problem that's fundamentally a minimum cost multicommodity flow (MCMF) problem with additional constraints. I'm exploring the use of column generation to solve it,...
Sina_Alef's user avatar
0 votes
1 answer
145 views

Question on Column generation

I am implementing a Column Generation algorithm to solve a set partitioning problem. The master problem takes the form : $\min \sum_{i \in I} c_i \lambda_i$ s.t $\sum_{i \in I} a_{ji} \lambda_i = 1, \...
CHE's user avatar
  • 113
1 vote
1 answer
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. \begin{equation} min ...
mdslt's user avatar
  • 615
0 votes
0 answers
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?
user12849's user avatar
1 vote
1 answer
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 ...
mdslt's user avatar
  • 615
-2 votes
2 answers
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 ...
IsalanOnkar's user avatar
4 votes
2 answers
327 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 (...
Rom's user avatar
  • 41
1 vote
1 answer
75 views

Question about Pricing Problem in Column Generation

In column generation, we need to solve the following pricing problem : $$\min c_j-\bf{c}^T_B\bf{B}^{-1}\bf{N}_j$$ In the book, I saw authors say that according to duality theory, $\bf{y}^T = \bf{c}^...
Lin Sen's user avatar
  • 25
2 votes
0 answers
152 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 ...
Nada.S's user avatar
  • 429
2 votes
1 answer
167 views

Can one strengthen the Lagrangian dual bound in column generation when there are multiple subproblems?

Consider a Linear Programme (LP) \begin{align} \min && \sum_{i \in I} c_i x_i \\ \text{s.t.} && \sum_{i \in I} a_{ij} x_i &\geq b_j & \quad & \forall j \in J \\ && ...
1 vote
2 answers
117 views

Combination of lagrangian relaxation and column generation

I am solving an integrated scheduling problem and have dealt with coupling constraints using Lagrangian relaxation to decompose the problem into two separate problems. However, it is still difficult ...
XXia's user avatar
  • 49
4 votes
1 answer
82 views

Can dual values smoothing lead to generating duplicate columns?

When using smoothing for dual values stabilization in column generation, the duals used in the subproblem lie on the segment joining the stability center (inside the dual feasible region) and the ...
Инженер человеческих душ's user avatar
1 vote
2 answers
233 views

Quality of the defined initial solution in column generation

In the context of column generation, specifically, price and branch or delayed column generation like Gilmore-Gomory (GG-CG) procedure, it needs to define an initial feasible solution as a trigger of ...
A.Omidi's user avatar
  • 8,960
0 votes
0 answers
43 views

Dual prices remain stable but negative in column generation

I arrive at an objective function value that I know to be optimal. However, dual prices remain negative (which leads me to believe another pattern can be added, but when I do, the dual prices don't ...
user11638's user avatar
2 votes
1 answer
160 views

Must the Newly Generated Column be used in RMP in the Column Generation Method?

When I used Column Generation, I found a column with reduced cost < 0, and added it to the Restricted Master Problem. Must the newly added column be used in the solution of RMP at once? If not, ...
West Wind's user avatar
4 votes
1 answer
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+...
Romio Rodriguez's user avatar
4 votes
1 answer
404 views

How do we branch a Cutting Stock problem using Branch and Price?

I'm sure this is a straightforward question, but since I started learning integer programming recently this isn't clear to me. Consider solving a 1 dimensional cutting stock problem using delayed ...
133crem's user avatar
  • 41
2 votes
1 answer
643 views

Adding variable to constraint in pyomo

I am trying to implement a delayed column generation approach in pyomo. However, I cannot find a way to add a variable to a constraint. I can add variables to the objective function, simply by adding ...
Sune's user avatar
  • 6,647
5 votes
1 answer
466 views

Reduced cost in column generation

I am following this tutorial to learn column generation. ` https://co-at-work.zib.de/slides/Donnerstag_24.9/cgbpdw-coatwork-annotated.pdf I have a couple of questions I thought someone experienced in ...
mars's user avatar
  • 629
2 votes
1 answer
196 views

Dantzig-Wolfe decomposition and optimal integer solutions

It is well known that applying the Dantzig-Wolfe Decomposition in the one period cutting stock problem with trim loss minimization leads to an optimal real solution that shares the round up property, ...
Eduardo Silva's user avatar
7 votes
1 answer
440 views

Can't solve a specific instance of Gilmore & Gomory Cutting Stock with Delayed Column Generation

I am now somewhat comfortable with delayed column generation, but one specific example has been bugging me, as it's quite simple (on the second iteration we stop) and I can't reach the optimal ...
J. Dionisio's user avatar
8 votes
1 answer
276 views

Column generation: decreasing value of restricted master problem

I am using column generation to solve a minimization problem. At a given iteration, my subproblem finds a column with reduced cost $-1$, and in the following restricted master problem, this new column ...
user123456's user avatar
4 votes
1 answer
227 views

Accelerating an integer programming model

I am working on a scheduling problem, where I am solving it through column generation. The pricing problem of this algorithm is an integer programming model as follows: \begin{equation} F_1 \Big\{V^...
mdslt's user avatar
  • 615
6 votes
0 answers
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) ...
Enthusiast's user avatar
4 votes
3 answers
207 views

Is this ILP formulation for Group Closeness Centrality a column generation approach?

I want to solve the Group Closeness Centrality problem where the input is a graph $G=(V,E)$ and integer $k$ and we want to find a vertex set $S$ of size $k$ minimizing the total distance of the ...
Christian Komusiewicz's user avatar
10 votes
1 answer
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 ...
pele's user avatar
  • 123
6 votes
2 answers
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 ...
mars's user avatar
  • 629
6 votes
0 answers
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? ...
gmn's user avatar
  • 676
8 votes
1 answer
275 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 ...
gmn's user avatar
  • 676
9 votes
1 answer
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 ...
Dr. Soomin Woo PhD's user avatar