assignment problem column generation

Solving Generalized Assignment Problem using Branch-And-Price

Oct 27, 2021

Table of Contents

Generalized assignment problem, dantzig-wolfe decomposition, column generation, standalone model, initial solution, branching rule, branch-and-price.

One of the best known and widely researched problems in combinatorial optimization is Knapsack Problem:

• given a set of items, each with its weight and value,
• select a set of items maximizing total value
• that can fit into a knapsack while respecting its weight limit.

The most common variant of a problem, called 0-1 Knapsack Problem can be formulated as follows:

• \(m\) - number of items;
• \(x_i\) - binary variable indicating whether item is selected;
• \(v_i\) - value of each items;
• \(w_i\) - weight of each items;
• \(W\) - maximum weight capacity.

As often happens in mathematics, or science in general, an obvious question to ask is how the problem can be generalized. One of generalization is Generalized Assignment Problem. It answers question - how to find a maximum profit assignment of \(m\) tasks to \(n\) machines such that each task (\(i=0, \ldots, m\)) is assigned to exactly one machine (\(j=1, \ldots, n\)), and one machine can have multiple tasks assigned to subject to its capacity limitation. Its standard formulation is presented below:

• \(n\) - number of machines;
• \(m\) - number of tasks;
• \(x_{ij}\) - binary variable indicating whether task \(i\) is assigned to machine \(j\);
• \(v_{ij}\) - value/profit of assigning task \(i\) to machine \(j\);
• \(w_{ij}\) - weight of assigning task \(i\) to machine \(j\);
• \(c_j\) - capacity of machine \(j\).

Branch-and-price

Branch-and-price is generalization of branch-and-bound method to solve integer programs (IPs),mixed integer programs (MIPs) or binary problems. Both branch-and-price, branch-and-bound, and also branch-and-cut, solve LP relaxation of a given IP. The goal of branch-and-price is to tighten LP relaxation by generating a subset of profitable columns associated with variables to join the current basis.

Branch-and-price builds at the top of branch-and-bound framework. It applies column generation priori to branching. Assuming maximization problem, branching occurs when:

• Column Generation is finished (i.e. no profitable columns can be found).
• Objective value of the current solution is greater than best lower bound.
• The current solution does not satisfy integrality constraints.

However, if only first two conditions are met but not the third one, meaning the current solution satisfies integrality constraints, then the best solution and lower bound are updated (lower bound is tightened) with respectively the current solution and its objective value.

The crucial element needed to apply branch-and-price successfully is to find branching scheme. It is tailored to specific problem to make sure that it does not destroy problem structure and can be used in pricing subproblem to effectively generate columns that enter Restricted Master Problem (RMP) while respecting branching rules .

Below is flow diagram describing branch-and-price method:

The successful application B&P depends on tight/strong model formulation. Model formulation is considered tight if solution of its LP relaxation satisfies (frequently) integrality constraints. One of structured approaches to come up with such a formulation is to use Dantzig-Wolfe Decomposition technique. We will see example of it applied to Generalized Assignment Problem (GAP).

A standard formulation was described above. Now, let’s try to reformulate problem. Let

be a set containing all feasible solutions to Knapsack problem for \(j\)-th machine. Clearly, \(S_j\) contains finite number of points, so \(S_j = \{ \mathbf{z}_j^1, \ldots, \mathbf{z}_j^{K_j} \}\), where \(\mathbf{z}_j^k \in \{0, 1\}^{m}\). You can think about \(\mathbf{z}_j^k \in \{0, 1\}^{m}\) as 0-1 encoding of tasks that form \(k\)-th feasible solution for machine \(j\). Now, let \(S = \{ \mathbf{z}_1^1, \ldots, \mathbf{z}_1^{K_1}, \ldots, \mathbf{z}_n^1, \ldots, \mathbf{z}_n^{K_n} \}\) be a set of all feasible solution to GAP. It, potentially, contains a very large number of elements. Then, every point \(x_{ij}\) can be expressed by the following convex combination:

where \(z_{ij}^k \in \{0, 1\}\), and \(z_{ij}^k = 1\) iff task \(i\) is assigned to machine \(j\) in \(k\)-th feasible solution for the machine.

Now, let’s use this representation to reformulate GAP:

Note that we do not need capacity restrictions as they are embedded into definition of feasible solution for machine \(j\).

Now that we have formulation that is suitable for column generation, let’s turn our attention to it.

Column generation is another crucial component of branch-and-price. There are many great resources devoted to column generation so I will mention only core points:

• Column generation is useful when a problem’s pool of feasible solutions contains many elements but only small subset will be present in the optimal solution.
• There exists subproblem (called often pricing problem) that can be used to effectively generate columns that should enter RMP.
• Column generation starts with initial feasible solution.
• Pricing subproblem objective function is updated with dual of the current solution.
• Columns with positive reduced cost, in case of maximization problem, enter problem.
• Procedure continues until such columns exist.

Below is flow diagram describing column generation method:

Implementation

Let’s see how one can approach implementation of B&P to solve Generalized Assignment Problem. Below is discussion about main concepts and few code excerpts, a repository containing all code can be found on github .

An example of problem instance taken from [1] is:

It is always good idea to have a reference simple(r) implementation that can be used to validate our results using more sophisticated methods. In our case it is based on standard problem formulation. Implementation can be found in repo by checking classes GAPStandaloneModelBuilder and GAPStandaloneModel . Formulation for a problem instance presented above looks as follows:

Now let’s try to examine building blocks of B&P to discus main part at the end, once all the puzzles are there.

To start column generation process, we need to have an initial solution. One possible way to derive it is to use two-phase Simplex method. In first step, you add slack variables to each constraint and set objective function as their sum. Then you minimize the problem. If your solution has objective value \(0\), then first of all you have initial solution and you know that your problem is feasible. In case you end up with positive value for any of slack variables, you can conclude that the problem is infeasible. You can stop here.

I took a different approach and came up with simple heuristic that generate initial solution. I have not analyzed it thoroughly so I am not sure if it is guaranteed to always return feasible solution if one exists. Its idea is quite simple:

• Construct bipartite graph defined as \(G=(V, A)\), where \(V = T \cup M\) – \(T\) is set of tasks and obviously \(M\) is set of machines. There exists arc \(a = (t, m)\) if \(w_{tm} \le rc_{m}\), where \(rc_{m}\) is remaining capacity for machine \(m\). Initially remaining capacity is equal to capacity of machine and with each iteration, and assignment of task to machine it is being update. If \(\vert A \vert = 0\), then stop.
• Solve a minimum weight matching problem.
• Update assignments – say that according to solution task \(t_0\) should be assigned to machine \(m_0\), then \(\overline{rc}_{m_0} = rc_{m_0} - w_{t_0 m_0}\).
• Find a machine where task is contributing with the lowest weight – say machine \(m_0 = \arg\min \{ m: w_{t_0 m} \}\).
• Free up remaining capacity so there is enough space for \(t_0\) on machine \(m_0\). Any tasks that were de-assigned in a process are added to pool of unassigned tasks.
• Repeat until there are no unassigned tasks.

See details on github .

As we said before the most important piece needed to implement B&P is branching rules which does not destroy structure of subproblem. Let’s consider non-integral solution to RMP. Given convexity constraint it means that there exists machine \(j_0\) and at least two, and for sake of example say exactly two, \(0 < \lambda_{j_0} ^{k_1} < 1\) and \(0 < \lambda_{j_0} ^{k_2} < 1\) such that \(\lambda_{j_0} ^{k_1} + \lambda_{j_0} ^{k_2} = 1\). Since with each of \(\lambda\)s is connected different assignment (set of tasks), then it leads us to a conclusion that there exists task \(i_0\) such that \(x_{i_0 j_0} < 1\) expressed in variables from the original formulation. Now, let’s use this information to formulate branching rule:

• left child node: a task \(i_0\) must be assigned to a machine \(j_0\).
• right child node: a task \(i_0\) cannot be assigned to a machine \(j_0\).

We can say that branching is based on \(x_{ij}\) from standard formulation. And it can be represented by:

Note that we can use the branching rule to easily to filter out initial columns for each node that do not satisfy those conditions:

• \(j = j_0\) and task \(i_0 \in T_{j_0}\), or
• \(j \neq j_0\) and task \(i_0 \notin T_{j}\).
• \(j = j_0\) and task \(i_0 \in T_{j_0}\).

See on github .

Based on the same principle, subproblem’s pool of feasible solution are created - i.e. on left child node:

• knapsack subproblem for machine \(j_0\) – variable representing task \(i_0\) is forced to be \(1\).
• knapsack subproblem for machine \(j \neq j_0\) – variable representing task \(i_0\) is forced to be \(0\).

Similarly for right childe node. See on github .

Below is an outline of main loop of column generation. It is an implementation of flow diagram from above so I will not spend too much time describing it. The only part maybe worth commenting is stop_due_to_no_progress - it evaluates whether column generation did not make any progress in last \(k\)-iterations and it should be stop.

Now, let’s see how constructing subproblems, solving them and then adding back column(s) to RMP looks like. We have as many subproblems as machines. Once a solution is available, we check whether it has positive reduced cost. A solution to knapsack problem corresponds to column in RMP. So if the column with positive reduced cost was identified and added, then new iteration of column generation will be executed. Gurobi allows to query information about all other identified solutions, so we can utilize this feature and add all columns that have the same objective value as optimal solution, potentially adding more than one column and hoping it will positively impact solution time.

Note that each subproblem is independent so in principle they could be solved in parallel. However due to Python Global Interpreter Lock (GIL) that prevent CPU-bounded threads to run in parallel, they are solved sequentially. Additionally depending on your Gurobi license, you might not be allowed to solve all those models in parallel even if Python would allow it.

Below you can find example of one of the RMPs:

and subproblem with dual information passed:

Now that we have all building blocks prepared, then let’s turn our attention back to B&P.

In the blog post, Branch-and-Price technique for solving MIP was explained. An example of applying B&P for Generalized Assignment Problem was presented. The solution approach used Python as programming language and Gurobi as solver.

[1] Der-San Chen, Robert G. Batson, Yu Dang (2010), Applied Integer Programming - Modeling and Solution, Willey. [2] Lasdon, Leon S. (2002), Optimization Theory for Large Systems, Mineola, New York: Dover Publications. [3] Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser, Martin W. P. Savelsbergh, Pamela H. Vance, (1998) Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research 46(3):316-329.

Column generation with the Generalized Assignment Problem

This quick start guide introduces the main features of Coluna through the example of the Generalized Assignment Problem.

Classic model solved with MIP solver

Consider a set of machines M and a set of jobs J . A machine $m$ has a resource capacity $Q_m$ . A job $j$ assigned to a machine $m$ has a cost $c_{mj}$ and consumes $w_{mj}$ resource units of the machine $m$ . The goal is to minimize the sum of job costs while assigning each job to a machine and not exceeding the capacity of each machine.

Let $x_{mj}$ equal to one if job $j$ is assigned to machine $m$ ; $0$ otherwise. The problem has the original formulation:

\[\begin{alignedat}{4} \text{[GAP]} \equiv \min \mathrlap{\sum_{m \in M}\sum_{j \in J} c_{mj} x_{mj}} \\ \text{s.t.} && \sum_{m \in M} x_{mj} &= 1 \quad& j \in J \\ && \sum_{j \in J} w_{mj} x_{mj} &\leq Q_m  \quad \quad& m \in M \\ && x_{mj} &\in \{0,1\} &m \in M,\; j \in J \end{alignedat}\]

Let us consider the following instance.

We write the model with JuMP , a domain-specific modeling language for mathematical optimization embedded in Julia. We optimize with GLPK. If you are not familiar with the JuMP package, you may want to check its documentation .

A JuMP model for the original formulation is:

We optimize the instance and retrieve the objective value.

Try column generation easily with Coluna and BlockDecomposition

This model has a block structure: each knapsack constraint defines an independent block and the set-partitioning constraints couple these independent blocks. By applying the Dantzig-Wolfe reformulation, each knapsack constraint forms a tractable subproblem and the set-partitioning constraints are handled in a master problem.

To write the model, you need JuMP and BlockDecomposition. The latter is an extension built on top of JuMP to model Dantzig-Wolfe and Benders decompositions. You will find more documentation about BlockDecomposition in the Decomposition & reformulation To optimize the problem, you need Coluna and a Julia package that provides a MIP solver such as GLPK.

Since we have already loaded JuMP and GLPK, we just need:

Next, you instantiate the solver and define the algorithm that you use to optimize the problem. In this case, the algorithm is a classic branch-and-price provided by Coluna.

In BlockDecomposition, an axis is an index set of subproblems. Let M_axis be the index set of machines; it defines an axis along which we can implement the desired decomposition.

In this example, the axis M_axis defines one knapsack subproblem for each machine. For instance, the first machine index is 1 and is of type BlockDecomposition.AxisId :

Jobs are not involved in the decomposition, set J of jobs thus stays as a classic range.

The model takes the form:

You can write BlockModel(coluna; direct_model = true) to pass names of variables and constraints to Coluna.

This is the same model as above except that we use a BlockModel instead of a Model and M_axis as the set of machines instead of M . Therefore, BlockDecomposition will know which variables and constraints are involved in subproblems because one of their indices is a BlockDecomposition.AxisId .

You then apply a Dantzig-Wolfe decomposition along M_axis :

where decomposition is a variable that contains information about the decomposition.

Once the decomposition is defined, you can retrieve the master and the subproblems to give additional information to the solver.

The multiplicity of a subproblem is the number of times that the same independent block shaped by the subproblem appears in the model. This multiplicity also specifies the number of solutions to the subproblem that can appear in the solution to the original problem.

In this GAP instance, the upper multiplicity is $1$ because every subproblem is different, i.e. , every machine is different and used at most once.

The lower multiplicity is $0$ because a machine may stay unused. The multiplicity specifications take the form:

The model is now fully defined. To solve it, you need to call:

You can find more information about the output of the column generation algorithm ColumnGeneration .

Finally, you can retrieve the solution to the original formulation with JuMP methods. For example, if we want to know if job 3 is assigned to machine 1:

This page was generated using Literate.jl .

Theme documenter-light documenter-dark Automatic (OS)

This document was generated with Documenter.jl version 1.2.1 on Wednesday 21 February 2024 . Using Julia version 1.10.1.

Column generation algorithms

Author: Lorena Garcia Fernandez (lgf572) (SysEn 5800 Fall 2020)

• 1 Introduction
• 2 Theory, methodology and algorithmic discussions
• 3 Numerical example: The Cutting Stock problem [8]
• 4 Applications
• 5 Conclusions
• 6 References

Introduction

Column Generation techniques have the scope of solving large linear optimization problems by generating only the variables that will have an influence on the objective function. This is important for big problems with many variables where the formulation with these techniques would simplify the problem formulation, since not all the possibilities need to be explicitly listed. [1]

Theory, methodology and algorithmic discussions

The way this method work is as follows; first, the original problem that is being solved needs to be split into two problems: the master problem and the sub-problem.

• The master problem is the original column-wise (i.e: one column at a time) formulation of the problem with only a subset of variables being considered. [2]
• The sub-problem is a new problem created to identify a new promising variable. The objective function of the sub-problem is the reduced cost of the new variable with respect to the current dual variables, and the constraints require that the variable obeys the naturally occurring constraints. The subproblem is also referred to as the RMP or “restricted master problem”. From this we can infer that this method will be a good fit for problems whose constraint set admit a natural breakdown (i.e: decomposition) into sub-systems representing a well understood combinatorial structure. [3]

To execute that decomposition from the original problem into Master and subproblems there are different techniques. The theory behind this method relies on the Dantzig-Wolfe decomposition. [4]

In summary, when the master problem is solved, we are able to obtain dual prices for each of the constraints in the master problem. This information is then utilized in the objective function of the subproblem. The subproblem is solved. If the objective value of the subproblem is negative, a variable with negative reduced cost has been identified. This variable is then added to the master problem, and the master problem is re-solved. Re-solving the master problem will generate a new set of dual values, and the process is repeated until no negative reduced cost variables are identified. The subproblem returns a solution with non-negative reduced cost, we can conclude that the solution to the master problem is optimal. [5]

Methodology [6]

Consider the problem in the form:

To solve the Master Linear Program, we use a column generation algorithm. This is in order to solve the linear programming relaxation of the Integer Programming Master Problem, called the Linear Programming Master Problem (LPM) :

Numerical example: The Cutting Stock problem [8]

Suppose we want to solve a numerical example of the cutting stock problem, specifically a one-dimensional cutting stock problem.

Problem Overview

The objective is to establish what is the minimum number of steel bars that should be used to satisfy the total demand.

A possible model for the problem, proposed by Gilmore and Gomory in the 1960ies is the one below:

Decision variables

Solving the problem

Key take-away: In the next steps of this example we will analyze how to solve the continuous relaxation of the model.

As a starting point, we need any feasible solution. Such a solution can be constructed as follows:

This solution could also be arrived to by applying the simplex method to the model (without integrality constraints), considering only the decision variables that correspond to the above single-item patterns:

In fact, if we solve this problem (for example, use CPLEX solver in GAMS) the solution is as below:

The solution for the dual problem can be computed in different software packages, or by hand. The example below shows the solution obtained with GAMS for this example:

Given a basic optimal solution for the problem in which only some variables are included, how can we find (if any exists) a variable with negative reduced cost (i.e., a constraint violated by the current dual solution)?

This question can be transformed into an optimization problem: in order to see whether a variable with negative reduced cost exists, we can look for the minimum of the reduced costs of all possible variables and check whether this minimum is negative:

And by so doing, it enables the conversion of the problem of finding a variable with negative reduced cost into the integer linear programming problem below:

In our example, if we start from the problem restricted to the five single-item patterns, the above problem reads as:

Optimality test

Algorithm discussion

Applications

As previously mentioned, column generation techniques are most relevant when the problem that we are trying to solve has a high ratio of number of variables with respect to the number of constraints. As such some common applications are:

• Bandwith packing

Bus driver scheduling

• Generally, column generation algorithms are used for large delivery networks, often in combination with other methods, helping to implement real-time solutions for on-demand logistics. We discuss a supply chain scheduling application below.

Bandwidth packing

The objective of this problem is to allocate bandwidth in a telecommunications network to maximize total revenue. The routing of a set of traffic demands between different users is to be decided, taking into account the capacity of the network arcs and the fact that the traffic between each pair of users cannot be split The problem can be formulated as an integer programming problem and the linear programming relaxation solved using column generation and the simplex algorithm. A branch and bound procedure which branches upon a particular path is used in this particular paper [9] that looks into bandwidth routing, to solve the IP. The column generation algorithm greatly reduces the complexity of this problem.

Bus driver scheduling aims to find the minimum number of bus drivers to cover a published timetable of a bus company. When scheduling bus drivers, contractual working rules must be enforced, thus complicating the problem. A column generation algorithm can decompose this complicated problem into a master problem and a series of pricing subproblems. The master problem would select optimal duties from a set of known feasible duties, and the pricing subproblem would augment the feasible duty set to improve the solution obtained in the master problem. [10]

Supply Chain scheduling problem

A typical application is where we consider the problem of scheduling a set of shipments between different nodes of a supply chain network. Each shipment has a fixed departure time, as well as an origin and a destination node, which, combined, determine the duration of the associated trip. The aim is to schedule as many shipments as possible, while also minimizing the number of vehicles utilized for this purpose. This problem can be formulated by an integer programming model and an associated branch and price solution algorithm. The optimal solution to the LP relaxation of the problem can be obtained through column generation, solving the linear program a huge number of variables, without explicitly considering all of them. In the context of this application, the master problem schedules the maximum possible number of shipments using only a small set of vehicle-routes, and a column generation (colgen) sub-problem would generate cost-effective vehicle-routes to be fed fed into the master problem. After finding the optimal solution to the LP relaxation of the problem, the algorithm would branch on the fractional decision variables (vehicle-routes), in order to reach the optimal integer solution. [11]

Conclusions

Column generation is a way of starting with a small, manageable part of a problem (specifically, with some of the variables), solving that part, analyzing that interim solution to find the next part of the problem (specifically, one or more variables) to add to the model, and then solving the full or extended model. In the column generation method, the algorithm steps are repeated until an optimal solution to the entire problem is achieved. [12]

This algorithm provides a way of solving a linear programming problem adding columns (corresponding to constrained variables) during the pricing phase of the problem solving phase, that would otherwise be very tedious to formulate and compute. Generating a column in the primal formulation of a linear programming problem corresponds to adding a constraint in its dual formulation.

• ↑ Desrosiers, Jacques & Lübbecke, Marco. (2006). A Primer in Column Generation.p7-p14 10.1007/0-387-25486-2_1.
• ↑ AlainChabrier, Column Generation techniques, 2019 URL: https://medium.com/@AlainChabrier/column-generation-techniques-6a414d723a64
• ↑ Dantzig-Wolfe decomposition. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Dantzig-Wolfe_decomposition&oldid=50750
• ↑ Wikipedia, the free encyclopeda. Column Generation. URL: https://en.wikipedia.org/wiki/Column_generation
• ↑ L.A. Wolsey, Integer programming. Wiley,Column Generation Algorithms p185-p189,1998
• ↑ GERARD. (2005). Personnel and Vehicle scheduling, Column Generation, slide 12. URL: https://slideplayer.com/slide/6574/
• ↑ L.A. Wolsey, Integer programming. Wiley,Column Generation Algorithms p185-p189,1998The Cutting Stock problem
• ↑ Parker, Mark & Ryan, Jennifer. (1993). A column generation algorithm for bandwidth packing. Telecommunication Systems. 2. 185-195. 10.1007/BF02109857.
• ↑ Dung‐Ying Lin, Ching‐Lan Hsu. Journal of Advanced Transportation. Volume50, Issue8, December 2016, Pages 1598-1615. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/atr.1417
• ↑ Kozanidis, George. (2014). Column generation for scheduling shipments within a supply chain network with the minimum number of vehicles. OPT-i 2014 - 1st International Conference on Engineering and Applied Sciences Optimization, Proceedings. 888-898
• ↑ ILOG CPLEX 11.0 User's Manual > Discrete Optimization > Using Column Generation: a Cutting Stock Example > What Is Column Generation? 1997-2007. URL: http://www-eio.upc.es/lceio/manuals/cplex-11/html/usrcplex/usingColumnGen2.html#:~:text=In%20formal%20terms%2C%20column%20generation,method%20of%20solving%20the%20problem.&text=By%201960%2C%20Dantzig%20and%20Wolfe,problems%20with%20a%20decomposable%20structure

Navigation menu

Branch and Price: Integer Programming with Column Generation

• Reference work entry
• Cite this reference work entry

• Martin W. P. Savelsbergh 3  

2751 Accesses

4 Citations

Branch and price is a generalization of linear programming (LP) based branch and bound specifically designed to handle integer programming (IP) formulations that contain a huge number of variables. The basic idea of branch and price is simple. Columns are left out of the LP relaxation because there are too many columns to handle efficiently and most of them will have their associated variable equal to zero in an optimal solution anyway. Then to check the optimality of an LP solution, a subproblem, called the pricing problem , is solved to try to identify columns with a profitable reduced cost . If such columns are found, the LP is reoptimized. Branching occurs when no profitable columns are found, but the LP solution does not satisfy the integrality conditions. Branch and price applies column generation at every node of the branch and bound tree.

There are several reasons for considering IP formulations with a huge number of variables.

A compact formulation of an IP may have a weak LP...

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P., and Vance, P.H. : ‘Branch-and-price: Column generation for solving integer programs’, Oper. Res. 46 (1998), 316–329.

MathSciNet   MATH   Google Scholar  

Desrosiers, J., Dumas, Y., Solomon, M.M., and Soumis, F. : ‘Time constrained routing and scheduling’, in M.E. Ball, T.L. Magnanti, C. Monma, and G.L. Nemhauser (eds.): Handbook Oper. Res. and Management Sci.: Network Routing , Vol. 8, Elsevier, 1995, pp. 35–140.

Google Scholar  

Savelsbergh, M.W.P. : ‘A branch-and-price algorithm for the generalized assignment problem’, Oper. Res. 6 (1997), 831–841.

Article   MathSciNet   Google Scholar  

Vanderbeck, F., and Wolsey, L.A. : ‘An exact algorithm for IP column generation’, Oper. Res. Lett. 19 (1996), 151–160.

Download references

Author information

Authors and affiliations.

School of Industrial and Systems Engin. Georgia Inst. Technology, Atlanta, GA, 30332-0205, USA

Martin W. P. Savelsbergh

You can also search for this author in PubMed   Google Scholar

Editor information

Editors and affiliations.

Dept. Chemical Engin., Princeton Univ., Princeton, NJ, 08544-5263, USA

Christodoulos A. Floudas

Center for Applied Optim. Dept. Industrial and Systems Engin., Univ. Florida, Gainesville, FL, 32611, USA

Panos M. Pardalos

Rights and permissions

Reprints and permissions

Copyright information

© 2001 Kluwer Academic Publishers

About this entry

Cite this entry.

Savelsbergh, M.W.P. (2001). Branch and Price: Integer Programming with Column Generation . In: Floudas, C.A., Pardalos, P.M. (eds) Encyclopedia of Optimization. Springer, Boston, MA. https://doi.org/10.1007/0-306-48332-7_47

Download citation

DOI : https://doi.org/10.1007/0-306-48332-7_47

Publisher Name : Springer, Boston, MA

Print ISBN : 978-0-7923-6932-5

Online ISBN : 978-0-306-48332-5

eBook Packages : Springer Book Archive

Share this entry

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

9   Column Generation Theories

If I have to choose my favorite decomposition algorithm, column generation is the one!

I used column generation in my Ph.D. dissertation and a couple industry projects. It proved to be a very powerful modeling and problem solving technique that I resort to frequently.

In this chapter, I will explain the basic theories behind column generation.

9.1 Linear Programs that are Conducive to Column Generation

Column generation is a linear programming (LP) technique primarily used in LP problems with too many variables. The idea behind column generation is to start with a smaller, more manageable subset of variables and iteratively add new variables (or “columns”) to the model, as needed, to improve the solution.

Define the following linear program as the Master Problem (MP) :

\[ \begin{aligned} \text{min.} &\quad \sum_{j \in \Omega} c_jx_j \\ \text{s.t.} &\quad \sum_{j \in \Omega} a_j x_j = b \\ &\quad x_j \geq 0, j \in \Omega \end{aligned} \]

In this formulation, \(\Omega\) represents the set of all candidate columns. In many real-world applications, \(\Omega\) could be prohibitively large that it is impossible to include all the columns in the model at the same time. For these problems, column generation enables us to work with a subset of columns and employ a special pricing subproblem to iteratively identify new columns.

9.2 Restricted Master Problem

Let \(\bar{\Omega}\) represent a subset of \(\Omega\) , that is, \(\bar{\Omega} \subset \Omega\) . The restricted mater problem (RMP) is defined as follows:

\[ \begin{aligned} \text{min.} &\quad \sum_{j \in \bar{\Omega}} c_jx_j \\ \text{s.t.} &\quad \sum_{j \in \bar{\Omega}} a_j x_j = b \\ &\quad x_j \geq 0, j \in \bar{\Omega} \end{aligned} \]

Let \(\pi\) denote the dual variables associated with the constraints \(\sum_{j \in \bar{\Omega}} a_j x_j = b\) . After solving the RMP, we could obtain the optimal dual values \(\pi^*\) , which is used to identify new columns to be added to the RMP.

9.3 Pricing Problem

Linear programming optimality condition tells us that a current solution is optimal if there is no variable with negative reduced cost. Note that the reduced cost of the variable \(x_j\) is defined as:

\[ \begin{aligned} \bar{c_j} = c_j - \pi^* a_j \end{aligned} \]

Then the subproblem aims to find a column with \(\bar{c_j} < 0\) , which could be formulated as:

\[ \begin{aligned} \text{min.} &\quad \bar{c_j} \\ \text{s.t.} &\quad \bar{c_j} = c_j - \pi^* a_j \\ &\quad j \in \Omega \backslash \bar{\Omega} \end{aligned} \]

This problem is also called the pricing problem.

9.4 Algorithm Workflow

Figure  9.1 shows the workflow of the column generation algorithm. Here’s a detailed workflow of how the column generation algorithm typically operates:

• Identify a subset of columns to initialize the RMP. This subset should still allow for a feasible solution to the problem, though not necessarily optimal.
• Solve the RMP using a linear programming solver to find an initial solution. This solution provides values for the objective function and dual variables, which are used to evaluate the potential of other columns not included in the RMP.
• Based on the dual prices obtained from the RMP, the subproblem is formulated to identify new columns that have the potential to improve the objective of the master problem. The subproblem is typically specific to the application domain, such as route generation in vehicle routing problems.
• The goal here is to find columns whose reduced costs indicate that they can improve the objective function if added to the RMP.
• If the subproblem generates new columns that can improve the solution, these columns are added to the RMP. If no such columns are found, the current solution to the RMP is optimal under the current column set.
• The process returns to step 2, where the RMP is solved again with the new set of columns. This iterative process continues until the pricing problem indicates that no further improvements can be made (i.e., no columns with negative reduced cost can be found).
• The algorithm stops when either no new improving columns can be generated, or another stopping criterion (such as a maximum number of iterations or a satisfactory solution quality) is reached.
• The final solution of the RMP, after the last iteration, represents the best solution to the overall problem, considering all the columns evaluated during the process.

We will illustrate the usage of column generation in the following chapters.

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to  upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

• We're Hiring!
• Help Center

Column Generation for a UAV Assignment Problem with Precedence Constraints

We apply column generation with branch-and-price optimization to a multi-target, multi-task assignment problem, with precedence constraints. Column generation transforms the nonlinear program with separable costs and constraints into a linear program. This reformulation divides the original problem into a number of smaller problems, where one of these smaller problems accounts for the coupling constraints between agents and must be known by every agent. All other divisions consider local constraints affecting only one agent; these smaller problems are known by only the one corresponding agent. Because of this reformulation, the assignment problem can be solved in a distributed manner. A theorem is proven which details the central analytical result of the paper, allowing a nonlinear program to be reformulated as a linear program. Simulation results for a multi-target, single-task assignment problem, as well as a multi-target, multi-task assignment problem with precedence constraints are presented.

Related Papers

Optimization Letters

Msc. Thesis - Middle East Technical University

fatih semiz

In the recent years, unmanned aerial vehicles (UAVs) have started to be utilized as a first choice for high risk and long duration tasks, because UAVs are cheaper, they are hard to be noticed and they can perform long duration jobs. Furthermore, the utilization of UAVs ensures to reduce the risk to the human life. Examples of these kind of missions are signal collection, surveillance and reconnaissance and combat support missions. It is valuable to develop a fully autonomous UAV fleet to perform these kind of tasks when it is needed, because these kind of missions usually start at unexpected times. Another problem which is in the set of high risk and long duration tasks is, multiple constraint UAV scheduling and target assignment problem. In this problem, a fleet of UAVs are supposed to traverse a set of target areas in a limited area. The targets are only available in certain time windows and need to be traversed in these time periods. Moreover, for some large target areas multiple UAVs are needed to perform the task. The objective of this problem is to find a complete scheduling and UAV-target assignment that minimizes the total fuel consumption of the UAVs. This problem is a highly critical real time problem and needs to be solved in a fast manner. Because of this, methods doing exhaustive search are infeasible for this problem. Most of the methods in the literature, tries to solve this problem by evolutionary approaches. In this thesis, we develop an algorithmic method to solve this problem. This method uses divide and conquer method to solve this problem. By this way, the problem is transformed into a combination of multiple small problems. We designed a method to convert these small problems into transportation problems. Each transportation problem is solved with simplex algorithm. The method proposed is compared with various methods and has been shown to provide fast, acceptably optimal and reliable results.

nuri ozalp , Ugur Ayan

This research is focused on the cooperative multi-task assignment problem for heterogeneous UAVs, where a set ofmultiple tasks, each requiring a predetermined number of UAVs,have to be completed at specific locations. We modeled this as anoptimization problem to minimize the number of uncompletedtasks while also minimizing total airtime and total distancetraveled by all the UAVs. By taking into account the UAV flightcapacities. For the solution of the problem, we adopted a multi-Traveling Salesman Problem (mTSP) method [1] and designed anew genetic structure for it so that it can be applied to cooperativemulti-task assignment problems. Furthermore, we developed twodomain specific mutation operators to improve the quality of thesolutions in terms of number of uncompleted tasks, total airtimeand total distance traveled by all the UAVs. The simulationexperiments showed that these operators significantly improve thesolution quality. Our main contributions are the application of theMulti Structure Genetic Algorithm (MSGA) to cooperative multi-task assignment problem and the development of two novelmutation operators to improve the solution of MSGA.

Ahmed Kamel

arpita sinha

AIAA Guidance, Navigation, and Control Conference

Aditya Undurti

Recent Developments in …

Kendall Nygard

Computers & Operations Research

Rakesh Nagi

Infotech@Aerospace 2012

Kelly Cohen

Loading Preview

Sorry, preview is currently unavailable. You can download the paper by clicking the button above.

RELATED PAPERS

S. Lacroix , Rachid Alami

IEEE Conference on Decision and Control and European Control Conference

Mariam Faied

Journal of Intelligent & …

Craig Tovey

International Journal of Robust and Nonlinear Control

AIAA Guidance, Navigation, and Control Conference and Exhibit

Arthur Richards

51st AIAA Aerospace Sciences Meeting including the New Horizons Forum and Aerospace Exposition

2020 Winter Simulation Conference (WSC)

Carles Serrat

International Conference on Robotics and Automation

Vijay Kumar

International Journal of Control

Leonardo Giovanini

2011 IEEE International Conference on Robotics and Automation

Katia Sycara

Proceedings of the 2003 American Control Conference, 2003.

Yoshiaki Kuwata

IEEE Transactions on Automation Science and Engineering

Michael Goodrich

AIAA Infotech@Aerospace 2010

Raymond W Holsapple

Engineering Applications of Artificial Intelligence

Edison Pignaton de Freitas

Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference

John-paul Clarke

Rafael Santos , N. GabasJunior

Eloi Pereira

Unmanned Systems

Decision and Control, 2003. …

Jeremi Gancet

International Journal of Design & Nature and Ecodynamics

Petr Skobelev

Operations Research

Giovanni Righini

RELATED TOPICS

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Computer Science
• Academia ©2024

A column-generation technique for the long-haul crew-assignment problem

New citation alert added.

This alert has been successfully added and will be sent to:

You will be notified whenever a record that you have chosen has been cited.

To manage your alert preferences, click on the button below.

New Citation Alert!

Please log in to your account

Information & Contributors

Bibliometrics & citations, view options.

• Aydemir-Karadag A Dengiz B Bolat A (2013) Crew pairing optimization based on hybrid approaches Computers and Industrial Engineering 10.1016/j.cie.2011.12.005 65 :1 (87-96) Online publication date: 1-May-2013 https://dl.acm.org/doi/10.1016/j.cie.2011.12.005
• Chen Q Lim A Zhu W (2011) A greedy heuristic for airline crew rostering Proceedings of the 24th international conference on Industrial engineering and other applications of applied intelligent systems conference on Modern approaches in applied intelligence - Volume Part II 10.5555/2025816.2025840 (237-245) Online publication date: 28-Jun-2011 https://dl.acm.org/doi/10.5555/2025816.2025840
• Jütte S Albers M Thonemann U Haase K (2011) Optimizing Railway Crew Scheduling at DB Schenker Interfaces 10.1287/inte.1100.0549 41 :2 (109-122) Online publication date: 1-Mar-2011 https://dl.acm.org/doi/10.1287/inte.1100.0549
• Show More Cited By

Index Terms

Mathematics of computing

Discrete mathematics

Graph theory

Network flows

Mathematical analysis

Mathematical optimization

Continuous optimization

Linear programming

Theory of computation

Design and analysis of algorithms

Graph algorithms analysis

Recommendations

A column generation approach for sonet ring assignment.

In this article we consider the SONET ring assignment problem (SRAP) presented in [7]. The authors pointed out the inadequacy of solving SRAP instances using their integer programming formulation and commercial linear programming solvers. Similar ...

WDM-PONs Hold Promise for the Long Haul

As they face challenging times, networking-service providers are looking to save money by studying the use of relatively new wavelength-division-multiplexing-based passive optical networks to create more efficient systems that increase data rates.

A column generation heuristic for a dynamic generalized assignment problem

This paper studies the dynamic generalized assignment problem (DGAP) which extends the well-known generalized assignment problem by considering a discretized time horizon and by associating a starting time and a finishing time with each task. Additional ...

Information

Published in.

IBM Scientific amp; Technical Solutions, Rome, Italy

Univ. of California at Berkeley

John Wiley & Sons, Inc.

United States

Publication History

Contributors, other metrics, bibliometrics, article metrics.

• 7 Total Citations View Citations
• 0 Total Downloads
• Downloads (Last 12 months) 0
• Downloads (Last 6 weeks) 0
• Gao C Johnson E Smith B (2009) Integrated Airline Fleet and Crew Robust Planning Transportation Science 10.1287/trsc.1080.0257 43 :1 (2-16) Online publication date: 1-Feb-2009 https://dl.acm.org/doi/10.1287/trsc.1080.0257
• Vaidyanathan B Jha K Ahuja R (2007) Multicommodity network flow approach to the railroad crew-scheduling problem IBM Journal of Research and Development 10.1147/rd.513.0325 51 :3 (325-344) Online publication date: 1-May-2007 https://dl.acm.org/doi/10.1147/rd.513.0325
• Emden-Weinert T Proksch M (1999) Best Practice Simulated Annealing for the Airline Crew Scheduling Problem Journal of Heuristics 10.1023/A:1009632422509 5 :4 (419-436) Online publication date: 1-Dec-1999 https://dl.acm.org/doi/10.1023/A%3A1009632422509
• Vance P Barnhart C Johnson E Nemhauser G (1997) Airline Crew Scheduling Operations Research 10.1287/opre.45.2.188 45 :2 (188-200) Online publication date: 1-Apr-1997 https://dl.acm.org/doi/10.1287/opre.45.2.188

View options

Login options.

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Share this publication link.

Copying failed.

Share on social media

Affiliations, export citations.

• Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download
• Download citation
• Copy citation

We are preparing your search results for download ...

We will inform you here when the file is ready.

Your file of search results citations is now ready.

Your search export query has expired. Please try again.

• DOI: 10.1007/s00186-024-00856-1
• Corpus ID: 269473115

Column generation based solution for bi-objective gate assignment problems

• G. Das , Fatma Gzara
• Published in Math. Methods Oper. Res. 29 April 2024
• Mathematics
• Math. Methods Oper. Res.

One Citation

Special issue on exact and approximation methods for mixed-integer multi-objective optimization, 33 references, exact and heuristic solution approaches for the airport gate assignment problem, using submodularity within column generation to solve the flight-to-gate assignment problem, a review on airport gate assignment problems: single versus multi objective approaches, a tutorial on multiobjective optimization: fundamentals and evolutionary methods, an adaptive large neighborhood search heuristic for solving a robust gate assignment problem, study on an improved adaptive pso algorithm for solving multi-objective gate assignment, solving the gate assignment problem through the fuzzy bee colony optimization, new multi objective models for the gate assignment problem, a non-dominated sorting genetic algorithm approach for optimization of multi-objective airport gate assignment problem, multiobjective optimization in the airport gate assignment problem, exact versus evolutionary multiobjective optimization, related papers.

Showing 1 through 3 of 0 Related Papers