what is assignment problem in daa

Assignment Problem: Meaning, Methods and Variations | Operations Research

After reading this article you will learn about:- 1. Meaning of Assignment Problem 2. Definition of Assignment Problem 3. Mathematical Formulation 4. Hungarian Method 5. Variations.

Meaning of Assignment Problem:

An assignment problem is a particular case of transportation problem where the objective is to assign a number of resources to an equal number of activities so as to minimise total cost or maximize total profit of allocation.

The problem of assignment arises because available resources such as men, machines etc. have varying degrees of efficiency for performing different activities, therefore, cost, profit or loss of performing the different activities is different.

Thus, the problem is “How should the assignments be made so as to optimize the given objective”. Some of the problem where the assignment technique may be useful are assignment of workers to machines, salesman to different sales areas.

Definition of Assignment Problem:

ADVERTISEMENTS:

Suppose there are n jobs to be performed and n persons are available for doing these jobs. Assume that each person can do each job at a term, though with varying degree of efficiency, let c ij be the cost if the i-th person is assigned to the j-th job. The problem is to find an assignment (which job should be assigned to which person one on-one basis) So that the total cost of performing all jobs is minimum, problem of this kind are known as assignment problem.

The assignment problem can be stated in the form of n x n cost matrix C real members as given in the following table:

Baeldung Pro comes with both absolutely No-Ads as well as finally with Dark Mode , for a clean learning experience:

>> Explore a clean Baeldung

Once the early-adopter seats are all used, the price will go up and stay at $33/year.

1. Overview

In computer science, there is a large number of optimization problems which has a finite but extensive number of feasible solutions. Among these, some problems like finding the shortest path in a graph  or  Minimum Spanning Tree  can be solved in polynomial time .

A significant number of optimization problems like production planning , crew scheduling can’t be solved in polynomial time, and they belong to the NP-Hard class . These problems are the example of NP-Hard combinatorial optimization problem .

Branch and bound (B&B) is an algorithm paradigm widely used for solving such problems.

In this tutorial, we’ll discuss the branch and bound method in detail.

2. Basic Idea

Branch and bound algorithms are used to find the optimal solution for combinatory, discrete, and general mathematical optimization problems. In general, given an NP-Hard problem, a branch and bound algorithm explores the entire search space of possible solutions and provides an optimal solution.

A branch and bound algorithm consist of stepwise enumeration of possible candidate solutions by exploring the entire search space. With all the possible solutions, we first build a rooted decision tree. The root node represents the entire search space:

Here, each child node is a partial solution and part of the solution set. Before constructing the rooted decision tree, we set an upper and lower bound for a given problem based on the optimal solution. At each level, we need to make a decision about which node to include in the solution set. At each level, we explore the node with the best bound. In this way, we can find the best and optimal solution fast.

Now it is crucial to find a good upper and lower bound in such cases. We can find an upper bound by using any local optimization method or by picking any point in the search space. On the other hand, we can obtain a lower bound from convex relaxation  or  duality .

In general, we want to partition the solution set into smaller subsets of solution. Then we construct a rooted decision tree, and finally, we choose the best possible subset (node) at each level to find the best possible solution set.

3. When Branch and Bound Is a Good Choice?

We already mentioned some problems where a branch and bound can be an efficient choice over the other algorithms. In this section, we’ll list all such cases where a branch and bound algorithm is a good choice.

If the given problem is a discrete optimization problem, a branch and bound is a good choice. Discrete optimization is a subsection of optimization where the variables in the problem should belong to the discrete set. Examples of such problems are 0-1 Integer Programming  or  Network Flow problem .

Branch and bound work efficiently on the combinatory optimization problems. Given an objective function for an optimization problem, combinatory optimization is a process to find the maxima or minima for the objective function. The domain of the objective function should be discrete and large. Boolean Satisfiability , Integer Linear Programming are examples of the combinatory optimization problems.

4. Branch and Bound Algorithm Example

In this section, we’ll discuss how the job assignment problem can be solved using a branch and bound algorithm.

4.1. Problem Statement

We can assign any of the available jobs to any worker with the condition that if a job is assigned to a worker, the other workers can’t take that particular job. We should also notice that each job has some cost associated with it, and it differs from one worker to another.

Here the main aim is to complete all the jobs by assigning one job to each worker in such a way that the sum of the cost of all the jobs should be minimized.

4.2. Branch and Bound Algorithm Pseudocode

Now let’s discuss how to solve the job assignment problem using a branch and bound algorithm.

Let’s see the pseudocode first:

In the search space tree, each node contains some information, such as cost, a total number of jobs, as well as a total number of workers.

Now let’s run the algorithm on the sample example we’ve created:

4. Advantages

In a branch and bound algorithm, we don’t explore all the nodes in the tree. That’s why the time complexity of the branch and bound algorithm is less when compared with other algorithms.

If the problem is not large and if we can do the branching in a reasonable amount of time, it finds an optimal solution for a given problem.

The branch and bound algorithm find a minimal path to reach the optimal solution for a given problem. It doesn’t repeat nodes while exploring the tree.

5. Disadvantages

The branch and bound algorithm are time-consuming. Depending on the size of the given problem, the number of nodes in the tree can be too large in the worst case.

Also, parallelization is extremely difficult in the branch and bound algorithm.

6. Conclusion

One of the most popular algorithms used in the optimization problem is the branch and bound algorithm. We’ve discussed it thoroughly in this tutorial.

We’ve explained when a branch and bound algorithm would be the right choice for a user to use. Furthermore, we’ve presented a branch and bound based algorithm for solving the job assignment problem.

Finally, we mentioned some advantages and disadvantages of the branch and bound algorithm.

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

Mastering LC Branch and Bound in DAA: A Comprehensive Guide

Learn how to solve complex optimization problems using the LC Branch and Bound algorithm in Design and Analysis of Algorithms (DAA). This in-depth guide covers the basics, implementation, and applications of this powerful technique.

Create an image featuring JavaScript code snippets and interview-related icons or graphics. Use a color scheme of yellows and blues. Include the title '7 Essential JavaScript Interview Questions for Freshers'.

LC Branch and Bound in DAA: A Comprehensive Guide

Introduction.

In the realm of Design and Analysis of Algorithms (DAA), the LC Branch and Bound method is a powerful technique used to solve complex optimization problems. This method is particularly useful in solving NP-hard problems, which are notoriously difficult to solve using traditional methods. In this blog post, we will delve into the world of LC Branch and Bound, exploring its principles, advantages, and applications.

What is LC Branch and Bound?

The LC Branch and Bound method is a hybrid algorithm that combines the strengths of two popular optimization techniques: Linear Programming (LP) and Branch and Bound (B&B). The "LC" in LC Branch and Bound stands for "Linear Cutting," which refers to the use of linear programming relaxations to generate bounds and cuts.

The Branch and Bound method is a popular optimization technique used to solve discrete optimization problems. It works by recursively partitioning the solution space into smaller sub-problems, solving each sub-problem, and then combining the solutions to obtain the optimal solution. However, the B&B method can be slow and inefficient, especially for large problems.

The LC Branch and Bound method addresses this limitation by incorporating linear programming relaxations into the B&B framework. By solving LP relaxations, the algorithm can generate tighter bounds and cuts, which help to prune the search space and reduce the number of nodes to be explored. This results in a significant reduction in computational time and memory usage.

How LC Branch and Bound Works

The LC Branch and Bound algorithm can be broken down into the following steps:

Step 1: Problem Formulation

The algorithm starts by formulating the optimization problem as a Mixed-Integer Linear Program (MILP). The MILP is a mathematical model that represents the problem using linear equations and inequalities, with some variables restricted to be integers.

Step 2: Linear Programming Relaxation

The algorithm solves the LP relaxation of the MILP, which is obtained by dropping the integrality constraints. The LP relaxation provides a lower bound on the optimal solution, which is used to prune the search space.

Step 3: Branching

The algorithm selects a node from the search tree and applies branching rules to create two child nodes. The branching rules are designed to partition the solution space into smaller sub-problems.

Step 4: Bounding

The algorithm solves the LP relaxation of each child node and computes a lower bound on the optimal solution. The lower bound is used to prune the search space and eliminate nodes that are unlikely to contain the optimal solution.

Step 5: Cutting

The algorithm applies cutting plane methods to generate additional constraints that help to tighten the LP relaxation. The cutting planes are used to reduce the search space and improve the lower bound.

Step 6: Fathoming

The algorithm applies fathoming rules to eliminate nodes that are unlikely to contain the optimal solution. Fathoming is based on the lower bound and the gap between the lower bound and the incumbent solution.

Step 7: Repeat

The algorithm repeats steps 3-6 until the optimal solution is found or a stopping criterion is reached.

Advantages of LC Branch and Bound

The LC Branch and Bound method offers several advantages over traditional optimization techniques:

Improved Computational Efficiency

The LC Branch and Bound method is computationally efficient, especially for large problems. By using LP relaxations and cutting planes, the algorithm can reduce the search space and prune nodes that are unlikely to contain the optimal solution.

Tighter Bounds

The LC Branch and Bound method provides tighter bounds on the optimal solution, which helps to reduce the search space and improve the convergence rate.

Flexibility

The LC Branch and Bound method can be applied to a wide range of optimization problems, including MILPs, integer programs, and stochastic programs.

Applications of LC Branch and Bound

The LC Branch and Bound method has been successfully applied to a wide range of optimization problems, including:

The LC Branch and Bound method has been used to solve complex scheduling problems, such as job shop scheduling and flow shop scheduling.

Logistics and Supply Chain Management

The LC Branch and Bound method has been used to optimize logistics and supply chain management problems, such as vehicle routing and inventory management.

Energy and Resource Allocation

The LC Branch and Bound method has been used to optimize energy and resource allocation problems, such as power grid management and resource allocation in cloud computing.

In this blog post, we have explored the principles and applications of the LC Branch and Bound method in DAA. This powerful optimization technique has been shown to be effective in solving complex optimization problems, including MILPs, integer programs, and stochastic programs. By combining the strengths of LP relaxations and Branch and Bound, the LC Branch and Bound method provides a robust and efficient framework for solving optimization problems.

• [1] Nemhauser, G. L., & Wolsey, L. A. (1988). Integer and combinatorial optimization. Wiley-Interscience.
• [2] Parker, R. G., & Rardin, R. L. (1988). Discrete optimization. Academic Press.
• [3] Geoffrion, A. M. (1972). Generalized Benders decomposition. Journal of Optimization Theory and Applications, 10(4), 237-260.

Q: What is the main advantage of the LC Branch and Bound method?

A: The main advantage of the LC Branch and Bound method is its ability to solve complex optimization problems efficiently, especially for large problems.

Q: How does the LC Branch and Bound method differ from traditional Branch and Bound?

A: The LC Branch and Bound method differs from traditional Branch and Bound in its use of LP relaxations and cutting planes to generate tighter bounds and prune the search space.

Q: What types of problems can be solved using the LC Branch and Bound method?

A: The LC Branch and Bound method can be used to solve a wide range of optimization problems, including MILPs, integer programs, and stochastic programs.

• Create Account

Design and Analysis of Algorithms

This course introduces basic elements of the design and analysis of computer algorithms. Topics include asymptotic notations and analysis, divide and conquer strategy, greedy methods, dynamic programming, basic graph algorithms, NP-completeness, and approximation algorithms. For each topic, beside in-depth coverage, one or more representative problems and their algorithms shall be discussed.

• Question Banks
• DAA Model question
• DAA Question Bank 2080
• DAA Question Bank 2079
• DAA Question Bank 2076
• DAA Question Bank 2078

Tribhuvan University

Institute of Science and Technology

Bachelor Level / fifth-semester / Science

Computer Science and Information Technology( CSC314 )

Full Marks: 60 + 20 + 20

Pass Marks: 24 + 8 + 8

Time: 3 Hours

Candidates are required to give their answers in their own words as far as practicable.

The figures in the margin indicate full marks.

Attempt any two questions.

What is recurrence relation? How it can be solved? Show that time complexity of the recurrence relation T(n) = 2T(n/2) + 1 is O(n) using substitution method.

Write down the advantages of dynamic programming over greedy strategy. Find optimal bracketing to multiply 4 matrices of order 2,3,4,2,5.

Discuss heapify operation with example. Write down its algorithm and analyze its time and space complexity.

Attempt any eight questions

Define RAM model. Write down iterative algorithm for finding factorial and provide its detailed analysis.

Write down algorithm of insertion sort and analyze its time and space complexity.

Write down minmax algorithm and analyze its complexity.

When greedy strategy provides optimal solution? Write down job sequencing with deadlines algorithm and analyze its complexity.

Suppose that a message contains alphabet frequencies as given below and find Huffman codes for each alphabet

Does backtracking give multiple solution? Trace subset sum algorithm for the set {3,5,2,4,1} andd sum=8.

Why extended euclidean algorithm is used? Write down its algorithm and analyze its complexity.

Define NP-complete problems with examples. Give brief proof of the statement “SAT is NP-complete”.

Write short notes on

a) Aggregate Analysis

b) Selection problems

Design and Analysis of Algorithms Question Bank Solution 2080

Share this link via

Or copy link

Copyright 2024 | HAMROCSIT.COM | All Right Reserved - Nymna Technology

• DAA Tutorial
• DAA Algorithm
• Need of Algorithm
• Complexity of Algorithm
• Algorithm Design Techniques
• Asymptotic Analysis
• Analyzing Algorithm Control Structure
• Recurrence Relation
• Recursion Tree Method
• Master Method

Analysis of Sorting

• Bubble Sort
• Selection Sort
• Insertion Sort

Divide and Conquer

• Introduction
• Max-Min Problem
• Binary Search
• Tower of Hanoi
• Binary Heap
• Stable Sorting
• Lower bound Theory

Sorting in Linear Time

• Linear Time
• Counting Sort
• Bucket Sort
• Hash Tables
• Hashing Method
• Open Addressing Techniques
• Hash Function

Binary Search Trees

• Red Black Tree
• Dynamic Programming
• Divide & Conquer Method vs Dynamic Programming
• Fibonacci sequence
• Matrix Chain Multiplication
• Matrix Chain Multiplication Example
• Matrix Chain Multiplication Algorithm
• Longest Common Sequence
• Longest Common Sequence Algorithm
• 0/1 Knapsack Problem
• DUTCH NATIONAL FLAG
• Longest Palindrome Subsequence
• Longest Increasing Subsequence
• Longest Common Subsequence
• Tabulation vs Memoization
• How to solve a dynamic programming problem
• Optimal Substructure Property
• Overlapping sub-problems
• Dynamic programming vs Greedy approach
• Regular Expression Matching
• Branch and bound vs backtracking
• Branch and bound
• Longest Repeated Subsequence
• Longest Common Substring
• Shortest Common Supersequence
• Dynamic Programming vs Divide and Conquer
• Maximum Sum Increasing Subsequence
• Wildcard Pattern Matching
• Largest Sum Contiguous Subarray
• Shortest Sum Contiguous Subarray
• Dynamic programming vs Backtracking
• Brute force approach
• Fractional vs 0/1 knapsack problem
• Traveling Salesperson problem using branch and bound
• Integer Partition Problem
• Kruskal Algorithm

Greedy Algorithm

• Greedy Algorithms
• Activity Selection Problem
• Fractional Knapsack problem
• Huffman Codes
• Algorithm of Huffman Code
• Activity or Task Scheduling Problem
• Travelling Sales Person Problem
• Dynamic Programming vs Greedy Method

Backtracking

• Backtracking Introduction
• Recursive Maze Algorithm
• Hamiltonian Circuit Problems
• Subset Sum Problems
• N Queens Problems
• MST Introduction
• MST Applications
• Kruskal's Algorithm
• Prim's Algorithm

Shortest Path

• Negative Weight Edges
• Representing Shortest Path
• Dijkstra's Algorithm
• Bellman-Ford Algorithm
• Single Source Shortest Path in a directed Acyclic Graphs

All-Pairs Shortest Paths

• Floyd-Warshall Algorithm
• Johnson's Algorithm

Maximum Flow

• Flow networks and Flows
• Network Flow Problems
• Ford Fulkerson Algorithm
• Maximum bipartite matching

Sorting Networks

• Comparison Network
• Bitonic Sorting Network
• Merging Network

Complexity Theory

• Complexity Classes
• Polynomial Time Verification
• NP-Completeness
• Circuit Satisfiability
• 3-CNF Satisfiability
• Clique Problem
• Vertex Cover Problem
• Subset-Sum Problem

Approximation Algo

• Vertex Cover
• Travelling Salesman Problem

String Matching

• Naive String Matching Algorithm
• Rabin-Karp-Algorithm
• String Matching with Finite Automata
• Knuth-Morris-Pratt Algorithm
• Boyer-Moore Algorithm
• Kosaraju Algorithm
• Hashing algorithm
• Huffman Coding Algorithm
• Kadane's Algorithm
• Dijkstra Algorithm Example
• Euclidean algorithm
• Floyd's Algorithm
• Properties of Algorithm
• Time Complexity of Kruskals Algorithm
• Kosaraju's Algorithm
• Characteristics of an Algorithm
• Algorithm Examples
• Searching Algorithms
• Algorithm for Binary Search
• Sorting Algorithms: Slowest to Fastest
• Extended Euclidian Algorithm
• How to Write an Algorithm
• Recursive Algorithm
• Sliding Window Algorithm
• Difference Between Algorithms and Flowcharts
• PageRank Algorithm
• Greedy Algorithm Example

Interview Questions

• DAA Interview Questions

Latest Courses

We provides tutorials and interview questions of all technology like java tutorial, android, java frameworks

Contact info

G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India

[email protected] .

Online Compiler

Knapsack Problem

When given a set of items, where each item has a weight and a value, we need to determine a subset of items that are to be included in a collection in such a way that the total weight aggregates up to be lower than or equal to a given limit and the total value could be as big as possible. 

The Knapsack problem is an instance of a Combinatorial Optimization problem. One general approach to crack difficult problems is to identify the most restrictive constraint. For this, we must ignore the others and solve a knapsack problem, and finally, we must somehow fit the solution to satisfy the constraints that are ignored. 

Applications

For multiple cases of resource allocation problems that have some specific constraints, the problem can be solved in a way that is similar to the Knapsack problem. Following are a set of examples. 

•  Finding the least wasteful way to cut down the basic materials 
•  portfolio optimization 
•  Cutting stock problems 

Problem Scenario

Consider a problem scenario where a thief is robbing a store and his knapsack ( bag) can carry a maximal weight of W. Consider that there are n items in the store and the weight of the ith item is wi and its respective profit is pi. 

What are all the items the thief should take?  

Here, the main goal/objective of the thief is to maximize the profit anyhow. So, the items should opt-in such a way that the items which are carried by the thief will fetch the maximum profit. 

Based on the nature of the items, Knapsack problems are classified into two categories 

• Fractional Knapsack 

Fractional Knapsack

In this category, items can be broken into smaller pieces, and the thief can select fractions of items.

According to the problem scenario,

• There are n items in the store
• Weight of ith item 
• Profit for ith item 
• pi>0 and
• The capacity of the Knapsack is W

As the name suggests, in the Knapsack problem, items can be broken into smaller fragments. So, the thief might only take a fraction or a part of xi of ith item.

The ith item in the store contributes a weight of xi.wi to the total weight in the knapsack(bag) and profit xi.pi to the Total Profit.

Hence, the main objective of the algorithm is basically to maximize the value of ∑n=1n(xi.pi) with respect to the given constraint,

We already know that a solution that is said to be an optimal solution must fill the knapsack(bag) exactly, if not, we could at least add a smaller fraction of one of the remaining items. This will result in an increase in the overall profit.

Thus, an optimal solution to this problem can be obtained by,

Now, we have to sort all those items based on their values of piwi, so that

Here,  x is an array that is used to store the fraction of items.

Suppose that we are provided with items that have already been sorted in the decreasing order of piwi, then the time taken by the “while” will be O(n) . So, the total time including that includes even sorting will be O(n logn) .

Let us consider that the capacity of the knapsack(bag) W = 60 and the list of items are shown in the following table −

We can see that the provided items are not sorted based on the value of piwi, we perform sorting. After sorting, the items are shown in the following table.

Once we sort all the items according to the piwi, we choose all of B as the weight of B is less compared to that of the capacity of the knapsack. Further, we choose item A , as the available capacity of the knapsack is greater than the weight of A . Now, we will choose C as the next item. Anyhow, the whole item cannot be chosen as the remaining capacity of the knapsack is less than the weight of the chosen item – C .

Hence, a fraction of C (i.e. (60 − 50)/20) is chosen.

Now, we reach the stage where the capacity of the Knapsack is equal to the chosen items. Hence, no more items can be selected.

The total weight of the chosen items is 40 + 10 + 20 * (10/20) = 60

And the total profit is 101 + 281 + 121 * (10/20) = 380 + 60 = 440

This is the optimal solution. We cannot gain more profit compared to this by selecting any different combination of items out of the provided items.

Algorithm :