Questions tagged [column-generation]
Questions on algorithms that solve mathematical models by generating columns (variables) in the pricing step during solution on demand.
61
questions
0
votes
0
answers
86
views
How should one proceed with column generation when the subproblem generates only columns with positive reduced costs?
I try to solve a MILP with Column generation. The Master Problem is a minimization problem with " $\le$ " constraint which lead to non-positive dual values. The problem is that the ...
- 409
1
vote
0
answers
80
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 ...
- 409
2
votes
1
answer
115
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
77
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 ...
- 11
4
votes
1
answer
65
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 ...
1
vote
2
answers
125
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 ...
- 8,165
0
votes
0
answers
35
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 ...
2
votes
1
answer
113
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, ...
- 21
4
votes
1
answer
115
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+...
4
votes
1
answer
269
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 ...
- 41
2
votes
1
answer
369
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 ...
- 6,212
5
votes
1
answer
264
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 ...
- 619
2
votes
1
answer
150
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, ...
- 153
7
votes
1
answer
403
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 ...
- 516
8
votes
1
answer
262
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 ...
- 81
4
votes
1
answer
215
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^...
- 561
6
votes
0
answers
203
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
4
votes
3
answers
201
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 ...
10
votes
1
answer
350
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
6
votes
2
answers
380
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 ...
- 619
6
votes
0
answers
102
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? ...
- 557
8
votes
1
answer
223
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 ...
- 557
9
votes
1
answer
262
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 ...
5
votes
0
answers
73
views
Linear programming approach to dynamic programming - an initial pair of state-decisions
I aim to solve the following Bellman equation:
\begin{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}^{'} | \...
- 561
6
votes
2
answers
444
views
What kind of data structure should be used to store labels when implementing a labeling algorithm?
The shortest path problem with resource constraints is a common subproblem when doing column generation. It is often solved with a labeling algorithm. The procedure is very well explained here and ...
- 557
4
votes
1
answer
170
views
How do you know if Column Generation is any faster than standard MIP formulations?
I'm currently in the process of learning about column generation, so I apologize in advance if I show a gross lack of understanding about it.
Anyways, what I've gathered so far is that Column ...
6
votes
1
answer
375
views
Dual of a model to obtain reduced costs
I have the following model which I am going to solve with column generation.
\begin{align}
\max & \sum_{b \in B} \sum_{s \in S} \sum_{r \in \Omega_s}\beta_{bs}p_r y_{br}\label{objective-set1}\\
...
- 61
6
votes
2
answers
260
views
Heuristic solution to the graph partitioning problem
I am working on a graph partitioning problem. A static column generation based solution was proposed in How to partition a graph with optimal number of groups?
But I need some MILP solver to solve ...
- 2,211
1
vote
0
answers
280
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
7
votes
1
answer
79
views
Branch and price with two sets of exponential variables
There are classes of problems which allow for "natural" extended formulations using multiple exponential-size sets of variables.
For example, 2-echelon routing problems can be modelled ...
- 2,073
2
votes
0
answers
90
views
Materials or sample code for column generation book (GERAD 25th Anniversary Series)
As far as I know, one of the interesting resource to learn the basic concept of the decomposition methods is column generation book (GERAD 25th Anniversary Series), which has been mentioned in some ...
- 8,165
4
votes
1
answer
533
views
Column generation for a linear optimization problem
I have an LP that has exponentially many constraints, and just linearly many variables. The dual of the problem, therefore, has exponentially many variables, while just linearly many constraints. My ...
- 3,970
6
votes
2
answers
556
views
Branch and Price Algorithm
Can branch and price be a good solution approach for a routing problem with min-max objective function? For example, minimizing the max length of any vehicle route in a VRP.
In the literature, I haven'...
- 445
5
votes
1
answer
782
views
Does pyomo support column generation?
I want to use column generation technique to solve cutting stock problem.
Is there any other python modeling library that supports column generation?
4
votes
1
answer
253
views
Column Generation algorithm
I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. but there is a point in calculating the arrival time of the vehicle in each node. the ...
- 445
6
votes
1
answer
254
views
Column generation approach for CVRP
I want to use a column generation based heuristic to solve a capacitated Vehicle Routing Problem. I know the basics of the algorithm but I don't have much experience in coding. is there any code about ...
- 445
4
votes
1
answer
246
views
A Question on A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet
I am reading A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet to learn the column generation approach, but I have a problem. in section 3.3 ...
- 445
6
votes
1
answer
477
views
Column Generation algorithm for vehicle routing problem
I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. In more detail, I want to minimize the arrival time of the last vehicle in the depot. I ...
- 445
13
votes
1
answer
757
views
Branch and Price algorithm is exact?
I know that the Column Generation algorithm delivers an exact solution when you are solving a linear programming optimization problem. I want to know that, does this column generation approach deliver ...
- 233
4
votes
1
answer
196
views
Column generation when intractable variables appear in the objective function
Is it possible to implement a column generation for a problem that the variables in the "complicating" constraint appear in the objective function?
Suppose the MIP is:
\begin{align}
z = \...
- 2,086
2
votes
1
answer
385
views
C++ code for branch and price
I looking to learn to use bpcolumn generation techniques in c++.
Does any body know of GitHub repository or any other site where I can find some code And learn about it...
The application can be ...
- 173
1
vote
1
answer
172
views
Column generation
I can't get my head around how to implement different subproblems in a column generation procedure with only one master problem.
Say the computer found a resource constraint shortest path for each ...
2
votes
0
answers
106
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}+...
- 21
3
votes
0
answers
325
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 ...
- 668
2
votes
1
answer
102
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
84
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
195
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.8k
12
votes
1
answer
503
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.8k
14
votes
2
answers
890
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.8k
9
votes
0
answers
91
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 ...
