## 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.

## DGAP - The Dynamic Generalized Assignment Problem

- Published: January 1997
- Volume 69 , pages 227–239, ( 1997 )

## Cite this article

- Konstantin Kogan &
- Avraham Shtub

292 Accesses

20 Citations

Explore all metrics

The Generalized Assignment Problem (GAP) is a well-known operations research model. Given a set of tasks to be assigned to a group of agents and the cost of performing each task by each agent, the model allocates tasks to agents to minimize the total cost subject to the availability of a single resource type. The single resource is consumed by the agents when performing these tasks. In this paper, we add the impact of time to the model assuming that each task has a due date, and inventory cost as well as shortage cost is incurred when a task is finished ahead or after its due date, respectively. We formulate the continuous-time op-timal control model of the problem where identical tasks are grouped into jobs (or batches), each job is performed by each agent with a fixed (production) rate, while due dates are transformed into demand. As a result, analytical properties of the optimal behavior of such a dynamic system are derived. Based on those properties, an efficient time-decomposition procedure is developed to solve the problem.

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

## Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

## Similar content being viewed by others

## An exhaustive review of the metaheuristic algorithms for search and optimization: taxonomy, applications, and open challenges

## Iterative MILP algorithm to find alternate solutions in linear programming models

## Survey on Lagrangian relaxation for MILP: importance, challenges, historical review, recent advancements, and opportunities

F.S. Hillier and G.J. Lieberman, Operations Research , 3rd ed., Holden-Day, 1980.

G.T. Ross and R.M. Soland, A branch and bound algorithm for the Generalized Assignment Problem, Math. Programming 8(1975)91.

Google Scholar

R.M. Nauss, An efficient algorithm for the 0–1 knapsack problem, Management Science 23 (1976)27.

S. Martello and P. Toth, An upper bound for the zero–one knapsack problem and branch and bound algorithm, European Journal of Operations Research 1(1977)168.

T.D. Klastorin, An effective subgradient algorithm for the Generalized Assignment Problem, Computers and Operations Research 6(1979)155.

E. Balas and E. Zemel, An algorithm for large zero–one knapsack problems, Operations Research 28(1980)1130.

A. Shtub, L.J. LeBlanc and C. Ziyong, Scheduling programs with repetitive projects: A comparison of a simulated annealing, a genetic and pair-wise swap algorithms, European Journal of Operational Research (to appear).

J.G. Kimemia and S.B. Gershwin, An algorithm for the computer control of a flexible manufacturing system, IEE Transactions 15(1983)353.

E. Khmelnisky, K. Kogan and O. Maimon, A maximum principle based method for scheduling in a flexible manufacturing system, Discrete Events Dynamic Systems 5(1985)343.

J.B. Sousa and F.L. Pereira, A hierarchical framework for the optimal flow control in manufacturing systems, in: Proceedings of the 3rd International Conference on Computer Integrated Manufacturing , IEEE Computer Society Press, Los Alamitos, 1992, p. 278.

Download references

You can also search for this author in PubMed Google Scholar

## Rights and permissions

Reprints and permissions

## About this article

Kogan, K., Shtub, A. DGAP - The Dynamic Generalized Assignment Problem. Annals of Operations Research 69 , 227–239 (1997). https://doi.org/10.1023/A:1018933012422

Download citation

Issue Date : January 1997

DOI : https://doi.org/10.1023/A:1018933012422

## Share this article

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

- Dynamic System
- Operation Research
- Control Model
- Assignment Problem
- Research Model
- Find a journal
- Publish with us
- Track your research

## IMAGES

## VIDEO

## COMMENTS

In applied mathematics, the maximum generalized assignment problem is a problem in combinatorial optimization.This problem is a generalization of the assignment problem in which both tasks and agents have a size. Moreover, the size of each task might vary from one agent to the other. This problem in its most general form is as follows: There are a number of agents and a number of tasks. Any ...

An assignment is a mapping σ: J → I, where σ(j) = i means that job j is assigned to agent i. Then the generalized assignment problem (GAP) is formulated as follows: minimize cost(σ) = ∑ j∈J cσ(j),j subject to ∑ j∈J σ(j)=i aij ≤ bi, ∀i ∈ I. (1) The GAP is known to be NP-hard, since the partition problem of a given set of ...

The generalized assignment problem (GAP) seeks the minimum cost assignment of n tasks to m agents such that each task is assigned to precisely one agent subject to capacity restrictions on the agents. The formulation of the problem is: where \ ( c_ {ij} \) is the cost of assigning task j to agent i , \ ( a_ {ij} \) is the capacity used when ...

The generalized assignment problem (GAP) asks to assign n clients to m servers in such a way that the assignment cost is minimized, provided that all clients are assigned to a server and that the capacity of each server is not exceeded. It is a problem that appears, by itself or as a subproblem, in a very high number of practical applications and has therefore been intensively studied.

The Generalized Assignment Problem 1.1 Introduction The generalized assignment problem (GAP) asks to assign n clients to m servers in such a way that the assignment cost is minimized, provided that all clients are assigned to a server and that thecapacityof each server is not exceeded. A mathematical model can be obtainedby deﬁning:1

cost of processing these jobs. The following is a natural LP relaxation for this problem known as Generalized Assignment Problem (GAP): min P i;j c Pijx ij P i x ij = 1 1 j n j p ijx ij T 1 i m x ij 0 Note that even to detect if there is a feasible schedule (respecting the deadline bound T) is NP-hard. Therefore, we cannot have an approximation ...

The generalized assignment problem (GAP) is the problem of determining an assignment of J jobs to M capacity constrained machines, such that each job is assigned to exactly one machine, while total costs are minimized. It has applications in e.g. routing (Fisher and Jaikumar. 1981),

the generalized assignment problems (GAP). GAP is a generic form of linear sum assignment problem (LSAP) and is more challenging to solve owing to the presence of both equality and inequality constraints. We propose a novel deep unsupervised learning (DUL) approach to solve GAP in a time-efﬁcient manner.

The classical generalized assignment problem (GAP) may be stated as finding a minimum-cost assignment of tasks to agents such that each task is assigned to exactly one agent and such that each agent's resource capacity is honored. This NP-hard problem has applications that include job scheduling, routing, loading for flexible manufacturing ...

We analyze the generalized assignment problem (GAP) in an environment where val-uations are private information of distributed decision makers.1 In GAP, a set of m items has to be assigned to a set of n bins. Each bin associates a different value and weight to each item and has a limited capacity. An allocation may assign each bin a

The generalized assignment problem (cf., for example, [1], [2]) is a classical generalization of both the (multiple) knapsack problem and the bin packing problem. In the classical version of GAP, one is given m bins, a capacity Bj for each bin j, and n items such that each item i has size si,j and yields profit pi,j when packed into bin j.

The Generalized Assignment Problem (GAP) is the problem of finding the minimal cost assignment of jobs to machines such that each job is assigned to exactly one machine, subject to capacity restrictions on the machines. We propose a new stochastic model for the GAP.

The well-known generalized assignment problem (GAP) is to achieve the optimal assignment between agents and tasks where each task is assigned to an agent exactly once and the capacity restrictions are respected. In many real-world applications, the assignment costs between agents and tasks are affected by several factors and could be unstable ...

In the special case in which all the agents' budgets and all tasks' costs are equal to 1, this problem reduces to the assignment problem. When the costs and profits of all tasks do not vary between different agents, this problem reduces to the multiple knapsack problem. If there is a single agent, then, this problem reduces to the knapsack problem.

The well-known generalized assignment problem (GAP) involves the identification of a minimum-cost assignment of tasks to agents when each agent is constrained by a resource in limited supply. The multi-resource generalized assignment problem (MRGAP) is the generalization of the GAP in which there are a number of different potentially ...

We present a simple family of algorithms for solving the Generalized Assignment Problem (GAP). Our technique is based on a novel combinatorial translation of any algorithm for the knapsack problem into an approximation algorithm for GAP. If the approximation ratio of the knapsack algorithm is α and its running time is O ( f ( N)), our ...

Maximum Generalized Assignment Problem (GAP): Given a set of bins with capacity constraint and a set of items that have a possibly different size and value for each bin, pack a maximum-valued subset of items into the bins. This problem has several applications in inventory planning. Distributed CachingProblem(DCP): This problemmo-

The generalized assignment problem (GAP) and its special cases multiple knapsack1 and bin packing2 capture several fundamental optimization problems and have many practical applications in computer science, operations research, and related disciplines. The (ofﬂine) GAP is deﬁned as follows: Deﬁnition 1(Generalized Assignment Problem).

The generalized assignment problem (GAP) has been studied by numerous researchers over the past 30 years or so. Simply stated, one must find a minimum-cost assignment of tasks to agents such that each task is assigned to exactly one agent and such that each agent's resource capacity is honoured. The problem is known to be NP-hard. In this paper, we study the elastic generalized assignment ...

Generalized Assignment Problem. 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; ... \ Model gap_standalone_model \ LP format - for model browsing. ...

This class of problems includes maximum generalized assignment problem (GAP)1 and a distributed caching problem (DCP) described in this paper. Given a /3-approximation algorithm for finding the highest value packing of a single bin, we give. (i) A polynomial-time LP-rounding based ((1 — l/e)/3)-approximation algorithm.

• The Generalized Assignment Problem (GAP). In GAP, we are given mjobs J, and nmachines I. The processing time of job jon machine iis p ij, and if it is allocated on machine i, it generates a revenue of w ijunits. On the other hand, every machine ihas a limit B iof the maximum time it can run for.

The generalized assignment problem (GAP) is another important extended version of the classical AS. The GAP is a well-known NP-hard combinatorial optimization problem [27]. It considers a situation in which n jobs have to been processed by m agents. The agent which is the generic term for machine, worker and so on in real systems has a capacity ...

The Generalized Assignment Problem (GAP) is a well-known operations research model. Given a set of tasks to be assigned to a group of agents and the cost of performing each task by each agent, the model allocates tasks to agents to minimize the total cost subject to the availability of a single resource type. The single resource is consumed by the agents when performing these tasks. In this ...