assignment problem matlab code

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

Algorithm to solve an assignment or matching with a constraint

Here is the problem. Suppose we have N workers and N jobs. We want to assign each job exactly one worker. For each worker i, he could do some jobs on some cost. Our goal is to minimize the total cost on the condition that any single cost should be less than some value.

For example, 10 workers and 10 jobs. Worker 1 can do job 1 with $0.8, job 2 with $2.3, job 3 with $15.8, jobs 4 to 8 with $100, job 9 with $3.2, job 10 with $15.3.

Worker 2 can do job 1 with $3.5, job 2 with $2.3, job 3 with $4.6, job 4 with $17, etc.

Our goal is to find a matching or we can call it an assignment such that the total cost is minimized but any single cost of the corresponding pair/matching between work i and job i is less than a value like $50.

I would very much like to solve it in MATLAB if possible.

• optimization
• variable-assignment
• linear-programming

• 1 Maybe I miss something, but the problem seems to be very simple. For every Job find the cheapest worker, check if the pair of job and worker is has costs below $50, assign job. –  Daniel Commented Oct 23, 2013 at 23:14
• 2 @DanielR: You are missing something. For example, worker 1 might be more expensive on job 1 than some other, but putting him on job 1 might still give the lowest overall cost (e.g., he's $0.01 extra on job 1, but costs $1.0 extra on any other job). –  Jerry Coffin Commented Oct 23, 2013 at 23:20
• 1 @JerryCoffin: You are right, if there is a limit of 1 job per worker. Don't know what is intended. –  Daniel Commented Oct 23, 2013 at 23:24
• @DanielR That idea is pretty much like the Greedy algorithm. It is useful. I was trying to find the minimum so that may not be the optimal solution. –  Appalachian Math Commented Oct 23, 2013 at 23:46

This is a slight variation of the Assignment Problem . To handle your additional constraint that no single job cost should be more than some value, just change all entries in the matrix of costs that are greater than this threshold to a huge value (bigger than the sum of all other entries will suffice), and solve as usual, using e.g. the Hungarian Algorithm .

• 1 @AppalachianMath: You're welcome :) Sure, it works for non-integer costs. It might be described in terms of maximising a sum of weights, rather than minimising them, in which case just swap all ">"s for "<"s and vice versa (or alternatively make all your numbers negative). –  j_random_hacker Commented Oct 23, 2013 at 23:46
• 1 Do you mean that it only goes slow if you change the values that are greater than the threshold? In any case I would expect it to take a while for a 1000x1000 matrix as it's an O(n^3) algorithm! You might be able to solve the assignment problem using a different algorithm, or get a linear program solver like lp_solve to solve it faster. –  j_random_hacker Commented Oct 24, 2013 at 1:32
• 1 I wrote that first sentence because I was trying to figure out why you wrote "There is a problem when I change all entries that are greater than the threshold into a larger value" instead of just "There is a problem". I suggested LP because it might be faster -- but probably only if the LP solver is smart enough to detect that this is a variant of the assignment problem, and apply a special solution technique for it. Commercial (I)LP solvers, like Gurobi, have a lot of this kind of stuff built in :) –  j_random_hacker Commented Oct 24, 2013 at 2:02
• 1 If you use LP, then you would just omit any pairings that exceed the threshold, rather than setting them to a huge value. If there are a large number of pairings that exceed the threshold, ordinary simplex or barrier LP methods might well solve the problem faster than the Hungarian method -- have to try and see! –  j_random_hacker Commented Oct 24, 2013 at 2:03
• 1 No I don't sorry -- it's been years since I touched MATLAB. I seem to recall there was an "Optimization Toolbox" or something for it though. That might have something like this. –  j_random_hacker Commented Oct 24, 2013 at 2:05

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 matlab optimization variable-assignment linear-programming or ask your own question .

• The Overflow Blog
• One of the best ways to get value for AI coding tools: generating tests
• The world’s largest open-source business has plans for enhancing LLMs
• Featured on Meta
• User activation: Learnings and opportunities
• Site maintenance - Mon, Sept 16 2024, 21:00 UTC to Tue, Sept 17 2024, 2:00...
• What does a new user need in a homepage experience on Stack Overflow?
• Announcing the new Staging Ground Reviewer Stats Widget

Hot Network Questions

• Why did early ASCII have ← and ↑ but not ↓ or →?
• security concerns of executing mariadb-dump with password over ssh
• Place with signs in Chinese & Arabic
• Stuck as a solo dev
• Why is the \[ThickSpace] character defined as 5/18 em instead of 1/4 em as in Unicode?
• When I use \llap to overlap words, the space between the overlapped words and the rest of the text is too much: how do I fix it?
• O(nloglogn) Sorting Algorithm?
• Trying to find air crash for a case study
• Multi-producer, multi-consumer blocking queue
• How should I email HR after an unpleasant / annoying interview?
• Would a scientific theory of everything be falsifiable?
• What was it that Wittgenstein found funny here?
• Looking for a short story on chess, maybe published in Playboy decades ago?
• Why does a capacitor act as an open circuit under a DC circuit?
• On the history of algae classification
• Does such a manifold exist??
• In Photoshop, when saving as PNG, why is the size of my output file bigger when I have more invisible layers in the original file?
• What's the strongest material known to humanity that we could use to make Powered Armor Plates?
• Longtable goes beyond the right margin and footnote does not fit under the table
• How many engineers/scientists believed that human flight was imminent as of the late 19th/early 20th century?
• Building rear track wheel from road wheel
• Function with memories of its past life
• "There is a bra for every ket, but there is not a ket for every bra"
• Existence of 2-fold branched covers

• 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
• OpenAI o1 AI Model Launched: Explore o1-Preview, o1-Mini, Pricing & Comparison
• How to Merge Cells in Google Sheets: Step by Step Guide
• How to Lock Cells in Google Sheets : Step by Step Guide
• PS5 Pro Launched: Controller, Price, Specs & Features, How to Pre-Order, and More
• #geekstreak2024 – 21 Days POTD Challenge Powered By Deutsche Bank

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Browse Course Material

Course info.

• Orhan Celiker

Departments

• Electrical Engineering and Computer Science

As Taught In

• Graphics and Visualization
• Programming Languages

Learning Resource Types

Introduction to matlab, assignments.

There are four problem sets, due daily. The first one will be released after the first class, and it will be due before the second class. The last problem set will be due before the last class. Problem set grading will be done coarsely (i.e. we will not penalize you for minor mistakes).

You are leaving MIT OpenCourseWare

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications You must be signed in to change notification settings

Gate Assignment Problem

mncosta/gap

Folders and files.

Repository files navigation

Airport gate assignment problem (agap).

Project developed for the PhD subject of Optimization of Transports Infrastructures and Operations . Reproduction of Optimization of multiple objective gate assignments, Shangyao Yan and Cheun-Ming Huo .

Gate assignment is done under two objective functions: Passenger Walking Distance and Passenger Waiting Time.

An airport layout is randomly generated, as well as flights. Then the optimization problem is created and solved in order to assign a gate to a flight.

• MATLAB 100.0%

• MATLAB Answers
• File Exchange
• AI Chat Playground
• Discussions
• Communities
• Treasure Hunt
• Community Advisors
• Virtual Badges
• MathWorks.com
• Trial software

You are now following this Submission

• You may receive emails, depending on your communication preferences

ACAC_Assignment_1

View License

• Open in MATLAB Online
• Version History
• Reviews (0)
• Discussions (0)

Abhinav (2024). ACAC_Assignment_1 (https://www.mathworks.com/matlabcentral/fileexchange/172585-acac_assignment_1), MATLAB Central File Exchange. Retrieved September 15, 2024 .

MATLAB Release Compatibility

Platform compatibility, tags add tags, community treasure hunt.

Find the treasures in MATLAB Central and discover how the community can help you!

Discover Live Editor

Create scripts with code, output, and formatted text in a single executable document.

Learn About Live Editor

• ACAC_Assignment1.m

Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

You can also select a web site from the following list

How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

• América Latina (Español)
• Canada (English)
• United States (English)
• Belgium (English)
• Denmark (English)
• Deutschland (Deutsch)
• España (Español)
• Finland (English)
• France (Français)
• Ireland (English)
• Italia (Italiano)
• Luxembourg (English)
• Netherlands (English)
• Norway (English)
• Österreich (Deutsch)
• Portugal (English)
• Sweden (English)
• United Kingdom (English)

Asia Pacific

• Australia (English)
• India (English)
• New Zealand (English)
• 简体中文 Chinese
• 日本 Japanese (日本語)
• 한국 Korean (한국어)

Contact your local office