generalized assignment problem (gap)

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