what is assignment problem model

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:

• In the above asignment problem, we have to provide assignments such that there is one to one assignments and the overall cost is minimized.

How Assignment Problem is related to LPP? OR Write mathematical formulation of Assignment Model.

→ Assignment Model is a special application of Linear Programming (LP).

→ The mathematical formulation for Assignment Model is given below:

→ Let, C i j \text {C}_{ij} C ij ​ denotes the cost of resources 'i' to the task 'j' ; such that

→ Now assignment problems are of the Minimization type. So, our objective function is to minimize the overall cost.

→ Subjected to constraint;

(i) For all j t h j^{th} j t h task, only one i t h i^{th} i t h resource is possible:

(ii) For all i t h i^{th} i t h resource, there is only one j t h j^{th} j t h task possible;

(iii) x i j x_{ij} x ij ​ is '0' or '1'.

Types of Assignment Problem:

(i) balanced assignment problem.

• It consist of a suqare matrix (n x n).
• Number of rows = Number of columns

(ii) Unbalanced Assignment Problem

• It consist of a Non-square matrix.
• Number of rows ≠ \not=  = Number of columns

Methods to solve Assignment Model:

(i) integer programming method:.

In assignment problem, either allocation is done to the cell or not.

So this can be formulated using 0 or 1 integer.

While using this method, we will have n x n decision varables, and n+n equalities.

So even for 4 x 4 matrix problem, it will have 16 decision variables and 8 equalities.

So this method becomes very lengthy and difficult to solve.

(ii) Transportation Methods:

As assignment problem is a special case of transportation problem, it can also be solved using transportation methods.

In transportation methods ( NWCM , LCM & VAM), the total number of allocations will be (m+n-1) and the solution is known as non-degenerated. (For eg: for 3 x 3 matrix, there will be 3+3-1 = 5 allocations)

But, here in assignment problems, the matrix is a square matrix (m=n).

So total allocations should be (n+n-1), i.e. for 3 x 3 matrix, it should be (3+3-1) = 5

But, we know that in 3 x 3 assignment problem, maximum possible possible assignments are 3 only.

So, if are we will use transportation methods, then the solution will be degenerated as it does not satisfy the condition of (m+n-1) allocations.

So, the method becomes lengthy and time consuming.

(iii) Enumeration Method:

It is a simple trail and error type method.

Consider a 3 x 3 assignment problem. Here the assignments are done randomly and the total cost is found out.

For 3 x 3 matrix, the total possible trails are 3! So total 3! = 3 x 2 x 1 = 6 trails are possible.

The assignments which gives minimum cost is selected as optimal solution.

But, such trail and error becomes very difficult and lengthy.

If there are more number of rows and columns, ( For eg: For 6 x 6 matrix, there will be 6! trails. So 6! = 6 x 5 x 4 x 3 x 2 x 1 = 720 trails possible) then such methods can't be applied for solving assignments problems.

(iv) Hungarian Method:

It was developed by two mathematicians of Hungary. So, it is known as Hungarian Method.

It is also know as Reduced matrix method or Flood's technique.

There are two main conditions for applying Hungarian Method:

(1) Square Matrix (n x n). (2) Problem should be of minimization type.

Suggested Notes:

Modified Distribution Method (MODI) | Transportation Problem | Transportation Model

Stepping Stone | Transportation Problem | Transportation Model

Vogel’s Approximation Method (VAM) | Method to Solve Transportation Problem | Transportation Model

Transportation Model - Introduction

North West Corner Method | Method to Solve Transportation Problem | Transportation Model

Least Cost Method | Method to Solve Transportation Problem | Transportation Model

Tie in selecting row and column (Vogel's Approximation Method - VAM) | Numerical | Solving Transportation Problem | Transportation Model

Crashing Special Case - Multiple (Parallel) Critical Paths

Crashing Special Case - Indirect cost less than Crash Cost

Basics of Program Evaluation and Review Technique (PERT)

Numerical on PERT (Program Evaluation and Review Technique)

Network Analysis - Dealing with Network Construction Basics

Construct a project network with predecessor relationship | Operation Research | Numerical

Graphical Method | Methods to solve LPP | Linear Programming

Basics of Linear Programming

Linear Programming Problem (LPP) Formulation with Numericals

All comments that you add will await moderation. We'll publish all comments that are topic related, and adhere to our Code of Conduct .

Want to tell us something privately? Contact Us

Post comment

Education Lessons

Stay in touch, [notes] operation research, [notes] dynamics of machinery, [notes] maths, [notes] science, [notes] computer aided design.

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

Solving an Assignment Problem

This section presents an example that shows how to solve an assignment problem using both the MIP solver and the CP-SAT solver.

In the example there are five workers (numbered 0-4) and four tasks (numbered 0-3). Note that there is one more worker than in the example in the Overview .

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.

MIP solution

The following sections describe how to solve the problem using the MPSolver wrapper .

Import the libraries

The following code imports the required libraries.

Create the data

The following code creates the data for the problem.

The costs array corresponds to the table of costs for assigning workers to tasks, shown above.

Declare the MIP solver

The following code declares the MIP solver.

Create the variables

The following code creates binary integer variables for the problem.

Create the constraints

Create the objective function.

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.

Print the solution

The following code prints the solution to the problem.

Here is the output of the program.

Complete programs

Here are the complete programs for the MIP solution.

CP SAT solution

The following sections describe how to solve the problem using the CP-SAT solver.

Declare the model

The following code declares the CP-SAT model.

The following code sets up the data for the problem.

The following code creates the constraints for the problem.

Here are the complete programs for the CP-SAT solution.

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 2023-01-02 UTC.

• Kopere Dashboard
• Online Resources University Website AMS Students Module AMS Lectuter's Module (LAN ONLY) Attachment System Clearance System University Intranet (LAN ONLY) Safe Exam Browser (Windows) Safe Exam Browser (macOS) Password Reset (Staff) Password Reset (Students)
• University Library Library Catalog Off-Campus Access SU Digital Repository ExamsBank (On-Campus) ExamsBank (Off-Campus) eBooks+ BigBlueButton
• SBS eLearning
• MAPE eLearning
• Help Usage Tutorials FAQs+

Log in to Strathmore University eLearning System

Log in using your account on:.

• Data Structures
• Linked List
• Binary Tree
• Binary Search Tree
• Segment Tree
• Disjoint Set Union
• Fenwick Tree
• Red-Black Tree
• Advanced Data Structures

Hungarian Algorithm for Assignment Problem | Set 1 (Introduction)

• Hungarian Algorithm for Assignment Problem | Set 2 (Implementation)
• Introduction to Exact Cover Problem and Algorithm X
• Greedy Approximate Algorithm for Set Cover Problem
• Job Assignment Problem using Branch And Bound
• Implementation of Exhaustive Search Algorithm for Set Packing
• Channel Assignment Problem
• Chocolate Distribution Problem | Set 2
• Transportation Problem | Set 1 (Introduction)
• OLA Interview Experience | Set 11 ( For Internship)
• Top 20 Greedy Algorithms Interview Questions
• Job Sequencing Problem - Loss Minimization
• Prim's Algorithm (Simple Implementation for Adjacency Matrix Representation)
• Data Structures and Algorithms | Set 21
• Adobe Interview Experience | Set 55 (On-Campus Full Time for MTS profile)
• Amazon Interview Experience | Set 211 (On-Campus for Internship)
• OYO Rooms Interview Experience | Set 3 (For SDE-II, Gurgaon)
• C# Program for Dijkstra's shortest path algorithm | Greedy Algo-7
• Algorithms | Dynamic Programming | Question 7
• Amazon Interview | Set 46 (On-campus for Internship)

• 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

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Assignment Problem: Linear Programming

The assignment problem is a special type of transportation problem , where the objective is to minimize the cost or time of completing a number of jobs by a number of persons.

In other words, when the problem involves the allocation of n different facilities to n different tasks, it is often termed as an assignment problem.

The model's primary usefulness is for planning. The assignment problem also encompasses an important sub-class of so-called shortest- (or longest-) route models. The assignment model is useful in solving problems such as, assignment of machines to jobs, assignment of salesmen to sales territories, travelling salesman problem, etc.

It may be noted that with n facilities and n jobs, there are n! possible assignments. One way of finding an optimal assignment is to write all the n! possible arrangements, evaluate their total cost, and select the assignment with minimum cost. But, due to heavy computational burden this method is not suitable. This chapter concentrates on an efficient method for solving assignment problems that was developed by a Hungarian mathematician D.Konig.

"A mathematician is a device for turning coffee into theorems." -Paul Erdos

Formulation of an assignment problem

Suppose a company has n persons of different capacities available for performing each different job in the concern, and there are the same number of jobs of different types. One person can be given one and only one job. The objective of this assignment problem is to assign n persons to n jobs, so as to minimize the total assignment cost. The cost matrix for this problem is given below:

The structure of an assignment problem is identical to that of a transportation problem.

To formulate the assignment problem in mathematical programming terms , we define the activity variables as

for i = 1, 2, ..., n and j = 1, 2, ..., n

In the above table, c ij is the cost of performing jth job by ith worker.

Generalized Form of an Assignment Problem

The optimization model is

Minimize c 11 x 11 + c 12 x 12 + ------- + c nn x nn

subject to x i1 + x i2 +..........+ x in = 1          i = 1, 2,......., n x 1j + x 2j +..........+ x nj = 1          j = 1, 2,......., n

x ij = 0 or 1

In Σ Sigma notation

x ij = 0 or 1 for all i and j

An assignment problem can be solved by transportation methods, but due to high degree of degeneracy the usual computational techniques of a transportation problem become very inefficient. Therefore, a special method is available for solving such type of problems in a more efficient way.

Assumptions in Assignment Problem

• Number of jobs is equal to the number of machines or persons.
• Each man or machine is assigned only one job.
• Each man or machine is independently capable of handling any job to be done.
• Assigning criteria is clearly specified (minimizing cost or maximizing profit).

Share this article with your friends

Operations Research Simplified Back Next

Goal programming Linear programming Simplex Method Transportation Problem

How to Solve the Assignment Problem: A Complete Guide

Table of Contents

Assignment problem is a special type of linear programming problem that deals with assigning a number of resources to an equal number of tasks in the most efficient way. The goal is to minimize the total cost of assignments while ensuring that each task is assigned to only one resource and each resource is assigned to only one task. In this blog, we will discuss the solution of the assignment problem using the Hungarian method, which is a popular algorithm for solving the problem.

Understanding the Assignment Problem

Before we dive into the solution, it is important to understand the problem itself. In the assignment problem, we have a matrix of costs, where each row represents a resource and each column represents a task. The objective is to assign each resource to a task in such a way that the total cost of assignments is minimized. However, there are certain constraints that need to be satisfied – each resource can be assigned to only one task and each task can be assigned to only one resource.

Solving the Assignment Problem

There are various methods for solving the assignment problem, including the Hungarian method, the brute force method, and the auction algorithm. Here, we will focus on the steps involved in solving the assignment problem using the Hungarian method, which is the most commonly used and efficient method.

Step 1: Set up the cost matrix

The first step in solving the assignment problem is to set up the cost matrix, which represents the cost of assigning a task to an agent. The matrix should be square and have the same number of rows and columns as the number of tasks and agents, respectively.

Step 2: Subtract the smallest element from each row and column

To simplify the calculations, we need to reduce the size of the cost matrix by subtracting the smallest element from each row and column. This step is called matrix reduction.

Step 3: Cover all zeros with the minimum number of lines

The next step is to cover all zeros in the matrix with the minimum number of horizontal and vertical lines. This step is called matrix covering.

Step 4: Test for optimality and adjust the matrix

To test for optimality, we need to calculate the minimum number of lines required to cover all zeros in the matrix. If the number of lines equals the number of rows or columns, the solution is optimal. If not, we need to adjust the matrix and repeat steps 3 and 4 until we get an optimal solution.

Step 5: Assign the tasks to the agents

The final step is to assign the tasks to the agents based on the optimal solution obtained in step 4. This will give us the most cost-effective or profit-maximizing assignment.

Solution of the Assignment Problem using the Hungarian Method

The Hungarian method is an algorithm that uses a step-by-step approach to find the optimal assignment. The algorithm consists of the following steps:

• Subtract the smallest entry in each row from all the entries of the row.
• Subtract the smallest entry in each column from all the entries of the column.
• Draw the minimum number of lines to cover all zeros in the matrix. If the number of lines drawn is equal to the number of rows, we have an optimal solution. If not, go to step 4.
• Determine the smallest entry not covered by any line. Subtract it from all uncovered entries and add it to all entries covered by two lines. Go to step 3.

The above steps are repeated until an optimal solution is obtained. The optimal solution will have all zeros covered by the minimum number of lines. The assignments can be made by selecting the rows and columns with a single zero in the final matrix.

Applications of the Assignment Problem

The assignment problem has various applications in different fields, including computer science, economics, logistics, and management. In this section, we will provide some examples of how the assignment problem is used in real-life situations.

Applications in Computer Science

The assignment problem can be used in computer science to allocate resources to different tasks, such as allocating memory to processes or assigning threads to processors.

Applications in Economics

The assignment problem can be used in economics to allocate resources to different agents, such as allocating workers to jobs or assigning projects to contractors.

Applications in Logistics

The assignment problem can be used in logistics to allocate resources to different activities, such as allocating vehicles to routes or assigning warehouses to customers.

Applications in Management

The assignment problem can be used in management to allocate resources to different projects, such as allocating employees to tasks or assigning budgets to departments.

Let’s consider the following scenario: a manager needs to assign three employees to three different tasks. Each employee has different skills, and each task requires specific skills. The manager wants to minimize the total time it takes to complete all the tasks. The skills and the time required for each task are given in the table below:

The assignment problem is to determine which employee should be assigned to which task to minimize the total time required. To solve this problem, we can use the Hungarian method, which we discussed in the previous blog.

Using the Hungarian method, we first subtract the smallest entry in each row from all the entries of the row:

Next, we subtract the smallest entry in each column from all the entries of the column:

We draw the minimum number of lines to cover all the zeros in the matrix, which in this case is three:

Since the number of lines is equal to the number of rows, we have an optimal solution. The assignments can be made by selecting the rows and columns with a single zero in the final matrix. In this case, the optimal assignments are:

• Emp 1 to Task 3
• Emp 2 to Task 2
• Emp 3 to Task 1

This assignment results in a total time of 9 units.

I hope this example helps you better understand the assignment problem and how to solve it using the Hungarian method.

Solving the assignment problem may seem daunting, but with the right approach, it can be a straightforward process. By following the steps outlined in this guide, you can confidently tackle any assignment problem that comes your way.

How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you! 😔

Let us improve this post!

Tell us how we can improve this post?

Operations Research

1 Operations Research-An Overview

• History of O.R.
• Approach, Techniques and Tools
• Phases and Processes of O.R. Study
• Typical Applications of O.R
• Limitations of Operations Research
• Models in Operations Research
• O.R. in real world

2 Linear Programming: Formulation and Graphical Method

• General formulation of Linear Programming Problem
• Optimisation Models
• Basics of Graphic Method
• Important steps to draw graph
• Multiple, Unbounded Solution and Infeasible Problems
• Solving Linear Programming Graphically Using Computer
• Application of Linear Programming in Business and Industry

3 Linear Programming-Simplex Method

• Principle of Simplex Method
• Computational aspect of Simplex Method
• Simplex Method with several Decision Variables
• Two Phase and M-method
• Multiple Solution, Unbounded Solution and Infeasible Problem
• Sensitivity Analysis
• Dual Linear Programming Problem

4 Transportation Problem

• Basic Feasible Solution of a Transportation Problem
• Modified Distribution Method
• Stepping Stone Method
• Unbalanced Transportation Problem
• Degenerate Transportation Problem
• Transhipment Problem
• Maximisation in a Transportation Problem

5 Assignment Problem

• Solution of the Assignment Problem
• Unbalanced Assignment Problem
• Problem with some Infeasible Assignments
• Maximisation in an Assignment Problem
• Crew Assignment Problem

6 Application of Excel Solver to Solve LPP

• Building Excel model for solving LP: An Illustrative Example

7 Goal Programming

• Concepts of goal programming
• Goal programming model formulation
• Graphical method of goal programming
• The simplex method of goal programming
• Using Excel Solver to Solve Goal Programming Models
• Application areas of goal programming

8 Integer Programming

• Some Integer Programming Formulation Techniques
• Binary Representation of General Integer Variables
• Unimodularity
• Cutting Plane Method
• Branch and Bound Method
• Solver Solution

9 Dynamic Programming

• Dynamic Programming Methodology: An Example
• Definitions and Notations
• Dynamic Programming Applications

10 Non-Linear Programming

• Solution of a Non-linear Programming Problem
• Convex and Concave Functions
• Kuhn-Tucker Conditions for Constrained Optimisation
• Quadratic Programming
• Separable Programming
• NLP Models with Solver

11 Introduction to game theory and its Applications

• Important terms in Game Theory
• Saddle points
• Mixed strategies: Games without saddle points
• 2 x n games
• Exploiting an opponent’s mistakes

12 Monte Carlo Simulation

• Reasons for using simulation
• Monte Carlo simulation
• Limitations of simulation
• Steps in the simulation process
• Some practical applications of simulation
• Two typical examples of hand-computed simulation
• Computer simulation

13 Queueing Models

• Characteristics of a queueing model
• Notations and Symbols
• Statistical methods in queueing
• The M/M/I System
• The M/M/C System
• The M/Ek/I System
• Decision problems in queueing

Operations Research by

Get full access to Operations Research and 60K+ other titles, with a free 10-day trial of O'Reilly.

There are also live events, courses curated by job role, and more.

Assignment Problem

5.1  introduction.

The assignment problem is one of the special type of transportation problem for which more efficient (less-time consuming) solution method has been devised by KUHN (1956) and FLOOD (1956). The justification of the steps leading to the solution is based on theorems proved by Hungarian mathematicians KONEIG (1950) and EGERVARY (1953), hence the method is named Hungarian.

5.2  GENERAL MODEL OF THE ASSIGNMENT PROBLEM

Consider n jobs and n persons. Assume that each job can be done only by one person and the time a person required for completing the i th job (i = 1,2,...n) by the j th person (j = 1,2,...n) is denoted by a real number C ij . On the whole this model deals with the assignment of n candidates to n jobs ...

Get Operations Research now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Don’t leave empty-handed

Get Mark Richards’s Software Architecture Patterns ebook to better understand how to design components—and how they should interact.

It’s yours, free.

Check it out now on O’Reilly

Dive in for free with a 10-day trial of the O’Reilly learning platform—then explore all the other resources our members count on to build skills and solve problems every day.

Generalized Assignment Problem

• Reference work entry
• pp 1153–1162
• Cite this reference work entry

• O. Erhun Kundakcioglu 3 &
• Saed Alizamir 3  

2906 Accesses

15 Citations

Article Outline

Introduction

  Multiple-Resource Generalized Assignment Problem

  Multilevel Generalized Assignment Problem

  Dynamic Generalized Assignment Problem

  Bottleneck Generalized Assignment Problem

  Generalized Assignment Problem with Special Ordered Set

  Stochastic Generalized Assignment Problem

  Bi-Objective Generalized Assignment Problem

  Generalized Multi-Assignment Problem

  Exact Algorithms

  Heuristics

Conclusions

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

Access this chapter

• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Durable hardcover edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Some results on an assignment problem variant

Combinatorial clustering: literature review, methods, examples.

Introduction to Optimisation

Albareda-Sambola M, van der Vlerk MH, Fernandez E (2006) Exact solutions to a class of stochastic generalized assignment problems. Eur J Oper Res 173:465–487

Article   MATH   Google Scholar  

Amini MM, Racer M (1994) A rigorous computational comparison of alternative solution methods for the generalized assignment problem. Manag Sci 40(7):868–890

Amini MM, Racer M (1995) A hybrid heuristic for the generalized assignment problem. Eur J Oper Res 87(2):343–348

Asahiro Y, Ishibashi M, Yamashita M (2003) Independent and cooperative parallel search methods for the generalized assignment problem. Optim Method Softw 18:129–141

Article   MathSciNet   MATH   Google Scholar  

Balachandran V (1976) An integer generalized transportation model for optimal job assignment in computer networks. Oper Res 24(4):742–759

Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: column generation for solving huge integer programs. Oper Res 46(3):316–329

Beasley JE (1993) Lagrangean heuristics for location problems. Eur J Oper Res 65:383–399

Cario MC, Clifford JJ, Hill RR, Yang J, Yang K, Reilly CH (2002) An investigation of the relationship between problem characteristics and algorithm performance: a case study of the gap. IIE Trans 34:297–313

Google Scholar  

Cattrysse DG, Salomon M, Van LN Wassenhove (1994) A set partitioning heuristic for the generalized assignment problem. Eur J Oper Res 72:167–174

Cattrysse DG, Van LN Wassenhove (1992) A survey of algorithms for the generalized assignment problem. Eur J Oper Res 60:260–272

Ceselli A, Righini G (2006) A branch-and-price algorithm for the multilevel generalized assignment problem. Oper Res 54:1172–1184

Chalmet L, Gelders L (1976) Lagrangean relaxation for a generalized assignment type problem. In: Advances in OR. EURO, North Holland, Amsterdam, pp 103–109

Chu EC, Beasley JE (1997) A genetic algorithm for the generalized assignment problem. Comput Oper Res 24:17–23

Cohen R, Katzir L, Raz D (2006) An efficient approximation for the generalized assignment problem. Inf Process Lett 100:162–166

de Farias Jr, Johnson EL, Nemhauser GL (2000) A generalized assignment problem with special ordered sets: a polyhedral approach. Math Program, Ser A 89:187–203

de Farias Jr, Nemhauser GL (2001) A family of inequalities for the generalized assignment polytope. Oper Res Lett 29:49–55

DeMaio A, Roveda C (1971) An all zero-one algorithm for a class of transportation problems. Oper Res 19:1406–1418

Diaz JA, Fernandez E (2001) A tabu search heuristic for the generalized assignment problem. Eur J Oper Res 132:22–38

Drexl A (1991) Scheduling of project networks by job assignment. Manag Sci 37:1590–1602

Dyer M, Frieze A (1992) Probabilistic analysis of the generalised assignment problem. Math Program 55:169–181

Article   MathSciNet   Google Scholar  

Feltl H, Raidl GR (2004) An improved hybrid genetic algorithm for the generalized assignment problem. In: SAC '04; Proceedings of the 2004 ACM symposium on Applied computing. ACM Press, New York, pp 990–995

Chapter   Google Scholar  

Fisher ML, Jaikumar R (1981) A generalized assignment heuristic for vehicle routing. Netw 11:109–124

Fisher ML, Jaikumar R, van Wassenhove LN (1986) A multiplier adjustment method for the generalized assignment problem. Manag Sci 32:1095–1103

Fleischer L, Goemans MX, Mirrokni VS, Sviridenko M (2006) Tight approximation algorithms for maximum general assignment problems. In SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. ACM Press, New York, pp 611–620

Book   Google Scholar  

Freling R, Romeijn HE, Morales DR, Wagelmans APM (2003) A branch-and-price algorithm for the multiperiod single-sourcing problem. Oper Res 51(6):922–939

French AP, Wilson JM (2002) Heuristic solution methods for the multilevel generalized assignment problem. J Heuristics 8:143–153

French AP, Wilson JM (2007) An lp-based heuristic procedure for the generalized assignment problem with special ordered sets. Comput Oper Res 34:2359–2369

Garey MR, Johnson DS (1990) Computers and Intractability; A Guide to the Theory of NP-Completeness. Freeman, New York

Gavish B, Pirkul H (1991) Algorithms for the multi-resource generalized assignment problem. Manag Sci 37:695–713

Geoffrion AM, Graves GW (1974) Multicommodity distribution system design by benders decomposition. Manag Sci 20(5):822–844

Glover F, Hultz J, Klingman D (1979) Improved computer based planning techniques, part ii. Interfaces 4:17–24

Gottlieb ES, Rao MR (1990) \( (1,k) \) -configuration facets for the generalized assignment problem. Math Program 46(1):53–60

Gottlieb ES, Rao MR (1990) The generalized assignment problem: Valid inequalities and facets. Math Stat 46:31–52

MathSciNet   MATH   Google Scholar  

Guignard M, Rosenwein MB (1989) An improved dual based algorithm for the generalized assignment problem. Oper Res 37(4):658–663

Haddadi S (1999) Lagrangian decomposition based heuristic for the generalized assignment problem. Inf Syst Oper Res 37:392–402

Haddadi S, Ouzia H (2004) Effective algorithm and heuristic for the generalized assignment problem. Eur J Oper Res 153:184–190

Hajri-Gabouj S (2003) A fuzzy genetic multiobjective optimization algorithm for a multilevel generalized assignment problem. IEEE Trans Syst 33:214–224

Janak SL, Taylor MS, Floudas CA, Burka M, Mountziaris TJ (2006) Novel and effective integer optimization approach for the nsf panel-assignment problem: a multiresource and preference-constrained generalized assignment problem. Ind Eng Chem Res 45:258–265

Article   Google Scholar  

Jörnsten K, Nasberg M (1986) A new lagrangian relaxation approach to the generalized assignment problem. Eur J Oper Res 27:313–323

Jörnsten KO, Varbrand P (1990) Relaxation techniques and valid inequalities applied to the generalized assignment problem. Asia-P J Oper Res 7(2):172–189

Klastorin TD (1979) An effective subgradient algorithm for the generalized assignment problem. Comp Oper Res 6:155–164

Klastorin TD (1979) On the maximal covering location problem and the generalized assignment problem. Manag Sci 25(1):107–112

Kogan K, Khmelnitsky E, Ibaraki T (2005) Dynamic generalized assignment problems with stochastic demands and multiple agent task relationships. J Glob Optim 31:17–43

Kogan K, Shtub A, Levit VE (1997) Dgap – the dynamic generalized assignment problem. Ann Oper Res 69:227–239

Kuhn H (1995) A heuristic algorithm for the loading problem in flexible manufacturing systems. Int J Flex Manuf Syst 7:229–254

Laguna M, Kelly JP, Gonzfilez-Velarde JL, Glover F (1995) Tabu search for the multilevel generalized assignment problem. Eur J Oper Res 82:176–189

Lawler E (1976) Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, Winston, New York

MATH   Google Scholar  

Lin BMT, Huang YS, Yu HK (2001) On the variable-depth-search heuristic for the linear-cost generalized assignment problem. Int J Comput Math 77:535–544

Lorena LAN, Narciso MG (1996) Relaxation heuristics for a generalized assignment problem. Eur J Oper Res 91:600–610

Lorena LAN, Narciso MG, Beasley JE (2003) A constructive genetic algorithm for the generalized assignment problem. J Evol Optim

Lourenço HR, Serra D (1998) Adaptive approach heuristics for the generalized assignment problem. Technical Report 288, Department of Economics and Business, Universitat Pompeu Fabra, Barcelona

Lourenço HR, Serra D (2002) Adaptive search heuristics for the generalized assignment problem. Mathw Soft Comput 9(2–3):209–234

Martello S, Toth P (1981) An algorithm for the generalized assignment problem. In: Brans JP (ed) Operational Research '81, 9th IFORS Conference, North-Holland, Amsterdam, pp 589–603

Martello S, Toth P (1990) Knapsack Problems: Algorithms and Computer Implementations. Wiley, New York

Martello S, Toth P (1992) Generalized assignment problems. Lect Notes Comput Sci 650:351–369

MathSciNet   Google Scholar  

Martello S, Toth P (1995) The bottleneck generalized assignment problem. Eur J Oper Res 83:621–638

Mazzola JB, Neebe AW (1988) Bottleneck generalized assignment problems. Eng Costs Prod Econ 14(1):61–65

Mazzola JB, Wilcox SP (2001) Heuristics for the multi-resource generalized assignment problem. Nav Res Logist 48(6):468–483

Monfared MAS, Etemadi M (2006) The impact of energy function structure on solving generalized assignment problem using hopfield neural network. Eur J Oper Res 168:645–654

Morales DR, Romeijn HE (2005) Handbook of Combinatorial Optimization, supplement vol B. In: Du D-Z, Pardalos PM (eds) The Generalized Assignment Problem and extensions. Springer, New York, pp 259–311

Narciso MG, Lorena LAN (1999) Lagrangean/surrogate relaxation for generalized assignment problems. Eur J Oper Res 114:165–177

Nauss RM (2003) Solving the generalized assignment problem: an optimizing and heuristic approach. INFORMS J Comput 15(3):249–266

Nauss RM (2005) The elastic generalized assignment problem. J Oper Res Soc 55:1333–1341

Nowakovski J, Schwarzler W, Triesch E (1999) Using the generalized assignment problem in scheduling the rosat space telescope. Eur J Oper Res 112:531–541

Nutov Z, Beniaminy I, Yuster R (2006) A  \( (1-1/e) \) ‐approximation algorithm for the generalized assignment problem. Oper Res Lett 34:283–288

Park JS, Lim BH, Lee Y (1998) A lagrangian dual-based branch-and-bound algorithm for the generalized multi-assignment problem. Manag Sci 44(12S):271–275

Pigatti A, de Aragao MP, Uchoa E (2005) Stabilized branch-and-cut-and-price for the generalized assignment problem. In: Electronic Notes in Discrete Mathematics, vol 19 of 2nd Brazilian Symposium on Graphs, Algorithms and Combinatorics, pp 385–395,

Osman IH (1995) Heuristics for the generalized assignment problem: simulated annealing and tabu search approaches. OR-Spektrum 17:211–225

Racer M, Amini MM (1994) A robust heuristic for the generalized assignment problem. Ann Oper Res 50(1):487–503

Romeijn HE, Morales DR (2000) A class of greedy algorithms for the generalized assignment problem. Discret Appl Math 103:209–235

Romeijn HE, Morales DR (2001) Generating experimental data for the generalized assignment problem. Oper Res 49(6):866–878

Romeijn HE, Piersma N (2000) A probabilistic feasibility and value analysis of the generalized assignment problem. J Comb Optim 4:325–355

Ronen D (1992) Allocation of trips to trucks operating from a single terminal. Comput Oper Res 19(5):445–451

Ross GT, Soland RM (1975) A branch and bound algorithm for the generalized assignment problem. Math Program 8:91–103

Ross GT, Soland RM (1977) Modeling facility location problems as generalized assignment problems. Manag Sci 24:345–357

Ross GT, Zoltners AA (1979) Weighted assignment models and their application. Manag Sci 25(7):683–696

Savelsbergh M (1997) A branch-and-price algorithm for the generalized assignment problem. Oper Res 45:831–841

Shmoys DB, Tardos E (1993) An approximation algorithm for the generalized assignment problem. Math Program 62:461–474

Shtub A (1989) Modelling group technology cell formation as a generalized assignment problem. Int J Prod Res 27:775–782

Srinivasan V, Thompson GL (1973) An algorithm for assigning uses to sources in a special class of transportation problems. Oper Res 21(1):284–295

Stützle T, Hoos H (1999) The Max-Min Ant System and Local Search for Combinatorial Optimization Problems. In: Voss S, Martello S, Osman IH, Roucairol C (eds) Meta-heuristics; Advances and trends in local search paradigms for optimization. Kluwer, Boston, pp 313–329

Toktas B, Yen JW, Zabinsky ZB (2006) Addressing capacity uncertainty in resource-constrained assignment problems. Comput Oper Res 33:724–745

Trick M (1992) A linear relaxation heuristic for the generalized assignment problem. Nav Res Logist 39:137–151

Trick MA (1994) Scheduling multiple variable-speed machines. Oper Res 42(2):234–248

Wilson JM (1997) A genetic algorithm for the generalised assignment problem. J Oper Res Soc 48:804–809

Wilson JM (2005) An algorithm for the generalized assignment problem with special ordered sets. J Heuristics 11:337–350

Yagiura M, Ibaraki T, Glover F (2004) An ejection chain approach for the generalized assignment problem. INFORMS J Comput 16:133–151

Yagiura M, Ibaraki T, Glover F (2006) A path relinking approach with ejection chains for the generalized assignment problem. Eur J Oper Res 169:548–569

Yagiura M, Yamaguchi T, Ibaraki T (1998) A variable depth search algorithm with branching search for the generalized assignment problem. Optim Method Softw 10:419–441

Yagiura M, Yamaguchi T, Ibaraki T (1999) A variable depth search algorithm for the generalized assignment problem. In: Voss S, Martello S, Osman IH, Roucairol C (eds) Meta-heuristics; Advances and Trends in Local Search paradigms for Optimization, Kluwer, Boston, pp 459–471

Zhang CW, Ong HL (2007) An efficient solution to biobjective generalized assignment problem. Adv Eng Softw 38:50–58

Zimokha VA, Rubinshtein MI (1988) R & d planning and the generalized assignment problem. Autom Remote Control 49:484–492

Download references

Author information

Authors and affiliations.

Department of Industrial and Systems Engineering, University of Florida, Gainesville, USA

O. Erhun Kundakcioglu & Saed Alizamir

You can also search for this author in PubMed   Google Scholar

Editor information

Editors and affiliations.

Department of Chemical Engineering, Princeton University, Princeton, NJ, 08544-5263, USA

Christodoulos A. Floudas

Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, 32611-6595, USA

Panos M. Pardalos

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag

About this entry

Cite this entry.

Kundakcioglu, O.E., Alizamir, S. (2008). Generalized Assignment Problem . In: Floudas, C., Pardalos, P. (eds) Encyclopedia of Optimization. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-74759-0_200

Download citation

DOI : https://doi.org/10.1007/978-0-387-74759-0_200

Publisher Name : Springer, Boston, MA

Print ISBN : 978-0-387-74758-3

Online ISBN : 978-0-387-74759-0

eBook Packages : Mathematics and Statistics Reference Module Computer Science and Engineering

Share this entry

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

• Publish with us

Policies and ethics

• Find a journal
• Track your research

• 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

Python Iterators Examples

Grid Search in scikit-learn

Decision Tree Classification in Python

• {{subColumn.name}}

AIMS Mathematics

• {{newsColumn.name}}
• Share facebook twitter google linkedin

A robust regional eigenvalue assignment problem using rank-one control for undamped gyroscopic systems

• Binxin He 1 , 
• Hao Liu 1,2 ,  , 
• 1. School of Mathematics, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China
• 2. Shenzhen Research Institute, Nanjing University of Aeronautics and Astronautics, Shenzhen 518063, China
• Received: 30 March 2024 Revised: 31 May 2024 Accepted: 04 June 2024 Published: 07 June 2024

MSC : 65F18, 93C15

• Full Text(HTML)
• Download PDF

Considering the advantages of economic benefit and cost reduction by using rank-one control, we investigated the problem of robust regional eigenvalue assignment using rank-one control for undamped gyroscopic systems. Based on the orthogonality relation, we presented a method for solving partial eigenvalue assignment problems to reassign partial undesired eigenvalues accurately. Since it is difficult to achieve robust control by assigning desired eigenvalues to precise positions with rank-one control, we assigned eigenvalues within specified regions to provide the necessary freedom. According to the sensitivity analysis theories, we derived the sensitivity of closed-loop eigenvalues to parameter perturbations to measure robustness and proposed a numerical algorithm for solving robust regional eigenvalue assignment problems so that the closed-loop eigenvalues were insensitive to parameter perturbations. Numerical experiments demonstrated the effectiveness of our method.

• undamped gyroscopic systems ,
• regional eigenvalue assignment ,
• rank-one control ,

Citation: Binxin He, Hao Liu. A robust regional eigenvalue assignment problem using rank-one control for undamped gyroscopic systems[J]. AIMS Mathematics, 2024, 9(7): 19104-19124. doi: 10.3934/math.2024931

Related Papers:

• This work is licensed under a Creative Commons Attribution-NonCommercial-Share Alike 4.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/4.0/ -->

Supplements

Access History

• Corresponding author: Email: [email protected]

Reader Comments

• © 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License ( http://creativecommons.org/licenses/by/4.0 )

通讯作者: 陈斌, [email protected]

沈阳化工大学材料科学与工程学院 沈阳 110142

Article views( 12 ) PDF downloads( 2 ) Cited by( 0 )

Figures and Tables

Figures( 8 )  /  Tables( 2 )

Associated material

Other articles by authors, related pages.

• on Google Scholar
• Email to a friend
• Order reprints

Export File

• Figure 1. Spatial oscillations of a particle
• Figure 2. A cylindrical rotor with flexible bearings
• Figure 3. Partial eigenvalue assignment results of Example 4.2
• Figure 4. The perturbed desired closed-loop eigenvalues of different methods
• Figure 5. Time response for Example 4.3 on $ {\omega} = 0.7 $
• Figure 6. Time response for Example 4.3 on $ {\omega} = 0.66 $
• Figure 7. Time response for Example 4.3 with an additional delay on $ {\omega} = 0.7 $
• Figure 8. Time response for Example 4.3 with an additional delay on $ {\omega} = 0.66 $

• DOI: 10.1080/0305215x.2024.2333400
• Corpus ID: 269413447

A model-driven decision support system for the storage location assignment problem in bulk ports

• Issam Krimi , Raca Todosijević
• Published in Engineering optimization… 26 April 2024
• Engineering
• Engineering Optimization

30 References

Planning an integrated stockyard–port system for smart iron ore supply chains via vnd optimization, bulk solids stacking strategy of a rectangular ship cabin, an integrated decision support system for planning production, storage and bulk port operations in a fertilizer supply chain, stockyard storage space allocation in large iron ore terminals, a rolling-horizon approach for multi-period optimization, constraint programming models for integrated container terminal operations, a comprehensive review of quay crane scheduling, yard operations and integrations thereof in container terminals, supporting the decision making process in the urban freight fleet composition problem, storage space allocation problem at inland bulk material stockyard, throughput optimisation in a coal export system with multiple terminals and shared resources, related papers.

Showing 1 through 3 of 0 Related Papers

The potential of AI technology has been percolating in the background for years. But when ChatGPT, the AI chatbot, began grabbing headlines in early 2023, it put generative AI in the spotlight. This guide is your go-to manual for generative AI, covering its benefits, limits, use cases, prospects and much more.

Ai hallucination.

• Ben Lutkevich, Site Editor

What are AI hallucinations?

An AI hallucination is when a large language model (LLM) generates false information.

LLMs are AI models that power chatbots, such as ChatGPT and Google Bard . Hallucinations can be deviations from external facts, contextual logic or both.

Hallucinations often appear plausible because LLMs are designed to produce fluent, coherent text . They occur because LLMs have no understanding of the underlying reality that language describes. LLMs use statistics to generate language that is grammatically and semantically correct within the context of the prompt.

However, hallucinations do not always appear plausible. Sometimes they can be clearly nonsensical. There is no clear way to determine the exact causes of hallucinations on a case-by-case basis.

Another term for an AI hallucination is a confabulation . Hallucinations are most associated with LLMs, but they can also appear in AI-generated video, images and audio .

This article is part of

What is generative AI? Everything you need to know

• Which also includes:
• 8 top generative AI tool categories for 2024
• Will AI replace jobs? 9 job types that might be affected
• 19 of the best large language models in 2024

Examples of AI hallucinations

One infamous example of an AI hallucination happened when Google's chatbot, Bard, made an untrue claim about the James Webb Space Telescope.

When prompted, "What new discoveries from the James Webb Space Telescope can I tell my 9-year-old about?" Bard responded with the claim that the James Webb Space Telescope took the very first pictures of an exoplanet outside this solar system. This information was false. The first images of an exoplanet were taken in 2004 according to NASA, and the James Webb Space Telescope was not launched until 2021.

Bard's answer sounded plausible, and was consistent with the prompt, but was proven false with some fact checking.

Another example was when Meta demoed Galactica, an LLM designed for science researchers and students. When asked to draft a paper about creating avatars, the model cited a fake paper about the topic from a real author working in a relevant area.

Types of AI hallucinations

Hallucinations can range from minor inconsistencies to completely fabricated or contradictory information.

There are several types of AI hallucinations, including the following:

• Prompt: "Write a description of a landscape in four-word sentences."
• Output: "The grass was green. The mountains were blue. The river was purple. The grass was brown."
• Prompt: "Write a birthday card for my niece."
• Output: "Happy anniversary, mom and dad!"
• Prompt: "Name three cities in the United States."
• Output: "New York, Los Angeles, Toronto."
• Prompt: "Describe London to me."
• Output: "London is a city in England. Cats need to be fed at least once a day."

Why do AI hallucinations happen?

There are many possible technical reasons for hallucinations in LLMs. While the inner workings of LLMs and the exact mechanisms that produce outputs are opaque, there are several general causes that researchers point to. Some of them include the following:

• Data quality. Hallucinations from data occur when there is bad information in the source content. LLMs rely on a large body of training data that data that can contain noise , errors, biases or inconsistencies. ChatGPT, for example, included Reddit in its training data .
• Generation method. Hallucinations can also occur from the training and generation methods -- even when the data set is consistent and reliable. For example, bias created by the model's previous generations could cause a hallucination. A false decoding from the transformer could also be the cause of hallucination. Models might also have a bias toward generic or specific words, which influences the information they generate and fabricate.
• Input context. If the input prompt is unclear, inconsistent or contradictory, hallucinations can arise. While data quality and training are out of the user's hands, input context is not. Users can hone their inputs to improve results.

Why are AI hallucinations a problem?

An immediate problem with AI hallucinations is that they significantly disturb user trust. As users begin to experience AI as more real, they might develop more inherent trust in them quickly and are more surprised when that trust is betrayed.

One challenge with framing these outputs as hallucinations is that it encourages anthropomorphism. Describing a false output from a language model as a hallucination anthropomorphizes the inanimate AI technology to some extent. AI systems, despite their function, are not conscious. They do not have their own perception of the world. Their output manipulates the users' perception and might be more aptly named a mirage -- something the user wants to believe isn't there, rather than a machine hallucination.

Another challenge of hallucinations is the newness of the phenomenon and large language models in general. Hallucinations and LLM outputs in general are designed to sound fluid and plausible. If someone is not prepared to read LLM outputs with a skeptical eye, they might believe the hallucination. Hallucinations can be dangerous due to their capacity to fool people. They could inadvertently spread misinformation , fabricate citations and references and even be weaponized in cyberattacks .

A third challenge of mitigating hallucination is that LLMs are often black box AI . It can be difficult or in many cases impossible to determine why the LLM generated the specific hallucination. There are limited ways to fix LLMs that produce these hallucinations because their training cuts off at a certain point. Going into the model to change the training data can use a lot of energy . AI infrastructure is expensive in general. It is often on the user -- not the proprietor of the LLM -- to watch for hallucinations.

Generative AI is just that -- generative . In some sense, generative AI makes everything up.

For more on generative AI, read the following articles:

Pros and cons of AI-generated content

How to prevent deepfakes in the era of generative AI

Generative AI challenges that businesses should consider

AI existential risk: Is AI a threat to humanity?

Generative AI landscape: Potential future trends

How to prevent AI hallucinations

There are several ways users can avoid or minimize the occurrence of hallucinations during LLM use , including the following:

• Limiting the possible outputs.
• Providing the model with relevant data sources.
• Giving the model a role to play. For example, "You are a writer for a technology website. Write an article about x, y and z."
• Filtering and ranking strategies. LLMs often have parameters that users can tune. One example is the temperature parameter, which controls output randomness. When the temperature is set higher, the outputs created by the language model are more random. TopK, which manages how the model deals with probabilities, is another example of a parameter that can be tuned.
• Multishot prompting. Provide several examples of the desired output format or context to help the model recognize patterns.

Hallucinations are considered an inherent feature of LLMs. There are ways that researchers and the people working on LLMs are trying to understand and mitigate hallucinations.

OpenAI proposed a strategy to reward AI models for each correct step in reasoning toward the correct answer instead of just rewarding the conclusion if correct. This approach is called process supervision and it aims to manipulate models into following a chain-of-thought approach that decomposes prompts into steps.

Other research proposed pointing two models at each other and instructing them to communicate until they arrive at an answer.

How can AI hallucinations be detected?

The most basic way to detect an AI hallucination is to carefully fact check the model's output. This can be difficult when dealing with unfamiliar, complex or dense material. Users can ask the model to self-evaluate and generate the probability that an answer is correct or highlight the parts of an answer that might be wrong, using that as a starting point for fact checking.

Users can also familiarize themselves with the model's sources of information to help them fact check. For example, ChatGPT's training data cuts off at 2021, so any answer generated that relies on detailed knowledge of the world past that point in time is worth double-checking.

History of hallucinations in AI

Google DeepMind researchers surfaced the term "IT hallucinations" in 2018 , which gained it some popularity. The term became more popular and tightly linked to AI with the rise of ChatGPT in late 2022, which made LLMs more accessible.

The term then appeared in 2000 in papers in Proceedings: Fourth IEEE International Conference on Automatic Face and Gesture Recognition. A 2022 report called "Survey of Hallucination in Natural Language Generation" describes the initial use of the term in computer vision, drawing from the original 2000 publication. Here is part of the description from that survey:

"…carried more positive meanings, such as superresolution, image inpainting and image synthesizing. Such hallucination is something we take advantage of rather than avoid in CV. Nevertheless, recent works have started to refer to a specific type of error as hallucination in image captioning and object detection, which denotes non-existing objects detected or localized at their expected position. The latter conception is similar to hallucination in NLG."

Editor's note: ChatGPT was many people's introduction to generative AI. Take a deep dive into the history of generative AI , which spans more than nine decades.

Continue Reading About AI hallucination

• Key benefits of AI for business
• AI risks businesses must confront and how to address them
• 4 main types of artificial intelligence: Explained
• AI transparency: What is it and why do we need it?
• Generative AI ethics: 8 biggest concerns

Related Terms

NBASE-T Ethernet is an IEEE standard and Ethernet-signaling technology that enables existing twisted-pair copper cabling to ...

SD-WAN security refers to the practices, protocols and technologies protecting data and resources transmitted across ...

Net neutrality is the concept of an open, equal internet for everyone, regardless of content consumed or the device, application ...

A proof of concept (PoC) exploit is a nonharmful attack against a computer or network. PoC exploits are not meant to cause harm, ...

A virtual firewall is a firewall device or service that provides network traffic filtering and monitoring for virtual machines (...

Cloud penetration testing is a tactic an organization uses to assess its cloud security effectiveness by attempting to evade its ...

Regulation SCI (Regulation Systems Compliance and Integrity) is a set of rules adopted by the U.S. Securities and Exchange ...

Strategic management is the ongoing planning, monitoring, analysis and assessment of all necessities an organization needs to ...

IT budget is the amount of money spent on an organization's information technology systems and services. It includes compensation...

ADP Mobile Solutions is a self-service mobile app that enables employees to access work records such as pay, schedules, timecards...

Director of employee engagement is one of the job titles for a human resources (HR) manager who is responsible for an ...

Digital HR is the digital transformation of HR services and processes through the use of social, mobile, analytics and cloud (...

A virtual agent -- sometimes called an intelligent virtual agent (IVA) -- is a software program or cloud service that uses ...

A chatbot is a software or computer program that simulates human conversation or "chatter" through text or voice interactions.

Martech (marketing technology) refers to the integration of software tools, platforms, and applications designed to streamline ...

The New ChatGPT Offers a Lesson in A.I. Hype

OpenAI released GPT-4o, its latest chatbot technology, in a partly finished state. It has much to prove.

ChatGPT-4o trying to solve a geometry problem Credit... Arsenii Vaselenko for The New York Times

Supported by

• Share full article

By Brian X. Chen

Brian X. Chen is the author of Tech Fix , a weekly column about the societal implications of the tech we use.

• May 31, 2024

When OpenAI unveiled the latest version of its immensely popular ChatGPT chatbot this month, it had a new voice possessing humanlike inflections and emotions. The online demonstration also featured the bot tutoring a child on solving a geometry problem.

To my chagrin, the demo turned out to be essentially a bait and switch. The new ChatGPT was released without most of its new features, including the improved voice (which the company told me it postponed to make fixes). The ability to use a phone’s video camera to get real-time analysis of something like a math problem isn’t available yet, either.

Amid the delay, the company also deactivated the ChatGPT voice that some said sounded like the actress Scarlett Johansson, after she threatened legal action , replacing it with a different female voice.

For now, what has actually been rolled out in the new ChatGPT is the ability to upload photos for the bot to analyze. Users can generally expect quicker, more lucid responses. The bot can also do real-time language translations, but ChatGPT will respond in its older, machine-like voice.

Nonetheless, this is the leading chatbot that upended the tech industry , so it was worth reviewing. After trying the sped-up chatbot for two weeks, I had mixed feelings. It excelled at language translations, but it struggled with math and physics. All told, I didn’t see a meaningful improvement from the last version, ChatGPT-4. I definitely wouldn’t let it tutor my child.

We are having trouble retrieving the article content.

Please enable JavaScript in your browser settings.

Thank you for your patience while we verify access. If you are in Reader mode please exit and  log into  your Times account, or  subscribe  for all of The Times.

Thank you for your patience while we verify access.

Already a subscriber?  Log in .

Want all of The Times?  Subscribe .

Advertisement