# Questions tagged [column-generation]

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

66 questions
Filter by
Sorted by
Tagged with
2k 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 ...
699 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 ...
432 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} ...
399 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 ...
1k 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 ...
260 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 ...
931 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 ...
585 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 ...
769 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 ...
597 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 ...
795 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 ...
524 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 ...
138 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 ...
366 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 ...
312 views

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 ...
267 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 ...
93 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 ...
234 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 ...
265 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 ...
407 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 ...
80 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 ...
560 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'...
406 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 ...
264 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 ...
488 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 ...
489 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 ...
262 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 ...
201 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 } \...
395 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}\\ ...
207 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) ...
103 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? ...
259 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 ...
300 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 ...
830 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?
75 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}^{'} | \...
203 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 ...
587 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 ...
198 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 = \...
255 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 ...
183 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 ...
220 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^...
188 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 (...
68 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 ...
301 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 ...
85 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 ...
119 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+...
359 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 ...
103 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.