generalized assignment problem github

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.

5   Generalized Assignment Problem

Assignment problems are really everywhere, that is, if we look around carefully. For example, vehicle routing problem could be formulated as an assignment problem coupled with a traveling salesman problem for each vehicle. The job shop scheduling problem involves assigning job processes onto machines and optimizing the processes on each machine to minimize a certain criterion like makespan. In this chapter, we examine the generalized assignment problem and its solution approach via Lagrangian relaxation.

The Generalized Assignment Problem (GAP) is a well-known problem in operations research and combinatorial optimization. It is an extension of the classic assignment problem where a set of tasks needs to be assigned to a set of agents, with each task requiring a specific amount of resources from the assigned agent. However, in the generalized version, multiple agents can be assigned to a single task, and each agent may have a limit on the amount of resource it can contribute.

5.1 Formulation

Formally, the Generalized Assignment Problem can be defined as follows:

• A set of tasks, \(T = \{1, 2, ..., n\}\)
• A set of agents, \(A = \{1, 2, ..., m\}\)
• For each task \(i\) and agent \(j\) , a cost or profit \(c_{ij}\) associated with assigning task \(i\) to agent \(j\)
• For each task \(i\) and agent \(j\) , a resource requirement \(r_{ij}\) specifying the amount of resource needed from agent \(j\) to complete task \(i\)
• For each agent \(j\) , a capacity \(b_j\) specifying the maximum amount of resource that agent \(j\) can contribute

The goal is to find an assignment of tasks to agents that minimizes the total cost or maximizes the total profit, while ensuring that each task is assigned to one or more agents, and the total resource requirement of each agent does not exceed its capacity.

Mathematically, the GAP can be formulated as an integer linear programming problem. One possible formulation is as follows:

\[\begin{align} \text{min.} &\quad \sum_{i=1}^{n} \sum_{j=1}^{m} c_{ij} x_{ij} \label{gap-obj}\\ \text{s.t.} &\quad \sum_{j=1}^{m} x_{ij} = 1, \ \forall i = 1, 2, ..., n \label{gap-cons1}\\ &\quad \sum_{i=1}^{n} r_{ij} x_{ij} \leq b_j, \ \forall j = 1, 2, ..., m \label{gap-cons2}\\ &\quad x_{ij} \in \{0, 1\}, \ \forall i = 1, 2, ..., n, j = 1, 2, ..., m \label{gap-cons3} \end{align}\]

where \(x_{ij}\) is a binary decision variable that equals 1 if task \(i\) is assigned to agent \(j\) , and 0 otherwise.

The first set of constraints ensures that each task is assigned to exactly one agent, and the second set of constraints ensures that the total resource requirement of each agent does not exceed its capacity.

Solving the GAP can be computationally challenging, especially for large instances, as it is a generalization of the classic assignment problem, which is known to be polynomial-time solvable. Various algorithms and heuristics, such as branch and bound, dynamic programming, and approximation algorithms, can be employed to find feasible or optimal solutions to the GAP.

5.2 Lagrangian Relaxation

The essence of Lagrangian relaxation is to choose some ‘hard’ constraints in the original model formulation and put them into the objective function. In the meantime, Lagrange multipliers are used to penalize the violations of these constraints. In the GAP formulation, we could choose the constraints \(\eqref{gap-cons1}\) and put them into the objective function, which gives us the corresponding Lagrangian relaxation:

\[\begin{align} LR(v): \text{min.} &\quad \sum_{i=1}^{n} \sum_{j=1}^{m} c_{ij} x_{ij} + \sum_{i=1}^{n} v_i (\sum_{j=1}^{m} x_{ij} - 1) \label{gap-lr-obj}\\ \text{s.t.} &\quad \sum_{i=1}^{n} r_{ij} x_{ij} \leq b_j, \ \forall j = 1, 2, ..., m \label{gap-lr-cons1}\\ &\quad x_{ij} \in \{0, 1\}, \ \forall i = 1, 2, ..., n, j = 1, 2, ..., m \label{gap-lr-cons2} \end{align}\]

In the above formulation, \(v_i\) is the Lagrange multiplier associated with each task \(i\) . Note that the optimal objective value of \(LR(v)\) for a given \(v\) serves as a lower bound of the original problem. Our goal is then to find the best value of \(v\) such that the best lower bound is obtained for the original problem.

5.3 Implementation

Optimization is fun, especially when we turn our curated models and algorithms into computer codes using our favorite programming languages. In this section, we will solve some GAP instances using Lagrangian Relaxation!

5.3.1 Benchmarking instances

All the benchmarking instances we solve here are taken from the OR-Library . There are a total of 16 data files, among which the first 12 data files are gap1, gap2, …, gap12, and the remaining 4 data files are gapa, gapb, gapc and gapd.

All the data files are formatted as follows:

• The total number of problem instances in the data set ( \(P\) )
• The number of agents ( \(m\) ), number of tasks ( \(n\) )
• The cost of allocating task \(j\) to agent \(i\) ( \(j = 1,...,n\) )
• The resource consumed in allocating task \(j\) to agent \(i\) ( \(j = 1,...,n\) )
• The resource capacity of agent \(i\) ( \(i = 1,...,m\) )

Since we have the luxury of unlimited space in this online book, I will show the full content of the data file gap1.txt . This file contains 5 GAP instances and all of them have the same number of agents (5) and tasks (15).

Listing  5.1 shows the python code that reads in all the instances from a data file and saves them into a Python list.

Below we read the data file ‘gap1.txt’ and display the first instance.

5.3.2 Solve the original problem

In this section, we use SCIP to solve the original formulation of the GAP, which is given in Listing  5.3 .

5.3.3 Solve the Lagrangian relaxation with fixed multipliers

5.3.4 approximating the best lagrange multipliers, 5.3.4.1 subgradient search, 5.3.4.2 surrogate subgradient search, 5.3.5 performance comparison.

5.4 Alternative Relaxation

In this section, we explore the performance of Lagrangian Relaxation if a different set of constraints were lifted into the objective function. The reformulation takes on the following form:

\[\begin{align} q(u) = \text{min.} &\quad \sum_{i=1}^{n} \sum_{j=1}^{m} c_{ij} x_{ij} + \sum_{j=1}^m u_j (\sum_{i=1}^{n} r_{ij} x_{ij} - b_j) \label{gap-lr2-obj}\\ \text{s.t.} &\quad \sum_{j=1}^{m} x_{ij} = 1, \ \forall i = 1, 2, ..., n \label{gap-lr2-cons1}\\ &\quad x_{ij} \in \{0, 1\}, \ \forall i = 1, 2, ..., n, j = 1, 2, ..., m \label{gap-lr2-cons3} \end{align}\]

The corresponding dual problem is defined as below:

\[\begin{align} \text{max.} &\quad q(u) \\ \text{s.t.} &\quad u \geq 0 \end{align}\]

Note that any violation of the relaxed constraints is penalized by a positive \(u\) multiplier.

5.5 Comparison with Linear Programming Relaxation

Now we have two forms of Lagrangian Relaxations and we give here some empirical performance evidence of the strength of this relaxation against linear programming relaxation.

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

How to solve large scale generalized assignment problem

I am looking for a way to solve a large scale Generalized assignment problem (To be precise, it is a relaxation of the Generalized assignment problem, because the second constraint has $\le$ instead of $=$ ). Here, $m$ is the number of agents and $n$ is the number of tasks. $$ \begin{aligned} &\text{maximize} && \sum_{i}^{m} \sum_{j}^{n} p_{ij}x_{ij} \\\ &\text{subject to} && \sum_{j}^{n} w_{ij}x_{ij} \le t_{i} &&& \forall i \\\ & && \sum_{i}^{m} x_{ij} \le 1 &&& \forall j \\\ & && x_{ij} \in \{0, 1\} \end{aligned} $$

• $m \le 1,000$
• $n \le 10,000,000$
• $p_{ij} \le 1,000$
• $w_{ij} \le 1,000$
• $t_i \le 200,000$
• valid agent-task pair(i.e. number of non zero $p_{ij}$ ) $\le 200,000,000$
• time limit : 6 hours

Generalized assignment problem is NP-hard, so I'm not trying to find an exact solution. Are there any approximation algorithm or heuristic to solve this problem?

Also, are there any other approaches to solving large scale NP-hard problems? For example, I was wondering if it is possible to reduce the number of variables by clustering agents or tasks, but I did not find such a method.

• assignment-problem

• $\begingroup$ All else failing, there is the greedy heuristic: sort the $p_{ij}$ in descending order, then make assignments in that order, tracking the remaining capacity of each agent and skipping assignments that would exceed that capacity. I did not put this in as an answer because it is such a low hanging fruit. $\endgroup$ –  prubin ♦ Commented Jul 29, 2021 at 18:13
• $\begingroup$ The problem that you wrote is not exactly the Generalized Assignment Problem, because the second set of constraints has $\le$ instead of $=$. This makes the problem much easier since finding a feasible solution is not an issue anymore in this case. Is it what you meant to write? $\endgroup$ –  fontanf Commented Jul 29, 2021 at 20:22
• $\begingroup$ @prubin Thank you. If there is no other way, I will use greedy algorithm. $\endgroup$ –  user5966 Commented Jul 30, 2021 at 6:02
• $\begingroup$ @fontanf Yes, I'm trying to solve the relaxation of the Generalized assignment problem. I've added this to the post $\endgroup$ –  user5966 Commented Jul 30, 2021 at 6:11

2 Answers 2

The instances you plan to solve are orders of magnitude larger than the ones from the datasets used in the scientific literature on the Generalized Assignment Problem. The largest instances of the literature have $m = 80$ and $n = 1600$ . Most algorithms designed for these instances won't be suitable for you.

What seems the most relevant in your case are the polynomial algorithms described in "Knapsack problems: algorithms and computer implementations" (Martello et Toth, 1990):

• Greedy: sort all agent-task pairs according to a given criterion, and then assign greedily from best to worst the unassigned tasks. Complexity: $O(n m \log (n m))$
• Regret greedy: for all tasks, sort its assignments according to a given criterion. At each step, assign the task with the greatest difference between its best assignment and its second-best assignment, and update the structures. Complexity: $O(n m \log m + n^2)$

Various sorting criteria have been proposed: pij , pij/wij , -wij , -wij/ti ... -wij and -wij/ti are more suited for the case where all items have to be assigned. In your case pij and pij/wij might yield good results

Then, they propose to try to shift each task once to improve the solution. With at most one shift per task, the algorithms remain polynomial, but you can try more shifts if you have more time.

Note that these algorithms might be optimized if not all pairs are possible, as you indicate in your case.

I have some implementations here for the standard GAP (and a min objective). You can try to play with them to get an overview of what might work or not in your case

You could try using the greedy heuristic to get an initial solution and then try out one of the many neighborhood-search type metaheuristics. I mentioned sorting on $p_{ij}$ in a comment, but it might (or might not) be better to sort on $p_{ij}/w_{ij}$ (or, time permitting, try both and pick the better solution). For improving on the starting solution, GRASP and simulated annealing would be possibilities. Tabu search is popular with some people, but the memory requirements of maintaining a table of tabu solutions might be prohibitive. I'm fond of genetic algorithms, but I think we can rule out a GA (or other "evolutionary" metaheuristic) based on memory considerations. Personally, I'd be tempted to check out GRASP first.

Your Answer

Sign up or log in, post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged heuristics assignment-problem or ask your own question .

• Featured on Meta
• User activation: Learnings and opportunities
• Join Stack Overflow’s CEO and me for the first Stack IRL Community Event in...

Hot Network Questions

• How much technological progress could a group of modern people make in a century?
• "Truth Function" v.s. "Truth-Functional"
• Should I write an email to a Latino teacher working in the US in English or Spanish?
• How to respond to subtle racism in the lab?
• Maximize finds solution outside the constraint
• Big Transition of Binary Counting in perspective of IEEE754 floating point
• Practice test paper answers all seem incorrect, but provider insists they are ... what am i missing?
• If a friend hands me a marijuana edible then dies of a heart attack am I guilty of felony murder?
• How do elected politicians get away with not giving straight answers?
• When deleting attribute from GDB file all the fields in the remaining attributes get deleted as well in QGIS
• Should one pay more than one fifth (20%) for goods or services from a fellow Jew?
• How does conservation of energy work with time dilation?
• Navigating career options after a disastrous PhD performance and a disappointed advisor?
• Inspector tells me that the electrician should have removed green screw from the panel
• Where did Gomez Addams get his last name?
• How to make conditions work in Which?
• Finding Exact Trigonometric Values
• If Act A repeals another Act B, and Act A is repealed, what happens to the Act B?
• Is it possible for one wing to stall due to icing while the other wing doesn't ice?
• Identify this 6 pin IC
• Why doesn't SiLU suffer from a worse version of a "dying ReLU" problem?
• What is a natural-sounding verb form for the word dorveille?
• The quest for a Wiki-less Game
• Is this a misstatement of Euclid in Halmos' Naive Set Theory book?

• Stack Overflow for Teams Where developers & technologists share private knowledge with coworkers
• Advertising & Talent Reach devs & technologists worldwide about your product, service or employer brand
• OverflowAI GenAI features for Teams
• OverflowAPI Train & fine-tune LLMs
• Labs The future of collective knowledge sharing
• About the company Visit the blog

Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Get early access and see previews of new features.

How to solve a (generalized) assignment problem?

Assume the following initial assignment data:

>>> unnamed_3.show() +---------+-------------+-----+-------+ | Client| Industry|Value|Advisor| +---------+-------------+-----+-------+ |Company A|Manufacturing| 3000| AD 1| |Company B|Manufacturing| 2000| AD 1| |Company C| Finance| 1000| AD 1| |Company D| Service| 2000| AD 2| |Company E| Health| 3000| AD 2| |Company F| Service| 2000| AD 3| |Company G| Finance| 4000| AD 3| |Company H|Manufacturing| 1000| AD 3| +---------+-------------+-----+-------+

i.e. we have clients from a certain industry and with a certain value assigned to an advisor.

The goal is to harmonize the Client - Advisor assignment in a way that the number of industries per advisor gets minimized while preserving as many of the current clients as possible (e.g. "AD1" has most of his clients in Manufacturing (see counts), so keeping that industry is "preferable").

Additional constraints are that each Advisor should get 20 clients at maximum and clients should be distributed as equally as possible (in terms of value) between advisors so that total sum of value is similar between advisors. As a last constraint, clients that cannot stay with their initial advisor should get at least an industry expert as advisor (e.g. if "Company C" has to leave "AD 1" it would preferably go to "AD 3", also an expert for finance):

>>> unnamed_3.groupby('Advisor','Industry').count().sort("Advisor").show() +-------+-------------+-----+ |Advisor| Industry|count| +-------+-------------+-----+ | AD 1|Manufacturing| 2| | AD 1| Finance| 1| | AD 2| Service| 1| | AD 2| Health| 1| | AD 3| Finance| 1| | AD 3|Manufacturing| 1| | AD 3| Service| 1| +-------+-------------+-----+

I hope that I formulated the problem in a way that you can understand it, but since this is my first question at stack overflow, please let me know if you need more information. Reading through other posts here, I have the feeling that this problem is closely related to a generalized assignment or binning/partitioning problem, however not fully matching any of them.

Any help on how to approach solving this problem is highly appreciated!

Many thanks!

Referring to David's answer maybe I can reformulate a bit and make things clearer here. My initial thought was that this could be done by something like a min-cost problem in a way that we connect clients nodes only with ADs from the industry sector giving cheaper weights to their initial advisors. I think this would tackle objectives 2 and 4. The client limitation per AD could also be easily fulfilled by setting the capacity of an advisor node to 20. But would I don't get in is the balancing part of the values.

• optimization
• linear-programming

• 1 This is a good start, but you’ve formulated multiple objectives that in general have to be traded off against one another: 1. Minimize industries per advisor 2. Minimize switches 3. Minimize differences in advisor total values 4. Minimize switches to non-expert advisors. I assume that 20 clients is a hard constraint, but if not 5. Minimize clients per advisor in excess of 20. By designing an optimization algorithm, we would have to decide for you (perhaps implicitly) the relative value of these things, but we really can’t. –  David Eisenstat Commented Nov 9, 2021 at 12:53
• Hi David, thank you for your answer! I edited the formulation a bit. Because of the balancing part I was thinking of the binning problem, but probably with an additional constraint/weight for bin preference? Does that make sense? Does something like this exist? –  jondon66 Commented Nov 10, 2021 at 9:13
• Probably not, but you can make one yourself with mixed integer programming. –  David Eisenstat Commented Nov 11, 2021 at 0:30

Know someone who can answer? Share a link to this question via email , Twitter , or Facebook .

Your answer.

Reminder: Answers generated by artificial intelligence tools are not allowed on Stack Overflow. Learn more

Sign up or log in

Post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Browse other questions tagged algorithm optimization linear-programming or ask your own question .

• The Overflow Blog
• The evolution of full stack engineers
• One of the best ways to get value for AI coding tools: generating tests
• Featured on Meta
• Join Stack Overflow’s CEO and me for the first Stack IRL Community Event in...
• User activation: Learnings and opportunities
• Staging Ground Reviewer Motivation
• What does a new user need in a homepage experience on Stack Overflow?

Hot Network Questions

• Is this a misstatement of Euclid in Halmos' Naive Set Theory book?
• Why doesn't SiLU suffer from a worse version of a "dying ReLU" problem?
• How much could gravity increase before a military tank is crushed
• Paying a parking fine when I don't trust the recipient
• Please help me identify my Dad's bike collection (80's-2000's)
• "Tail -f" on symlink that points to a file on another drive has interval stops, but not when tailing the original file
• Navigating career options after a disastrous PhD performance and a disappointed advisor?
• Why do so many great Tzaddikim die so young?
• What is the least number of colours Peter could use to color the 3x3 square?
• An English word for "visible side". (cooking term)
• Where did Gomez Addams get his last name?
• Why does friendship seem transitive with befriended function templates?
• Does hydrogen peroxide work as a rocket fuel oxidizer by itself?
• Best memory / storage solution for high read / write throughput application(s)?
• How do I go about writing a tragic ending in a story while making it overall satisfying to the reader?
• How to hold large sandstone tiles to cement wall while glue cures?
• Should one pay more than one fifth (20%) for goods or services from a fellow Jew?
• Can a V22 Osprey operate with only one propeller?
• Is there mathematical significance to the LaGuardia floor tiles?
• Practice test paper answers all seem incorrect, but provider insists they are ... what am i missing?
• What's wrong with this solution?
• jq - ip addr show in tabular format
• Maximize finds solution outside the constraint
• Use of "them" in "…she fights for the rights and causes I believe need a warrior to champion them" by Taylor Swift

Subscribe to the PwC Newsletter

Join the community, edit social preview.

Add a new code entry for this paper

Remove a code repository from this paper, mark the official implementation from paper authors, add a new evaluation result row.

Remove a task

Add a method, remove a method, edit datasets, sample-based online generalized assignment problem with unknown poisson arrivals.

16 Feb 2023  ·  Zihao Li , Hao Wang , Zhenzhen Yan · Edit social preview

We study an edge-weighted online stochastic \emph{Generalized Assignment Problem} with \emph{unknown} Poisson arrivals. In this model, we consider a bipartite graph that contains offline bins and online items, where each offline bin is associated with a $D$-dimensional capacity vector and each online item is with a $D$-dimensional demand vector. Online arrivals are sampled from a set of online item types which follow independent but not necessarily identical Poisson processes. The arrival rate for each Poisson process is unknown. Each online item will either be packed into an offline bin which will deduct the allocated bin's capacity vector and generate a reward, or be rejected. The decision should be made immediately and irrevocably upon its arrival. Our goal is to maximize the total reward of the allocation without violating the capacity constraints. We provide a sample-based multi-phase algorithm by utilizing both pre-existing offline data (named historical data) and sequentially revealed online data. We establish its performance guarantee measured by a competitive ratio. In a simplified setting where $D=1$ and all capacities and demands are equal to $1$, we prove that the ratio depends on the number of historical data size and the minimum number of arrivals for each online item type during the planning horizon, from which we analyze the effect of the historical data size and the Poisson arrival model on the algorithm's performance. We further generalize the algorithm to the general multidimensional and multi-demand setting, and present its parametric performance guarantee. The effect of the capacity's (demand's) dimension on the algorithm's performance is further analyzed based on the established parametric form. Finally, we demonstrate the effectiveness of our algorithms numerically.

Code Edit Add Remove Mark official

Datasets edit.

This week: the arXiv Accessibility Forum

Help | Advanced Search

Computer Science > Machine Learning

Title: deep unsupervised learning for generalized assignment problems: a case-study of user-association in wireless networks.

Abstract: There exists many resource allocation problems in the field of wireless communications which can be formulated as 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-efficient manner. More specifically, we propose a new approach that facilitates to train a deep neural network (DNN) using a customized loss function. This customized loss function constitutes the objective function and penalty terms corresponding to both equality and inequality constraints. Furthermore, we propose to employ a Softmax activation function at the output of DNN along with tensor splitting which simplifies the customized loss function and guarantees to meet the equality constraint. As a case-study, we consider a typical user-association problem in a wireless network, formulate it as GAP, and consequently solve it using our proposed DUL approach. Numerical results demonstrate that the proposed DUL approach provides near-optimal results with significantly lower time-complexity.

Submission history

Access paper:.

• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

DBLP - CS Bibliography

Bibtex formatted citation.

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .

Gurobi Modeling Examples

Explore our modeling examples for the Gurobi Python API

Target audience

Data scientists, engineers, computer scientists, economists, and in general, professionals with a background in mathematical modeling and a basic knowledge of Python.

Goals of modeling examples

• Illustrate the broad applicability of mathematical optimization.
• Show how to build mathematical optimization models.

These modeling examples are coded using the Gurobi Python API and distributed as Jupyter Notebooks.

These modeling examples illustrate important capabilities of the Gurobi Python API, including adding decision variables, building linear expressions, adding constraints, and adding an objective function. They touch on more advanced features such as generalized constraints, piecewise-linear functions, and multi-objective hierarchical optimization. They also illustrate common constraint types such as “allocation constraints”, “balance constraints”, “sequencing constraints”, “precedence constraints”, and others.

The examples are from different business purposes and reflect different levels of building mathematical optimization models.

Introductory examples

The introductory examples walk you through the process of building a mathematical optimization model. The basic requirements are that you know Python and have a background in a discipline that uses quantitative methods.

• GDD 2023: Intro to Gurobipy: This tutorial was given at the Gurobi Days Digital 2023. It is an introduction to the Gurobi Python API Gurobipy. It walks you through the basics of Gurobipy and explains its usage with some small examples.
• Intro to Mathematical Optimization Modeling: This tutorial discusses the basics of mathematical modeling on the example of a simple assignment problem.
• Optimization 101: This tutorial is based on the Webinar on Optimization 101 for Data Scientists and consists of two modeling sessions with exercises and questions as well as a discussion of a use case.
• Airline Planning After Flight Disruption
• Music Recommendation
• Text Dissimilarity
• Power Generation

Beginner Examples

The notebooks at the beginner level assume you know Python and have some knowledge about building mathematical optimization models.

• 3D Tic-Tac-Toe: This example will show you how a binary programming model can be used to capture simple logical constraints.
• Cell Tower: In this example, you will learn how to define and solve a covering-type problem, namely, how to configure a network of cell towers to provide signal coverage to the largest number of people.
• Curve Fitting: Try this Jupyter Notebook Modeling Example to learn how you can fit a function to a set of observations.
• Facility Location: In this example, we will show you how to tackle a facility location problem that involves determining the number and location of warehouses that are needed to supply a group of supermarkets.
• Fantasy Basketball: This example combines machine learning and optimization modeling in fantasy basketball.
• Food Program: Transporting food in a global transportation network is a challenging undertaking. In this notebook, we will build an optimization model to set up a food supply chain based on real data from the UN World Food Program.
• Market Sharing: In this example, we will show you how to solve a goal programming problem that involves allocating the retailers to two divisions of a company in order to optimize the trade-offs of several market-sharing goals.
• Marketing Campaign Optimization: Companies across almost every industry are looking to optimize their marketing campaigns. In this Jupyter Notebook, we will explore a marketing campaign optimization problem that is common in the banking and financial services industry, which involves determining which products to offer to individual customers in order to maximize total expected profit while satisfying various business constraints.
• Offshore Wind Farming: In this example, we will learn how to solve an offshore wind power generation problem. The goal of the problem is to figure out which underwater cables should be laid to connect an offshore wind farm power network at a minimum cost.
• Supply Network Design 1: Try this Jupyter Notebook Modeling Example to learn how to solve a classic supply network design problem that involves finding the minimum cost flow through a network. We will show you how – given a set of factories, depots, and customers – you can use mathematical optimization to determine the best way to satisfy customer demand while minimizing shipping costs. In part 2, we additionally determine which depots to open or close in order to minimize overall costs.

Intermediate Examples

Examples at the intermediate level assume that you know Python and are familiar with the Gurobi Python API. In addition, you should have knowledge about building mathematical optimization models.

• Agricultural Pricing: Try this example to learn how to use mathematical optimization to tackle a common, but critical agricultural pricing problem: Determining the prices and demand for a country’s dairy products in order to maximize total revenue derived from the sales of those products. You will learn how to model this problem as a quadratic optimization problem using the Gurobi Python API and solve it using the Gurobi Optimizer.
• Linear Regression: In this example, you will learn how to perform linear regression with feature selection using mathematical programming. We will show you how to construct a mixed-integer quadratic programming (MIQP) model of this linear regression problem.
• Car Rental: This notebook will teach you how you can use mathematical optimization to figure out how many cars a car rental company should own and where they should be located every day to maximize weekly profits. Part 2 considers an extension on how mathematical optimization can be used to figure out in which locations a car rental company should expand repair capacity.
• Customer Assignment: This notebook is an intermediate version of the facility location problem. In addition, we show how machine learning can be used in the pre-processing so as to reduce the computational burden of big datasets.
• Economic Planning: In this example, you will discover how mathematical optimization can be used to address a macroeconomic planning problem that a country may face. The goal is to determine different possible growth patterns for the economy.
• Efficiency Analysis: How can mathematical optimization be used to measure the efficiency of an organization? Find out in this example, where you will learn how to formulate an Efficiency Analysis model as a linear programming problem.
• Electrical Power Generation: This model is an example of an electrical power generation problem (also known as a unit commitment problem). It selects an optimal set of power stations to turn on in order to satisfy anticipated power demand over a 24-hour time horizon. In part 2, the model is extended and adds the option of using hydroelectric power plants to satisfy demand.
• Factory Planning: In this example, we create an optimal production plan that maximizes profits. In part 2, we create an optimal production plan that will not only maximize profits but also determine the months in which to perform maintenance operations on the machines.
• Food Manufacturing: You will learn how to create an optimal multi-period production plan for a product that requires a number of ingredients – each of which has different costs, restrictions, and features. In part 2, additional constraints are considered that change the problem type from a linear program (LP) problem to a mixed-integer program (MIP) problem, making it harder to solve.
• Logical Design: In this example, you will learn how to solve a logical design problem, which involves constructing a circuit using the minimum number of NOR gates (devices with two inputs and one output) that will perform the logical function specified by a truth table.
• Mining: In this example, you will learn how to model and solve a multi-period production planning problem that involves optimizing the operations of a group of mines over a five-year period.
• Opencast Mining: This notebook shows a mathematical optimization problem to identify which excavation locations to choose in order to maximize the gross margins of extracting ore.
• Power Generation: Assume that we know the set of all available power plants and the demand for power for each hour of a day. We want to create a schedule to decide how much power each plant should generate, and when to switch the plants “on” and “off” in order to minimize the overall costs.
• Refinery: This model is an example of a production planning problem where decisions must be made regarding which products to produce and which resources to use.
• Technician Routing and Scheduling: Try this modeling example to discover how mathematical optimization can help telecommunications firms automate and improve their technician assignment, scheduling, and routing decisions in order to ensure the highest levels of customer satisfaction. You will learn how to formulate a multi-depot vehicle routing problem with time windows constraints.

Advanced Examples

For modeling examples at the advanced level, we assume that you know Python and the Gurobi Python API and that you have advanced knowledge of building mathematical optimization models. Typically, the objective function and/or constraints of these examples are complex or require advanced features of the Gurobi Python API.

• Constraint Optimization: In this example, we consider a constraint of an integer programming model where all the decision variables in the constraint are binary, the goal is to find another constraint involving the same binary variables that is logically equivalent to the original constraint, but that has the smallest possible absolute value of the right-hand side.
• Decentralization Planning: This model is an advanced version of a facility location problem. Given a set of departments of a company and potential cities where these departments can be located, we want to determine the “best” location of each department in order to maximize gross margins.
• Farm Planning: This is an example of an advanced production planning problem.
• Lost Luggage Distribution: This is an example of a vehicle routing problem with time windows. It involves helping a company figure out the minimum number of vans required to deliver pieces of lost or delayed baggage to their rightful owners and determining the optimal assignment of vans to customers.
• Manpower Planning: This notebook solves a staffing planning problem where choices must be made regarding recruitment, training, redundancy, and scheduling of staff.
• Milk Collection: This is an example of a capacitated vehicle routing problem. With only one tanker truck with limited capacity, you will need to determine the best possible route for the tanker to take to collect milk every day from a set of farms.
• Portfolio Selection Optimization: This model is an example of the classic Markowitz portfolio selection optimization model. We want to find the fraction of the portfolio to invest among a set of stocks that balances risk and return. It is a Quadratic Programming (QP) model with vector and matrix data for returns and risk, respectively.
• Pooling: Companies across numerous industries – including petrochemical refining, wastewater treatment, and mining – use mathematical optimization to solve the pooling problem. This problem can be regarded as a generalization of the minimum-cost flow problem and the blending problem.
• Protein Comparison: You will learn how to model the protein comparison problem as a quadratic assignment problem. It involves measuring the similarities of two proteins.
• Protein Folding: The problem pertains to a protein, which consists of a chain of amino acids. The objective is to predict the optimum folding of the chain.
• Traveling Salesman: This notebook covers one of the most famous combinatorial optimization problems in existence: the Traveling Salesman Problem (TSP). The goal of the TSP – to find the shortest possible route that visits each city once and returns to the original city – is simple, but solving the problem is a complex and challenging endeavor. This example uses the callback feature of Gurobi.
• Workforce Scheduling: In this notebook, we demonstrate how you can use mathematical optimization to generate an optimal workforce schedule that minimizes the number of temporary workers your company needs to hire and maximizes employee fairness. The problem is formulated as a multi-objective mixed-integer-programming (MIP) model and uses the multiple objectives feature of Gurobi.
• Yield Management: In this example, we will show you how an airline can use AI technology to devise an optimal seat pricing strategy. You will learn how to formulate this Yield Management Problem as a three-period stochastic programming problem.

Examples via Business Needs

• Marketing Campaign Optimization (beginner)
• Supply Network Design (beginner)
• Technician Routing and Scheduling (intermediate)
• Manpower Planning (advanced)
• Workforce Scheduling (advanced)
• Covid19 Facility Optimization (beginner)
• Yield Management (advanced)
• Price Optimization (introductory)
• Music Recommendation (introductory)
• Fantasy Basketball (beginner)
• Agricultural Pricing (intermediate)
• Linear Regression (intermediate)
• Food Program (beginner)
• Car Rental (intermediate)
• Economic Planning (intermediate)
• Factory Planning (intermediate)
• Food Manufacturing (intermediate)
• Farm Planning (advanced)
• Cell Tower (beginner)
• Facility Location (beginner)
• Customer Assignment (intermediate)
• Opencast Mining (intermediate)
• Decentralization Planning (advanced)
• Traveling Salesman (advanced)
• Airline Planning After Flight Disruption (introductory)
• Power Generation (intermediate)
• Portfolio Selection Optimization (advanced)
• Efficiency Analysis (intermediate)
• Electrical Power Generation (intermediate)
• Mining (intermediate)
• Refinery (intermediate)
• Curve Fitting (beginner)
• Constraint Optimization (intermediate)
• Lost Luggage Distribution (advanced)
• Milk Collection (advanced)
• Market Sharing (beginner)

It is also possible to browse through the examples w.r.t. difficulty level and business needs on the Gurobi website .

Run on Google Colab

You can access all the examples in Google Colab, which is a free, online Jupyter Notebook environment that allows you to write and execute Python code through your browser. You will need to be signed into a Google account to execute the notebooks. But you do not need an account if you just want to look at the notebooks. For each example, the respective colab link is given in the readme:

• To run the example the first time, choose “Runtime” and then click “Run all”.
• All the cells in the Jupyter Notebook will be executed.
• The example will install the gurobipy package. The Gurobi pip package includes a size-limited trial license equivalent to the Gurobi “online course” license. For most of the notebooks, this restricted license is sufficient to run them. For others, you will need a full license, see the license section below.
• You can also modify and re-run individual cells.
• For subsequent runs, choose “Runtime” and click “Restart and run all”.
• The Gurobi Optimizer will find the optimal solution of the modeling example. Check out the Colab Getting Started Guide for full details on how to use Colab Notebooks as well as create your own.

Run locally

• Clone the repository containing all examples or download it by clicking here
• Start Jupyter Notebook Server
• Open the particular notebook in Jupyter Notebook.
• The notebook will install the gurobipy package and other dependencies. The Gurobi pip package includes a size-limited trial license equivalent to the Gurobi “online course” license. For most of the notebooks, this restricted license is sufficient. For others, you will need a full license.

In order to run the Jupyter Notebooks you will need a Gurobi license. Most of the notebooks can be run using the “online course” license version of Gurobi. This is a limited license and restricts the number of allowed variables and constraints. This restricted license comes also with the gurobipy package when installing it via pip or conda. You can also request a full license, i.e., an evaluation license as a commercial user , or download a free license as an academic user . The latter two license types allow you to run all notebooks. All licenses can also be requested in the Gurobi User Portal after registering for a Gurobi account .

Download the repository

You can download the repository containing all examples by clicking here .

Index of modeling examples

• 3D Tic-Tac-Toe
• Agricultural Pricing
• Burrito Game
• Cutting Stock
• Constraint Optimization
• Covid19 Facility Optimization
• Curve Fitting
• Customer Assignment
• Decentralization Planning
• Drone Network
• Economic Planning
• Efficiency Analysis
• Electrical Power Generation
• Facility Location
• Factory Planning
• Fantasy Basketball
• Farm Planning
• Food Manufacturing
• Food Program
• GDD 2023: Intro to Gurobipy
• Intro to Mathematical Optimization Modeling / MILP Tutorial
• Linear Regression
• Logical Design
• Lost Luggage Distribution
• Manpower Planning
• Market Sharing
• Marketing Campaign Optimization
• Milk Collection
• Offshore Wind Farming
• Opencast Mining
• Optimization 101
• Portfolio Selection Optimization
• Price Optimization
• Protein Comparison
• Protein Folding
• Supply Network Design
• Technician Routing and Scheduling
• Traveling Salesman
• Workforce Scheduling
• Yield Management

These modeling examples are distributed under the Apache 2.0 license © Gurobi Optimization, LLC

Programming Assignment ZERO: Warming Up

Parallel Programming by Prof. Yi-Ping You

The purpose of this assignment is to assess whether you are familiar with Makefile and C/C++ programming. This is a calibration homework based on prerequisite material. You will receive no credit score from this assignment, but we highly encourage you to finish it. A later assignment will build upon this assignment.

Table of contents

Problem statement.

Suppose we toss darts randomly at a square dartboard, whose bullseye is at the origin, and whose sides are two feet in length. Suppose also that there is a circle inscribed in the square dartboard. The radius of the circle is one foot, and its area is π   square feet. If the points that are hit by the darts are uniformly distributed (and we always hit the square), then the number of darts that hit inside the circle should approximately satisfy the equation:

Number_in_Circle/Total_Number_of_Tosses = PI/4 ,

since the ratio of the area of the circle to the area of the square is PI/4 ( π   / 4).

We can use this pseudo code to estimate the value of π   with a random number generator:

This is called a “ Monte Carlo method ”, since it uses randomness (the dart tosses). Write a serial C/C++ program that uses the Monte Carlo method to estimate π  , with a reasonable number of tosses. You may want to use the type of long long int for the number of hits in the circle and the number of tosses, since both may have to be very large to get a reasonable estimate of π .

Hint: You may want to check if RAND_MAX is large enough for use with rand() to get a higher precision, and if the number of tosses is great enough to reach a higher accuracy.

Requirement

You are supposed to build and run your program by simply typing make and ./pi.out . An example shows as follows.

Grading Policy

This assignment is for practice only , and you will receive no credit score from this assignment. However, some parts of the coming assignments will be based on this assignment. You should still make sure the two commands, make && ./pi.out , work as they should be.

Performance Profiling

In the future assignments, you will need to parallelize serial versions of applications. In order to identify the “hot code” of a program so as to make an effective improvement, you may need to use profiling tools to find out the program’s bottleneck. Profiling tools, such as time , gprof , and perf , provide you some useful information (e.g., call graphs, execution times, hardware events like cache-miss or branch-miss counts).

Here we give you a brief introduction on how to use these tools. For more details, please refer to the references .

The time utility executes and times the specified program command with the given arguments. It prints the elapsed time during the execution of a command, time in the system, and execution time of the time command in seconds to standard error.

For example,

gprof produces an execution profile of C, Pascal, or Fortran77 programs. The effect of called routines is incorporated in the profile of each caller. The profile data is taken from the call graph profile file ( gmon.out default) which is created by programs that are compiled with the -pg option

Compile the program with the -pg option to instrument the program with code that enables profiling.

Now, just execute the executable file to generate gmon.out .

After gmon.out is generated, the gprof tool is run with the executable name and the above generated gmon.out as arguments. The -b option suppresses the printing of a description of each field in the profile. You may also redirect stdout to a file (say, profiling_result ) for later use.

Read the profiling_result file to get the profiling information.

Note: If the execution time is less than 0.01 seconds, no time will be counted.

The perf command is used as a primary interface to the Linux kernel performance monitoring capabilities and can record CPU performance counters and trace points. Similar to gprof , before you profile the program, you need to compile the program with -g option to enable profiling.

Use the perf list command to list available events.

Let’s say if we are interested in the cpu-cycles event, then we just run the program using the perf tool with the event(s) we want to monitor.

Now you can read the profiling result by running

Evaluation Platform

Your program should be able to run on UNIX-like platforms.

No submission is required for this assignment.