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
5 votes
0 answers
76 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? ...
user avatar
  • 389
7 votes
1 answer
111 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 ...
user avatar
  • 389
8 votes
1 answer
177 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 ...
user avatar
5 votes
0 answers
61 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}^{'} | \...
user avatar
  • 293
6 votes
2 answers
186 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 ...
user avatar
  • 389
4 votes
1 answer
104 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 ...
user avatar
6 votes
1 answer
293 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}\\ ...
user avatar
6 votes
2 answers
210 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 ...
user avatar
0 votes
0 answers
152 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..!
user avatar
7 votes
1 answer
69 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 ...
user avatar
2 votes
0 answers
77 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 ...
user avatar
  • 5,705
4 votes
1 answer
283 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 ...
user avatar
6 votes
2 answers
462 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'...
user avatar
  • 415
5 votes
1 answer
458 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?
user avatar
4 votes
1 answer
216 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 ...
user avatar
  • 415
5 votes
0 answers
128 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 ...
user avatar
  • 415
3 votes
1 answer
165 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 ...
user avatar
  • 415
5 votes
1 answer
354 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 ...
user avatar
  • 415
11 votes
1 answer
356 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 ...
user avatar
  • 213
4 votes
1 answer
173 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 = \...
user avatar
  • 2,034
2 votes
1 answer
234 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 ...
user avatar
1 vote
1 answer
93 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 ...
user avatar
2 votes
0 answers
75 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}+...
user avatar
3 votes
0 answers
178 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 ...
user avatar
2 votes
1 answer
86 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.
user avatar
4 votes
0 answers
75 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 ...
user avatar
6 votes
1 answer
129 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 } \...
user avatar
  • 10k
12 votes
1 answer
391 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 ...
user avatar
  • 10k
13 votes
2 answers
583 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 ...
user avatar
  • 10k
9 votes
0 answers
86 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 ...
user avatar
14 votes
1 answer
435 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 ...
user avatar
  • 383
14 votes
2 answers
701 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 ...
user avatar
  • 383
11 votes
1 answer
113 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 ...
user avatar
14 votes
4 answers
547 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 ...
user avatar
  • 299
10 votes
1 answer
213 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 ...
user avatar
  • 1,335
18 votes
1 answer
175 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 ...
user avatar
  • 1,335
23 votes
5 answers
1k 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 ...
user avatar
19 votes
3 answers
317 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} \] ...
user avatar
  • 1,011
19 votes
2 answers
317 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 ...
user avatar
  • 293
23 votes
9 answers
566 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 ...
user avatar
  • 5,641
19 votes
3 answers
699 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 ...
user avatar
  • 1,225