assignment optimisation problems

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

One of the most well-known combinatorial optimization problems is the assignment problem . Here's an example: suppose a group of workers needs to perform a set of tasks, and for each worker and task, there is a cost for assigning the worker to the task. 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.

You can visualize this problem by the graph below, in which there are four workers and four tasks. The edges represent all possible ways to assign workers to tasks. The labels on the edges are the costs of assigning workers to tasks.

An assignment corresponds to a subset of the edges, in which each worker has at most one edge leading out, and no two workers have edges leading to the same task. One possible assignment is shown below.

The total cost of the assignment is 70 + 55 + 95 + 45 = 265 .

The next section shows how solve an assignment problem, using both the MIP solver and the CP-SAT solver.

Other tools for solving assignment problems

OR-Tools also provides a couple of other tools for solving assignment problems, which can be faster than the MIP or CP solvers:

• Linear sum assignment solver
• Minimum cost flow solver

However, these tools can only solve simple types of assignment problems. So for general solvers that can handle a wide variety of problems (and are fast enough for most applications), we recommend the MIP and CP-SAT solvers.

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

Last updated 2024-08-28 UTC.

4.7 Applied Optimization Problems

Learning objectives.

• 4.7.1 Set up and solve optimization problems in several applied fields.

One common application of calculus is calculating the minimum or maximum value of a function. For example, companies often want to minimize production costs or maximize revenue. In manufacturing, it is often desirable to minimize the amount of material used to package a product with a certain volume. In this section, we show how to set up these types of minimization and maximization problems and solve them by using the tools developed in this chapter.

Solving Optimization Problems over a Closed, Bounded Interval

The basic idea of the optimization problems that follow is the same. We have a particular quantity that we are interested in maximizing or minimizing. However, we also have some auxiliary condition that needs to be satisfied. For example, in Example 4.32 , we are interested in maximizing the area of a rectangular garden. Certainly, if we keep making the side lengths of the garden larger, the area will continue to become larger. However, what if we have some restriction on how much fencing we can use for the perimeter? In this case, we cannot make the garden as large as we like. Let’s look at how we can maximize the area of a rectangle subject to some constraint on the perimeter.

Example 4.32

Maximizing the area of a garden.

A rectangular garden is to be constructed using a rock wall as one side of the garden and wire fencing for the other three sides ( Figure 4.62 ). Given 100 100 ft of wire fencing, determine the dimensions that would create a garden of maximum area. What is the maximum area?

Let x x denote the length of the side of the garden perpendicular to the rock wall and y y denote the length of the side parallel to the rock wall. Then the area of the garden is

We want to find the maximum possible area subject to the constraint that the total fencing is 100 ft . 100 ft . From Figure 4.62 , the total amount of fencing used will be 2 x + y . 2 x + y . Therefore, the constraint equation is

Solving this equation for y , y , we have y = 100 − 2 x . y = 100 − 2 x . Thus, we can write the area as

Before trying to maximize the area function A ( x ) = 100 x − 2 x 2 , A ( x ) = 100 x − 2 x 2 , we need to determine the domain under consideration. To construct a rectangular garden, we certainly need the lengths of both sides to be positive. Therefore, we need x > 0 x > 0 and y > 0 . y > 0 . Since y = 100 − 2 x , y = 100 − 2 x , if y > 0 , y > 0 , then x < 50 . x < 50 . Therefore, we are trying to determine the maximum value of A ( x ) A ( x ) for x x over the open interval ( 0 , 50 ) . ( 0 , 50 ) . We do not know that a function necessarily has a maximum value over an open interval. However, we do know that a continuous function has an absolute maximum (and absolute minimum) over a closed interval. Therefore, let’s consider the function A ( x ) = 100 x − 2 x 2 A ( x ) = 100 x − 2 x 2 over the closed interval [ 0 , 50 ] . [ 0 , 50 ] . If the maximum value occurs at an interior point, then we have found the value x x in the open interval ( 0 , 50 ) ( 0 , 50 ) that maximizes the area of the garden. Therefore, we consider the following problem:

Maximize A ( x ) = 100 x − 2 x 2 A ( x ) = 100 x − 2 x 2 over the interval [ 0 , 50 ] . [ 0 , 50 ] .

As mentioned earlier, since A A is a continuous function on a closed, bounded interval, by the extreme value theorem, it has a maximum and a minimum. These extreme values occur either at endpoints or critical points. At the endpoints, A ( x ) = 0 . A ( x ) = 0 . Since the area is positive for all x x in the open interval ( 0 , 50 ) , ( 0 , 50 ) , the maximum must occur at a critical point. Differentiating the function A ( x ) , A ( x ) , we obtain

Therefore, the only critical point is x = 25 x = 25 ( Figure 4.63 ). We conclude that the maximum area must occur when x = 25 . x = 25 . Then we have y = 100 − 2 x = 100 − 2 ( 25 ) = 50 . y = 100 − 2 x = 100 − 2 ( 25 ) = 50 . To maximize the area of the garden, let x = 25 x = 25 ft and y = 50 ft . y = 50 ft . The area of this garden is 1250 ft 2 . 1250 ft 2 .

Checkpoint 4.31

Determine the maximum area if we want to make the same rectangular garden as in Figure 4.63 , but we have 200 200 ft of fencing.

Now let’s look at a general strategy for solving optimization problems similar to Example 4.32 .

Problem-Solving Strategy

Solving optimization problems.

• Introduce all variables. If applicable, draw a figure and label all variables.
• Determine which quantity is to be maximized or minimized, and for what range of values of the other variables (if this can be determined at this time).
• Write a formula for the quantity to be maximized or minimized in terms of the variables. This formula may involve more than one variable.
• Write any equations relating the independent variables in the formula from step 3 . 3 . Use these equations to write the quantity to be maximized or minimized as a function of one variable.
• Identify the domain of consideration for the function in step 4 4 based on the physical problem to be solved.
• Locate the maximum or minimum value of the function from step 4 . 4 . This step typically involves looking for critical points and evaluating a function at endpoints.

Now let’s apply this strategy to maximize the volume of an open-top box given a constraint on the amount of material to be used.

Example 4.33

Maximizing the volume of a box.

An open-top box is to be made from a 24 24 in. by 36 36 in. piece of cardboard by removing a square from each corner of the box and folding up the flaps on each side. What size square should be cut out of each corner to get a box with the maximum volume?

Step 1: Let x x be the side length of the square to be removed from each corner ( Figure 4.64 ). Then, the remaining four flaps can be folded up to form an open-top box. Let V V be the volume of the resulting box.

Step 2: We are trying to maximize the volume of a box. Therefore, the problem is to maximize V . V .

Step 3: As mentioned in step 2 , 2 , we are trying to maximize the volume of a box. The volume of a box is V = L · W · H , V = L · W · H , where L , W , and H L , W , and H are the length, width, and height, respectively.

Step 4: From Figure 4.64 , we see that the height of the box is x x inches, the length is 36 − 2 x 36 − 2 x inches, and the width is 24 − 2 x 24 − 2 x inches. Therefore, the volume of the box is

Step 5: To determine the domain of consideration, let’s examine Figure 4.64 . Certainly, we need x > 0 . x > 0 . Furthermore, the side length of the square cannot be greater than or equal to half the length of the shorter side, 24 24 in.; otherwise, one of the flaps would be completely cut off. Therefore, we are trying to determine whether there is a maximum volume of the box for x x over the open interval ( 0 , 12 ) . ( 0 , 12 ) . Since V V is a continuous function over the closed interval [ 0 , 12 ] , [ 0 , 12 ] , we know V V will have an absolute maximum over the closed interval. Therefore, we consider V V over the closed interval [ 0 , 12 ] [ 0 , 12 ] and check whether the absolute maximum occurs at an interior point.

Step 6: Since V ( x ) V ( x ) is a continuous function over the closed, bounded interval [ 0 , 12 ] , [ 0 , 12 ] , V V must have an absolute maximum (and an absolute minimum). Since V ( x ) = 0 V ( x ) = 0 at the endpoints and V ( x ) > 0 V ( x ) > 0 for 0 < x < 12 , 0 < x < 12 , the maximum must occur at a critical point. The derivative is

To find the critical points, we need to solve the equation

Dividing both sides of this equation by 12 , 12 , the problem simplifies to solving the equation

Using the quadratic formula, we find that the critical points are

Since 10 + 2 7 10 + 2 7 is not in the domain of consideration, the only critical point we need to consider is 10 − 2 7 . 10 − 2 7 . Therefore, the volume is maximized if we let x = 10 − 2 7 in . x = 10 − 2 7 in . The maximum volume is V ( 10 − 2 7 ) = 640 + 448 7 ≈ 1825 in . 3 V ( 10 − 2 7 ) = 640 + 448 7 ≈ 1825 in . 3 as shown in the following graph.

Watch a video about optimizing the volume of a box.

Checkpoint 4.32

Suppose the dimensions of the cardboard in Example 4.33 are 20 in. by 30 in. Let x x be the side length of each square and write the volume of the open-top box as a function of x . x . Determine the domain of consideration for x . x .

Example 4.34

Minimizing travel time.

An island is 2 mi 2 mi due north of its closest point along a straight shoreline. A visitor is staying at a cabin on the shore that is 6 mi 6 mi west of that point. The visitor is planning to go from the cabin to the island. Suppose the visitor runs at a rate of 8 mph 8 mph and swims at a rate of 3 mph . 3 mph . How far should the visitor run before swimming to minimize the time it takes to reach the island?

Step 1: Let x x be the distance running and let y y be the distance swimming ( Figure 4.66 ). Let T T be the time it takes to get from the cabin to the island.

Step 2: The problem is to minimize T . T .

Step 3: To find the time spent traveling from the cabin to the island, add the time spent running and the time spent swimming. Since Distance = = Rate × × Time ( D = R × T ) , ( D = R × T ) , the time spent running is

and the time spent swimming is

Therefore, the total time spent traveling is

Step 4: From Figure 4.66 , the line segment of y y miles forms the hypotenuse of a right triangle with legs of length 2 mi 2 mi and 6 − x mi . 6 − x mi . Therefore, by the Pythagorean theorem, 2 2 + ( 6 − x ) 2 = y 2 , 2 2 + ( 6 − x ) 2 = y 2 , and we obtain y = ( 6 − x ) 2 + 4 . y = ( 6 − x ) 2 + 4 . Thus, the total time spent traveling is given by the function

Step 5: From Figure 4.66 , we see that 0 ≤ x ≤ 6 . 0 ≤ x ≤ 6 . Therefore, [ 0 , 6 ] [ 0 , 6 ] is the domain of consideration.

Step 6: Since T ( x ) T ( x ) is a continuous function over a closed, bounded interval, it has a maximum and a minimum. Let’s begin by looking for any critical points of T T over the interval [ 0 , 6 ] . [ 0 , 6 ] . The derivative is

If T ′ ( x ) = 0 , T ′ ( x ) = 0 , then

Squaring both sides of this equation, we see that if x x satisfies this equation, then x x must satisfy

which implies

We conclude that if x x is a critical point, then x x satisfies

Therefore, the possibilities for critical points are

Since x = 6 + 6 / 55 x = 6 + 6 / 55 is not in the domain, it is not a possibility for a critical point. On the other hand, x = 6 − 6 / 55 x = 6 − 6 / 55 is in the domain. Since we squared both sides of Equation 4.6 to arrive at the possible critical points, it remains to verify that x = 6 − 6 / 55 x = 6 − 6 / 55 satisfies Equation 4.6 . Since x = 6 − 6 / 55 x = 6 − 6 / 55 does satisfy that equation, we conclude that x = 6 − 6 / 55 x = 6 − 6 / 55 is a critical point, and it is the only one. To justify that the time is minimized for this value of x , x , we just need to check the values of T ( x ) T ( x ) at the endpoints x = 0 x = 0 and x = 6 , x = 6 , and compare them with the value of T ( x ) T ( x ) at the critical point x = 6 − 6 / 55 . x = 6 − 6 / 55 . We find that T ( 0 ) ≈ 2.108 h T ( 0 ) ≈ 2.108 h and T ( 6 ) ≈ 1.417 h, T ( 6 ) ≈ 1.417 h, whereas T ( 6 − 6 / 55 ) ≈ 1.368 h . T ( 6 − 6 / 55 ) ≈ 1.368 h . Therefore, we conclude that T T has a local minimum at x ≈ 5.19 x ≈ 5.19 mi.

Checkpoint 4.33

Suppose the island is 1 1 mi from shore, and the distance from the cabin to the point on the shore closest to the island is 15 mi . 15 mi . Suppose a visitor swims at the rate of 2.5 mph 2.5 mph and runs at a rate of 6 mph . 6 mph . Let x x denote the distance the visitor will run before swimming, and find a function for the time it takes the visitor to get from the cabin to the island.

In business, companies are interested in maximizing revenue . In the following example, we consider a scenario in which a company has collected data on how many cars it is able to lease, depending on the price it charges its customers to rent a car. Let’s use these data to determine the price the company should charge to maximize the amount of money it brings in.

Example 4.35

Maximizing revenue.

Owners of a car rental company have determined that if they charge customers p p dollars per day to rent a car, where 50 ≤ p ≤ 200 , 50 ≤ p ≤ 200 , the number of cars n n they rent per day can be modeled by the linear function n ( p ) = 1000 − 5 p . n ( p ) = 1000 − 5 p . If they charge $ 50 $ 50 per day or less, they will rent all their cars. If they charge $ 200 $ 200 per day or more, they will not rent any cars. Assuming the owners plan to charge customers between $50 per day and $ 200 $ 200 per day to rent a car, how much should they charge to maximize their revenue?

Step 1: Let p p be the price charged per car per day and let n n be the number of cars rented per day. Let R R be the revenue per day.

Step 2: The problem is to maximize R . R .

Step 3: The revenue (per day) is equal to the number of cars rented per day times the price charged per car per day—that is, R = n × p . R = n × p .

Step 4: Since the number of cars rented per day is modeled by the linear function n ( p ) = 1000 − 5 p , n ( p ) = 1000 − 5 p , the revenue R R can be represented by the function

Step 5: Since the owners plan to charge between $ 50 $ 50 per car per day and $ 200 $ 200 per car per day, the problem is to find the maximum revenue R ( p ) R ( p ) for p p in the closed interval [ 50 , 200 ] . [ 50 , 200 ] .

Step 6: Since R R is a continuous function over the closed, bounded interval [ 50 , 200 ] , [ 50 , 200 ] , it has an absolute maximum (and an absolute minimum) in that interval. To find the maximum value, look for critical points. The derivative is R ′ ( p ) = −10 p + 1000 . R ′ ( p ) = −10 p + 1000 . Therefore, the critical point is p = 100 p = 100 When p = 100 , p = 100 , R ( 100 ) = $ 50,000 . R ( 100 ) = $ 50,000 . When p = 50 , p = 50 , R ( p ) = $ 37,500 . R ( p ) = $ 37,500 . When p = 200 , p = 200 , R ( p ) = $ 0 . R ( p ) = $ 0 . Therefore, the absolute maximum occurs at p = $ 100 . p = $ 100 . The car rental company should charge $ 100 $ 100 per day per car to maximize revenue as shown in the following figure.

Checkpoint 4.34

A car rental company charges its customers p p dollars per day, where 60 ≤ p ≤ 150 . 60 ≤ p ≤ 150 . It has found that the number of cars rented per day can be modeled by the linear function n ( p ) = 750 − 5 p . n ( p ) = 750 − 5 p . How much should the company charge each customer to maximize revenue?

Example 4.36

Maximizing the area of an inscribed rectangle.

A rectangle is to be inscribed in the ellipse

What should the dimensions of the rectangle be to maximize its area? What is the maximum area?

Step 1: For a rectangle to be inscribed in the ellipse, the sides of the rectangle must be parallel to the axes. Let L L be the length of the rectangle and W W be its width. Let A A be the area of the rectangle.

Step 2: The problem is to maximize A . A .

Step 3: The area of the rectangle is A = L W . A = L W .

Step 4: Let ( x , y ) ( x , y ) be the corner of the rectangle that lies in the first quadrant, as shown in Figure 4.68 . We can write length L = 2 x L = 2 x and width W = 2 y . W = 2 y . Since x 2 4 + y 2 = 1 x 2 4 + y 2 = 1 and y > 0 , y > 0 , we have y = 1 − x 2 4 . y = 1 − x 2 4 . Therefore, the area is

Step 5: From Figure 4.68 , we see that to inscribe a rectangle in the ellipse, the x x -coordinate of the corner in the first quadrant must satisfy 0 < x < 2 . 0 < x < 2 . Therefore, the problem reduces to looking for the maximum value of A ( x ) A ( x ) over the open interval ( 0 , 2 ) . ( 0 , 2 ) . Since A ( x ) A ( x ) will have an absolute maximum (and absolute minimum) over the closed interval [ 0 , 2 ] , [ 0 , 2 ] , we consider A ( x ) = 2 x 4 − x 2 A ( x ) = 2 x 4 − x 2 over the interval [ 0 , 2 ] . [ 0 , 2 ] . If the absolute maximum occurs at an interior point, then we have found an absolute maximum in the open interval.

Step 6: As mentioned earlier, A ( x ) A ( x ) is a continuous function over the closed, bounded interval [ 0 , 2 ] . [ 0 , 2 ] . Therefore, it has an absolute maximum (and absolute minimum). At the endpoints x = 0 x = 0 and x = 2 , x = 2 , A ( x ) = 0 . A ( x ) = 0 . For 0 < x < 2 , 0 < x < 2 , A ( x ) > 0 . A ( x ) > 0 . Therefore, the maximum must occur at a critical point. Taking the derivative of A ( x ) , A ( x ) , we obtain

To find critical points, we need to find where A ′ ( x ) = 0 . A ′ ( x ) = 0 . We can see that if x x is a solution of

then x x must satisfy

Therefore, x 2 = 2 . x 2 = 2 . Thus, x = ± 2 x = ± 2 are the possible solutions of Equation 4.7 . Since we are considering x x over the interval [ 0 , 2 ] , [ 0 , 2 ] , x = 2 x = 2 is a possibility for a critical point, but x = − 2 x = − 2 is not. Therefore, we check whether 2 2 is a solution of Equation 4.7 . Since x = 2 x = 2 is a solution of Equation 4.7 , we conclude that 2 2 is the only critical point of A ( x ) A ( x ) in the interval [ 0 , 2 ] . [ 0 , 2 ] . Therefore, A ( x ) A ( x ) must have an absolute maximum at the critical point x = 2 . x = 2 . To determine the dimensions of the rectangle, we need to find the length L L and the width W . W . If x = 2 x = 2 then

Therefore, the dimensions of the rectangle are L = 2 x = 2 2 L = 2 x = 2 2 and W = 2 y = 2 2 = 2 . W = 2 y = 2 2 = 2 . The area of this rectangle is A = L W = ( 2 2 ) ( 2 ) = 4 . A = L W = ( 2 2 ) ( 2 ) = 4 .

Checkpoint 4.35

Modify the area function A A if the rectangle is to be inscribed in the unit circle x 2 + y 2 = 1 . x 2 + y 2 = 1 . What is the domain of consideration?

Solving Optimization Problems when the Interval Is Not Closed or Is Unbounded

In the previous examples, we considered functions on closed, bounded domains. Consequently, by the extreme value theorem, we were guaranteed that the functions had absolute extrema. Let’s now consider functions for which the domain is neither closed nor bounded.

Many functions still have at least one absolute extrema, even if the domain is not closed or the domain is unbounded. For example, the function f ( x ) = x 2 + 4 f ( x ) = x 2 + 4 over ( − ∞ , ∞ ) ( − ∞ , ∞ ) has an absolute minimum of 4 4 at x = 0 . x = 0 . Therefore, we can still consider functions over unbounded domains or open intervals and determine whether they have any absolute extrema. In the next example, we try to minimize a function over an unbounded domain. We will see that, although the domain of consideration is ( 0 , ∞ ) , ( 0 , ∞ ) , the function has an absolute minimum.

In the following example, we look at constructing a box of least surface area with a prescribed volume. It is not difficult to show that for a closed-top box, by symmetry, among all boxes with a specified volume, a cube will have the smallest surface area. Consequently, we consider the modified problem of determining which open-topped box with a specified volume has the smallest surface area.

Example 4.37

Minimizing surface area.

A rectangular box with a square base, an open top, and a volume of 216 216 in. 3 is to be constructed. What should the dimensions of the box be to minimize the surface area of the box? What is the minimum surface area?

Step 1: Draw a rectangular box and introduce the variable x x to represent the length of each side of the square base; let y y represent the height of the box. Let S S denote the surface area of the open-top box.

Step 2: We need to minimize the surface area. Therefore, we need to minimize S . S .

Step 3: Since the box has an open top, we need only determine the area of the four vertical sides and the base. The area of each of the four vertical sides is x · y . x · y . The area of the base is x 2 . x 2 . Therefore, the surface area of the box is

Step 4: Since the volume of this box is x 2 y x 2 y and the volume is given as 216 in . 3 , 216 in . 3 , the constraint equation is

Solving the constraint equation for y , y , we have y = 216 x 2 . y = 216 x 2 . Therefore, we can write the surface area as a function of x x only:

Therefore, S ( x ) = 864 x + x 2 . S ( x ) = 864 x + x 2 .

Step 5: Since we are requiring that x 2 y = 216 , x 2 y = 216 , we cannot have x = 0 . x = 0 . Therefore, we need x > 0 . x > 0 . On the other hand, x x is allowed to have any positive value. Note that as x x becomes large, the height of the box y y becomes correspondingly small so that x 2 y = 216 . x 2 y = 216 . Similarly, as x x becomes small, the height of the box becomes correspondingly large. We conclude that the domain is the open, unbounded interval ( 0 , ∞ ) . ( 0 , ∞ ) . Note that, unlike the previous examples, we cannot reduce our problem to looking for an absolute maximum or absolute minimum over a closed, bounded interval. However, in the next step, we discover why this function must have an absolute minimum over the interval ( 0 , ∞ ) . ( 0 , ∞ ) .

Step 6: Note that as x → 0 + , x → 0 + , S ( x ) → ∞ . S ( x ) → ∞ . Also, as x → ∞ , x → ∞ , S ( x ) → ∞ . S ( x ) → ∞ . Since S S is a continuous function that approaches infinity at the ends, it must have an absolute minimum at some x ∈ ( 0 , ∞ ) . x ∈ ( 0 , ∞ ) . This minimum must occur at a critical point of S . S . The derivative is

Therefore, S ′ ( x ) = 0 S ′ ( x ) = 0 when 2 x = 864 x 2 . 2 x = 864 x 2 . Solving this equation for x , x , we obtain x 3 = 432 , x 3 = 432 , so x = 432 3 = 6 2 3 . x = 432 3 = 6 2 3 . Since this is the only critical point of S , S , the absolute minimum must occur at x = 6 2 3 x = 6 2 3 (see Figure 4.70 ). When x = 6 2 3 , x = 6 2 3 , y = 216 ( 6 2 3 ) 2 = 3 2 3 in . y = 216 ( 6 2 3 ) 2 = 3 2 3 in . Therefore, the dimensions of the box should be x = 6 2 3 in . x = 6 2 3 in . and y = 3 2 3 in . y = 3 2 3 in . With these dimensions, the surface area is

Checkpoint 4.36

Consider the same open-top box, which is to have volume 216 in . 3 . 216 in . 3 . Suppose the cost of the material for the base is 20 ¢ / in . 2 20 ¢ / in . 2 and the cost of the material for the sides is 30 ¢ / in . 2 30 ¢ / in . 2 and we are trying to minimize the cost of this box. Write the cost as a function of the side lengths of the base. (Let x x be the side length of the base and y y be the height of the box.)

Section 4.7 Exercises

For the following exercises, answer by proof, counterexample, or explanation.

When you find the maximum for an optimization problem, why do you need to check the sign of the derivative around the critical points?

Why do you need to check the endpoints for optimization problems?

True or False . For every continuous nonlinear function, you can find the value x x that maximizes the function.

True or False . For every continuous nonconstant function on a closed, finite domain, there exists at least one x x that minimizes or maximizes the function.

For the following exercises, set up and evaluate each optimization problem.

To carry a suitcase on an airplane, the length + width + + width + height of the box must be less than or equal to 62 in . 62 in . Assuming the base of the suitcase is square, show that the volume is V = h ( 31 − ( 1 2 ) h ) 2 . V = h ( 31 − ( 1 2 ) h ) 2 . What height allows you to have the largest volume?

You are constructing a cardboard box with the dimensions 2 m by 4 m . 2 m by 4 m . You then cut equal-size squares from each corner so you may fold the edges. What are the dimensions of the box with the largest volume?

Find the positive integer that minimizes the sum of the number and its reciprocal.

Find two positive integers such that their sum is 10 , 10 , and minimize and maximize the sum of their squares.

For the following exercises, consider the construction of a pen to enclose an area.

You have 400 ft 400 ft of fencing to construct a rectangular pen for cattle. What are the dimensions of the pen that maximize the area?

You have 800 ft 800 ft of fencing to make a pen for hogs. If you have a river on one side of your property, what is the dimension of the rectangular pen that maximizes the area?

You need to construct a fence around an area of 1600 ft 2 . 1600 ft 2 . What are the dimensions of the rectangular pen to minimize the amount of material needed?

Two poles are connected by a wire that is also connected to the ground. The first pole is 20 ft 20 ft tall and the second pole is 10 ft 10 ft tall. There is a distance of 30 ft 30 ft between the two poles. Where should the wire be anchored to the ground to minimize the amount of wire needed?

[T] You are moving into a new apartment and notice there is a corner where the hallway narrows from 8 ft to 6 ft . 8 ft to 6 ft . What is the length of the longest item that can be carried horizontally around the corner?

A patient’s pulse measures 70 bpm, 80 bpm, then 120 bpm . 70 bpm, 80 bpm, then 120 bpm . To determine an accurate measurement of pulse, the doctor wants to know what value minimizes the expression ( x − 70 ) 2 + ( x − 80 ) 2 + ( x − 120 ) 2 ? ( x − 70 ) 2 + ( x − 80 ) 2 + ( x − 120 ) 2 ? What value minimizes it?

In the previous problem, assume the patient was nervous during the third measurement, so we only weight that value half as much as the others. What is the value that minimizes ( x − 70 ) 2 + ( x − 80 ) 2 + 1 2 ( x − 120 ) 2 ? ( x − 70 ) 2 + ( x − 80 ) 2 + 1 2 ( x − 120 ) 2 ?

You can run at a speed of 6 6 mph and swim at a speed of 3 3 mph and are located on the shore, 4 4 miles east of an island that is 1 1 mile north of the shoreline. How far should you run west to minimize the time needed to reach the island?

For the following problems, consider a lifeguard at a circular pool with diameter 40 m . 40 m . He must reach someone who is drowning on the exact opposite side of the pool, at position C . C . The lifeguard swims with a speed v v and runs around the pool at speed w = 3 v . w = 3 v .

Find a function that measures the total amount of time it takes to reach the drowning person as a function of the swim angle, θ . θ .

Find at what angle θ θ the lifeguard should swim to reach the drowning person in the least amount of time.

A truck uses gas as g ( v ) = a v + b v , g ( v ) = a v + b v , where v v represents the speed of the truck and g g represents the gallons of fuel per mile. Assuming a a and b b are positive, at what speed is fuel consumption minimized?

For the following exercises, consider a limousine that gets m ( v ) = ( 120 − 2 v ) 5 mi/gal m ( v ) = ( 120 − 2 v ) 5 mi/gal at speed v , v , the chauffeur costs $15/h , $15/h , and gas is $ 3.5 / gal . $ 3.5 / gal .

Find the cost per mile at speed v . v .

Find the cheapest driving speed.

For the following exercises, consider a pizzeria that sell pizzas for a revenue of R ( x ) = a x R ( x ) = a x and costs C ( x ) = b + c x + d x 2 , C ( x ) = b + c x + d x 2 , where x x represents the number of pizzas ;   a   >   c ;   a   >   c .

Find the profit function for the number of pizzas. How many pizzas gives the largest profit per pizza?

Assume that R ( x ) = 10 x R ( x ) = 10 x and C ( x ) = 2 x + x 2 . C ( x ) = 2 x + x 2 . How many pizzas sold maximizes the profit?

Assume that R ( x ) = 15 x , R ( x ) = 15 x , and C ( x ) = 60 + 3 x + 1 2 x 2 . C ( x ) = 60 + 3 x + 1 2 x 2 . How many pizzas sold maximizes the profit?

For the following exercises, consider a wire 4 ft 4 ft long cut into two pieces. One piece forms a circle with radius r r and the other forms a square of side x . x .

Choose x x to maximize the sum of their areas.

Choose x x to minimize the sum of their areas.

For the following exercises, consider two nonnegative numbers x x and y y such that x + y = 10 . x + y = 10 . Maximize and minimize the quantities.

x 2 y 2 x 2 y 2

y − 1 x y − 1 x

x 2 − y x 2 − y

For the following exercises, draw the given optimization problem and solve.

Find the volume of the largest right circular cylinder that fits in a sphere of radius 1 . 1 .

Find the volume of the largest right cone that fits in a sphere of radius 1 . 1 .

Find the area of the largest rectangle that fits into the triangle with sides x = 0 , y = 0 x = 0 , y = 0 and x 4 + y 6 = 1 . x 4 + y 6 = 1 .

Find the largest volume of a cylinder that fits into a cone that has base radius R R and height h . h .

Find the dimensions of the closed cylinder volume V = 16 π V = 16 π that has the least amount of surface area.

Find the dimensions of a right cone with surface area S = 4 π S = 4 π that has the largest volume.

For the following exercises, consider the points on the given graphs. Use a calculator to graph the functions.

[T] Where is the line y = 5 − 2 x y = 5 − 2 x closest to the origin?

[T] Where is the line y = 5 − 2 x y = 5 − 2 x closest to point ( 1 , 1 ) ? ( 1 , 1 ) ?

[T] Where is the parabola y = x 2 y = x 2 closest to point ( 2 , 0 ) ? ( 2 , 0 ) ?

[T] Where is the parabola y = x 2 y = x 2 closest to point ( 0 , 3 ) ? ( 0 , 3 ) ?

For the following exercises, set up, but do not evaluate, each optimization problem.

A window is composed of a semicircle placed on top of a rectangle. If you have 20 ft 20 ft of window-framing materials for the outer frame, what is the maximum size of the window you can create? Use r r to represent the radius of the semicircle.

You have a garden row of 20 20 watermelon plants that produce an average of 30 30 watermelons apiece. For any additional watermelon plants planted, the output per watermelon plant drops by one watermelon. How many extra watermelon plants should you plant?

You are constructing a box for your cat to sleep in. The plush material for the square bottom of the box costs $ 5 / ft 2 $ 5 / ft 2 and the material for the sides costs $ 2 / ft 2 . $ 2 / ft 2 . You need a box with volume 4 ft 3 . 4 ft 3 . Find the dimensions of the box that minimize cost. Use x x to represent the length of the side of the box.

You are building five identical pens adjacent to each other with a total area of 1000 m 2 , 1000 m 2 , as shown in the following figure. What dimensions should you use to minimize the amount of fencing?

You are the manager of an apartment complex with 50 50 units. When you set rent at $ 800 / month, $ 800 / month, all apartments are rented. As you increase rent by $ 25 / month, $ 25 / month, one fewer apartment is rented. Maintenance costs run $ 50 / month $ 50 / month for each occupied unit. What is the rent that maximizes the total amount of profit?

This book may not be used in the training of large language models or otherwise be ingested into large language models or generative AI offerings without OpenStax's permission.

Want to cite, share, or modify this book? This book uses the Creative Commons Attribution-NonCommercial-ShareAlike License and you must attribute OpenStax.

Access for free at https://openstax.org/books/calculus-volume-1/pages/1-introduction

• Authors: Gilbert Strang, Edwin “Jed” Herman
• Publisher/website: OpenStax
• Book title: Calculus Volume 1
• Publication date: Mar 30, 2016
• Location: Houston, Texas
• Book URL: https://openstax.org/books/calculus-volume-1/pages/1-introduction
• Section URL: https://openstax.org/books/calculus-volume-1/pages/4-7-applied-optimization-problems

© Jul 25, 2024 OpenStax. Textbook content produced by OpenStax is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike License . The OpenStax name, OpenStax logo, OpenStax book covers, OpenStax CNX name, and OpenStax CNX logo are not subject to the Creative Commons license and may not be reproduced without the prior and express written consent of Rice University.

Quadratic assignment problem

Author: Thomas Kueny, Eric Miller, Natasha Rice, Joseph Szczerba, David Wittmann (SysEn 5800 Fall 2020)

• 1 Introduction
• 2.1 Koopmans-Beckman Mathematical Formulation
• 2.2.1 Parameters
• 2.3.1 Optimization Problem
• 2.4 Computational Complexity
• 2.5 Algorithmic Discussions
• 2.6 Branch and Bound Procedures
• 2.7 Linearizations
• 3.1 QAP with 3 Facilities
• 4.1 Inter-plant Transportation Problem
• 4.2 The Backboard Wiring Problem
• 4.3 Hospital Layout
• 4.4 Exam Scheduling System
• 5 Conclusion
• 6 References

Introduction

The Quadratic Assignment Problem (QAP), discovered by Koopmans and Beckmann in 1957 [1] , is a mathematical optimization module created to describe the location of invisible economic activities. An NP-Complete problem, this model can be applied to many other optimization problems outside of the field of economics. It has been used to optimize backboards, inter-plant transportation, hospital transportation, exam scheduling, along with many other applications not described within this page.

Theory, Methodology, and/or Algorithmic Discussions

Koopmans-beckman mathematical formulation.

Economists Koopmans and Beckman began their investigation of the QAP to ascertain the optimal method of locating important economic resources in a given area. The Koopmans-Beckman formulation of the QAP aims to achieve the objective of assigning facilities to locations in order to minimize the overall cost. Below is the Koopmans-Beckman formulation of the QAP as described by neos-guide.org.

Quadratic Assignment Problem Formulation

Inner Product

Note: The true objective cost function only requires summing entries above the diagonal in the matrix comprised of elements

Since this matrix is symmetric with zeroes on the diagonal, dividing by 2 removes the double count of each element to give the correct cost value. See the Numerical Example section for an example of this note.

Optimization Problem

With all of this information, the QAP can be summarized as:

Computational Complexity

QAP belongs to the classification of problems known as NP-complete, thus being a computationally complex problem. QAP’s NP-completeness was proven by Sahni and Gonzalez in 1976, who states that of all combinatorial optimization problems, QAP is the “hardest of the hard”. [2]

Algorithmic Discussions

While an algorithm that can solve QAP in polynomial time is unlikely to exist, there are three primary methods for acquiring the optimal solution to a QAP problem:

• Dynamic Program
• Cutting Plane

Branch and Bound Procedures

The third method has been proven to be the most effective in solving QAP, although when n > 15, QAP begins to become virtually unsolvable.

The Branch and Bound method was first proposed by Ailsa Land and Alison Doig in 1960 and is the most commonly used tool for solving NP-hard optimization problems.

A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before one lists all of the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and the branch is eliminated if it cannot produce a better solution than the best one found so far by the algorithm.

Linearizations

The first attempts to solve the QAP eliminated the quadratic term in the objective function of

in order to transform the problem into a (mixed) 0-1 linear program. The objective function is usually linearized by introducing new variables and new linear (and binary) constraints. Then existing methods for (mixed) linear integer programming (MILP) can be applied. The very large number of new variables and constraints, however, usually poses an obstacle for efficiently solving the resulting linear integer programs. MILP formulations provide LP relaxations of the problem which can be used to compute lower bounds.

Numerical Example

Qap with 3 facilities.

Applications

Inter-plant transportation problem.

The QAP was first introduced by Koopmans and Beckmann to address how economic decisions could be made to optimize the transportation costs of goods between both manufacturing plants and locations. [1] Factoring in the location of each of the manufacturing plants as well as the volume of goods between locations to maximize revenue is what distinguishes this from other linear programming assignment problems like the Knapsack Problem.

The Backboard Wiring Problem

As the QAP is focused on minimizing the cost of traveling from one location to another, it is an ideal approach to determining the placement of components in many modern electronics. Leon Steinberg proposed a QAP solution to optimize the layout of elements on a blackboard by minimizing the total amount of wiring required. [4]

When defining the problem Steinberg states that we have a set of n elements

as well as a set of r points

In his paper he derives the below formula:

In his paper Steinberg a backboard with a 9 by 4 array, allowing for 36 potential positions for the 34 components that needed to be placed on the backboard. For the calculation, he selected a random initial placement of s1 and chose a random family of 25 unconnected sets.

The initial placement of components is shown below:

After the initial placement of elements, it took an additional 35 iterations to get us to our final optimized backboard layout. Leading to a total of 59 iterations and a final wire length of 4,969.440.

Hospital Layout

Building new hospitals was a common event in 1977 when Alealid N Elshafei wrote his paper on "Hospital Layouts as a Quadratic Assignment Problem". [5] With the high initial cost to construct the hospital and to staff it, it is important to ensure that it is operating as efficiently as possible. Elshafei's paper was commissioned to create an optimization formula to locate clinics within a building in such a way that minimizes the total distance that a patient travels within the hospital throughout the year. When doing a study of a major hospital in Cairo he determined that the Outpatient ward was acting as a bottleneck in the hospital and focused his efforts on optimizing the 17 departments there.

Elshafei identified the following QAP to determine where clinics should be placed:

For the Cairo hospital with 17 clinics, and one receiving and recording room bringing us to a total of 18 facilities. By running the above optimization Elshafei was able to get the total distance per year down to 11,281,887 from a distance of 13,973,298 based on the original hospital layout.

Exam Scheduling System

The scheduling system uses matrices for Exams, Time Slots, and Rooms with the goal of reducing the rate of schedule conflicts. To accomplish this goal, the “examination with the highest cross faculty student is been prioritized in the schedule after which the examination with the highest number of cross-program is considered and finally with the highest number of repeating student, at each stage group with the highest number of student are prioritized.” [6]

• ↑ 1.0 1.1 1.2 Koopmans, T., & Beckmann, M. (1957). Assignment Problems and the Location of Economic Activities. Econometrica, 25(1), 53-76. doi:10.2307/1907742
• ↑ 2.0 2.1 Quadratic Assignment Problem. (2020). Retrieved December 14, 2020, from https://neos-guide.org/content/quadratic-assignment-problem
• ↑ 3.0 3.1 3.2 Burkard, R. E., Çela, E., Pardalos, P. M., & Pitsoulis, L. S. (2013). The Quadratic Assignment Problem. https://www.opt.math.tugraz.at/~cela/papers/qap_bericht.pdf .
• ↑ 4.0 4.1 Leon Steinberg. The Backboard Wiring Problem: A Placement Algorithm. SIAM Review . 1961;3(1):37.
• ↑ 5.0 5.1 Alwalid N. Elshafei. Hospital Layout as a Quadratic Assignment Problem. Operational Research Quarterly (1970-1977) . 1977;28(1):167. doi:10.2307/300878
• ↑ 6.0 6.1 Muktar, D., & Ahmad, Z.M. (2014). Examination Scheduling System Based On Quadratic Assignment.

Navigation menu

A Comparative Analysis of Assignment Problem

• Conference paper
• First Online: 06 June 2023
• Cite this conference paper

• Shahriar Tanvir Alam   ORCID: orcid.org/0000-0002-0567-3381 5 ,
• Eshfar Sagor 5 ,
• Tanjeel Ahmed 5 ,
• Tabassum Haque 5 ,
• Md Shoaib Mahmud 5 ,
• Salman Ibrahim 5 ,
• Ononya Shahjahan 5 &
• Mubtasim Rubaet 5  

Part of the book series: EAI/Springer Innovations in Communication and Computing ((EAISICC))

Included in the following conference series:

• International Conference on Big Data Innovation for Sustainable Cognitive Computing

147 Accesses

The aim of a supply chain team is to formulate a network layout that minimizes the total cost. In this research, the lowest production cost of the final product has been determined using a generalized plant location model. Furthermore, it is anticipated that units have been set up appropriately so that one unit of input from a source of supply results in one unit of output. The assignment problem is equivalent to distributing a job to the appropriate machine in order to meet customer demand. This study concentrates on reducing the cost of fulfilling the overall customer demand. Many studies have been conducted, and various algorithms have been proposed to achieve the best possible result. The purpose of this study is to present an appropriate model for exploring the solution to the assignment problem using the “Hungarian Method.” To find a feasible output of the assignment problem, this study conducted a detailed case study. The computational results indicate that the “Hungarian Method” provides an optimum solution for both balanced and unbalanced assignment problems. Moreover, decision-makers can use the study’s findings as a reference to mitigate production costs and adopt any sustainable market policy.

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

Access this chapter

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Available as EPUB and PDF
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info
• Durable hardcover edition

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Optimization model for a production, inventory, distribution and routing problem in small furniture companies.

New Hybrid Algorithm for Supply Chain Optimization

Bi-objective optimization model with economic and environmental consideration for an integrated supply chain with random demand and flexible production rate

Z. Xiang, J. Yang, X. Liang, M.H. Naseem, Application of discrete Grey Wolf Algorithm in balanced transport problem, in 2021 3rd International Academic Exchange Conference on Science and Technology Innovation, IAECST 2021 , (2021), pp. 1312–1318. https://doi.org/10.1109/IAECST54258.2021.9695827

Chapter   Google Scholar  

C. Woodyard, New York City Is Costliest Place to Park in USA (2018). https://content.usatoday.com/communities/driveon/post/2011/07/new-york-city-costliest-place-to-park-your-car/1#.WWUoFoQrJdg . Accessed 23 Apr 2022

K. McCoy, Drivers spend an average of 17 hours a year searching for parking spots. USA Today (2017). https://www.usatoday.com/story/money/2017/07/12/parking-pain-causes-financial-and-personal-strain/467637001/ . Accessed 23 Apr 2022

W. Ho, P. Ji, A genetic algorithm for the generalised transportation problem. Int. J. Comput. Appl. Technol. 22 (4), 190–197 (2005). https://doi.org/10.1504/IJCAT.2005.006959

Article   Google Scholar  

Z. Nakat, S. Herrera, Y. Cherkaoui, Cairo Traffic Congestion Study (World Bank, Washington, DC, 2013)

Google Scholar  

S. Bussmann, K. Schild, An agent-based approach to the control of flexible production systems, in IEEE International Conference on Emerging Technologies and Factory Automation, ETFA , vol. 2, (2001), pp. 481–488. https://doi.org/10.1109/etfa.2001.997722

S. Emde, M. Gendreau, Scheduling in-house transport vehicles to feed parts to automotive assembly lines. Eur. J. Oper. Res. 260 (1), 255–267 (2017). https://doi.org/10.1016/j.ejor.2016.12.012

Article   MathSciNet   MATH   Google Scholar  

S. Chopra, G. Notarstefano, M. Rice, M. Egerstedt, A distributed version of the Hungarian method for multirobot assignment. IEEE Trans. Robot. 33 (4), 932–947 (2017). https://doi.org/10.1109/TRO.2017.2693377

H.A. Hussein, M.A.K. Shiker, Two new effective methods to find the optimal solution for the assignment problems. J. Adv. Res. Dyn. Control Syst. 12 (7), 49–54 (2020). https://doi.org/10.5373/JARDCS/V12I7/20201983

M. Chen, D. Zhu, A workload balanced algorithm for task assignment and path planning of inhomogeneous autonomous underwater vehicle system. IEEE Trans. Cogn. Develop. Syst. 11 (4), 483–493 (2018)

C. Cubukcuoglu, P. Nourian, M.F. Tasgetiren, I.S. Sariyildiz, S. Azadi, Hospital layout design renovation as a quadratic assignment problem with geodesic distances. J. Build. Eng. 44 , 102952 (2021). https://doi.org/10.1016/j.jobe.2021.102952

U. Tosun, A new tool for automated transformation of quadratic assignment problem instances to quadratic unconstrained binary optimisation models. Expert Syst. Appl. 201 , 116953 (2022). https://doi.org/10.1016/j.eswa.2022.116953

S.M. Homayouni, D.B.M.M. Fontes, Production and transport scheduling in flexible job shop manufacturing systems. J. Glob. Optim. 79 (2), 463–502 (2021). https://doi.org/10.1007/s10898-021-00992-6

Article   MathSciNet   Google Scholar  

R. Wang, J. Yan, X. Yang, Neural graph matching network: Learning Lawler’s quadratic assignment problem with extension to hypergraph and multiple-graph matching. IEEE Trans. Pattern Anal. Mach. Intell. 44 (9), 5261–5279 (2022). https://doi.org/10.1109/TPAMI.2021.3078053

T. Dokeroglu, E. Sevinc, A. Cosar, Artificial bee colony optimization for the quadratic assignment problem. Appl. Soft Comput. J. 76 , 595–606 (2019). https://doi.org/10.1016/j.asoc.2019.01.001

X. Xiang, C. Liu, An almost robust optimization model for integrated berth allocation and quay crane assignment problem. Omega (United Kingdom) 104 , 102455 (2021). https://doi.org/10.1016/j.omega.2021.102455

Ö. Karsu, M. Azizoğlu, K. Alanlı, Exact and heuristic solution approaches for the airport gate assignment problem. Omega (United Kingdom) 103 , 102422 (2021). https://doi.org/10.1016/j.omega.2021.102422

A.S. Hameed, M.L. Mutar, H.M.B. Alrikabi, Z.H. Ahmed, A.A. Abdul-Razaq, H.K. Nasser, A hybrid method integrating a discrete differential evolution algorithm with tabu search algorithm for the quadratic assignment problem: A new approach for locating hospital departments. Math. Probl. Eng. 2021 (2021). https://doi.org/10.1155/2021/6653056

S.T. Ngo, J. Jaafar, I.A. Aziz, B.N. Anh, A compromise programming for multi-objective task assignment problem. Computers 10 (2), 1–16 (2021). https://doi.org/10.3390/computers10020015

X. Zheng, D. Zhou, N. Li, T. Wu, Y. Lei, J. Shi, Self-adaptive multi-task differential evolution optimization: With case studies in weapon–target assignment problem. Electronics 10 (23), 2945 (2021). https://doi.org/10.3390/electronics10232945

X. Hu, C. Liang, D. Chang, Y. Zhang, Container storage space assignment problem in two terminals with the consideration of yard sharing. Adv. Eng. Inform. 47 , 101224 (2021). https://doi.org/10.1016/j.aei.2020.101224

Q. Rabbani, A. Khan, A. Quddoos, Modified Hungarian method for unbalanced assignment problem with multiple jobs. Appl. Math. Comput. 361 , 493–498 (2019). https://doi.org/10.1016/j.amc.2019.05.041

A. Kumar, A modified method for solving the unbalanced assignment problems. Appl. Math. Comput. 176 (1), 76–82 (2006). https://doi.org/10.1016/j.amc.2005.09.056

A. Iampang, V. Boonjing, P. Chanvarasuth, A cost and space efficient method for unbalanced assignment problems, in IEEM2010 – IEEE International Conference on Industrial Engineering and Engineering Management , (2010), pp. 985–988. https://doi.org/10.1109/IEEM.2010.5674228

L. Wang, Z. He, C. Liu, Q. Chen, Graph based twin cost matrices for unbalanced assignment problem with improved ant colony algorithm. Results Appl. Math. 12 , 100207 (2021). https://doi.org/10.1016/j.rinam.2021.100207

Download references

Author information

Authors and affiliations.

Military Institute of Science and Technology, Department of Industrial and Production Engineering, Dhaka, Bangladesh

Shahriar Tanvir Alam, Eshfar Sagor, Tanjeel Ahmed, Tabassum Haque, Md Shoaib Mahmud, Salman Ibrahim, Ononya Shahjahan & Mubtasim Rubaet

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Shahriar Tanvir Alam .

Editor information

Editors and affiliations.

Department of Computer Science and Engineering, Sri Eshwar College of Engineering, Coimbatore, Tamil Nadu, India

Anandakumar Haldorai

Department of Computer Science and Engineering, CMR University, Bengaluru, Karnataka, India

Arulmurugan Ramu

Sri Eshwar College of Engineering, Coimbatore, Tamil Nadu, India

Sudha Mohanram

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Cite this paper.

Alam, S.T. et al. (2023). A Comparative Analysis of Assignment Problem. In: Haldorai, A., Ramu, A., Mohanram, S. (eds) 5th EAI International Conference on Big Data Innovation for Sustainable Cognitive Computing. BDCC 2022. EAI/Springer Innovations in Communication and Computing. Springer, Cham. https://doi.org/10.1007/978-3-031-28324-6_11

Download citation

DOI : https://doi.org/10.1007/978-3-031-28324-6_11

Published : 06 June 2023

Publisher Name : Springer, Cham

Print ISBN : 978-3-031-28323-9

Online ISBN : 978-3-031-28324-6

eBook Packages : Engineering Engineering (R0)

Share this paper

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

• WolframAlpha.com
• WolframCloud.com
• All Sites & Public Resources...

• Wolfram|One
• Mathematica
• Wolfram|Alpha Notebook Edition
• Finance Platform
• System Modeler
• Wolfram Player
• Wolfram Engine
• WolframScript
• Enterprise Private Cloud
• Application Server
• Enterprise Mathematica
• Wolfram|Alpha Appliance
• Corporate Consulting
• Technical Consulting
• Wolfram|Alpha Business Solutions
• Data Repository
• Neural Net Repository
• Function Repository
• Wolfram|Alpha Pro
• Problem Generator
• Products for Education
• Wolfram Cloud App
• Wolfram|Alpha for Mobile
• Wolfram|Alpha-Powered Apps
• Paid Project Support
• Summer Programs
• All Products & Services »
• Wolfram Language Revolutionary knowledge-based programming language. Wolfram Cloud Central infrastructure for Wolfram's cloud products & services. Wolfram Science Technology-enabling science of the computational universe. Wolfram Notebooks The preeminent environment for any technical workflows. Wolfram Engine Software engine implementing the Wolfram Language. Wolfram Natural Language Understanding System Knowledge-based broadly deployed natural language. Wolfram Data Framework Semantic framework for real-world data. Wolfram Universal Deployment System Instant deployment across cloud, desktop, mobile, and more. Wolfram Knowledgebase Curated computable knowledge powering Wolfram|Alpha.
• All Technologies »
• Aerospace & Defense
• Chemical Engineering
• Control Systems
• Electrical Engineering
• Image Processing
• Industrial Engineering
• Mechanical Engineering
• Operations Research
• Actuarial Sciences
• Bioinformatics
• Data Science
• Econometrics
• Financial Risk Management
• All Solutions for Education
• Machine Learning
• Multiparadigm Data Science
• High-Performance Computing
• Quantum Computation Framework
• Software Development
• Authoring & Publishing
• Interface Development
• Web Development
• All Solutions »
• Wolfram Language Documentation
• Fast Introduction for Programmers
• Videos & Screencasts
• Wolfram Language Introductory Book
• Webinars & Training
• Support FAQ
• Wolfram Community
• Contact Support
• All Learning & Support »
• Company Background
• Wolfram Blog
• Careers at Wolfram
• Internships
• Other Wolfram Language Jobs
• Wolfram Foundation
• Computer-Based Math
• A New Kind of Science
• Wolfram Technology for Hackathons
• Student Ambassador Program
• Wolfram for Startups
• Demonstrations Project
• Wolfram Innovator Awards
• Wolfram + Raspberry Pi
• All Company »

Wolfram Language ™

Optimal assignment problem.

Find the amount of electricity a company must send from its four power plants to five cities so as to maximize profit and minimize cost while meeting the cities' peak demands.

This example demonstrates how LinearFractionalOptimization may be used to minimize the ratio of cost to profit within given constraints. Use of a matrix-valued variable makes the modeling relatively simple.

As an example, here is the cost of transporting one million kilowatt hours (kWh) of electricity from four plants to five cities.

The profit that each power plant generates by selling 1 million kWh to each city is shown here.

The cities have a peak demand of 45, 20, 30, 30 and 40 million kWh, respectively, and a minimum demand of 5 million kWh.

The power plants can supply a minimum of 35, 50, 40 and 40 million kWh of electricity, respectively.

The optimal amount of electricity to send each city by each plant can be found by minimizing the ratio of cost to profit.

The breakdown of electricity supplied is shown.

Related Examples

• Wolfram|Alpha Notebook Edition
• Mobile Apps
• Wolfram Workbench
• Volume & Site Licensing
• View all...
• For Customers
• Online Store
• Product Registration
• Product Downloads
• Service Plans Benefits
• User Portal
• Your Account
• Customer Service
• Get Started with Wolfram
• Fast Introduction for Math Students
• Public Resources
• Wolfram|Alpha
• Resource System
• Connected Devices Project
• Wolfram Data Drop
• Wolfram Science
• Computational Thinking
• About Wolfram
• Legal & Privacy Policy

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

Collectives™ on Stack Overflow

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

Q&A for work

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

Get early access and see previews of new features.

How to tractably solve the assignment optimisation task

I'm working on a script that takes the elements from companies and pairs them up with the elements of people . The goal is to optimize the pairings such that the sum of all pair values is maximized (the value of each individual pairing is precomputed and stored in the dictionary ctrPairs ).

They're all paired in a 1:1, each company has only one person and each person belongs to only one company, and the number of companies is equal to the number of people. I used a top-down approach with a memoization table ( memDict ) to avoid recomputing areas that have already been solved.

I believe that I could vastly improve the speed of what's going on here but I'm not really sure how. Areas I'm worried about are marked with #slow? , any advice would be appreciated (the script works for inputs of lists n<15 but it gets incredibly slow for n > ~15)

• optimization
• dynamic-programming

• Sorry I guess that was confusing. I think it follows the model of a knapsack type problem, so the idea is to come up with a solution that has every element of companies paired with an element of people where the sum of all their pairings is the maximum possible value for all potential combinations (i.e. there would be no other arrangement of pairs that could yield a higher sum) –  spencewah Commented Jun 11, 2009 at 16:35
• 1 @SilentGhost Stop setting a title that actually describes the question? –  Marcin Commented Nov 1, 2012 at 15:36
• 1 @Marcin: stop messing about w/ privileges and go answer some questions. –  SilentGhost Commented Nov 1, 2012 at 15:37
• @SilentGhost What do you mean, "Messing about with privileges"? What is your objection to the title I just set? –  Marcin Commented Nov 1, 2012 at 15:39

4 Answers 4

To all those who wonder about the use of learning theory, this question is a good illustration. The right question is not about a "fast way to bounce between lists and tuples in python" — the reason for the slowness is something deeper.

What you're trying to solve here is known as the assignment problem : given two lists of n elements each and n×n values (the value of each pair), how to assign them so that the total "value" is maximized (or equivalently, minimized). There are several algorithms for this, such as the Hungarian algorithm ( Python implementation ), or you could solve it using more general min-cost flow algorithms, or even cast it as a linear program and use an LP solver. Most of these would have a running time of O(n 3 ).

What your algorithm above does is to try each possible way of pairing them. (The memoisation only helps to avoid recomputing answers for pairs of subsets, but you're still looking at all pairs of subsets.) This approach is at least Ω(n 2 2 2n ). For n=16, n 3 is 4096 and n 2 2 2n is 1099511627776. There are constant factors in each algorithm of course, but see the difference? :-) (The approach in the question is still better than the naive O(n!), which would be much worse.) Use one of the O(n^3) algorithms, and I predict it should run in time for up to n=10000 or so, instead of just up to n=15.

"Premature optimization is the root of all evil", as Knuth said, but so is delayed/overdue optimization: you should first carefully consider an appropriate algorithm before implementing it, not pick a bad one and then wonder what parts of it are slow. :-) Even badly implementing a good algorithm in Python would be orders of magnitude faster than fixing all the "slow?" parts of the code above (e.g., by rewriting in C).

• 1 NB: The original title of the question was "Help requested: what's a fast way to bounce between lists and tuples in python?", hence the first paragraph of this answer. –  Marcin Commented Feb 9, 2012 at 17:39

i see two issues here:

efficiency: you're recreating the same remainingPeople sublists for each company. it would be better to create all the remainingPeople and all the remainingCompanies once and then do all the combinations.

memoization: you're using tuples instead of lists to use them as dict keys for memoization; but tuple identity is order-sensitive. IOW: (1,2) != (2,1) you better use set s and frozenset s for this: frozenset((1,2)) == frozenset((2,1))

remainingCompanies = companies[1:len(companies)]

Can be replaced with this line:

For a very slight speed increase. That's the only improvement I see.

If you want to get a copy of a tuple as a list you can do mylist = list(mytuple)

Your Answer

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

Sign up or log in

Post as a guest.

Required, but never shown

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

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

• The Overflow Blog
• The evolution of full stack engineers
• One of the best ways to get value for AI coding tools: generating tests
• Featured on Meta
• Bringing clarity to status tag usage on meta sites
• Join Stack Overflow’s CEO and me for the first Stack IRL Community Event in...
• Feedback requested: How do you use tag hover descriptions for curating and do...
• Staging Ground Reviewer Motivation
• What does a new user need in a homepage experience on Stack Overflow?

Hot Network Questions

• Could they free up a docking port on ISS by undocking the emergency vehicle and letting it float next to the station for a little while
• Practice test paper answers all seem incorrect, but provider insists they are ... what am i missing?
• Text processing: Filter & re-publish HTML table
• Using "provide" with value of a variable
• How much does a ma'ah cost in £/$ in today's world?
• Can I land on the "EuroAirport Basel-Mulhouse-Freiburg" with a German National Visa as first destination (NON-EU Citizen)?
• Somebody used recommendation by an in-law – should I report it?
• Understanding the solution of a differential equation found with Fourier Transform
• Remove spaces from the 3rd line onwards in a file on linux
• How do I go about writing a tragic ending in a story while making it overall satisfying to the reader?
• What does it mean for a predicate to be ground?
• The meaning of "sharp" in "sharp sweetness"
• package accents seems to be incompatible with Unicode-math
• What is the purpose of long plastic sleeve tubes around connections in appliances?
• Mistake on car insurance policy about use of car (commuting/social)
• Does a Debt Exist for A Parking Charge Notice
• What sci-fi show was Ernie watching in the show My Three Sons?
• Is the highlighted part false?
• Inspector tells me that the electrician should have removed green screw from the panel
• Engaging students in the beauty of mathematics
• Can't identify logo for a 135N68A MOSFET. Hunting for datasheet. Any ideas?
• Best memory / storage solution for high read / write throughput application(s)?
• ESTA for dual national: what can happen if I lie about being American?
• Overstaying knowing I have a new Schengen visa

Stack Exchange Network

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

Q&A for work

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

Relationship Between "Assignment Problems" and "Graphs"

I was reading the following Wikipedia Article on "Assignment Problems" that talks about the relationship between Assignment Problems and Graph Theory ( https://en.wikipedia.org/wiki/Assignment_problem ) :

The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:

The problem instance has a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform as many tasks as possible by assigning at most one agent to each task and at most one task to each agent, in such a way that the total cost of the assignment is minimized.

Alternatively, describing the problem using graph theory: The assignment problem consists of finding, in a weighted bipartite graph, a matching of a given size, in which the sum of weights of the edges is minimum.

I am familiar with both of these concepts individually, but I do not understand why these concepts are related:

1) Assignment Problems

Assignment Problems - as the name implies - are usually about determining an "optimal assignment of tasks to agents". For example, suppose there are 4 Workers (Worker A, Worker B, Worker C, Worker D) and 4 Jobs (Job A, Job B, Job C, Job D). Each worker has a "certain cost" associated with performing each of these jobs (e.g. Worker A performs Job B better than Worker D, but Worker D performs Job D better than Worker A). The Assignment Problem involves "assigning" only one job to each worker such that the total cost is minimized:

2) Weighted Bipartite Graphs

A Bipartite Graph is a Graph in which all "Nodes" within the Graph (i.e. circles) either belong to one of two sets (e.g. red and blue). A Weighted Bipartite Graph is a Bipartite Graph in which each "Edge" has a certain cost associated with it:

My Question: The formal definition of a general Assignment Problem is seen below:

Thus, can someone please explain why " the assignment problem consists of finding, in a weighted bipartite graph, a matching of a given size, in which the sum of weights of the edges is minimum" ?

• optimization
• combinatorial-optimization

• 1 $\begingroup$ Let yellow be the agents A, B, C, D. Let blue be the tasks job1, job 2, job 3, job 4. Let the cost of each edge be the corresponding entry of the assignment cost matrix. Now minimize the cost of the matching. That seems like a pretty good correspondence to me. $\endgroup$ –  Mark L. Stone Commented Feb 10, 2022 at 17:57
• $\begingroup$ @ Mark L Stone: Thank you for your reply! I can see that the Assignment Problem does correspond to a Weighted Bipartite Graph , and that we want to find the sum of weights of the edges in minimum .... but why do we want to find a "matching"? $\endgroup$ –  stats_noob Commented Feb 10, 2022 at 18:01
• $\begingroup$ I think this is just a formality that corresponds to the constraint - a "matching" is a graph where each edge is without common vertices. I guess this is to make sure that a worker can not be assigned more than one job? thank you so much! $\endgroup$ –  stats_noob Commented Feb 10, 2022 at 18:05
• 1 $\begingroup$ Each node in the yellow should be matched to exactly one node in the blue. Just as each agent should be assigned (matched) to exactly one task. No agent can be assigned more than one task, and no task can be assigned to more than one agent. $\endgroup$ –  Mark L. Stone Commented Feb 10, 2022 at 18:23

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

Your answer, sign up or log in, post as a guest.

Required, but never shown

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

Browse other questions tagged optimization combinatorial-optimization or ask your own question .

• Featured on Meta
• Join Stack Overflow’s CEO and me for the first Stack IRL Community Event in...
• Bringing clarity to status tag usage on meta sites

Hot Network Questions

• Please help me identify my Dad's bike collection (80's-2000's)
• Can I land on the "EuroAirport Basel-Mulhouse-Freiburg" with a German National Visa as first destination (NON-EU Citizen)?
• Text processing: Filter & re-publish HTML table
• Paying a parking fine when I don't trust the recipient
• Can't identify logo for a 135N68A MOSFET. Hunting for datasheet. Any ideas?
• Humans are forbidden from using complex computers. But what defines a complex computer?
• Fantasy book about humans and gnomes entering one another's worlds
• How are you supposed to trust SSO popups in desktop and mobile applications?
• Why would the GPL be viral, while EUPL isn't, according to the EUPL authors?
• What is the shortest viable hmac for non-critical applications?
• The pronoun in short yes/no answers to rhetorical tag-questions with the generic "you"
• If a friend hands me a marijuana edible then dies of a heart attack am I guilty of felony murder?
• Does this policy mean that my work has flawed password storage?
• Key fob frequency filter design
• How much does a ma'ah cost in £/$ in today's world?
• A journal has published an AI-generated article under my name. What to do?
• The quest for a Wiki-less Game
• What are the steps to write a book?
• Expansion in Latex3 when transforming an input and forwarding it to another function
• Did the heavenly Temple have a separation of the two inner rooms?
• package accents seems to be incompatible with Unicode-math
• I want to be a observational astronomer, but have no idea where to start
• ESTA for dual national: what can happen if I lie about being American?
• Is it possible for one wing to stall due to icing while the other wing doesn't ice?

Stack Exchange Network

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

Q&A for work

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

Is there an algorithm for solving a many-to-one assignment problem?

I'm looking for an algorithm to solve assignment problem, but it is not one to one problem. I know the Hungarian algorithm it can simply assign one task to one agent.

Let's say I have 4 tasks and 20 agents and I want to assign 5 agents to each task (based on the cost matrix). Is there any efficient algorithm to do this?

It will be great if there is a Python library with algorithm like that.

• optimization

2 Answers 2

Let's say that you now have a 20 by 4 cost matrix $C$ consisting of the costs of assigning agents to tasks. You can make 5 new tasks, each requiring one agent, out of each original task.

To do this, make a new cost matrix $C_{\text{new}}$ , which is 20 by 20, in which each column of $C$ appears 5 times. Use the Hungarian algorithm on $C_{\text{new}}$ . and you will have 1 agent assigned to every new task, which will therefore be 5 agents assigned to every original task.

Using the matrix scheme suggested by Mark, you could use the Jonker-Volgenant algorithm which is a modification of the Hungarian algorithm.

It is implemented in scipy.optimize.linear_sum_assignment . Here is an example from the documentation, which you can modify to include your own choice of cost matrix.

Your Answer

Sign up or log in, post as a guest.

Required, but never shown

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

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

• Featured on Meta
• Bringing clarity to status tag usage on meta sites
• Join Stack Overflow’s CEO and me for the first Stack IRL Community Event in...

Hot Network Questions

• Does Poincare recurrence show that Gibbs entropy is not strictly increasing?
• Electromagnetic Eigenvalue problem in FEM yielding spurious solutions
• Is it true that before modern Europe, there were no "nations"?
• Why public key is taken in private key in Kyber KEM?
• Can't identify logo for a 135N68A MOSFET. Hunting for datasheet. Any ideas?
• What is the least number of colours Peter could use to color the 3x3 square?
• How to fold or expand the wingtips on Boeing 777?
• package accents seems to be incompatible with Unicode-math
• Is this a misstatement of Euclid in Halmos' Naive Set Theory book?
• Is the white man at the other side of the Joliba river a historically identifiable person?
• Wrong explanation for why "electron can't exist in the nucleus"?
• Does a Debt Exist for A Parking Charge Notice
• Children's book about intelligent bears or maybe cats
• What is the purpose of long plastic sleeve tubes around connections in appliances?
• A journal has published an AI-generated article under my name. What to do?
• How much could gravity increase before a military tank is crushed
• ESTA for dual national: what can happen if I lie about being American?
• Did Queen (or Freddie Mercury) really not like Star Wars?
• Is the highlighted part false?
• What is the working justification of this circuit?
• Best memory / storage solution for high read / write throughput application(s)?
• Colossians 1:16 New World Translation renders τα πάντα as “all other things” but why is this is not shown in their Kingdom Interlinear?
• Big Transition of Binary Counting in perspective of IEEE754 floating point
• Why do "modern" languages not provide argv and exit code in main?

IEEE Account

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

PRX Quantum

A physical review journal.

• Editorial Team
• Open Access

Solving Boolean Satisfiability Problems With The Quantum Approximate Optimization Algorithm

Sami boulebnane and ashley montanaro, prx quantum 5 , 030348 – published 10 september 2024.

• No Citing Articles

Supplemental Material

• INTRODUCTION
• DEFINITIONS AND PRELIMINARIES
• ACKNOWLEDGMENTS

One of the most prominent application areas for quantum computers is solving hard constraint satisfaction and optimization problems. However, detailed analyses of the complexity of standard quantum algorithms have suggested that outperforming classical methods for these problems would require extremely large and powerful quantum computers. The quantum approximate optimization algorithm (QAOA) is designed for near-term quantum computers, yet previous work has shown strong limitations on the ability of QAOA to outperform classical algorithms for optimization problems. Here we instead apply QAOA to hard constraint satisfaction problems, where both classical and quantum algorithms are expected to require exponential time. We analytically characterize the average success probability of QAOA on a constraint satisfaction problem commonly studied using statistical physics methods: random k -SAT at the threshold for satisfiability, as the number of variables n goes to infinity. We complement these theoretical results with numerical experiments on the performance of QAOA for small n , which match the limiting theoretical bounds closely. We then compare QAOA with leading classical solvers. For random 8-SAT, we find that for more than 14 quantum circuit layers, QAOA achieves more efficient scaling than the highest-performance classical solver we tested, WalkSATlm. Our results suggest that near-term quantum algorithms for solving constraint satisfaction problems may outperform their classical counterparts.

• Received 19 September 2023
• Revised 28 July 2024
• Accepted 5 August 2024

DOI: https://doi.org/10.1103/PRXQuantum.5.030348

Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.

Published by the American Physical Society

Physics Subject Headings (PhySH)

• Research Areas

Authors & Affiliations

• Phasecraft Ltd. , Bristol, United Kingdom
• * Contact author: [email protected]
• † Also at University College London.
• ‡ Also at University of Bristol.

Popular Summary

Combinatorial optimization—optimizing a function over a discrete domain—is considered a promising application of quantum computers. The quantum approximate optimization algorithm (QAOA) is the best-known near-term quantum algorithm for this task. The algorithm nonetheless poses several challenges. On the theoretical side, the techniques for predicting the algorithm's performance remain limited. On the practical side, QAOA depends on a set of hyperparameters to be tuned; this task could potentially be a difficult optimization problem of its own.

In this work, we address these issues for a specific combinatorial optimization problem: k -SAT, one of the most fundamental and well-studied problems in computer science. When applying QAOA to this constraint satisfaction problem, we aim at producing an exact solution (satisfying all constraints) rather than maximizing the quality of the solution, as is usually done in the literature. Also, we use common QAOA hyperparameters for all k -SAT instances rather than training them on an instance-by-instance basis. In this setting, we develop analytic methods to estimate the probability of QAOA outputting an exact solution to k -SAT as the instance size goes to infinity. These results are validated and complemented by a set of numerical experiments, pointing to a potential advantage of QAOA over best-known classical algorithms for k -SAT.

A natural next step in this line of research is to determine the ultimate extent of the acceleration over classical algorithms and to shed light on the problem structures QAOA leverages to achieve speedup.

Article Text

Vol. 5, Iss. 3 — September - November 2024

Authorization Required

Other options.

• Buy Article »
• Find an Institution with the Article »

Download & Share

Comparison of numerical results to limiting theoretical predictions. Top: points are empirical averages. Solid lines are fits to empirical averages, dashed lines are scaling predicted by theory (assuming unknown constant factor is 1). Error bars are too small to be seen. Bottom: points are relative differences in excess scaling exponents between numerical and theoretical results, solid lines are added to guide the eye. (a) k = 8 , varying p ; (b) p = 1 , varying k .

Scaling behavior of QAOA on random k -SAT. Top: analytic scaling exponents c in terms of p , such that success probability is predicted to be 2 − c n up to lower-order terms. Fit to a power law for each k . Fits are c ≈ 0.13 p − 1.12 ( k = 2 ), c ≈ 0.57 p − 0.51 ( k = 4 ), c ≈ 0.69 p − 0.32 ( k = 8 ). Bottom: median running time (solid line) compared with running time estimated from average success probability for random 8-SAT instances (dashed line). Lines are linear fits. Error bars are too small to be seen.

Scaling behavior of median running times of selected classical and quantum algorithms for 8-SAT. WalkSAT QAOA uses p = 60 .

Running times of QAOA compared with WalkSATlm for random 8-SAT. Top: scaling exponent α in running time approximately 2 α n for QAOA estimated by inverting analytic ( p ≤ 10 ) and numerical ( p ≤ 60 ) results on average probabilities, and from numerical results on median running times for n ∈ { 12 , … , 20 } . Horizontal line is experimentally estimated WalkSATlm median running time scaling exponent. Other lines are fits. Blue dashed line is fitting based on all p , blue solid line is using p ≤ 10 . Error bars are too small to be seen. Bottom: histogram of ratios of running times of QAOA ( p = 60 ) and WalkSAT for n = 20 instances.

QAOA optimization landscape at p = 1 and for k = 2 . By periodicity (following from the integrality of the cost function), β and γ can be, respectively, restricted to [ − π , π ] and [ − 2 π , 2 π ] . In case the represented function is negligible except on a small part of this domain, we choose to enlarge the rectangle while keeping centered at 0 ; for instance, when enlarging by a factor of 2 , the represented domain is [ − ( π / 2 ) , ( π / 2 ) ] × [ π , π ] . The central symmetry is a general feature of QAOA, applying to all cost functions and diagonal unitaries. (a) Logarithmic success probability. (b) Exponential fit. (c) Correlation coefficient.

QAOA optimization landscape at p = 1 and for k = 4 (enlargement: 2 × ). (a) Logarithmic success probability. (b) Exponential fit. (c) Correlation coefficient.

QAOA optimization landscape at p = 1 and for k = 8 (enlargement: 2 × ). (a) Logarithmic success probability. (b) Exponential fit. (c) Correlation coefficient.

QAOA optimization landscape at p = 1 and for k = 16 (enlargement: 4 × ). (a) Logarithmic success probability. (b) Exponential fit. (c) Correlation coefficient.

Relative variation of scaling exponent and optimized angles after reoptimization from analytic method. The relative error for the exponent is defined as the ratio between the new and old value, minus 1. For angles, the distance between the old angles ( β (i) , γ (i) ) and the new ones ( β (f) , γ (f) ) is calculated by considering the representative of ( β (f) , γ (f) ) closest to the ( β (i) , γ (i) ) in order to account for 2 π periodicity in the β j and 4 π periodicity in the γ j . The β components of the difference vector ( β (f) − β (i) , γ (f) − γ (i) ) are then rescaled by ( 1 / ( π 2 p ) ) , and the γ components by ( 1 / ( 2 π 2 p ) ) , mapping the 2 -norm of the resulting vector into [ 0 , 1 ] . (a) Exponent. (b) Angles.

Sign up to receive regular email alerts from PRX Quantum

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 4.0 International license. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

• Forgot your username/password?
• Create an account

Article Lookup

Paste a citation or doi, enter a citation.

This week: the arXiv Accessibility Forum

Help | Advanced Search

Computer Science > Machine Learning

Title: forward kl regularized preference optimization for aligning diffusion policies.

Abstract: Diffusion models have achieved remarkable success in sequential decision-making by leveraging the highly expressive model capabilities in policy learning. A central problem for learning diffusion policies is to align the policy output with human intents in various tasks. To achieve this, previous methods conduct return-conditioned policy generation or Reinforcement Learning (RL)-based policy optimization, while they both rely on pre-defined reward functions. In this work, we propose a novel framework, Forward KL regularized Preference optimization for aligning Diffusion policies, to align the diffusion policy with preferences directly. We first train a diffusion policy from the offline dataset without considering the preference, and then align the policy to the preference data via direct preference optimization. During the alignment phase, we formulate direct preference learning in a diffusion policy, where the forward KL regularization is employed in preference optimization to avoid generating out-of-distribution actions. We conduct extensive experiments for MetaWorld manipulation and D4RL tasks. The results show our method exhibits superior alignment with preferences and outperforms previous state-of-the-art algorithms.

Submission history

Access paper:.

• HTML (experimental)
• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

BibTeX formatted citation

Bibliographic and Citation Tools

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

• Institution

arXivLabs: experimental projects with community collaborators

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

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

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