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
4
votes
1answer
57 views

Column Generation algorithm for VRP with Min makespan objective function

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 ...
10
votes
1answer
102 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 ...
4
votes
1answer
145 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
votes
1answer
62 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 ...
1
vote
1answer
48 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
0answers
51 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}+...
3
votes
0answers
73 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 ...
2
votes
1answer
64 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.
3
votes
0answers
62 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 ...
5
votes
1answer
90 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 } \...
11
votes
1answer
340 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 ...
10
votes
0answers
110 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 ...
8
votes
0answers
67 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 ...
11
votes
0answers
172 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 ...
14
votes
2answers
633 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 ...
10
votes
1answer
89 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 ...
14
votes
4answers
509 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 ...
10
votes
1answer
142 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 ...
18
votes
1answer
119 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 ...
21
votes
5answers
986 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 ...
18
votes
3answers
229 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} \] ...
17
votes
2answers
179 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 ...
22
votes
9answers
389 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 ...
19
votes
3answers
500 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 ...