assignment problem constraint

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 can I solve this constrained assignment problem?

The assignment problem is defined as follows:

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one task to each agent in such a way that the total cost of the assignment is minimized.

The number of tasks is larger than the number of agents.

My problem statement though imposes an additional constraint on the above.

Each task belongs to exactly one 'category'. Each 'category' has an associated maximum number of tasks that can be assigned. Enforce this constraint on the earlier definition.

For a layman's example, consider this -

A restaurant serves n customers (agents), and has on it's menu m possible dishes (tasks), with m > n. Each customer gives his preference for each of the m dishes, which is the cost for this particular assignment problem. Find a solution which minimizes cost i.e. which gives each customer a dish that is as high on their preference as possible. Additionally, each dish belong to a certain cuisine (category). The restaurant can only make a certain number of dishes per cuisine. Enforce this constraint on the problem above.

I understand that this is a very specific problem, but any help would be appreciated.

I am currently solving the first part of the problem using the Hungarian Algorithm for assignment.

• optimization
• combinatorics
• assignment-problem

• 2 $\begingroup$ You should be able to reformulate this as a Maximum-Flow Problem $\endgroup$ –  Francesco Gramano Commented Jan 15, 2015 at 18:45

3 Answers 3

Introduce dummy variables with zero cost so that it becomes a balanced assignment, which can be solved with Hungarian Algorithm .

• $\begingroup$ Does not work for the additional constraint. $\endgroup$ –  Rohan Sood Commented Jul 5, 2015 at 11:51

This can be formulated as an instance of minimum-cost flow problem . Have a graph with one vertex per agent, one vertex per task, and one vertex per category. Now add edges:

Add an edge from the source to each agent, with capacity 1 and cost 0.

Add an edge from each agent to each task, with capacity 1 and cost according to the cost of that assignment.

Add an edge from each task to the category it is part of, with capacity 1 and cost 0.

Add an edge from each category to the sink, with capacity given by the maximum number of tasks assignable in that category and cost 0.

Now find the minimum-cost flow of size $t$, where $t$ is the number of tasks. There are polynomial-time algorithms for that.

I know it is a bit late for an answer to that post. Maybe you should have closed it within a year of no relevant answer. The problem is not that easy, just with one additional constraint, there is a lot of work dealing with the problem. You can use branch and bound algorithm. In the branch and bound, there are different ways to proceed.

• 1 $\begingroup$ Could you please describe the branch and bound algorithm in detail? $\endgroup$ –  xskxzr Commented Sep 1, 2020 at 1:12
• $\begingroup$ it is tree like method, based on : 1) solving a relaxation of your problem,, a good relaxation (without some complicating constraints). 2) setting up a branching criteria (a way how you construct the subproblems). You have to manage with bounds, upper and lowers bounds. There are ways to fathom (cut it out) a vertex or branch of the tree according to the bounds. if it is a min problem, then a lower bound is determined by the value obtained by solving the relaxed problem, and an upper bound is the value of any feasible solution (that satisfies all the constraints of the initial problem). $\endgroup$ –  Rima Awhid Commented Sep 2, 2020 at 23:15

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 algorithms optimization combinatorics assignment-problem or ask your own question .

• Featured on Meta
• Bringing clarity to status tag usage on meta sites
• Announcing a change to the data-dump process

Hot Network Questions

• How to fold or expand the wingtips on Boeing 777?
• Audio mixing problem in cpp
• Do US universities invite faculty applicants from outside the US for an interview?
• How high does the ocean tide rise every 90 minutes due to the gravitational pull of the space station?
• is it possible to add a stepwise counter for assigning a number to each text block?
• Colossians 1:16 New World Translation renders τα πάντα as “all other things” but why is this is not shown in their Kingdom Interlinear?
• How to go from Asia to America by ferry
• Acceleration command in proportional navigation?
• Is my magic enough to keep a person without skin alive for a month?
• Do you believe something to be the truth or do you know the truth?
• What are the most common types of FOD (Foreign Object Debris)?
• Why does each leg of my 240V outlet measure 125V to ground, but 217V across the hot wires?
• What does こんなところ refer to here
• Weird error in RegionPlot3D?
• Can you move between an attack and the attack granted by Horde Breaker?
• Humans are forbidden from using complex computers. But what defines a complex computer?
• What was IBM VS/PC?
• I want to be a observational astronomer, but have no idea where to start
• Where is this railroad track as seen in Rocky II during the training montage?
• Are others allowed to use my copyrighted figures in theses, without asking?
• Setting the desired kernel in GRUB menu
• Why do "modern" languages not provide argv and exit code in main?
• Information theoretical interpretation of Free Energy
• How would you read this time change with the given note equivalence?

• Practice Mathematical Algorithm
• Mathematical Algorithms
• Pythagorean Triplet
• Fibonacci Number
• Euclidean Algorithm
• LCM of Array
• GCD of Array
• Binomial Coefficient
• Catalan Numbers
• Sieve of Eratosthenes
• Euler Totient Function
• Modular Exponentiation
• Modular Multiplicative Inverse
• Stein's Algorithm
• Juggler Sequence
• Chinese Remainder Theorem
• Quiz on Fibonacci Numbers

Hungarian Algorithm for Assignment Problem | Set 1 (Introduction)

• For each row of the matrix, find the smallest element and subtract it from every element in its row.
• Do the same (as step 1) for all columns.
• Cover all zeros in the matrix using minimum number of horizontal and vertical lines.
• Test for Optimality: If the minimum number of covering lines is n, an optimal assignment is possible and we are finished. Else if lines are lesser than n, we haven’t found the optimal assignment, and must proceed to step 5.
• Determine the smallest entry not covered by any line. Subtract this entry from each uncovered row, and then add it to each covered column. Return to step 3.

Try it before moving to see the solution

Explanation for above simple example:

  An example that doesn’t lead to optimal value in first attempt: In the above example, the first check for optimality did give us solution. What if we the number covering lines is less than n.

Time complexity : O(n^3), where n is the number of workers and jobs. This is because the algorithm implements the Hungarian algorithm, which is known to have a time complexity of O(n^3).

Space complexity :   O(n^2), where n is the number of workers and jobs. This is because the algorithm uses a 2D cost matrix of size n x n to store the costs of assigning each worker to a job, and additional arrays of size n to store the labels, matches, and auxiliary information needed for the algorithm.

In the next post, we will be discussing implementation of the above algorithm. The implementation requires more steps as we need to find minimum number of lines to cover all 0’s using a program. References: http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf https://www.youtube.com/watch?v=dQDZNHwuuOY

Please Login to comment...

Similar reads.

• Mathematical
• Best Twitch Extensions for 2024: Top Tools for Viewers and Streamers
• Discord Emojis List 2024: Copy and Paste
• Best Adblockers for Twitch TV: Enjoy Ad-Free Streaming in 2024
• PS4 vs. PS5: Which PlayStation Should You Buy in 2024?
• 10 Best Free VPN Services in 2024

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

• MapReduce Algorithm
• Linear Programming using Pyomo
• Networking and Professional Development for Machine Learning Careers in the USA
• Predicting Employee Churn in Python
• Airflow Operators

Solving Assignment Problem using Linear Programming in Python

Learn how to use Python PuLP to solve Assignment problems using Linear Programming.

In earlier articles, we have seen various applications of Linear programming such as transportation, transshipment problem, Cargo Loading problem, and shift-scheduling problem. Now In this tutorial, we will focus on another model that comes under the class of linear programming model known as the Assignment problem. Its objective function is similar to transportation problems. Here we minimize the objective function time or cost of manufacturing the products by allocating one job to one machine.

If we want to solve the maximization problem assignment problem then we subtract all the elements of the matrix from the highest element in the matrix or multiply the entire matrix by –1 and continue with the procedure. For solving the assignment problem, we use the Assignment technique or Hungarian method, or Flood’s technique.

The transportation problem is a special case of the linear programming model and the assignment problem is a special case of transportation problem, therefore it is also a special case of the linear programming problem.

In this tutorial, we are going to cover the following topics:

Assignment Problem

A problem that requires pairing two sets of items given a set of paired costs or profit in such a way that the total cost of the pairings is minimized or maximized. The assignment problem is a special case of linear programming.

For example, an operation manager needs to assign four jobs to four machines. The project manager needs to assign four projects to four staff members. Similarly, the marketing manager needs to assign the 4 salespersons to 4 territories. The manager’s goal is to minimize the total time or cost.

Problem Formulation

A manager has prepared a table that shows the cost of performing each of four jobs by each of four employees. The manager has stated his goal is to develop a set of job assignments that will minimize the total cost of getting all 4 jobs.  

Initialize LP Model

In this step, we will import all the classes and functions of pulp module and create a Minimization LP problem using LpProblem class.

Define Decision Variable

In this step, we will define the decision variables. In our problem, we have two variable lists: workers and jobs. Let’s create them using  LpVariable.dicts()  class.  LpVariable.dicts()  used with Python’s list comprehension.  LpVariable.dicts()  will take the following four values:

• First, prefix name of what this variable represents.
• Second is the list of all the variables.
• Third is the lower bound on this variable.
• Fourth variable is the upper bound.
• Fourth is essentially the type of data (discrete or continuous). The options for the fourth parameter are  LpContinuous  or  LpInteger .

Let’s first create a list route for the route between warehouse and project site and create the decision variables using LpVariable.dicts() the method.

Define Objective Function

In this step, we will define the minimum objective function by adding it to the LpProblem  object. lpSum(vector)is used here to define multiple linear expressions. It also used list comprehension to add multiple variables.

Define the Constraints

Here, we are adding two types of constraints: Each job can be assigned to only one employee constraint and Each employee can be assigned to only one job. We have added the 2 constraints defined in the problem by adding them to the LpProblem  object.

Solve Model

In this step, we will solve the LP problem by calling solve() method. We can print the final value by using the following for loop.

From the above results, we can infer that Worker-1 will be assigned to Job-1, Worker-2 will be assigned to job-3, Worker-3 will be assigned to Job-2, and Worker-4 will assign with job-4.

In this article, we have learned about Assignment problems, Problem Formulation, and implementation using the python PuLp library. We have solved the Assignment problem using a Linear programming problem in Python. Of course, this is just a simple case study, we can add more constraints to it and make it more complicated. You can also run other case studies on Cargo Loading problems , Staff scheduling problems . In upcoming articles, we will write more on different optimization problems such as transshipment problem, balanced diet problem. You can revise the basics of mathematical concepts in  this article  and learn about Linear Programming  in this article .

• Solving Blending Problem in Python using Gurobi
• Transshipment Problem in Python Using PuLP

You May Also Like

Grid Search in scikit-learn

Solving Balanced Diet Problem in Python using PuLP

Dimensionality Reduction using PCA

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.

Adding sequence constraints to the assignment problem- Python

This is an online assignment problem and yet can be considered as an assignment problem with a sequence. Assume that workers are coming into the system sequentially and I want to assign a task to them based on their cost for each task. I have set up the python model without the sequence constraint, I just couldn't figure out how to mandate the order: This example from the OR-Tools: In the example there are four workers (numbered 0-3) and four tasks (numbered 0-3).

The costs of assigning workers to tasks are shown in the following table.

The problem is to assign each worker to at most one task, with no two workers performing the same task while minimizing the total cost. Since there are more workers than tasks, one worker will not be assigned a task.

Assume that I want to force an order/ sequence. Say worker 0 has to be assigned first worker 2, then worker 3... So in practice:

• worker 0 assigned to task 3 (lowest cost)
• worker 1 assigned to task 0 (lowest cost)
• worker 2 assigned to task 2 (task 3 has the lowest cost but since it is already assigned to worker 0 it is not available)
• worker 3 assigned to task 1

MIP solution The following sections describe how to solve the problem using the MIP solver as an assignment problem without enforcing the order.

Import the libraries The following code imports the required libraries.

The following code declares the MIP solver.

The following code creates the data for the problem.

The following code creates binary integer variables for the problem.

The following code creates the constraints for the problem.

HERE I want to add another constraint(s) that forces the order

The following code creates the objective function for the problem.

The value of the objective function is the total cost over all variables that are assigned the value 1 by the solver.

Invoke the solver The following code invokes the solver and prints the solution.

• assignment-problem

• $\begingroup$ You posted data for 4 tasks and 4 resources whereas you mentioned workers are more than tasks, could you please explain and also what constraint you want to include ? Is it just that 1Task per worker or other constraints are there too ? And is objective that you want to minimize total cost of Tasks wrt workers they are assigned to (That's what I made out from explanation). And also what are problems you facing as you've included almost all the program so aren't you getting desired OP ? $\endgroup$ –  user3237357 Commented Sep 1, 2021 at 7:36

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

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 .

Browse other questions tagged python constraint scheduling or-tools assignment-problem or ask your own question .

• Featured on Meta
• Bringing clarity to status tag usage on meta sites
• Announcing a change to the data-dump process

Hot Network Questions

• What is the resulting initiative order when a readied action triggers after a summoned monsters action but before the summoner?
• Parsing and processing "resolvectl statistics" output using awk
• Is there a way to prove ownership of church land?
• What qualifies as a Cantor diagonal argument?
• Where is this railroad track as seen in Rocky II during the training montage?
• Improper Subpanel Concerns
• What does こんなところ refer to here
• Looking for the name of a possibly fictional science fiction TV show
• Could they free up a docking port on ISS by undocking the emergency vehicle and letting it float next to the station for a little while
• On the convex cone of convex functions
• Replacement derailleur for Schwinn
• Why do "modern" languages not provide argv and exit code in main?
• Why a minus sign is often put into the law of induction for an inductor
• What prevents random software installation popups from mis-interpreting our consents
• How to truncate text in latex?
• Do you believe something to be the truth or do you know the truth?
• Nothing to do with books but everything to do with "BANGS"!
• \documentclass in separate .tex file
• Does Psalm 127:2 promote laidback attitude towards hard work?
• How many color information loss if I iterate all hue and value while keep saturation constant?
• Beatles reference in parody story from the 1980s
• What happens on a CAN bus when impedance is too low?
• Weird error in RegionPlot3D?
• How does a miner create multiple outputs in a coinbase transaction?

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.

Assignment problem with constraints - dual formulation - auction algorithm

I have to solve with an auction algorithm a typical assignment problem between $N$ agents and $M\ge N$ objects, but with some less usual constraints.

Let me first introduce the general formulation without any additional constraints.

The benefit for assigning object $j$ to agent $i$ is the non negative value $\beta_{ij}$ . So, the assignment problem turns to maximizing the sum of benefits :

\begin{equation} \sum_{ij} \beta_{ij}x_{ij} \end{equation}

where $x_{ij} = 1$ if object $j$ is assigned to $i$ , $0$ otherwise.

This is known as the primal formulation, which usually comes with some constraints :

• an object $j$ can only be assigned once : \begin{equation} \forall j~,~~\sum_i x_{ij} = 1 \end{equation}
• an agent $i$ has to assign $M_i$ objects : \begin{equation} \forall i~,~~\sum_j x_{ij} = M_i \end{equation}

Let's say $\sum_{i=1}^N M_i = M$ to ensure the problem is feasible and assume $M_i = 1~,~\forall i$ for the moment.

To solve this with an auction algorithm, I need to write the dual formulation, which is obtained by writing the lagrangian : \begin{equation} L = \sum_{ij} (-\beta_{ij}) x_{ij} + \sum_i \pi_i (\sum_j x_{ij} - 1) + \sum_j p_j (\sum_i x_{ij} - 1) \end{equation} \begin{equation} L = \sum_{ij}(\pi_i + p_j - \beta_{ij}) x_{ij} - \sum_i \pi_i -\sum_j p_j \end{equation} where I replaced the maximization problem by a minimization one and introduced dual variables for constraints on agents ( $\pi_i$ ) and objects ( $p_j$ ).

The dual function is the minimum of the Lagrangian on $x_{ij}$ values. If $\pi_i + p_j > \beta_{ij}$ , the minimum is obtained with $x_{ij} = 0$ , if $\pi_i + p_j < \beta_{ij}$ , there is no minimum as $x_{ij}$ goes to infinity. When $\pi_i + p_j = \beta_{ij}$ , $x_{ij}$ can be taken to unity. So the dual function to maximize is \begin{equation} - \sum_i \pi_i -\sum_j p_j \end{equation} with the constraint $\pi_i + p_j \ge \beta_{ij}$ and there is equality for the optimal assignment set.

The dual variables $p_j$ for objects are called their prices, the ones for agents are called marginal profits and equal : \begin{equation} \pi_i = \max_j (\beta_{ij} - p_j) \end{equation}

Very shortly, the auction algorithm consists in letting each agent bid on its most profitable object \begin{equation} j_i = \arg\max_j (\beta_{ij} - p_j) \end{equation} and its bid $b_i$ is computed by the difference between $\pi_i$ and the second one most profitable object : \begin{equation} b_i = \pi_i - \max_{j\ne j_i} (\beta_{ij} - p_j) + \varepsilon \end{equation} where $\varepsilon$ is a small value guaranting bids to never be null.

Then, the bidded objects are attributed to the agent with highest bid and the object price is raised by that bid, so that prices can only strictly increase.

And so on, until there are no more unassigned agents.

===============

I come now to my question which is how to adapt the previous development in order to account for additional constraints on objects.

These ones consist in saying that if one object is assigned then some other ones will be forbidden to be assigned by any other agent.

You may think for example as renting cars. People may bid to get the car but at different times. You have several benefits at renting a given car at several times, say you want it more in the morning than in the afternoon, the opposite for another person.

Assume further that the car is rented for all day, which means that if you rent it for the morning, it will not be available in the afternoon for anyone. Conversely, if someone rents if for the afternoon, it is lost for you in the morning.

The object is then the couple (car, time) where time is either morning or afternoon. It is then clear that if you win the bid for (car, morning), the object (car, afternoon) becomes unassignable, and conversely.

Coming back to the mathematical formulation, such a constraint on a set $J$ of objects can be formulated as follows : \begin{equation} \sum_{j\in J} \sum_i x_{ij} = 1 \end{equation} from which it is clear that if there is $j'\in J$ such that $x_{ij} =1$ then $\forall j\in J~, j\ne j'~,~\forall i~,~~x_{ij} = 0$

My question is then how to integrate this constraint in the lagrangian in order to get the right dual function to optimize, with the auction algorithm.

Here is how I would do.

Because the new constraint on objects in J is stronger than the former one $\sum_i x_{ij} = 1$ . This latter could be completely relaxed because implied by the additional constraint. So \begin{equation} L = \sum_{ij} (-\beta_{ij}) x_{ij} + \sum_i \pi_i (\sum_j x_{ij} - 1) + \sum_{j\notin J} p_j (\sum_i x_{ij} - 1) + \lambda (\sum_{j\in J} \sum_i x_{ij} - 1) \end{equation} then \begin{equation} L = \sum_{i,j\in J}(\pi_i + \lambda - \beta_{ij}) x_{ij} +\sum_{i,j\notin J}(\pi_i + p_j - \beta_{ij}) x_{ij}- \sum_i \pi_i -\sum_{j\notin J} p_j -\lambda \end{equation}

where $\lambda$ is the dual variable for the additional constraint.

I wonder if this is the correct formulation and how the auction algorithm can be adapted to this case. How agents bids on objects in $J$ ?

Thanks in advance for your attention.

• duality-theorems
• discrete-optimization

I wonder if my problem could be better managed by reviewing completely the assignment problem.

Indeed, consider still $N$ agents bidding on $M$ objects at $P$ time slots. The sum of benefits to maximize is \begin{equation} \sum_{i=1}^N\sum_{j=1}^M\sum_{k=1}^P \beta_{ijk}x_{ijk} \end{equation} with the constraints :

an agent $i$ has to allocate $M_i$ (objects-time slots) $(j,k)$ \begin{equation} \forall i~,~\sum_{j,k} x_{ijk} = M_i~,~~0\le x_{ijk} \le M_i \end{equation} consider objects as being the parkings where you want to rent $M_i$ cars. You may want to rent all of them in the same parking $j$ and at the same time slot, $x_{ijk} = M_i$ , or dispatch the rentings on several parkings and several time slots.

the number of rentings for a given parking must not exceed its capacity : \begin{equation} \forall j~,~\sum_{i,k} x_{ijk} \le Q_j \end{equation}

the additional constraint is that for a given parking $j$ , there is a limited number of renting per time slot : \begin{equation} \forall j,k~,~\sum_{i} x_{ijk} \le P_{jk} \end{equation}

The benefit cannot be defined apart of either the parking or the time slot : an agent $i$ has a benefit at renting a car from that parking $j$ at a given time slot $k$ : $\beta_{ijk}$ .

Then the Lagrangian is : \begin{equation} L = \sum_{ijk}(-\beta_{ijk})x_{ijk} + \sum_i \pi_i (\sum_{jk} x_{ijk} - M_i) +\sum_j p_j (\sum_{ik} x_{ijk} - Q_j) + \sum_{jk} \lambda_{jk} (\sum_i x_{ijk} - P_{jk}) \end{equation} \begin{equation} L = \sum_{ijk}(\pi_i + p_j + \lambda_{jk}-\beta_{ijk})x_{ijk} - \sum_i\pi_iM_i - \sum_j p_jQ_j -\sum_{jk} \lambda_{jk} P_{jk} \end{equation}

Then, we have to minimize \begin{equation} \sum_i\pi_iM_i + \sum_j p_jQ_j +\sum_{jk} \lambda_{jk} P_{jk} \end{equation} with the constraints : \begin{equation} \pi_i + p_j + \lambda_{jk}\ge \beta_{ijk} \end{equation} and $0\le x_{ijk}\le M_i$

I wonder if this formulation is more tractable and efficiently solvable by an auction algorithm than previous one.

You must log in to answer this question.

Not the answer you're looking for browse other questions tagged duality-theorems discrete-optimization ..

• Featured on Meta
• Announcing a change to the data-dump process
• Bringing clarity to status tag usage on meta sites
• 2024 Election Results: Congratulations to our new moderator!

Hot Network Questions

• What do these expressions mean in NASA's Steve Stitch's brief Starliner undocking statement?
• How to clean a female disconnect spade connector
• Why does the guardian who admits guilt pay more than when his guilt is established by witnesses?
• Why does each leg of my 240V outlet measure 125V to ground, but 217V across the hot wires?
• Generating function for A261041
• How does registration work in a modern accordion?
• Do you believe something to be the truth or do you know the truth?
• What is the least number of colours Peter could use to color the 3x3 square?
• Humans are forbidden from using complex computers. But what defines a complex computer?
• Potential Syscall Note Loophole?
• How many color information loss if I iterate all hue and value while keep saturation constant?
• Is the 2024 Ukrainian invasion of the Kursk region the first time since WW2 Russia was invaded?
• \documentclass in separate .tex file
• Are others allowed to use my copyrighted figures in theses, without asking?
• Somebody used recommendation by an in-law – should I report it?
• Question about word (relationship between language and thought)
• Could they free up a docking port on ISS by undocking the emergency vehicle and letting it float next to the station for a little while
• Is it suspicious to write about research with no accompanying letter from a PI for PhD admissions?
• CompizConfig not working with xubuntu 24.04
• Plausible orbit to have a visible object slowly circle over the night sky
• Looking for the name of a possibly fictional science fiction TV show
• Beatles reference in parody story from the 1980s
• Could a lawyer agree not to take any further cases against a company?
• How to raise and lower indices as a physicist would handle it?

This week: the arXiv Accessibility Forum

Help | Advanced Search

Computer Science > Artificial Intelligence

Title: reinforcement learning for assignment problem with time constraints.

Abstract: We present an end-to-end framework for the Assignment Problem with multiple tasks mapped to a group of workers, using reinforcement learning while preserving many constraints. Tasks and workers have time constraints and there is a cost associated with assigning a worker to a task. Each worker can perform multiple tasks until it exhausts its allowed time units (capacity). We train a reinforcement learning agent to find near optimal solutions to the problem by minimizing total cost associated with the assignments while maintaining hard constraints. We use proximal policy optimization to optimize model parameters. The model generates a sequence of actions in real-time which correspond to task assignment to workers, without having to retrain for changes in the dynamic state of the environment. In our problem setting reward is computed as negative of the assignment cost. We also demonstrate our results on bin packing and capacitated vehicle routing problem, using the same framework. Our results outperform Google OR-Tools using MIP and CP-SAT solvers with large problem instances, in terms of solution quality and computation time.

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 .

• Google OR-Tools
• Español – América Latina
• Português – Brasil
• Tiếng Việt

Assignment as a Minimum Cost Flow Problem

You can use the min cost flow solver to solve special cases of the assignment problem .

In fact, min cost flow can often return a solution faster than either the MIP or CP-SAT solver. However, MIP and CP-SAT can solve a larger class of problems than min cost flow, so in most cases MIP or CP-SAT are the best choices.

The following sections present Python programs that solve the following assignment problems using the min cost flow solver:

• A minimal linear assignment example .
• An assignment problem with teams of workers .

Linear assignment example

This section show how to solve the example, described in the section Linear Assignment Solver , as a min cost flow problem.

Import the libraries

The following code imports the required library.

Declare the solver

The following code creates the minimum cost flow solver.

Create the data

The flow diagram for the problem consists of the bipartite graph for the cost matrix (see the assignment overview for a slightly different example), with a source and sink added.

The data contains the following four arrays, corresponding to the start nodes, end nodes, capacities, and costs for the problem. The length of each array is the number of arcs in the graph.

To make clear how the data is set up, each array is divided into three sub-arrays:

• The first array corresponds to arcs leading out of the source.
• The second array corresponds to the arcs between workers and tasks. For the costs , this is just the cost matrix (used by the linear assignment solver), flattened into a vector.
• The third array corresponds to the arcs leading into the sink.

The data also includes the vector supplies , which gives the supply at each node.

How a min cost flow problem represents an assignment problem

How does the min cost flow problem above represent an assignment problem? First, since the capacity of every arc is 1, the supply of 4 at the source forces each of the four arcs leading into the workers to have a flow of 1.

Next, the flow-in-equals-flow-out condition forces the flow out of each worker to be 1. If possible, the solver would direct that flow across the minimum cost arc leading out of each worker. However, the solver cannot direct the flows from two different workers to a single task. If it did, there would be a combined flow of 2 at that task, which couldn't be sent across the single arc with capacity 1 from the task to the sink. This means that the solver can only assign a task to a single worker, as required by the assignment problem.

Finally, the flow-in-equals-flow-out condition forces each task to have an outflow of 1, so each task is performed by some worker.

Create the graph and constraints

The following code creates the graph and constraints.

Invoke the solver

The following code invokes the solver and displays the solution.

The solution consists of the arcs between workers and tasks that are assigned a flow of 1 by the solver. (Arcs connected to the source or sink are not part of the solution.)

The program checks each arc to see if it has flow 1, and if so, prints the Tail (start node) and the Head (end node) of the arc, which correspond to a worker and task in the assignment.

Output of the program

Here is the output of the program.

The result is the same as that for the linear assignment solver (except for the different numbering of workers and costs). The linear assignment solver is slightly faster than min cost flow — 0.000147 seconds versus 0.000458 seconds.

The entire program

The entire program is shown below.

Assignment with teams of workers

This section presents a more general assignment problem. In this problem, six workers are divided into two teams. The problem is to assign four tasks to the workers so that the workload is equally balanced between the teams — that is, so each team performs two of the tasks.

For a MIP solver solution to this problem see Assignment with Teams of Workers .

The following sections describe a program that solves the problem using the min cost flow solver.

The following code creates the data for the program.

The workers correspond to nodes 1 - 6. Team A consists of workers 1, 3, and 5, and team B consists of workers 2, 4, and 6. The tasks are numbered 7 - 10.

There are two new nodes, 11 and 12, between the source and workers. Node 11 is connected to the nodes for team A, and Node 12 is connected to the nodes for team B, with arcs of capacity 1. The graph below shows just the nodes and arcs from the source to the workers.

The key to balancing the workload is that the source 0 is connected to nodes 11 and 12 by arcs of capacity 2. This means that nodes 11 and 12 (and therefore teams A and B) can have a maximum flow of 2. As a result, each team can perform at most two of the tasks.

Create the constraints

The following shows the output of the program.

Team A is assigned tasks 9 and 10, while team B is assigned tasks 7 and 8.

Note that the min cost flow solver is faster for this problem than the MIP solver , which takes around 0.006 seconds.

Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License , and code samples are licensed under the Apache 2.0 License . For details, see the Google Developers Site Policies . Java is a registered trademark of Oracle and/or its affiliates.

Last updated 2024-08-28 UTC.

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

Computing assignment with additional constraints

Suppose I have a bunch of students and a couple of professors. Each student needs to take an oral exam with one of the professors. For this, every student supplies an (ordered) list consisting of three professors he would prefer taking the exam with. Of course, each professor can only give a limited number of exams. I can use the Kuhn-Munkres algorithm to compute an assignment where as many students as possible are assigned to their first wish professor.

Now suppose instead that every student has to take two exams, and accordingly supplies two wish lists. Again I want to assign as many students as possible to their first wish professors, but subject to the constraint that a student must not take both his exams with the same professor .

Is there some algorithm for computing an optimal assignment efficiently? Maybe a generalization of the Kuhn-Munkres algorithm? Or is this new problem already NP-hard? What hard problem could one try to reduce to this one?

I should emphasize that I am looking for an exact solution. It is pretty easy to think of some heuristics, like considering one type of exam after the other.

• mathematical-optimization

• 1 If you want to maximize the number of students assigned to their first wish professor, why do you need lists with three professors? –  Lior Kogan Commented Jul 5, 2013 at 12:59
• 1 I'm not sure about the hardness, but regardless, there's a good chance that integer programming is the path of least resistance. –  David Eisenstat Commented Jul 5, 2013 at 13:32
• @LiorKogan I think the goal is to have all students assigned to one of their 3 chosen professors, then, if there are multiple solutions , pick the one that maximizes the number of students that have their first-wish professor. –  Bernhard Barker Commented Jul 5, 2013 at 13:42
• Instead of using Kuhn-Munkres to match students to professors, you can use Kuhn-Munkres to match students to pairs of professors. You'll just need to take a student's wish lists, and combine it into one in some manner. The ranking of a pair of professors could be the average of the individual ranking, or the ranking of the less desirable professor, for example. –  Teepeemm Commented Jul 5, 2013 at 13:47
• @Teepeemm It's difficult to control each professor's workload that way. –  David Eisenstat Commented Jul 5, 2013 at 13:55

2 Answers 2

You can model this exactly using Integer programming as an Assignment Problem.

Let there be s students and p professors.

The decision variable

Handling Student Preferences

We can handle each student's preference through the costs (objective)

We keep progressively making the costs higher as the preference decreases.

Formulation

Case 1: One Exam

Case 2: student takes two Exams

Taking care of no student can take both exams with the same professor

Normally, we'd have to introduce indicator variables Y_sp to denote whether or not a student has taken an exam with professor p. However, in this case we don't even have to do that. The fact that X_sp is binary will ensure that no student ends up taking 2 exams with the same professor.

If the student has a preference of which exam they'd like to take with a professor, then adding a subscript e to the decision variable is required. X_spe

You can solve this either through the Hungarian method, or easier still, any available implementation of LP/IP solver.

The Hungarian algorithm's complexity is O(n^3), and since we haven't introduced any side constraints to spoil the integrality property, the linear solution will always be integral.

Update (A little bit of theory)

Why are the solutions integral? To understand why the solutions are guaranteed to be integral, a little bit of theory is necessary.

Typically, when confronted with an IP, the first thought is to try solving the linear relaxation (Forget the integral values requirements and try.) This will give a lower bound to minimization problems. There are usually a few so-called complicating constraints that make integer solutions very difficult to find. One solution technique is to relax those by throwing them to the objective function, and solving the simpler problem (the Lagrangian Relaxation problem.)

Now, if the solution to the Lagrangian doesn't change whether or not you have integrality (as is the case with Assignment Problems) then you always get integer solutions.

For those who are really interested in learning about Integrality and Lagrangian duals, this reference is quite readable. The example in Section 3 specifically covers the Assignment Problem.

Free MILP Solvers: This SO question is quite exhaustive for that.

Hope that helps.

• You have to take care of the fact that the wish lists for the two exams usually differ. So one would have variables X_spe if student s takes exam e with professor p. Of course, it's still easy to formulate this as an ILP problem. However, I don't get your point why an LP solution should automatically be integral. Can you explain this in more detail? Anyway, what would be a good (I)LP solver which is available for free? –  pgraf Commented Jul 6, 2013 at 17:35
• Updated my response with the clarifications you asked for. –  Ram Narasimhan Commented Jul 6, 2013 at 19:36
• Now I plugged it into lp_solve, and it works great. The integrality of solutions seems to stem from the fact that the matrix is totally unimodular. Unfortunately, I cannot upvote your answer because my reputation is too low ... –  pgraf Commented Jul 10, 2013 at 13:27

I think you can solve this optimally by solving a min cost flow problem.

The Python code below illustrates how this can be done for 3 students using the networkx library.

The key is that we have a separate node (called n2 in the code) for each combination of student and professor. By giving n2 a capacity of 1 to the destination, we ensure that each student can only take a single test with that professor.

The dictionary multiple_prefs stores two dictionaries. The first dictionary contains the lists of preferences for each student for the first test. The second has the preferences for the second test.

The code now also includes nodes n3 for each professor. The capacity on the edges between these nodes and the dest will limit the maximum workload for each professor.

The dictionary workload stores the maximum number of allowed tests for each professor.

• Two Questions: 1. Is it clear that nx.min_cost_flow() produces an integer solution? Clearly a solution with fractional values is no good. 2. How do you ensure that no professor exceeds his workload? In your code, I cannot see where the professors' capacities enter. –  pgraf Commented Jul 5, 2013 at 15:58
• 1) I believe the flow will always be integer because all the capacities are integer. 2) Sorry, I had missed this part of the problem. However, it is easy to fix by simply adding additional nodes n3 for each professor. Each n2 node will connect to the corresponding n3 with capacity 1, and then the n3 nodes will connect to the dest with capacity corresponding to that professors workload. I'll edit the answer to add the corresponding code when I am next at a computer with Python installed... –  Peter de Rivaz Commented Jul 5, 2013 at 16:42
• Adding the n3s is a good point. I'm looking forward to your code. However, I'm still worried about integrality. When I look at the source code of networkx, it seems it's using some kind of simplex algorithm. One would have to test some real-world examples. –  pgraf Commented Jul 6, 2013 at 17:44
• It works, but at least with interpreted Python it's painfully slow. Therefore I accepted Ram's answer instead. Mathematically, it boils down to the same thing. I would upvote your answer, but my reputation is not sufficient. –  pgraf Commented Jul 10, 2013 at 13:30

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 .

Not the answer you're looking for? Browse other questions tagged algorithm mathematical-optimization or ask your own question .

• The Overflow Blog
• The hidden cost of speed
• The creator of Jenkins discusses CI/CD and balancing business with open source
• Featured on Meta
• Announcing a change to the data-dump process
• Bringing clarity to status tag usage on meta sites
• What does a new user need in a homepage experience on Stack Overflow?
• Feedback requested: How do you use tag hover descriptions for curating and do...
• Staging Ground Reviewer Motivation

Hot Network Questions

• What's the best format or way to generate a short-lived access token?
• Are others allowed to use my copyrighted figures in theses, without asking?
• Replacement derailleur for Schwinn
• How high does the ocean tide rise every 90 minutes due to the gravitational pull of the space station?
• What was the typical amount of disk storage for a mainframe installation in the 1980s?
• Where did they get facehuggers from?
• lib/xorg/Xorg →lib/x86_64-linux-gnu/libc.so →xorg/modules/drivers/nvidia_drv.so causes a segmentation fault. Should I report that to Debian team?
• What happens on a CAN bus when impedance is too low?
• Is it possible to travel to Uppsala from Stockholm with SL unlimited card?
• Multiplicity of the smallest non-zero Laplacian eigenvalue for tree graphs
• Fundamental Question on Noise Figure
• Unable to understand a proof of the squeeze theorem
• What qualifies as a Cantor diagonal argument?
• Humans are forbidden from using complex computers. But what defines a complex computer?
• Information theoretical interpretation of Free Energy
• Why does the guardian who admits guilt pay more than when his guilt is established by witnesses?
• Audio mixing problem in cpp
• Where is this railroad track as seen in Rocky II during the training montage?
• Is it suspicious to write about research with no accompanying letter from a PI for PhD admissions?
• How to raise and lower indices as a physicist would handle it?
• Somebody used recommendation by an in-law – should I report it?
• Setting the desired kernel in GRUB menu
• Is this host and 'parasite' interaction feasible?
• At what point is the best to switch instruction language to the target language

Constraint Programming with python-constraint

• Introduction

The first thing we have to understand while dealing with constraint programming is that the way of thinking is very different from our usual way of thinking when we sit down to write code.

Constraint programming is an example of the declarative programming paradigm, as opposed to the usual imperative paradigm that we use most of the time.

What is a programming paradigm?

A paradigm means "an example" or "a pattern" of something. A programming paradigm is often described as a "way of thinking" or "way of programming". The most common examples including Procedural Programming (e.g. C), Object-Oriented Programming (e.g. Java) and Functional Programming (e.g. Haskell).

Most programming paradigms can be classified as a member of either the imperative or declarative paradigm group.

What is the difference between imperative and declarative programming?

• Imperative programming, simply put, is based on the developer describing the solution/algorithm for achieving a goal (some kind of result). This happens by changing the program state through assignment statements, while executing instructions step-by-step. Therefore it makes a huge difference in what order the instructions are written.
• Declarative programming does the opposite - we don't write the steps on how to achieve a goal, we describe the goal , and the computer gives us a solution. A common example you should be familiar with is SQL. Do you tell the computer how to give you the results you need? No, you describe what you need - you need the values from some column, from some table, where some conditions are met.
• Installing the python-constraint Module

In this article we'll be working with a module called python-constraint (Note: there's a module called "constraint" for Python, that is not what we want), which aims to bring the constraint programming idea to Python.

To install this module, open the terminal and run:

• Basics of Using python-constraint

This is the generalized skeleton of programs written using this module (Note: we use import constraint and not import python-constraint )

• import constraint
• define a variable as our problem
• add variables and their respective intervals to our problem
• add built-in/custom constraints to our problem
• fetch the solutions
• go through the solutions to find the ones we need

As previously mentioned, constraint programming is a form of declarative programming. The order of statements doesn't matter, as long as everything is there in the end. It's usually used to solve problems like this:

If we look at this sentence, we can see several conditions (let's call them constraints) that x and y have to meet.

For example, x is "constrained" to the values 1,2,3 , y has to be less than 10 and their sum has to be greater than or equal to 5 . This is done in a few lines of code and in a few minutes using constraint programming.

Looking at the problem above you probably thought "So what? I can do this with 2 for loops and half a cup of coffee in Python in less than 10 minutes".

You're absolutely right, though through this example we can get an idea of what constraint programming looks like:

Let's walk through this program step by step. We had two variables, x and y . We've added them to our problem with their respective acceptable ranges.

Those two lines mean the following:

Next we define our custom constraint (that is, x + y >= 5 ). Constraint methods are supposed to return True if a combination of variable values is acceptable, and None if it isn't.

In our our_constraint() method, we say "The only acceptable situation is when x + y >= 5 , otherwise don't include those values of (x,y) in the final solutions."

After defining our constraint, we have to add it to our problem. The structure of the .addConstraint() method is:

Note : in our case, it doesn't matter if we write [x,y] or [y,x] as our second parameter, but the order does matter in most cases.

After that, we fetch the solutions with problem.getSolutions() (returns a list of all combinations of variable values that satisfy all the conditions) and we iterate through them.

Note : If, for example, we wanted to fetch only combinations where x /= y , we'd add a built-in constraint before fetching the solutions:

You can find the list of all built-in constraints here . That's almost everything you need to know to be able to do any task of this type.

• Warm-Up Examples

Here's a type of problem constraint programming is fun to use on, called crypt-arithmetic puzzles . In the following form of crypt-arithmetic puzzles, each character represents a different digit (the leading characters can't be 0):

Think about how you'd solve this using regular Python. In fact, I encourage you to look up the solution for this problem that uses imperative programming.

It should also give you all the knowledge you need to solve Example D on your own.

Keep in mind that 'T' and 'F' can't be zero since they're the leading characters, i.e. the first digit in a number.

Running this piece of code, we're greeted with the possible solutions:

Note : The order in which our result is printed isn't necessarily the same as the order in which we've added the variables. That is, if the result is ( a,b,c,d,e ) we don't know whether we have a of 1 cent coins, b of 3 cent coins, etc.

So we should explicitly print the variable and its value. One consequence of this is that we can't use the built-in .ExactSumConstraint() in its two-parameter form, ExactSumConstraint(50,[1,3,5,10,20]) .

The second parameter here is the "weight" of each variable (how many times it should be multiplied), and we have no guarantee which of our variables will have what weight.

It's a common mistake to assume the weights will be allocated to the variables in the order in which the variables were added, instead we use the three-parameter form of this built-in constraint in the code below:

Check out our hands-on, practical guide to learning Git, with best-practices, industry-accepted standards, and included cheat sheet. Stop Googling Git commands and actually learn it!

Running this piece of code will yield:

Example B and D are nearly identical when using constraints, just a few variables up and down and more verbose constraints. That's one good thing about constraint programming - good scalability, at least when time spent coding is concerned. There is only one solution to this puzzle and it is A=3 B=7 C=8 E=2 H=6 K=0 O=1 R=5 S=9 T=4.

Both of these types of tasks (especially crypt-arithmetic) are used more for fun and for easy demonstration of how constraint programming works, but there are certain situations in which constraint programming has practical value.

We can calculate the minimal number of broadcasting stations to cover a certain area, or find out how to set up traffic lights so that the flow of traffic is optimal. In general terms - constraints are used where there are a lot of possible combinations.

These examples are too complex for the scope of this article, but serve to show that constraint programming can have uses in the real world.

• Harder Examples

Now let's roll up our sleeves and get started. It shouldn't be too difficult if you've understood the previous examples.

We'll first figure out how much of each chocolate we can have if we ONLY brought that type, so we can have the upper bound of our intervals. For example, for Chocolate A, based on weight we can bring at most 30 bars, based on value we can bring 37 at most, and based on volume we can bring 100.

The smallest of these numbers is 30, and that's the maximum number of Chocolate A we can bring. The same steps give us the maximum amount of the rest, B -> 44, C -> 75, D -> 100 .

Note : We can store all relevant information for each chocolate type in a dictionary, e.g. weight_dictionary = {'A' : 100, 'B' : 45, 'C' : 10, 'D' : 25} , and accessing values that way, instead of hardcoding them in functions. However, for the sake of readability, code length and focus on things more important for this tutorial, I prefer to hardcode in the constraint functions themselves.

Note : You probably noticed that it took a while for this result to be computed, this is a drawback of constraint programming.

Now for something more fun - let's make a sudoku (classic 9x9) solver. We'll read the puzzle from a JSON file and find all the solutions for that particular puzzle (assuming that the puzzle has a solution).

If you forgot the rules for solving sudoku:

• Cells can have values 1 - 9
• All cells in the same row must have different values
• All cells in the same column must have different values
• All cells in a 3x3 square (nine in total) must have different values

One of the issues in this program is - how do we store the values? We can't just add a matrix as a variable to our problem and have Python magically figure out what we want.

We're going to use a system where we'll treat numbers like variable names (that's allowed), and pretend that we have a matrix. The indices start from (1,1) instead of the usual (0,0). Using that we'll access elements of the board in a way that we're used to.

Next, we need to do the easy part of telling Python that all those cells can have values between 1 and 9.

Then we note that cells in the same row have the same first index, e.g. (1,x) for the first row. We can easily iterate through all rows and say that all the cell have to contain different values. Same goes for the columns. The rest is more easily understood when looking at the code.

Let's take a look at an example JSON file:

Output (when we use our example JSON file as input):

Note : It's very easy to overlook the part of the code that makes sure we don't touch the values already in the puzzle.

If we tried to run the code without that part, the program would try to come up with ALL SUDOKU PUZZLES IMAGINABLE. Which might as well be an endless loop.

• Conclusion and Drawbacks

As fun and different as constraint programming is, it certainly has its drawbacks. Every problem solved using constraint programming can be written in imperative style with an equal or (as in most cases) better runtime.

It's only natural that the developer understands the problem better than he can describe it to python-constraint . A very important note to make is that constraint programming can, in some situations, save hours and hours of development time in exchange for slightly worse runtime.

I recently had a real life example of this. A friend of mine, someone who only learned of Python's existence a few months before, needed to solve a problem for a physical chemistry research project she was working on.

That friend needed the following problem solved:

Try and think how you would solve this using imperative programming.

I couldn't even come up with an idea of a good solution imperatively. At least not in the 5 minutes it took me to solve her problem in constraint programming, in literally a few lines of code.

That's it. We just didn't add any constraints and the program generated all acceptable combinations for us. In her case, the minimal difference in runtime of this program doesn't remotely matter as much as how quickly it was written and how readable it is.

One more thing to note is that python-constraint can do more than just test whether a combination fits all constraints mindlessly.

There are backtracking (and recursive backtracking) capabilities implemented, as well as problem solvers based on the minimum conflicts theory. These can be passed as an argument to the .Problem() method, e.g .Problem(BacktrackingSolver) , the rest is done in the same way as in the examples above.

• List of Built-in Constraints

When using constraints that can take a list of multipliers as a parameter (Like ExactSum or MinSum ) take care to explicitly say the order or variables if necessary, like we did in Example E

Constraint programming is amazing as far as readability and ease of developing certain programs is concerned, but does so at the cost of runtime. It's up to the developer to decide which is more important to him/her for a particular problem.

You might also like...

• Hidden Features of Python
• Python Docstrings
• Handling Unix Signals in Python
• The Best Machine Learning Libraries in Python
• Guide to Sending HTTP Requests in Python with urllib3

Improve your dev skills!

Get tutorials, guides, and dev jobs in your inbox.

No spam ever. Unsubscribe at any time. Read our Privacy Policy.

LinkedIn: https://rs.linkedin.com/in/227503161 If you need any help - post it in the comments :) That way someone else can reply if I'm busy.

In this article

Monitor with Ping Bot

Reliable monitoring for your app, databases, infrastructure, and the vendors they rely on. Ping Bot is a powerful uptime and performance monitoring tool that helps notify you and resolve issues before they affect your customers.

Vendor Alerts with Ping Bot

Get detailed incident alerts about the status of your favorite vendors. Don't learn about downtime from your customers, be the first to know with Ping Bot.

© 2013- 2024 Stack Abuse. All rights reserved.

A three-dimensional bin packing problem with item fragmentation and its application in the storage location assignment problem

• Research Paper
• Published: 04 September 2024

Cite this article

• Hamid Salamati-Hormozi   ORCID: orcid.org/0000-0001-6500-3403 1 ,
• Ali Husseinzadeh Kashan   ORCID: orcid.org/0000-0002-6004-6882 1 &
• Bakhtiar Ostadi   ORCID: orcid.org/0000-0001-8472-6244 1  

This paper introduces the three-dimensional bin packing problem with item fragmentation (3D-BPPIF) and explores its application in the storage location assignment problem (SLAP) to efficiently allocate warehouse spaces to product groups. Based on real-world constraints, the aim is to find an effective 3D-packing of the product groups into warehouse storage spaces to minimize the total distance. Given the internal limitations present in many warehouses, the storage spaces are not homogeneous, making the allocation to product groups a challenging task that can reduce space utilization efficiency. Accordingly, to effectively utilize warehouse storage spaces, we developed a MILP formulation incorporating the concepts of shape changeability and item fragmentation, significantly enhancing the flexibility of the arrangements. Due to the NP-hard nature of the problem, we proposed a simulated annealing-based meta-heuristic to solve large-scale real-world problems. Numerous computational experiments prove the validity of the proposed model and illustrate that the proposed algorithm can provide appropriate 3D assignments.

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

Access this article

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime

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

A Constructive Heuristic Algorithm for 3D Bin Packing of Irregular Shaped Items

A Heuristic for the Two-Dimensional Irregular Bin Packing Problem with Limited Rotations

The Two Dimensional Bin Packing Problem with Side Constraints

Bortfeldt A, Wäscher G (2013) Constraints in container loading–a state-of-the-art review. Eur J Oper Res 229(1):1–20

Article   Google Scholar  

Caserta M, Voß S, Sniedovich M (2011) Applying the corridor method to a blocks relocation problem. Or Spectrum 33(4):915–929

Chen C, Lee S-M, Shen Q (1995) An analytical model for the container loading problem. Eur J Oper Res 80(1):68–76

Crainic TG, Perboli G, Tadei R (2008) Extreme point-based heuristics for three-dimensional bin packing. INFORMS J Comput 20(3):368–384

Crainic TG, Perboli G, Tadei R (2009) TS2PACK: a two-level tabu search for the three-dimensional bin packing problem. Eur J Oper Res 195(3):744–760

De Koster R, Le-Duc T, Roodbergen KJ (2007) Design and control of warehouse order picking: a literature review. Eur J Oper Res 182(2):481–501

Den Boef E, Korst J, Martello S, Pisinger D, Vigo D (2005) Erratum to “the three-dimensional bin packing problem”: robot-packable and orthogonal variants of packing problems. Oper Res 53(4):735–736

Derhami S, Smith JS, Gue KR (2017) Optimising space utilisation in block stacking warehouses. Int J Prod Res 55(21):6436–6452

Derhami S, Smith JS, Gue KR (2019) Space-efficient layouts for block stacking warehouses. IISE Trans 51(9):957–971

Derhami S, Smith JS, Gue KR (2020) A simulation-based optimization approach to design optimal layouts for block stacking warehouses. Int J Prod Econ 223:107525

Dijkstra AS, Roodbergen KJ (2017) Exact route-length formulas and a storage location assignment heuristic for picker-to-parts warehouses. Transp Res Part e Logist Transp Rev 102:38–59

Duan J, Tong X, Ni F, He Z, Chen L, Yuan M (2022) A data-driven column generation algorithm for bin packing problem in manufacturing industry. https://arxiv.org/abs/2202.12466

Elhedhli S, Gzara F, Yildiz B (2019) Three-dimensional bin packing and mixed-case palletization. INFORMS J Optim 1(4):323–352

Ene S, Öztürk N (2012) Storage location assignment and order picking optimization in the automotive industry. Int J Adv Manuf Technol 60(5):787–797

Erbayrak S, Özkır V, Yıldırım UM (2021) Multi-objective 3D bin packing problem with load balance and product family concerns. Comput Ind Eng 159:107518

Farhadi Sartangi M, Husseinzadeh Kashan A, Haleh H, Kazemi A (2022) A mixed integer linear formulation and a grouping league championship algorithm for a multiperiod-multitrip order picking system with product replenishment to minimize total tardiness. Complexity 2022

Frazelle EH (1989) Stock location assignment and order picking productivity. Georgia Institute of Technology

Google Scholar  

Gonçalves JF, Resende MG (2013) A biased random key genetic algorithm for 2D and 3D bin packing problems. Int J Prod Econ 145(2):500–510

Gu J, Goetschalckx M, McGinnis LF (2007) Research on warehouse operation: a comprehensive review. Eur J Oper Res 177(1):1–21

Gu J, Goetschalckx M, McGinnis LF (2010) Research on warehouse design and performance evaluation: a comprehensive review. Eur J Oper Res 203(3):539–549

Harrath Y (2022) A three-stage layer-based heuristic to solve the 3D bin-packing problem under balancing constraint. J King Saud Univ-Comput Inf Sci 34(8):6425–6431

Hausman WH, Schwarz LB, Graves SC (1976) Optimal storage assignment in automatic warehousing systems. Manage Sci 22(6):629–638

He K, Tole K, Ni F, Yuan Y, Liao L (2020) Adaptive large neighborhood search for circle bin packing problem. https://arxiv.org/abs/2001.07709

Jang D-W, Kim SW, Kim KH (2013) The optimization of mixed block stacking requiring relocations. Int J Prod Econ 143(2):256–262

Junqueira L, Morabito R, Yamashita DS (2012) Three-dimensional container loading models with cargo stability and load bearing constraints. Comput Oper Res 39(1):74–85

Kashan AH, Akbari AA, Ostadi B (2015) Grouping evolution strategies: an effective approach for grouping problems. Appl Math Model 39(9):2703–2720

Kashan AH, Kashan MH, Karimiyan S (2013) A particle swarm optimizer for grouping problems. Inf Sci 252:81–95

Kofler M, Beham A, Wagner S, Affenzeller M (2014) Affinity based slotting in warehouses with dynamic order patterns. In: Advanced methods and applications in computational intelligence. Springer, pp 123–143

Kovács G (2020) Special optimization process for warehouse layout design. Vehicle and Automotive Engineering

Mahvash B, Awasthi A, Chauhan S (2013) Column generation based heuristic for the three dimensional vehicle loading problem. In: International conference on computational logistics

Mahvash B, Awasthi A, Chauhan S (2017) A column generation-based heuristic for the three-dimensional bin packing problem with rotation. J Oper Res Soc:1–13

Maniezzo V, Boschetti MA, Gutjahr WJ (2021) Stochastic premarshalling of block stacking warehouses. Omega 102:102336

Martello S, Pisinger D, Vigo D (2000) The three-dimensional bin packing problem. Oper Res 48(2):256–267

Martello S, Pisinger D, Vigo D, Boef ED, Korst J (2007) Algorithm 864: general and robot-packable variants of the three-dimensional bin packing problem. ACM Trans Math Softw (TOMS) 33(1):7-es

Muppani VR, Adil GK (2008) Efficient formation of storage classes for warehouse storage location assignment: a simulated annealing approach. Omega 36(4):609–618

Narciso M (2010) Revisiting the pallet loading problem using a discrete event system approach to minimize logistic costs

Paquay C (2017) The three-dimensional rectangular multiple bin size bin packing problem with transportation constraints: a case study in the field of air transportation. Springer

Book   Google Scholar  

Paquay C, Limbourg S, Schyns M (2018) A tailored two-phase constructive heuristic for the three-dimensional Multiple Bin Size Bin Packing Problem with transportation constraints. Eur J Oper Res 267(1):52–64

Paquay C, Schyns M, Limbourg S (2016) A mixed integer programming formulation for the three-dimensional bin packing problem deriving from an air cargo application. Int Trans Oper Res 23(1–2):187–213

Petersen CG, Aase GR, Heiser DR (2004) Improving order‐picking performance through the implementation of class‐based storage. Int J Phys Distrib Logist Manag

Petersen CG, Siu C, Heiser DR (2005) Improving order picking performance utilizing slotting and golden zone storage. Int J Oper Prod Manag

Prasad SA, Krishnakumar P (2021) Higher order block heuristics for 2D pallet loading problems with multiple box inputs. Mater Today Proc 46:4625–4633

Riccardo A, Giulia B, Riccardo M (2017) Design and manage deep lane storage system layout: an iterative decision-support model. Int J Adv Manuf Technol 92(1–4):57–67

Roodbergen KJ, Vis IF, Taylor GD Jr (2015) Simultaneous determination of warehouse layout and control policies. Int J Prod Res 53(11):3306–3326

Silva A, Coelho LC, Darvish M, Renaud J (2020) Integrating storage location and order picking problems in warehouse planning. Transp Res Part e Logist Transp Rev 140:102003

Tappia E, Roy D, Melacini M, De Koster R (2019) Integrated storage-order picking systems: technology, performance models, and design insights. Eur J Oper Res 274(3):947–965

Tole K, Moqa R, Zheng J, He K (2023) A simulated annealing approach for the circle bin packing problem with rectangular items. Comput Ind Eng 176:109004

Trivella A, Pisinger D (2016) The load-balanced multi-dimensional bin-packing problem. Comput Oper Res 74:152–164

Venkitasubramony R, Adil GK (2019) An integrated design approach for class-based block stacked warehouse. Facilities

Yuan Y, Tole K, Ni F, He K, Xiong Z, Liu J (2022) Adaptive simulated annealing with greedy search for the circle bin packing problem. Comput Oper Res 144:105826

Zhang G, Nishi T, Turner SD, Oga K, Li X (2017) An integrated strategy for a production planning and warehouse layout problem: Modeling and solution approaches. Omega 68:85–94

Download references

Author information

Authors and affiliations.

Faculty of Industrial and Systems Engineering, Tarbiat Modares University, Tehran, Iran

Hamid Salamati-Hormozi, Ali Husseinzadeh Kashan & Bakhtiar Ostadi

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Ali Husseinzadeh Kashan .

Ethics declarations

Conflict of interest.

The authors declare that there is no conflict of interest.

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Suppose a problem involving the packing of 3 items into a bin with dimensions \(4 \times 4 \times 2\) (see Fig. 

The available space of a bin with dimensions \(4 \times 4 \times 2\)

16 ). Table

10 represents the specifications of the items. The fixed item, with volume 4, is represented by a black box in the bin and serves as an obstacle. The order of packing the items is predetermined based on the ascending order of COI. The packing phase is as follows:

Warehouse door coordinates (I/O): \(\left( {O^{x} ,O^{y} ,O^{z} } \right) = \left( {0,0,0} \right)\) .

List of sorted items ( S) : \(S = \left\{ {1 \to 2 \to 3} \right\}\) .

1.1 Iteration #1

Update the available space: the best candidate points (nearest points to the I/O) to assign the first item are A, B, and C (Fig. 

The available space in iteration #1

Call the first item from the list \(S\) : \(v_{1} = 6.\)

Regarding the objective function (minimizing the total distance to the I/O point), the model tries to find the best location and dimensions for the item. Various arrangement options are shown in Fig. 

Different arrangements of the first item in iteration #1

18 . As shown, the best arrangement for \(v_{1} = 6\) is the place with the minimum value of objective function which it is \(z = 12.2\) .

Fix the location and dimensions of the item:

1.2 Iteration #2

Update the available space: point A is occupied by the first item. The available spaces closest to the I/O point (points B and C) are shown in Fig. 

The available space in iteration #2

Call the second item from the list \(S\) : \(v_{2} = 7.\)

There is no feasible way to arrange the second item as a single piece within the available space. Therefore, the model divides it into two parts. Some arrangement options are shown in Fig. 

Different arrangements of the second item in iteration #2

20 . The best arrangement for \(v_{2} = 7\) results in a minimum objective function value of \(z = 30.7\) .

1.3 Iteration #3

Update the available space: points B and C are occupied by the second item. The available spaces closest to the I/O point (D, E, F, and G) are shown in Fig. 

The available space in iteration #3

Call the third item from the list S: \(v_{3} = 10.\)

There is no way to arrange the third item with a single box in the available space. As a result, the model divides it into two parts. Different arrangement modes are shown in Fig. 

Different arrangements of the third item in iteration #3

22 . The best arrangement for \(v_{3} = 10\) is obtained. The points F and G are occupied by the third item.

Fix location and dimensions of item:

Arrangements of classes 7–27 of large-size items

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Salamati-Hormozi, H., Husseinzadeh Kashan, A. & Ostadi, B. A three-dimensional bin packing problem with item fragmentation and its application in the storage location assignment problem. 4OR-Q J Oper Res (2024). https://doi.org/10.1007/s10288-024-00576-6

Download citation

Received : 05 December 2023

Revised : 27 June 2024

Accepted : 14 August 2024

Published : 04 September 2024

DOI : https://doi.org/10.1007/s10288-024-00576-6

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

• Three-dimensional bin packing problem
• Storage location assignment problem
• Item fragmentation
• Shape changeability
• Simulated annealing

Mathematics Subject Classification

• Find a journal
• Publish with us
• Track your research

• Departments
• Audiology & Speech-Language Pathology
• Behavior Analysis
• Criminal Justice
• Emergency Management & Disaster Science
• Public Administration
• Rehabilitation & Health Services
• Social Work
• HPS IT Services
• Degree Programs
• Undergraduate Degrees
• Graduate Degrees
• Minors & Certificates
• Student Resources
• Graduate Advising
• Scholarships
• HPS Graduate Admissions Appeal
• HPS Philanthropy Cord
• Student Orgs
• HPS Research
• HPS Grant & Funding Resources
• Search HPS Faculty Research
• HPS Student Research
• HPS Research Seminars
• HPS Global Projects
• HPS Faculty Publications
• Faculty & Staff Resources
• Request for Space Allocation
• HPS Incentive Program for Grant Writing
• HPS Small Seed Grants Program
• Give to HPS
• Faculty & Staff Directory
• HPS Community Engagement & Service
• Notify Niki
• Search Type THIS SITE ALL of UNT Search Search
• Quicklinks:
• STUDENT EMAIL
• UNT DIRECTORY

Internships

• Current Students
• Future Students
• EADP Academic Advising
• EMDS Scholarships
• Research and Engagement in EADP
• EMDS Faculty and Staff
• Give to EMDS

Bridging Classroom Learning to Real-World Emergency Management

Purpose of the Internship

The purpose of the internship is to provide the fledgling emergency manager with the opportunity to gain first-hand experience related to all four phases of Emergency Management. The internship is a key component of the Emergency Administration and Planning program and provides pre-career students an opportunity to apply classroom knowledge and develop professional skills that will lead to a successful career. Moreover, the internship experience frequently provides the student with an entry into a permanent position.

Emergency Administration and Planning students must complete an internship of at least 240 hours of employment. Students must register for EADP 4800, EADP Internship Preparation, and complete the course before beginning an internship appointment. This three hour course meets four times during the semester and prepares students for an internship. Career testing, resume and interview preparation, and discussions of professional and ethical conduct are covered. When the student is ready to begin an internship, the internship coordinator will assist in identifying internships, but the student is ultimately responsible for securing an appointment.

Internships may be completed during the summer months, on a part-time basis during the academic year, or once all course work has been completed.

Internship Resources

Internship Guidelines

Career Center Internship Information

Current EADP Internship Placements

Internship Practicum Testimonials

Internship Waiver Request   - Please include your current resume with this form.

For more information, please contact the EADP Internship Coordinator,   Dr. Ron Timmons .

Internship Details

There are three categories for internships in the EADP program:

Students with NO Professional Work Experience: 48 Hours in Major

Required: Internship Preparation (EADP 4800)

Required: Internship Practicum (EADP 4810) and a 240 hour internship.

Students with Professional Work Experience (but not in EADP field): 45 Hours in Major

Not required: Internship Preparation (EADP 4800)

This change must be approved. Please contact  Dr. Ron Timmons , the EADP Internship Coordinator (Chilton 204J), to request a waiver for EADP 4800.

Students with Three (3) years Professional Work Experience in Emergency Management: 42 Hours in Major

Not required: Internship Practicum (EADP 4810) and a 240 hour internship.

This change must be approved. Please see   Dr. Ron Timmons ,  EADP Internship Coordinator (Chilton Hall 204J) to request a waiver for EADP 4800/4810.

If you choose the 42 hour degree plan, you may not complete an internship for credit.

EADP 4810 (Internship Practicum) is a restricted enrollment course and requires a permission code for registration. You MUST contact the Internship Coordinator prior to your registration date. It is best to acquire your code at least two weeks prior to your registration date. DO NOT wait until the day you are scheduled to register to try to obtain your registration code.

EADP 4800 - Internship Preparation 

During Internship Preparation, students will meet with the internship coordinator to begin arranging their internship. The internship coordinator will assist the student in securing a practicum, but the final responsibility for finding an internship rests with the student.

Enroll in Internship Preparation at least one semester before beginning an internship.

Prerequisites:  Enrollment is restricted to EADP majors who have completed EADP 3010, 3035, and 3045, and consent of the Internship Coordinator.

Topics covered in this course include: career counseling, resume development, professionalism and interviewing skills.

EADP 4810 - Internship Practicum 

Students will meet during scheduled classes to monitor progress, discuss experiences, turn in documentation and resolve concerns. The dates, locations and time for the class will be announced at the beginning of each semester via student email.

Internship Coordinator must approve internship prior to beginning internship. If it is not approved, it will not count.

Pre-requisites: Enrollment is restricted to EADP majors who have completed EADP 4800, 3010, 3035, 3045, plus 3 additional hours of EADP coursework. After a student has arranged for an internship, they must register for Internship Practicum (EADP 4810).

EADP 4810 is a restricted enrollment course and requires a restriction code for registration. You MUST contact the Internship Coordinator prior to registration in order to enroll in this course. It is best to acquire your code at least two weeks prior to your registration date. Do NOT wait until the day you are scheduled to register to try to obtain your registration code.

Obtaining an Internship

Internship opportunities are available with a variety of public agencies and departments, as well as at various levels of government. Students may also serve as interns in the private and nonprofit sectors. Internships complement coursework in the major field with practical, hands on knowledge. Students gain a better understanding of emergency management principles while also obtaining experience, credentials, and identity in the field. EADP internships, therefore, serve a very important step in the student's career preparation and development.

When anticipating an internship, you should begin by thinking about the type of work experience you would like to complete.  For example, consider whether you hope to work in the public, private or nonprofit sector.  Then, narrow the choice further by specific organization (e.g. municipal, state or federal government) and functional area (e.g. planning or response).  The internship preparation course will also help to identify student's strengths and areas of professional interest.  All students enrolled in EADP 4810 must register with Eagle Careers through the UNT Career Center. Students may find an internship searching opportunities posted on Eagle Careers, through networking, and reading professional newsletters.  To qualify for course credit, the internship must be approved by the Internship Coordinator prior to beginning the internship, be related to Emergency Administration and Planning, and supervised by a professional in the field.

If you have any questions about internship requirements or procedures, please contact the Internship Coordinator,  Dr. Ron Timmons.

Internship Waiver Form

Occasionally, students will enter the Emergency Administration and Planning program with professional experience in the field. Students who feel they have a great deal of experience directly related to emergency management can appeal for an internship waiver. Students will need to be able to articulate in a scholarly manner how their full-time professional experiences directly relate to all four phases of emergency management. A faculty committee will carefully review the request. If a student is waived from the internship requirement, their degree plan will be altered.

Additionally, a few students will have sufficient experience in a professional setting although not necessarily related to emergency management. In this situation, students may appeal to be waived from the Internship Preparation class, but still expect to do an internship. In order to be waived from the Internship Preparation Course, students will fill out the Internship Waiver Request. If the student is granted a waiver from EADP 4800, then the student will need to meet with the Internship Coordinator BEFORE accepting an internship for academic credit.