linear programming assignment problem

• School Guide
• Mathematics
• Number System and Arithmetic
• Trigonometry
• Probability
• Mensuration
• Maths Formulas
• Integration Formulas
• Differentiation Formulas
• Trigonometry Formulas
• Algebra Formulas
• Mensuration Formula
• Statistics Formulas
• Trigonometric Table

Linear Programming

Linear programming is a mathematical concept that is used to find the optimal solution of the linear function. This method uses simple assumptions for optimizing the given function. Linear Programming has a huge real-world application and it is used to solve various types of problems.

The term “linear programming” consists of two words linear and programming, the word linear tells the relation between various types of variables of degree one used in a problem and the word programming tells us the step-by-step procedure to solve these problems.

In this article, we will learn about linear programming, its examples, formulas, and other concepts in detail.

Table of Content

What is Linear Programming? 

Components of linear programming, linear programming examples, linear programming problems, types of linear programming problems, linear programming formula, how to solve linear programming problems, linear programming methods, linear programming simplex method, linear programming graphical method, linear programming applications, importance of linear programming, up-to-date applications of linear programming, linear programming in operations research, simplex method.

Linear programming or Linear optimization is a technique that helps us to find the optimum solution for a given problem, an optimum solution is a solution that is the best possible outcome of a given particular problem.

In simple terms, it is the method to find out how to do something in the best possible way. With limited resources, you need to do the optimum utilization of resources and achieve the best possible result in a particular objective such as least cost, highest margin, or least time. 

The situation that requires a search for the best values of the variables subject to certain constraints is where we use linear programming problems. These situations cannot be handled by the usual calculus and numerical techniques.

Linear Programming Definition

Linear programming is the technique used for optimizing a particular scenario. Using linear programming provides us with the best possible outcome in a given situation. It uses all the available resources in a manner such that they produce the optimum result.

The basic components of a linear programming(LP) problem are:

• Decision Variables: Variables you want to determine to achieve the optimal solution.
• Objective Function: M athematical equation that represents the goal you want to achieve
• Constraints: Limitations or restrictions that your decision variables must follow.
• Non-Negativity Restrictions: In some real-world scenarios, decision variables cannot be negative

Additional Characteristics of Linear Programming

• Finiteness: The number of decision variables and constraints in an LP problem are finite.
• Linearity: The objective function and all constraints must be linear functions of the decision variables . It means the degree of variables should be one.

We can understand the situations in which Linear programming is applied with the help of the example discussed below,

Suppose a delivery man has to deliver 8 packets in a day to the different locations of a city. He has to pick all the packets from A and has to deliver them to points P, Q, R, S, T, U, V, and W. The distance between them is indicated using the lines as shown in the image below. The shortest path followed by the delivery man is calculated using the concept of Linear Programming.

Linear Programming Problems (LPP) involve optimizing a linear function to find the optimal value solution for the function. The optimal value can be either the maximum value or the minimum value.

In LPP, the linear functions are called objective functions. An objective function can have multiple variables, which are subjected to conditions and have to satisfy the linear constraints .

There are many different linear programming problems(LPP) but we will deal with three major linear programming problems in this article.

Manufacturing Problems

Manufacturing problems are a problem that deals with the number of units that should be produced or sold to maximize profits when each product requires fixed manpower, machine hours, and raw materials.

Diet Problems

It is used to calculate the number of different kinds of constituents to be included in the diet to get the minimum cost, subject to the availability of food and their prices.

Transportation Problems

It is used to determine the transportation schedule to find the cheapest way of transporting a product from plants /factories situated at different locations to different markets.

A linear programming problem consists of,

• Decision variables
• Objective function
• Constraints
• Non-Negative restrictions

Decision variables are the variables x, and y, which decide the output of the linear programming problem and represent the final solution. 

The objective function , generally represented by Z, is the linear function that needs to be optimized according to the given condition to get the final solution. 

The restrictions imposed on decision variables that limit their values are called constraints.

Now, the general formula of a linear programming problem is,

Objective Function : Z = ax + by

Constraints: cx + dy ≥ e, px + qy ≤ r

Non-Negative restrictions: x ≥ 0, y ≥ 0

In the above condition x, and y are the decision variables.

Before solving the linear programming problems first we have to formulate the problems according to the standard parameters. The steps for solving linear programming problems are,

Step 1: Mark the decision variables in the problem. Step 2: Build the objective function of the problem and check if the function needs to be minimized or maximized. Step 3: Write down all the constraints of the linear problems. Step 4: Ensure non-negative restrictions of the decision variables. Step 5: Now solve the linear programming problem using any method generally we use either the simplex or graphical method.

We use various methods for solving linear programming problems. The two most common methods used are,

• Graphical Method

Let’s learn about these two methods in detail in this article,

One of the most common methods to solve the linear programming problem is the simplex method. In this method, we repeat a specific condition ‘n’ a number of times until an optimum solution is achieved.

The steps required to solve linear programming problems using the simplex method are,

Step 1: Formulate the linear programming problems based on the given constraints. Step 2: Convert all the given inequalities to equations or equalities of the linear programming problems by adding the slack variable to each inequality where ever required. Step 3: Construct the initial simplex table. By representing each constraint equation in a row and writing the objective function at the bottom row. The table so obtained is called the Simplex table. Step 4: Identify the greatest negative entry in the bottom row the column of the element with the highest negative entry is called the pivot column Step 5: Divide the entries of the right-most column with the entries of the respective pivot column, excluding the entries of the bottommost row. Now the row containing the least entry is called the pivot row. The pivot element is obtained by the intersection of the pivot row and the pivot column. Step 6: Using matrix operation and with the help of the pivot element make all the entries in the pivot column to be zero. Step 7: Check for the non-negative entries in the bottommost row if there are no negative entries in the bottom row, end the process else start the process again from step 4. Step 8: The final simplex table so obtained gives the solution to our problem.

Graphical Method is another method than the Simplex method which is used to solve linear programming problems. As the name suggests this method uses graphs to solve the given linear programming problems. This is the best method to solve linear programming problems and requires less effort than the simplex method. 

While using this method we plot all the inequalities that are subjected to constraints in the given linear programming problems. As soon as all the inequalities of the given LPP are plotted in the XY graph the common region of all the inequalities gives the optimum solution. All the corner points of the feasible region are calculated and the value of the objective function at all those points is calculated then comparing these values we get the optimum solution of the LPP.

Example: Find the maximal and minimal value of z = 6x + 9y when the constraint conditions are,

• 2x + 3y ≤ 12
• x and y ≥ 0

Step 1 : First convert the inequations into normal equations. Hence the equations will be 2x+3y = 0, x = 0, y = 0 and x + y = 5. Step 2 : Find the points at which 2x + 3y and x + y = 5 cut the x-axis and y-axis. To find the point of intersection of the x-axis put y = 0 in the respective equation and find the point. Similarly for y-axis intersection points put x = 0 in the respective equation. Step 3 : Draw the two lines cutting the x-axis and y-axis. We find that the two axes cut each other at (3,2). Step 4 : For x ≥ 0 and y ≥ 0, we find that both inequations are followed. Hence the region will include an area region enclosed by two axes and both lines including the origin. The plotted region is shown below in the figure. Step 5 : Find Z for each point and maxima and minima. Coordinates Z = 6x + 9y (0,5) Z = 45 (0,4) Z = 36 (5,0) Z = 30 (6,0) Z = 36 (3,2) Z = 36 Hence, we find that Z = 6x + 9y is maximum at (0,5) and minimum at (5,0).

Linear Programming has applications in various fields. It is used to find the minimum cost of a process when all the constraints of the problems are given. It is used to optimize the transportation cost of the vehicle, etc. Various applications of Linear Programming are

Engineering Industries

Engineering Industries use linear programming to solve design and manufacturing problems and to get the maximum output from a given condition.

Manufacturing Industries

Manufacturing Industries use linear programming to maximize the profit of the companies and to reduce the manufacturing cost.

Energy Industries

Energy companies use linear programming to optimize their production output.

Transportation Industries

Linear programming is also used in transportation industries to find the path to minimize the cost of transportation.

Linear Programming has huge importance in various industries it maximizes the output value while minimizing the input values according to various constraints.

LP is highly applicable when we have multiple conditions while solving a problem and we have to optimize the output of the problem i.e. either we have to find the minimum or the maximum value according to a given condition.

Linear Inequalities Algebraic Solution of Linear Inequalities

Problem 1: A company manufactures and sells two types of products and the cost of production of each unit a and b is rupees 200 and 150 respectively each unit of product yields a profit of 20 rupees and each unit of product b yields a profit of 15 rupees on selling. The company estimates the monthly demand of A and B to be at a maximum of the harvested unit in all the production budget for the month is set at rupees 50000. How many units should the company manufacture to earn maximum profit from its monthly sales from a and b?

Let x = number of units of type A y = Number of units of type B Maximize Z = 40x + 50y Subject to the constraints 3x + y ≤ 9 x + 2y ≤ 8 and x, y ≥ 0 Consider the equation, 3x + y = 9 x = 3 y = 0 and x + 2y = 8 x = 8 y = 0 Now, we can determine the maximum value of Z by evaluating the value of Z at the four points (vertices) is shown below Vertices Z = 40x + 50y (0, 0) Z = 40 × 0 + 50 × 0 = Rs. 0 (3, 0) Z = 40 × 3 + 50 × 0 = Rs. 120 (0, 4)  Z = 40 × 0 + 50 × 4 = Rs. 200 (2, 3) Z = 40 × 2 + 50 × 3 = Rs. 230 Maximum profit, Z = Rs. 230 ∴ Number of units of type A is 2 and the number of units of type B is 3.

Problem 2: Maximize Z = 3x + 4y.

Subject to constraints , x + y ≤ 450, 2x + y ≤ 600 and x, y ≤ 0.

We have from the given Constraints (1) X + Y = 450 Putting x = 0, ⇒ 0 + y = 450 ⇒ y = 450 Putting y = 0, ⇒ x + 0 = 450 ⇒ x = 450 From, Constraints (2) 2x + y = 600 Putting x = 0, ⇒ 0 + y = 600 ⇒ y = 600 Putting  y = 0, ⇒ 2x + 0 = 600 ⇒ x = 300 Now, we have the points co-ordinate Z = 3x + 4y

Therefore, the optimal solution maximum Z = 1800 at co-ordinate x = 0 and y = 450. The graph is given below.

Linear programming, a powerful mathematical technique, is used to solve optimization problems in various industries. Here are some modern applications:

• Supply Chain Optimization : Linear programming helps companies minimize costs and maximize efficiency in their supply chains. It’s used for determining the most cost-effective transportation routes, warehouse operations, and inventory management strategies.
• Energy Management : In the energy sector, linear programming is utilized to optimize the mix of energy production methods. This includes balancing traditional energy sources with renewable ones to reduce costs and environmental impact while meeting demand.
• Telecommunications Network Design : Linear programming aids in designing efficient telecommunications networks. It helps in allocating bandwidth, designing network layouts, and optimizing the flow of data to ensure high-speed communication at lower costs.
• Financial Planning : Businesses and financial analysts use linear programming for portfolio optimization, risk management, and capital budgeting. It helps in making investment decisions that maximize returns while minimizing risk.
• Healthcare Logistics : In healthcare, linear programming is applied to optimize the allocation of resources, such as hospital beds, medical staff, and equipment. It’s crucial for improving patient care, reducing wait times, and managing costs effectively.
• Manufacturing Process Optimization : Linear programming is used to determine the optimal production levels for multiple products within a manufacturing facility, considering constraints like labor, materials, and machine availability.
• Agricultural Planning : Farmers and agricultural planners use linear programming to decide on crop selection, land use, and resource allocation to maximize yields and profits while conserving resources.
• Airline Crew Scheduling : Airlines employ linear programming to schedule crews efficiently, ensuring that flights are staffed in compliance with regulations and minimizing operational costs.

These applications demonstrate the versatility and power of linear programming in solving complex optimization problems across various sectors, showcasing its relevance in today’s data-driven world.

• Core Tool : Linear programming is a foundational tool in operations research for optimizing resources.
• Decision Making : Helps in making the best decisions regarding resource allocation, maximizing profits, or minimizing costs.
• Wide Applications : Used in various fields such as logistics, manufacturing, finance, and healthcare for solving complex problems.
• Modeling Real-World Problems : Transforms real-world problems into mathematical models to find the most efficient solutions.
• Optimization Algorithm : The Simplex Method is a powerful algorithm used in linear programming to find the optimal solution to linear inequalities.
• Step-by-Step Approach : It iteratively moves towards the best solution by navigating the edges of the feasible region defined by constraints.
• Efficiency : Known for its efficiency in solving large-scale linear programming problems.
• Versatility : Applicable in various domains like diet planning, network flows, production scheduling, and more, showcasing its versatility.

Practice Problems on Linear Programming

Problem 1: Maximize Z=3x+4y subject to the constraints:

• [Tex]x+2\leq 8[/Tex]
• [Tex]3x+y\leq 9[/Tex]
• [Tex]x \geq 0[/Tex]
• [Tex]y \geq 0[/Tex]

Problem 2: Minimize Z=5x+2y subject to the constraints:

• [Tex]2x + y \geq 10[/Tex]
• [Tex]x + 3y \geq 15[/Tex]

Problem 3: A factory produces two products, P1 and P2. The profit for P1 is $40 and for P2 is $30. Each product requires processing in two departments. The processing times in hours per unit for each department are given below:

The available hours for Department A are 100 and for Department B are 80. Formulate the linear programming problem to maximize the profit.

Problem 4: Minimize the cost of a diet containing at least 60 units of protein and 70 units of carbohydrates. Two food items, A and B, provide the following nutrients per unit:

The cost per unit of food A is $2 and food B is $3. Formulate the linear programming problem to minimize the cost.

Problem 5: A company needs to transport goods from two warehouses to three retail stores. The supply at Warehouse 1 is 70 units, and at Warehouse 2 is 80 units. The demand at Store 1 is 40 units, at Store 2 is 50 units, and at Store 3 is 60 units. The transportation costs per unit are given below:

Formulate the linear programming problem to minimize the transportation cost.

Problem 6: Maximize the return on an investment portfolio consisting of two investments, A and B. Investment A has a return of 5% and investment B has a return of 7%. The total investment is $100,000, with at least $30,000 in investment A and no more than $60,000 in investment B. Formulate the linear programming problem.

Problem 7: A company needs to schedule workers for a week with the following constraints: At least 3 workers on Monday, 2 on Tuesday, 4 on Wednesday, 3 on Thursday, and 5 on Friday. Each worker can work at most 3 days a week. Formulate the linear programming problem to minimize the number of workers needed.

Problem 8: A company produces a blend of two chemicals, A and B. The blend must contain at least 30% of A and at least 40% of B. Chemical A costs $10 per unit and chemical B costs $15 per unit. The company needs to produce 100 units of the blend. Formulate the linear programming problem to minimize the cost.

Problem 9: Assign 4 workers to 4 jobs with the following costs:

Formulate the linear programming problem to minimize the total cost.

Problem 10: An investor wants to maximize the return from a portfolio consisting of three investments: X, Y, and Z. The returns are 6%, 8%, and 10%, respectively. The total investment is $200,000, with at least $50,000 in each investment and at least as much in X as in Y. Formulate the linear programming problem.

Linear Programming – FAQs

What is linear programming.

Linear programming is a mathematical concept which is used to optimize a given linear problem which has a variety of constraints. Using linear programming we the optimum output of the given problem

What are Linear Programming Problems?

Linear Programming Problems (LPP) are the problems which give the optimum solution to the given conditions.

What is Linear Programming Formula?

General Linear Programming Formulas are, Objective Function: Z = ax + by Constraints: px + qy ≤ r, sx + ty ≤ u Non-Negative Restrictions: x ≥ 0, y ≥ 0

What are the different types of Linear Programming?

Different types of linear programming methods are, Linear Programming by Simplex Method Linear Programming by R Method Linear Programming by Graphical Method

What are requirements of Linear Programming?

Various requirements of linear programming problems are, Linearity Objective Function Constraints Non-negativity

What are the advantages of Linear Programming?

Various advantages of linear programming are, It provides the optimal solution to any given linear problem. It is easy to use and always gives consistent results It helps to maximize profits and to reduce the input cost.

Please Login to comment...

Similar reads.

• School Learning
• Technical Scripter
• Math-Concepts
• Maths-Class-12
• Technical Scripter 2020
• Top Android Apps for 2024
• Top Cell Phone Signal Boosters in 2024
• Best Travel Apps (Paid & Free) in 2024
• The Best Smart Home Devices for 2024
• 15 Most Important Aptitude Topics For Placements [2024]

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Quantitative Techniques: Theory and Problems by P. C. Tulsian, Vishal Pandey

Get full access to Quantitative Techniques: Theory and Problems 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.

WHAT IS ASSIGNMENT PROBLEM

Assignment Problem is a special type of linear programming problem where the objective is to minimise the cost or time of completing a number of jobs by a number of persons.

The assignment problem in the general form can be stated as follows:

“Given n facilities, n jobs and the effectiveness of each facility for each job, the problem is to assign each facility to one and only one job in such a way that the measure of effectiveness is optimised (Maximised or Minimised).”

Several problems of management has a structure identical with the assignment problem.

Example I A manager has four persons (i.e. facilities) available for four separate jobs (i.e. jobs) and the cost of assigning (i.e. effectiveness) each job to each ...

Get Quantitative Techniques: Theory and Problems 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.

Your Article Library

Assignment problem in linear programming : introduction and assignment model.

ADVERTISEMENTS:

Assignment problem is a special type of linear programming problem which deals with the allocation of the various resources to the various activities on one to one basis. It does it in such a way that the cost or time involved in the process is minimum and profit or sale is maximum. Though there problems can be solved by simplex method or by transportation method but assignment model gives a simpler approach for these problems.

In a factory, a supervisor may have six workers available and six jobs to fire. He will have to take decision regarding which job should be given to which worker. Problem forms one to one basis. This is an assignment problem.

1. Assignment Model :

Suppose there are n facilitates and n jobs it is clear that in this case, there will be n assignments. Each facility or say worker can perform each job, one at a time. But there should be certain procedure by which assignment should be made so that the profit is maximized or the cost or time is minimized.

In the table, Co ij is defined as the cost when j th job is assigned to i th worker. It maybe noted here that this is a special case of transportation problem when the number of rows is equal to number of columns.

Mathematical Formulation:

Any basic feasible solution of an Assignment problem consists (2n – 1) variables of which the (n – 1) variables are zero, n is number of jobs or number of facilities. Due to this high degeneracy, if we solve the problem by usual transportation method, it will be a complex and time consuming work. Thus a separate technique is derived for it. Before going to the absolute method it is very important to formulate the problem.

Suppose x jj is a variable which is defined as

1 if the i th job is assigned to j th machine or facility

0 if the i th job is not assigned to j th machine or facility.

Now as the problem forms one to one basis or one job is to be assigned to one facility or machine.

The total assignment cost will be given by

The above definition can be developed into mathematical model as follows:

Determine x ij > 0 (i, j = 1,2, 3…n) in order to

Subjected to constraints

and x ij is either zero or one.

Method to solve Problem (Hungarian Technique):

Consider the objective function of minimization type. Following steps are involved in solving this Assignment problem,

1. Locate the smallest cost element in each row of the given cost table starting with the first row. Now, this smallest element is subtracted form each element of that row. So, we will be getting at least one zero in each row of this new table.

2. Having constructed the table (as by step-1) take the columns of the table. Starting from first column locate the smallest cost element in each column. Now subtract this smallest element from each element of that column. Having performed the step 1 and step 2, we will be getting at least one zero in each column in the reduced cost table.

3. Now, the assignments are made for the reduced table in following manner.

(i) Rows are examined successively, until the row with exactly single (one) zero is found. Assignment is made to this single zero by putting square □ around it and in the corresponding column, all other zeros are crossed out (x) because these will not be used to make any other assignment in this column. Step is conducted for each row.

(ii) Step 3 (i) in now performed on the columns as follow:- columns are examined successively till a column with exactly one zero is found. Now , assignment is made to this single zero by putting the square around it and at the same time, all other zeros in the corresponding rows are crossed out (x) step is conducted for each column.

(iii) Step 3, (i) and 3 (ii) are repeated till all the zeros are either marked or crossed out. Now, if the number of marked zeros or the assignments made are equal to number of rows or columns, optimum solution has been achieved. There will be exactly single assignment in each or columns without any assignment. In this case, we will go to step 4.

4. At this stage, draw the minimum number of lines (horizontal and vertical) necessary to cover all zeros in the matrix obtained in step 3, Following procedure is adopted:

(iii) Now tick mark all the rows that are not already marked and that have assignment in the marked columns.

(iv) All the steps i.e. (4(i), 4(ii), 4(iii) are repeated until no more rows or columns can be marked.

(v) Now draw straight lines which pass through all the un marked rows and marked columns. It can also be noticed that in an n x n matrix, always less than ‘n’ lines will cover all the zeros if there is no solution among them.

5. In step 4, if the number of lines drawn are equal to n or the number of rows, then it is the optimum solution if not, then go to step 6.

6. Select the smallest element among all the uncovered elements. Now, this element is subtracted from all the uncovered elements and added to the element which lies at the intersection of two lines. This is the matrix for fresh assignments.

7. Repeat the procedure from step (3) until the number of assignments becomes equal to the number of rows or number of columns.

Related Articles:

• Two Phase Methods of Problem Solving in Linear Programming: First and Second Phase
• Linear Programming: Applications, Definitions and Problems

No comments yet.

Leave a reply click here to cancel reply..

You must be logged in to post a comment.

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

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.

Difference between solving Assignment Problem using the Hungarian Method vs. LP

When trying to solve for assignments given a cost matrix, what is the difference between

using Scipy's linear_sum_assignment function (which I think uses the Hungarian method)

describing the LP problem using a objective function with many boolean variables, add in the appropriate constraints and send it to a solver, such as through scipy.optimize.linprog ?

Is the later method slower than Hungarian method's O(N^3) but allows for more constraints to be added?

• linear-programming
• combinatorial-optimization
• assignment-problem

• $\begingroup$ The main difference between a mathematical model and a heuristic algorithm to solve a specific problem is more likely to prove optimality rather feasibility. Now, one can decide which one to be selected in order to satisfy needs. $\endgroup$ –  A.Omidi Commented Mar 20, 2022 at 7:54
• 4 $\begingroup$ @A.Omidi the Hungarian method is an exact algorithm $\endgroup$ –  fontanf Commented Mar 20, 2022 at 8:26
• $\begingroup$ @fontanf, you are right. What I said was to compare the exact and heuristic methods and it is not specific to Hungarian alg. Thanks for your hint. $\endgroup$ –  A.Omidi Commented Mar 20, 2022 at 10:32

The main differences probably are that there is a somewhat large overhead you have to pay when solving the AP as a linear program: You have to build an LP model and ship it to a solver. In addition, an LP solver is a generalist. It solves all LP problems and focus in development is to be fast on average on all LPs and also to be fast-ish in the pathological cases.

When using the Hungarian method, you do not build a model, you just pass the cost matrix to a tailored algorithm. You will then use an algorithm developed for that specific problem to solve it. Hence, it will most likely solve it faster since it is a specialist.

So if you want to solve an AP you should probably use the tailored algorithm. If you plan on extending your model to handle other more general constraints as well, you might need the LP after all.

Edit: From a simple test in Python, my assumption is confirmed in this specific setup (which is to the advantage of the Hungarian method, I believe). The set up is as follows:

• A size is chosen in $n\in \{5,10,\dots,500\}$
• A cost matrix is generated. Each coefficient $c_{ij}$ is generated as a uniformly distributed integer in the range $[250,999]$ .
• The instance is solved using both linear_sum_assignment and as a linear program. The solution time is measured as wall clock time and only the time spent by linear_sum_assignment and the solve function is timed (not building the LP and not not generating the instance)

For each size, I have generated and solved ten instances, and I report the average time only.

And then there is of course the "but". I am not a ninja in Python and I have used pyomo for modelling the LPs. I believe that pyomo is known to be slow-ish whenbuilding models, hence I have only timed the solver.solve(model) part of the code - not building the model. There is however possibly a hugh overhead cost coming from pyomo translating the model to "gurobian" (I use gurobi as solver).

• 1 $\begingroup$ Do you have some benchmark results to support this claim? Intuitively, I would have thought that the Hungarian method would be much slower in practice $\endgroup$ –  fontanf Commented Mar 20, 2022 at 7:39
• $\begingroup$ @fontanf I only have anecdotal proof from past experiments. Maybe an LP solver can work faster for repeated solves, where you exploit that the model is already build and basis info is available. But I honestly don't know. $\endgroup$ –  Sune Commented Mar 20, 2022 at 9:37
• 1 $\begingroup$ It might be the case that the Hungarian method is faster for small problems (due to the overhead Sune mentioned for setting up an LP model) while simplex (or dual simplex, or maybe barrier) might be faster for large models because the setup cost is "amortized" better. (I'm just speculating here.) $\endgroup$ –  prubin ♦ Commented Mar 20, 2022 at 15:30
• 2 $\begingroup$ The Hungarian algorithm is, of course, O(n^3) for fully dense assignment problems. I don't know if there is a simplex bound explicitly for assignments. Simplex is exponential in the worst case and linear in variables plus constraints (n^2 + 2n here) in practice. But assignments are highly degenerate (n positive basics out of 2n rows). Dual simplex may fare better than primal. Hungarian is all integer for integer costs, whereas a standard simplex code won't be unless it knows to detect that in preprocessing. That may lead to some overhead for linear algebra. Ha, an idea for a class project! $\endgroup$ –  mjsaltzman Commented Mar 20, 2022 at 17:04
• 2 $\begingroup$ Just for the sake of completeness, here 's the same with gurobipy instead of Pyomo. On my machine, all LPs (n = 500) are solved in less than a second compared to roughly 4 seconds with Pyomo. $\endgroup$ –  joni Commented Mar 21, 2022 at 16:21

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

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

Hot Network Questions

• What's "the archetypal book" called?
• Confusion about time dilation
• Long and protected macros in LaTeX3
• How do you tip cash when you don't have proper denomination or no cash at all?
• Light switch that is flush or recessed (next to fridge door)
• Why doesn’t dust interfere with the adhesion of geckos’ feet?
• Did Babylon 4 actually do anything in the first shadow war?
• How can I play MechWarrior 2?
• Has any astronomer ever observed that after a specific star going supernova it became a Black Hole?
• How do I apologize to a lecturer who told me not to ever call him again?
• Is response variable/dependent variable data required for simr simulation?
• Quantum Gravity is non-renormalizable...So what?
• Sylvester primes
• Would an LEO asking for a race constitute entrapment?
• Why is there so much salt in cheese?
• Fusion September 2024: Where are we with respect to "engineering break even"?
• Why is a USB memory stick getting hotter when connected to USB-3 (compared to USB-2)?
• Clarification Regarding a Possible Typo in David J. Griffiths' Introduction to Electrodynamics
• Short story about humanoid creatures living on ice, which can swim under the ice and eat the moss/plants that grow on the underside of the ice
• In Lord Rosse's 1845 drawing of M51, was the galaxy depicted in white or black?
• Does a party have to wait 1d4 hours to start a Short Rest if no healing is available and an ally is only stabilized?
• How can I prevent solid mix-ins from sinking or floating in my sous vide egg bites
• Why is notation in logic so different from algebra?
• How to change upward facing track lights 26 feet above living room?

Hands-On Linear Programming: Optimization With Python

Table of Contents

What Is Linear Programming?

What is mixed-integer linear programming, why is linear programming important, linear programming with python, small linear programming problem, infeasible linear programming problem, unbounded linear programming problem, resource allocation problem, installing scipy and pulp, using scipy, linear programming resources, linear programming solvers.

Linear programming is a set of techniques used in mathematical programming , sometimes called mathematical optimization, to solve systems of linear equations and inequalities while maximizing or minimizing some linear function . It’s important in fields like scientific computing, economics, technical sciences, manufacturing, transportation, military, management, energy, and so on.

The Python ecosystem offers several comprehensive and powerful tools for linear programming. You can choose between simple and complex tools as well as between free and commercial ones. It all depends on your needs.

In this tutorial, you’ll learn:

• What linear programming is and why it’s important
• Which Python tools are suitable for linear programming
• How to build a linear programming model in Python
• How to solve a linear programming problem with Python

You’ll first learn about the fundamentals of linear programming. Then you’ll explore how to implement linear programming techniques in Python. Finally, you’ll look at resources and libraries to help further your linear programming journey.

Free Bonus: 5 Thoughts On Python Mastery , a free course for Python developers that shows you the roadmap and the mindset you’ll need to take your Python skills to the next level.

Linear Programming Explanation

In this section, you’ll learn the basics of linear programming and a related discipline, mixed-integer linear programming. In the next section , you’ll see some practical linear programming examples. Later, you’ll solve linear programming and mixed-integer linear programming problems with Python.

Imagine that you have a system of linear equations and inequalities. Such systems often have many possible solutions. Linear programming is a set of mathematical and computational tools that allows you to find a particular solution to this system that corresponds to the maximum or minimum of some other linear function.

Mixed-integer linear programming is an extension of linear programming. It handles problems in which at least one variable takes a discrete integer rather than a continuous value . Although mixed-integer problems look similar to continuous variable problems at first sight, they offer significant advantages in terms of flexibility and precision.

Integer variables are important for properly representing quantities naturally expressed with integers, like the number of airplanes produced or the number of customers served.

A particularly important kind of integer variable is the binary variable . It can take only the values zero or one and is useful in making yes-or-no decisions, such as whether a plant should be built or if a machine should be turned on or off. You can also use them to mimic logical constraints.

Linear programming is a fundamental optimization technique that’s been used for decades in science- and math-intensive fields. It’s precise, relatively fast, and suitable for a range of practical applications.

Mixed-integer linear programming allows you to overcome many of the limitations of linear programming. You can approximate non-linear functions with piecewise linear functions , use semi-continuous variables , model logical constraints, and more. It’s a computationally intensive tool, but the advances in computer hardware and software make it more applicable every day.

Often, when people try to formulate and solve an optimization problem, the first question is whether they can apply linear programming or mixed-integer linear programming.

Some use cases of linear programming and mixed-integer linear programming are illustrated in the following articles:

• Gurobi Optimization Case Studies
• Five Areas of Application for Linear Programming Techniques

The importance of linear programming, and especially mixed-integer linear programming, has increased over time as computers have gotten more capable, algorithms have improved, and more user-friendly software solutions have become available.

The basic method for solving linear programming problems is called the simplex method , which has several variants. Another popular approach is the interior-point method .

Mixed-integer linear programming problems are solved with more complex and computationally intensive methods like the branch-and-bound method , which uses linear programming under the hood. Some variants of this method are the branch-and-cut method , which involves the use of cutting planes , and the branch-and-price method .

There are several suitable and well-known Python tools for linear programming and mixed-integer linear programming. Some of them are open source, while others are proprietary. Whether you need a free or paid tool depends on the size and complexity of your problem as well as on the need for speed and flexibility.

It’s worth mentioning that almost all widely used linear programming and mixed-integer linear programming libraries are native to and written in Fortran or C or C++. This is because linear programming requires computationally intensive work with (often large) matrices. Such libraries are called solvers . The Python tools are just wrappers around the solvers.

Python is suitable for building wrappers around native libraries because it works well with C/C++. You’re not going to need any C/C++ (or Fortran) for this tutorial, but if you want to learn more about this cool feature, then check out the following resources:

• Building a Python C Extension Module
• CPython Internals
• Extending Python with C or C++

Basically, when you define and solve a model, you use Python functions or methods to call a low-level library that does the actual optimization job and returns the solution to your Python object.

Several free Python libraries are specialized to interact with linear or mixed-integer linear programming solvers:

• SciPy Optimization and Root Finding

In this tutorial, you’ll use SciPy and PuLP to define and solve linear programming problems.

Linear Programming Examples

In this section, you’ll see two examples of linear programming problems:

• A small problem that illustrates what linear programming is
• A practical problem related to resource allocation that illustrates linear programming concepts in a real-world scenario

You’ll use Python to solve these two problems in the next section .

Consider the following linear programming problem:

You need to find x and y such that the red, blue, and yellow inequalities, as well as the inequalities x ≥ 0 and y ≥ 0, are satisfied. At the same time, your solution must correspond to the largest possible value of z .

The independent variables you need to find—in this case x and y —are called the decision variables . The function of the decision variables to be maximized or minimized—in this case z —is called the objective function , the cost function , or just the goal . The inequalities you need to satisfy are called the inequality constraints . You can also have equations among the constraints called equality constraints .

This is how you can visualize the problem:

The red line represents the function 2 x + y = 20, and the red area above it shows where the red inequality is not satisfied. Similarly, the blue line is the function −4 x + 5 y = 10, and the blue area is forbidden because it violates the blue inequality. The yellow line is − x + 2 y = −2, and the yellow area below it is where the yellow inequality isn’t valid.

If you disregard the red, blue, and yellow areas, only the gray area remains. Each point of the gray area satisfies all constraints and is a potential solution to the problem. This area is called the feasible region , and its points are feasible solutions . In this case, there’s an infinite number of feasible solutions.

You want to maximize z . The feasible solution that corresponds to maximal z is the optimal solution . If you were trying to minimize the objective function instead, then the optimal solution would correspond to its feasible minimum.

Note that z is linear. You can imagine it as a plane in three-dimensional space. This is why the optimal solution must be on a vertex , or corner, of the feasible region. In this case, the optimal solution is the point where the red and blue lines intersect, as you’ll see later .

Sometimes a whole edge of the feasible region, or even the entire region, can correspond to the same value of z . In that case, you have many optimal solutions.

You’re now ready to expand the problem with the additional equality constraint shown in green:

The equation − x + 5 y = 15, written in green, is new. It’s an equality constraint. You can visualize it by adding a corresponding green line to the previous image:

The solution now must satisfy the green equality, so the feasible region isn’t the entire gray area anymore. It’s the part of the green line passing through the gray area from the intersection point with the blue line to the intersection point with the red line. The latter point is the solution.

If you insert the demand that all values of x must be integers, then you’ll get a mixed-integer linear programming problem, and the set of feasible solutions will change once again:

You no longer have the green line, only the points along the line where the value of x is an integer. The feasible solutions are the green points on the gray background, and the optimal one in this case is nearest to the red line.

These three examples illustrate feasible linear programming problems because they have bounded feasible regions and finite solutions.

A linear programming problem is infeasible if it doesn’t have a solution. This usually happens when no solution can satisfy all constraints at once.

For example, consider what would happen if you added the constraint x + y ≤ −1. Then at least one of the decision variables ( x or y ) would have to be negative. This is in conflict with the given constraints x ≥ 0 and y ≥ 0. Such a system doesn’t have a feasible solution, so it’s called infeasible.

Another example would be adding a second equality constraint parallel to the green line. These two lines wouldn’t have a point in common, so there wouldn’t be a solution that satisfies both constraints.

A linear programming problem is unbounded if its feasible region isn’t bounded and the solution is not finite. This means that at least one of your variables isn’t constrained and can reach to positive or negative infinity, making the objective infinite as well.

For example, say you take the initial problem above and drop the red and yellow constraints. Dropping constraints out of a problem is called relaxing the problem. In such a case, x and y wouldn’t be bounded on the positive side. You’d be able to increase them toward positive infinity, yielding an infinitely large z value.

In the previous sections, you looked at an abstract linear programming problem that wasn’t tied to any real-world application. In this subsection, you’ll find a more concrete and practical optimization problem related to resource allocation in manufacturing.

Say that a factory produces four different products, and that the daily produced amount of the first product is x ₁, the amount produced of the second product is x ₂, and so on. The goal is to determine the profit-maximizing daily production amount for each product, bearing in mind the following conditions:

The profit per unit of product is $20, $12, $40, and $25 for the first, second, third, and fourth product, respectively.

Due to manpower constraints, the total number of units produced per day can’t exceed fifty.

For each unit of the first product, three units of the raw material A are consumed. Each unit of the second product requires two units of the raw material A and one unit of the raw material B. Each unit of the third product needs one unit of A and two units of B. Finally, each unit of the fourth product requires three units of B.

Due to the transportation and storage constraints, the factory can consume up to one hundred units of the raw material A and ninety units of B per day.

The mathematical model can be defined like this:

The objective function (profit) is defined in condition 1. The manpower constraint follows from condition 2. The constraints on the raw materials A and B can be derived from conditions 3 and 4 by summing the raw material requirements for each product.

Finally, the product amounts can’t be negative, so all decision variables must be greater than or equal to zero.

Unlike the previous example, you can’t conveniently visualize this one because it has four decision variables. However, the principles remain the same regardless of the dimensionality of the problem.

Linear Programming Python Implementation

In this tutorial, you’ll use two Python packages to solve the linear programming problem described above:

• SciPy is a general-purpose package for scientific computing with Python.
• PuLP is a Python linear programming API for defining problems and invoking external solvers.

SciPy is straightforward to set up. Once you install it, you’ll have everything you need to start. Its subpackage scipy.optimize can be used for both linear and nonlinear optimization .

PuLP allows you to choose solvers and formulate problems in a more natural way. The default solver used by PuLP is the COIN-OR Branch and Cut Solver (CBC) . It’s connected to the COIN-OR Linear Programming Solver (CLP) for linear relaxations and the COIN-OR Cut Generator Library (CGL) for cuts generation.

Another great open source solver is the GNU Linear Programming Kit (GLPK) . Some well-known and very powerful commercial and proprietary solutions are Gurobi , CPLEX , and XPRESS .

Besides offering flexibility when defining problems and the ability to run various solvers, PuLP is less complicated to use than alternatives like Pyomo or CVXOPT, which require more time and effort to master.

To follow this tutorial, you’ll need to install SciPy and PuLP. The examples below use version 1.4.1 of SciPy and version 2.1 of PuLP.

You can install both using pip :

You might need to run pulptest or sudo pulptest to enable the default solvers for PuLP, especially if you’re using Linux or Mac:

Optionally, you can download, install, and use GLPK. It’s free and open source and works on Windows, MacOS, and Linux. You’ll see how to use GLPK (in addition to CBC) with PuLP later in this tutorial.

On Windows, you can download the archives and run the installation files.

On MacOS, you can use Homebrew :

On Debian and Ubuntu, use apt to install glpk and glpk-utils :

On Fedora, use dnf with glpk-utils :

You might also find conda useful for installing GLPK:

After completing the installation, you can check the version of GLPK:

See GLPK’s tutorials on installing with Windows executables and Linux packages for more information.

In this section, you’ll learn how to use the SciPy optimization and root-finding library for linear programming.

To define and solve optimization problems with SciPy, you need to import scipy.optimize.linprog() :

Now that you have linprog() imported, you can start optimizing.

Let’s first solve the linear programming problem from above:

linprog() solves only minimization (not maximization) problems and doesn’t allow inequality constraints with the greater than or equal to sign (≥). To work around these issues, you need to modify your problem before starting optimization:

• Instead of maximizing z = x + 2 y, you can minimize its negative(− z = − x − 2 y).
• Instead of having the greater than or equal to sign, you can multiply the yellow inequality by −1 and get the opposite less than or equal to sign (≤).

After introducing these changes, you get a new system:

This system is equivalent to the original and will have the same solution. The only reason to apply these changes is to overcome the limitations of SciPy related to the problem formulation.

The next step is to define the input values:

You put the values from the system above into the appropriate lists, tuples , or NumPy arrays :

• obj holds the coefficients from the objective function.
• lhs_ineq holds the left-side coefficients from the inequality (red, blue, and yellow) constraints.
• rhs_ineq holds the right-side coefficients from the inequality (red, blue, and yellow) constraints.
• lhs_eq holds the left-side coefficients from the equality (green) constraint.
• rhs_eq holds the right-side coefficients from the equality (green) constraint.

Note: Please, be careful with the order of rows and columns!

The order of the rows for the left and right sides of the constraints must be the same. Each row represents one constraint.

The order of the coefficients from the objective function and left sides of the constraints must match. Each column corresponds to a single decision variable.

The next step is to define the bounds for each variable in the same order as the coefficients. In this case, they’re both between zero and positive infinity:

This statement is redundant because linprog() takes these bounds (zero to positive infinity) by default.

Note: Instead of float("inf") , you can use math.inf , numpy.inf , or scipy.inf .

Finally, it’s time to optimize and solve your problem of interest. You can do that with linprog() :

The parameter c refers to the coefficients from the objective function. A_ub and b_ub are related to the coefficients from the left and right sides of the inequality constraints, respectively. Similarly, A_eq and b_eq refer to equality constraints. You can use bounds to provide the lower and upper bounds on the decision variables.

You can use the parameter method to define the linear programming method that you want to use. There are three options:

• method="interior-point" selects the interior-point method. This option is set by default.
• method="revised simplex" selects the revised two-phase simplex method.
• method="simplex" selects the legacy two-phase simplex method.

linprog() returns a data structure with these attributes:

.con is the equality constraints residuals.

.fun is the objective function value at the optimum (if found).

.message is the status of the solution.

.nit is the number of iterations needed to finish the calculation.

.slack is the values of the slack variables, or the differences between the values of the left and right sides of the constraints.

.status is an integer between 0 and 4 that shows the status of the solution, such as 0 for when the optimal solution has been found.

.success is a Boolean that shows whether the optimal solution has been found.

.x is a NumPy array holding the optimal values of the decision variables.

You can access these values separately:

That’s how you get the results of optimization. You can also show them graphically:

As discussed earlier, the optimal solutions to linear programming problems lie at the vertices of the feasible regions. In this case, the feasible region is just the portion of the green line between the blue and red lines. The optimal solution is the green square that represents the point of intersection between the green and red lines.

If you want to exclude the equality (green) constraint, just drop the parameters A_eq and b_eq from the linprog() call:

The solution is different from the previous case. You can see it on the chart:

In this example, the optimal solution is the purple vertex of the feasible (gray) region where the red and blue constraints intersect. Other vertices, like the yellow one, have higher values for the objective function.

You can use SciPy to solve the resource allocation problem stated in the earlier section :

As in the previous example, you need to extract the necessary vectors and matrix from the problem above, pass them as the arguments to .linprog() , and get the results:

The result tells you that the maximal profit is 1900 and corresponds to x ₁ = 5 and x ₃ = 45. It’s not profitable to produce the second and fourth products under the given conditions. You can draw several interesting conclusions here:

The third product brings the largest profit per unit, so the factory will produce it the most.

The first slack is 0 , which means that the values of the left and right sides of the manpower (first) constraint are the same. The factory produces 50 units per day, and that’s its full capacity.

The second slack is 40 because the factory consumes 60 units of raw material A (15 units for the first product plus 45 for the third) out of a potential 100 units.

The third slack is 0 , which means that the factory consumes all 90 units of the raw material B. This entire amount is consumed for the third product. That’s why the factory can’t produce the second or fourth product at all and can’t produce more than 45 units of the third product. It lacks the raw material B.

opt.status is 0 and opt.success is True , indicating that the optimization problem was successfully solved with the optimal feasible solution.

SciPy’s linear programming capabilities are useful mainly for smaller problems. For larger and more complex problems, you might find other libraries more suitable for the following reasons:

SciPy can’t run various external solvers.

SciPy can’t work with integer decision variables.

SciPy doesn’t provide classes or functions that facilitate model building. You have to define arrays and matrices, which might be a tedious and error-prone task for large problems.

SciPy doesn’t allow you to define maximization problems directly. You must convert them to minimization problems.

SciPy doesn’t allow you to define constraints using the greater-than-or-equal-to sign directly. You must use the less-than-or-equal-to instead.

Fortunately, the Python ecosystem offers several alternative solutions for linear programming that are very useful for larger problems. One of them is PuLP, which you’ll see in action in the next section.

PuLP has a more convenient linear programming API than SciPy. You don’t have to mathematically modify your problem or use vectors and matrices. Everything is cleaner and less prone to errors.

As usual, you start by importing what you need:

Now that you have PuLP imported, you can solve your problems.

You’ll now solve this system with PuLP:

The first step is to initialize an instance of LpProblem to represent your model:

You use the sense parameter to choose whether to perform minimization ( LpMinimize or 1 , which is the default) or maximization ( LpMaximize or -1 ). This choice will affect the result of your problem.

Once that you have the model, you can define the decision variables as instances of the LpVariable class:

You need to provide a lower bound with lowBound=0 because the default value is negative infinity. The parameter upBound defines the upper bound, but you can omit it here because it defaults to positive infinity.

The optional parameter cat defines the category of a decision variable. If you’re working with continuous variables, then you can use the default value "Continuous" .

You can use the variables x and y to create other PuLP objects that represent linear expressions and constraints:

When you multiply a decision variable with a scalar or build a linear combination of multiple decision variables, you get an instance of pulp.LpAffineExpression that represents a linear expression.

Note: You can add or subtract variables or expressions, and you can multiply them with constants because PuLP classes implement some of the Python special methods that emulate numeric types like __add__() , __sub__() , and __mul__() . These methods are used to customize the behavior of operators like + , - , and * .

Similarly, you can combine linear expressions, variables, and scalars with the operators == , <= , or >= to get instances of pulp.LpConstraint that represent the linear constraints of your model.

Note: It’s also possible to build constraints with the rich comparison methods .__eq__() , .__le__() , and .__ge__() that define the behavior of the operators == , <= , and >= .

Having this in mind, the next step is to create the constraints and objective function as well as to assign them to your model. You don’t need to create lists or matrices. Just write Python expressions and use the += operator to append them to the model:

In the above code, you define tuples that hold the constraints and their names. LpProblem allows you to add constraints to a model by specifying them as tuples. The first element is a LpConstraint instance. The second element is a human-readable name for that constraint.

Setting the objective function is very similar:

Alternatively, you can use a shorter notation:

Now you have the objective function added and the model defined.

Note: You can append a constraint or objective to the model with the operator += because its class, LpProblem , implements the special method .__iadd__() , which is used to specify the behavior of += .

For larger problems, it’s often more convenient to use lpSum() with a list or other sequence than to repeat the + operator. For example, you could add the objective function to the model with this statement:

It produces the same result as the previous statement.

You can now see the full definition of this model:

The string representation of the model contains all relevant data: the variables, constraints, objective, and their names.

Note: String representations are built by defining the special method .__repr__() . For more details about .__repr__() , check out Pythonic OOP String Conversion: __repr__ vs __str__ or When Should You Use .__repr__() vs .__str__() in Python? .

Finally, you’re ready to solve the problem. You can do that by calling .solve() on your model object. If you want to use the default solver (CBC), then you don’t need to pass any arguments:

.solve() calls the underlying solver, modifies the model object, and returns the integer status of the solution, which will be 1 if the optimum is found. For the rest of the status codes, see LpStatus[] .

You can get the optimization results as the attributes of model . The function value() and the corresponding method .value() return the actual values of the attributes:

model.objective holds the value of the objective function, model.constraints contains the values of the slack variables, and the objects x and y have the optimal values of the decision variables. model.variables() returns a list with the decision variables:

As you can see, this list contains the exact objects that are created with the constructor of LpVariable .

The results are approximately the same as the ones you got with SciPy.

Note: Be careful with the method .solve() —it changes the state of the objects x and y !

You can see which solver was used by calling .solver :

The output informs you that the solver is CBC. You didn’t specify a solver, so PuLP called the default one.

If you want to run a different solver, then you can specify it as an argument of .solve() . For example, if you want to use GLPK and already have it installed, then you can use solver=GLPK(msg=False) in the last line. Keep in mind that you’ll also need to import it:

Now that you have GLPK imported, you can use it inside .solve() :

The msg parameter is used to display information from the solver. msg=False disables showing this information. If you want to include the information, then just omit msg or set msg=True .

Your model is defined and solved, so you can inspect the results the same way you did in the previous case:

You got practically the same result with GLPK as you did with SciPy and CBC.

Let’s peek and see which solver was used this time:

As you defined above with the highlighted statement model.solve(solver=GLPK(msg=False)) , the solver is GLPK.

You can also use PuLP to solve mixed-integer linear programming problems. To define an integer or binary variable, just pass cat="Integer" or cat="Binary" to LpVariable . Everything else remains the same:

In this example, you have one integer variable and get different results from before:

Now x is an integer, as specified in the model. (Technically it holds a float value with zero after the decimal point.) This fact changes the whole solution. Let’s show this on the graph:

As you can see, the optimal solution is the rightmost green point on the gray background. This is the feasible solution with the largest values of both x and y , giving it the maximal objective function value.

GLPK is capable of solving such problems as well.

Now you can use PuLP to solve the resource allocation problem from above:

The approach for defining and solving the problem is the same as in the previous example:

In this case, you use the dictionary x to store all decision variables. This approach is convenient because dictionaries can store the names or indices of decision variables as keys and the corresponding LpVariable objects as values. Lists or tuples of LpVariable instances can be useful as well.

The code above produces the following result:

As you can see, the solution is consistent with the one obtained using SciPy. The most profitable solution is to produce 5.0 units of the first product and 45.0 units of the third product per day.

Let’s make this problem more complicated and interesting. Say the factory can’t produce the first and third products in parallel due to a machinery issue. What’s the most profitable solution in this case?

Now you have another logical constraint: if x ₁ is positive, then x ₃ must be zero and vice versa. This is where binary decision variables are very useful. You’ll use two binary decision variables, y ₁ and y ₃, that’ll denote if the first or third products are generated at all:

The code is very similar to the previous example except for the highlighted lines. Here are the differences:

Line 5 defines the binary decision variables y[1] and y[3] held in the dictionary y .

Line 12 defines an arbitrarily large number M . The value 100 is large enough in this case because you can’t have more than 100 units per day.

Line 13 says that if y[1] is zero, then x[1] must be zero, else it can be any non-negative number.

Line 14 says that if y[3] is zero, then x[3] must be zero, else it can be any non-negative number.

Line 15 says that either y[1] or y[3] is zero (or both are), so either x[1] or x[3] must be zero as well.

Here’s the solution:

It turns out that the optimal approach is to exclude the first product and to produce only the third one.

Linear programming and mixed-integer linear programming are very important topics. If you want to learn more about them—and there’s much more to learn than what you saw here—then you can find plenty of resources. Here are a few to get started with:

• Wikipedia Linear Programming Article
• Wikipedia Integer Programming Article
• MIT Introduction to Mathematical Programming Course
• Brilliant.org Linear Programming Article
• CalcWorkshop What Is Linear Programming?
• BYJU’S Linear Programming Article

Gurobi Optimization is a company that offers a very fast commercial solver with a Python API. It also provides valuable resources on linear programming and mixed-integer linear programming, including the following:

• Linear Programming (LP) – A Primer on the Basics
• Mixed-Integer Programming (MIP) – A Primer on the Basics
• Choosing a Math Programming Solver

If you’re in the mood to learn optimization theory, then there’s plenty of math books out there. Here are a few popular choices:

• Linear Programming: Foundations and Extensions
• Convex Optimization
• Model Building in Mathematical Programming
• Engineering Optimization: Theory and Practice

This is just a part of what’s available. Linear programming and mixed-integer linear programming are popular and widely used techniques, so you can find countless resources to help deepen your understanding.

Just like there are many resources to help you learn linear programming and mixed-integer linear programming, there’s also a wide range of solvers that have Python wrappers available. Here’s a partial list:

• SCIP with PySCIPOpt
• Gurobi Optimizer

Some of these libraries, like Gurobi, include their own Python wrappers. Others use external wrappers. For example, you saw that you can access CBC and GLPK with PuLP.

You now know what linear programming is and how to use Python to solve linear programming problems. You also learned that Python linear programming libraries are just wrappers around native solvers. When the solver finishes its job, the wrapper returns the solution status, the decision variable values, the slack variables, the objective function, and so on.

In this tutorial, you learned how to:

• Define a model that represents your problem
• Create a Python program for optimization
• Run the optimization program to find the solution to the problem
• Retrieve the result of optimization

You used SciPy with its own solver as well as PuLP with CBC and GLPK, but you also learned that there are many other linear programming solvers and Python wrappers. You’re now ready to dive into the world of linear programming!

If you have any questions or comments, then please put them in the comments section below.

🐍 Python Tricks 💌

Get a short & sweet Python Trick delivered to your inbox every couple of days. No spam ever. Unsubscribe any time. Curated by the Real Python team.

About Mirko Stojiljković

Mirko has a Ph.D. in Mechanical Engineering and works as a university professor. He is a Pythonista who applies hybrid optimization and machine learning methods to support decision making in the energy sector.

Each tutorial at Real Python is created by a team of developers so that it meets our high quality standards. The team members who worked on this tutorial are:

Master Real-World Python Skills With Unlimited Access to Real Python

Join us and get access to thousands of tutorials, hands-on video courses, and a community of expert Pythonistas:

Join us and get access to thousands of tutorials, hands-on video courses, and a community of expert Pythonistas:

What Do You Think?

What’s your #1 takeaway or favorite thing you learned? How are you going to put your newfound skills to use? Leave a comment below and let us know.

Commenting Tips: The most useful comments are those written with the goal of learning from or helping out other students. Get tips for asking good questions and get answers to common questions in our support portal . Looking for a real-time conversation? Visit the Real Python Community Chat or join the next “Office Hours” Live Q&A Session . Happy Pythoning!

Keep Learning

Related Topics: intermediate data-science

Keep reading Real Python by creating a free account or signing in:

Already have an account? Sign-In

Almost there! Complete this form and click the button below to gain instant access:

5 Thoughts On Python Mastery

🔒 No spam. We take your privacy seriously.

Linear Programming

Linear programming is a process that is used to determine the best outcome of a linear function. It is the best method to perform linear optimization by making a few simple assumptions. The linear function is known as the objective function. Real-world relationships can be extremely complicated. However, linear programming can be used to depict such relationships, thus, making it easier to analyze them.

Linear programming is used in many industries such as energy, telecommunication, transportation, and manufacturing. This article sheds light on the various aspects of linear programming such as the definition, formula, methods to solve problems using this technique, and associated linear programming examples.

What is Linear Programming?

Linear programming, also abbreviated as LP, is a simple method that is used to depict complicated real-world relationships by using a linear function . The elements in the mathematical model so obtained have a linear relationship with each other. Linear programming is used to perform linear optimization so as to achieve the best outcome.

Linear Programming Definition

Linear programming can be defined as a technique that is used for optimizing a linear function in order to reach the best outcome. This linear function or objective function consists of linear equality and inequality constraints. We obtain the best outcome by minimizing or maximizing the objective function .

Linear Programming Examples

Suppose a postman has to deliver 6 letters in a day from the post office (located at A) to different houses (U, V, W, Y, Z). The distance between the houses is indicated on the lines as given in the image. If the postman wants to find the shortest route that will enable him to deliver the letters as well as save on fuel then it becomes a linear programming problem. Thus, LP will be used to get the optimal solution which will be the shortest route in this example.

Linear Programming Formula

A linear programming problem will consist of decision variables , an objective function, constraints, and non-negative restrictions. The decision variables, x, and y, decide the output of the LP problem and represent the final solution. The objective function, Z, is the linear function that needs to be optimized (maximized or minimized) to get the solution. The constraints are the restrictions that are imposed on the decision variables to limit their value. The decision variables must always have a non-negative value which is given by the non-negative restrictions. The general formula of a linear programming problem is given below:

• Objective Function: Z = ax + by
• Constraints: cx + dy ≤ e, fx + gy ≤ h. The inequalities can also be "≥"
• Non-negative restrictions: x ≥ 0, y ≥ 0

How to Solve Linear Programming Problems?

The most important part of solving linear programming problem is to first formulate the problem using the given data. The steps to solve linear programming problems are given below:

• Step 1: Identify the decision variables.
• Step 2: Formulate the objective function. Check whether the function needs to be minimized or maximized.
• Step 3: Write down the constraints.
• Step 4: Ensure that the decision variables are greater than or equal to 0. (Non-negative restraint)
• Step 5: Solve the linear programming problem using either the simplex or graphical method.

Let us study about these methods in detail in the following sections.

Linear Programming Methods

There are two main methods available for solving linear programming problem. These are the simplex method and the graphical method. Given below are the steps to solve a linear programming problem using both methods.

Linear Programming by Simplex Method

The simplex method in lpp can be applied to problems with two or more decision variables. Suppose the objective function Z = 40\(x_{1}\) + 30\(x_{2}\) needs to be maximized and the constraints are given as follows:

\(x_{1}\) + \(x_{2}\) ≤ 12

2\(x_{1}\) + \(x_{2}\) ≤ 16

\(x_{1}\) ≥ 0, \(x_{2}\) ≥ 0

Step 1: Add another variable, known as the slack variable, to convert the inequalities into equations. Also, rewrite the objective function as an equation .

- 40\(x_{1}\) - 30\(x_{2}\) + Z = 0

\(x_{1}\) + \(x_{2}\) + \(y_{1}\) =12

2\(x_{1}\) + \(x_{2}\) + \(y_{2}\) =16

\(y_{1}\) and \(y_{2}\) are the slack variables.

Step 2: Construct the initial simplex matrix as follows:

\(\begin{bmatrix} x_{1} & x_{2} &y_{1} & y_{2} & Z & \\ 1&1 &1 &0 &0 &12 \\ 2& 1 & 0& 1 & 0 & 16 \\ -40&-30&0&0&1&0 \end{bmatrix}\)

Step 3: Identify the column with the highest negative entry. This is called the pivot column. As -40 is the highest negative entry, thus, column 1 will be the pivot column.

Step 4: Divide the entries in the rightmost column by the entries in the pivot column. We exclude the entries in the bottom-most row.

12 / 1 = 12

The row containing the smallest quotient is identified to get the pivot row. As 8 is the smaller quotient as compared to 12 thus, row 2 becomes the pivot row. The intersection of the pivot row and the pivot column gives the pivot element.

Thus, pivot element = 2.

Step 5: With the help of the pivot element perform pivoting, using matrix properties , to make all other entries in the pivot column 0.

Using the elementary operations divide row 2 by 2 (\(R_{2}\) / 2)

\(\begin{bmatrix} x_{1} & x_{2} &y_{1} & y_{2} & Z & \\ 1&1 &1 &0 &0 &12 \\ 1& 1/2 & 0& 1/2 & 0 & 8 \\ -40&-30&0&0&1&0 \end{bmatrix}\)

Now apply \(R_{1}\) = \(R_{1}\) - \(R_{2}\)

\(\begin{bmatrix} x_{1} & x_{2} &y_{1} & y_{2} & Z & \\ 0&1/2 &1 &-1/2 &0 &4 \\ 1& 1/2 & 0& 1/2 & 0 & 8 \\ -40&-30&0&0&1&0 \end{bmatrix}\)

Finally \(R_{3}\) = \(R_{3}\) + 40\(R_{2}\) to get the required matrix.

\(\begin{bmatrix} x_{1} & x_{2} &y_{1} & y_{2} & Z & \\ 0&1/2 &1 &-1/2 &0 &4 \\ 1& 1/2 & 0& 1/2 & 0 & 8 \\ 0&-10&0&20&1&320 \end{bmatrix}\)

Step 6: Check if the bottom-most row has negative entries. If no, then the optimal solution has been determined. If yes, then go back to step 3 and repeat the process. -10 is a negative entry in the matrix thus, the process needs to be repeated. We get the following matrix.

\(\begin{bmatrix} x_{1} & x_{2} &y_{1} & y_{2} & Z & \\ 0&1 &2 &-1 &0 &8 \\ 1& 0 & -1& 1 & 0 & 4 \\ 0&0&20&10&1&400 \end{bmatrix}\)

Writing the bottom row in the form of an equation we get Z = 400 - 20\(y_{1}\) - 10\(y_{2}\). Thus, 400 is the highest value that Z can achieve when both \(y_{1}\) and \(y_{2}\) are 0.

Also, when \(x_{1}\) = 4 and \(x_{2}\) = 8 then value of Z = 400

Thus, \(x_{1}\) = 4 and \(x_{2}\) = 8 are the optimal points and the solution to our linear programming problem.

Linear Programming by Graphical Method

If there are two decision variables in a linear programming problem then the graphical method can be used to solve such a problem easily.

Suppose we have to maximize Z = 2x + 5y.

The constraints are x + 4y ≤ 24, 3x + y ≤ 21 and x + y ≤ 9

where, x ≥ 0 and y ≥ 0.

To solve this problem using the graphical method the steps are as follows.

Step 1: Write all inequality constraints in the form of equations.

x + 4y = 24

3x + y = 21

Step 2: Plot these lines on a graph by identifying test points.

x + 4y = 24 is a line passing through (0, 6) and (24, 0). [By substituting x = 0 the point (0, 6) is obtained. Similarly, when y = 0 the point (24, 0) is determined.]

3x + y = 21 passes through (0, 21) and (7, 0).

x + y = 9 passes through (9, 0) and (0, 9).

Step 3: Identify the feasible region. The feasible region can be defined as the area that is bounded by a set of coordinates that can satisfy some particular system of inequalities.

Any point that lies on or below the line x + 4y = 24 will satisfy the constraint x + 4y ≤ 24.

Similarly, a point that lies on or below 3x + y = 21 satisfies 3x + y ≤ 21.

Also, a point lying on or below the line x + y = 9 satisfies x + y ≤ 9.

The feasible region is represented by OABCD as it satisfies all the above-mentioned three restrictions.

Step 4: Determine the coordinates of the corner points. The corner points are the vertices of the feasible region.

B = (6, 3). B is the intersection of the two lines 3x + y = 21 and x + y = 9. Thus, by substituting y = 9 - x in 3x + y = 21 we can determine the point of intersection.

C = (4, 5) formed by the intersection of x + 4y = 24 and x + y = 9

Step 5: Substitute each corner point in the objective function. The point that gives the greatest (maximizing) or smallest (minimizing) value of the objective function will be the optimal point.

33 is the maximum value of Z and it occurs at C. Thus, the solution is x = 4 and y = 5.

Applications of Linear Programming

Linear programming is used in several real-world applications. It is used as the basis for creating mathematical models to denote real-world relationships. Some applications of LP are listed below:

• Manufacturing companies make widespread use of linear programming to plan and schedule production.
• Delivery services use linear programming to decide the shortest route in order to minimize time and fuel consumption.
• Financial institutions use linear programming to determine the portfolio of financial products that can be offered to clients.

Related Articles:

• Introduction to Graphing
• Linear Equations in Two Variables
• Solutions of a Linear Equation
• Mathematical Induction

Important Notes on Linear Programming

• Linear programming is a technique that is used to determine the optimal solution of a linear objective function.
• The simplex method in lpp and the graphical method can be used to solve a linear programming problem.
• In a linear programming problem, the variables will always be greater than or equal to 0.

As the minimum value of Z is 127, thus, B (3, 28) gives the optimal solution. Answer: The minimum value of Z is 127 and the optimal solution is (3, 28)

• Example 3: Using the simplex method in lpp solve the linear programming problem Minimize Z = \(x_{1}\) + 2\(x_{2}\) + 3\(x_{3}\) \(x_{1}\) + \(x_{2}\) + \(x_{3}\) ≤ 12 2\(x_{1}\) + \(x_{2}\) + 3\(x_{3}\) ≤ 18 \(x_{1}\), \(x_{2}\), \(x_{3}\) ≥ 0 Solution: Convert all inequalities to equations by introducing slack variables. -\(x_{1}\) - 2\(x_{2}\) - 3\(x_{3}\) + Z = 0 \(x_{1}\) + \(x_{2}\) + \(x_{3}\) + \(y_{1}\) = 12 2\(x_{1}\) + \(x_{2}\) + 3\(x_{3}\) + \(y_{2}\) = 18 Expressing this as a matrix we get, \(\begin{bmatrix} x_{1} & x_{2} & x_{3} & y_{1} & y_{2} & Z & \\ 1 & 1 & 1 & 1 & 0 & 0 & 12\\ 2 & 1 & 3 & 0 & 1 & 0 & 18\\ -1 & -2 & -3 & 0 & 0 & 1 & 0 \end{bmatrix}\) As -3 is the greatest negative value thus, column 3 is the pivot column. 12 / 1 = 12 18 / 3 = 6 As 6 is the smaller quotient thus, row 2 is the pivot row and 3 is the pivot element. By applying matrix operations we get, \(\begin{bmatrix} x_{1} & x_{2} & x_{3} & y_{1} & y_{2} & Z & \\ 0.33 & 0.667 & 0 & 1 & -0.33 & 0 & 6\\ 0.667 & 0.33 & 1 & 0 & 0.33 & 0 & 6\\ 1 & -1 & 0 & 0 & 1 & 1 & 18 \end{bmatrix}\) Now -1 needs to be eliminated. Thus, by repreating the steps the matrix so obtained is as follows \(\begin{bmatrix} x_{1} & x_{2} & x_{3} & y_{1} & y_{2} & Z & \\ 0.5 & 1 & 0 & 1.5 & 0.5 & 0 & 9\\ 0.5 & 0 & 1 & -0.5 & 0.5 & 0 & 3\\ 1.5 & 0 & 0 & 1.5 & 0.5 & 1 & 27 \end{bmatrix}\) We get the maximum value of Z = 27 at \(x_{1}\) = 0, \(x_{2}\) = 9 \(x_{3}\) = 3 Answer: Maximum value of Z = 27 and optimal solution (0, 9, 3)

go to slide go to slide go to slide

Book a Free Trial Class

Practice Questions on Linear Programming

go to slide go to slide

FAQs on Linear Programming

What is meant by linear programming.

Linear programming is a technique that is used to identify the optimal solution of a function wherein the elements have a linear relationship.

What is Linear Programming Formula?

The general formula for a linear programming problem is given as follows:

What is the Objective Function in Linear Programming Problems?

The objective function is the linear function that needs to be maximized or minimized and is subject to certain constraints. It is of the form Z = ax + by.

How to Formulate a Linear Programming Model?

The steps to formulate a linear programming model are given as follows:

• Identify the decision variables.
• Formulate the objective function.
• Identify the constraints.
• Solve the obtained model using the simplex or the graphical method.

How to Find Optimal Solution in Linear Programming?

We can find the optimal solution in a linear programming problem by using either the simplex method or the graphical method. The simplex method in lpp can be applied to problems with two or more variables while the graphical method can be applied to problems containing 2 variables only.

How to Find Feasible Region in Linear Programming?

To find the feasible region in a linear programming problem the steps are as follows:

• Draw the straight lines of the linear inequalities of the constraints.
• Use the "≤" and "≥" signs to denote the feasible region of each constraint.
• The region common to all constraints will be the feasible region for the linear programming problem.

What are Linear Programming Uses?

Linear programming is widely used in many industries such as delivery services, transportation industries, manufacturing companies, and financial institutions. The linear program is solved through linear optimization method, and it is used to determine the best outcome in a given scenerio.

The Linear Assignment Problem

• Conference paper
• Cite this conference paper

• Mustafa Akgül 4  

Part of the book series: NATO ASI Series ((NATO ASI F,volume 82))

353 Accesses

9 Citations

We present a broad survey of recent polynomial algorithms for the linear assignment problem. They all use essentially alternating trees and/or strongly feasible trees. Most of them employ Dijkstra’s shortest path algorithm directly or indirectly. When properly implemented, each has the same complexity: O( n 3 ) for dense graphs with simple data structures and O( n 2 log n + nm ) for sparse graphs using Fibonacci Heaps.

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
• Compact, lightweight 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

Unable to display preview.  Download preview PDF.

Similar content being viewed by others

The Quadratic Assignment Problem

A linear formulation with \(o(n^2)\) variables for quadratic assignment problems with manhattan distance matrices.

Linear Programming

H. Achatz, P. Kleinschmidt, and K. Paparrizos, A dual forest algorithm for the assignment problem , Tech. Rep., Universität Passau, Germany, 1989.

Google Scholar  

R.K. Ahuja and J.B. Orlin, Improved primal simplex algorithms for shortest path , assignment and minimum cost flow problems , Working Paper OR 189–88, M. I. T. 1988

R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows , in, Optimization, Handbooks in Operations Research and Management Science Vol. 1, Eds., G.L. Nemhauser, A.H.G. Rinnoy Kan, and M.J. Todd, ( Nort-Holland, New York, 1989 ).

R.K. Ahuja, K. Mehlhorn, J.B. Orlin, and R.E. Tarjan, Faster Algorithms for the Shortest Path Problem , Journal of ACM 37 (1990) 213–223.

Article   MathSciNet   MATH   Google Scholar  

M. Akgiil, Topics in Relaxation and Ellipsoidal Methods ,(Pitman, London, 1984. Research Notes in Mathematics Vol. 97.)

M. Akgül, A genuinely polynomial primal simplex algorithm for the assignment problem ,Technical Report, North Carolina State University, 1985, and Working Paper IEOR 87–07, Bilkent University, 1987. (To appear in Discrete Applied Mathematics)

M. Akgiil, A sequential dual simplex algorithm for the linear assignment problem , Operations Research Letters 7 (1988) 155–158.

Article   MathSciNet   Google Scholar  

M. Akgiil, Shortest paths and the simplex method , Working Paper IEOR-8804, Bilkent University, 1988.

M. Akgiil and O. Ekin, A dual feasible forest algorithm for the assignment problem ,Working Paper IEOR 90–11, Bilkent University, 1990. (to appear in RAIRO)

M. Akgiil, A forest primal-dual algorithm for the assignment problem , Working Paper IEOR 90–14, Bilkent University, 1990.

M. Akgiil, A faster version of Hung-Rom algorithm for the assignment problem , Working Paper IEOR 90–16, Bilkent University, 1990.

M. Akgiil and O. Ekin, A criss-cross algorithm for the assignment problem , Working Paper IEOR 90–22, Bilkent University, 1990.

A.I. Ali, R.V. Helgason, J.L. Kennington, and H.S. Lall, Primal simplex network codes: state-of-the-art implementation technology , Networks 8 (1978) 315–339.

J. Araoz and J. Edmonds, A case of non-convergent dual changes in assignment problems , Discrete Applied Mathematics 11 (1985) 95–102

M.L. Balinski, Signature method for the assignment problem , Operations Research 33 (1985) 527–536. Presented at Mathematical Programming Symposium, Bonn 1982.

M.L. Balinski, A competitive (dual) simplex method for the assignment problem , Mathematical Programming 34 (1986) 125–141.

M.L. Balinski and R.E. Gomory, A primal method for the assignment and transportation problems , Management Science 10 (1964) 578–598.

Article   Google Scholar  

R.S. Barr, F. Glover, and D. Klingman, The alternating basis algorithm for assignment problems , Mathematical Programming 13 (1977) 1–13.

D. Bertsekas, A new algorithm for the assignment problem , Mathematical Programming 21 (1981) 152–157.

D. Bertsekas, P.A. Hosein, and P. Tseng, Relaxation methods for network flow problems , SIAM J. Control & Optimization 25 (1987) 1219–1243.

D. Bertsekas, The auction algorithm: a distributed relaxation method for the assignment problem , Annals of Operations Research 14 (1988) 105–123.

R.B. Bixby, Matroids and operations research ,in Advanced Techniques in the Practice of Operations Research, H.J. Greenberg et. al., ed., (North-Holland, 1982) 333459.

G.H. Bradley G.G. Brown G.W. Graves, Design and implementation of large scale primal transshipment algorithms , Management Science 24 (1977) 1–34.

Article   MATH   Google Scholar  

R.E. Burkard, Travelling salesman and assignment problems: a survey , Annals of Discrete Mathematics 4 (1979) 193–215.

R.E. Burkard, W. Hahn, and W. Zimmermann, An algebraic approach to assignment problems , Mathematical Programming 12 (1977) 318–327.

G. Carpaneto and P. Toth, Primal-dual algorithms for the assignment problem , Discrete Applied Mathematics 18 (1987) 137–153.

P. Carraresi and C. Sodini, An efficient algorithm for the bipartite matching problem , EJOR 23 (1986) 86–93.

V. Chvátal, Linear Programming ,(Freeman, San Francisco, 1983.)

W.H. Cunningham, A network simplex method , Mathematical Programming 11 (1976) 105–116.

W.H. Cunningham, Theoretical properties of the network simplex method , Mathematics of Operations Research 4 (1979) 196–208.

W.H. Cunningham and A.B. Marsh, A primal algorithm for optimum matching , Mathematical Programming Study 8 (1978) 50–72.

MathSciNet   Google Scholar  

G.B. Dantzig, Linear Programming and Extensions ,(Princeton University Press, Princeton, 1963.)

E. Denardo and B. Fox, Shortest-route methods: 1. reaching , pruning , buckets , Operations Research 27 (1979) 161–186.

N. Deo and C. Pang, Shortest path algorithms: taxonomy and annotation , Networks 14 (1984) 275–323.

U. Derigs, The shortest augmenting path method for solving assignment problems—motivation and computational experience ,Annals of Operations Research 4 (1985/6) 57–102.

R. Dial, Algorithm 360: shortest path forest with topological ordering , Communications of ACM 12 (1965) 632–633.

R. Dial, F. Glover, D. Karney, and D. Klingman, A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees , Networks 9 (1979) 215–248.

E.W. Dijkstra, A note on two problems in connexion with graphs , Numerische Mathematik 1 (1959) 269–271.

E.A. Dinic and M.A. Kronrod, An algorithm for the solution of the assignment problem , Soviet Mathematics Doklady 10 (1969) 1324–1326.

MATH   Google Scholar  

S. Dreyfus, An appraisal of some shortest path algorithms , Operations Research 17 (1969) 396–412.

J. Edmonds and R.M. Karp, Theoretical improvements in algorithmic e fficiency for network flow problems , Journal of ACM 19 (1972) 248–264.

M. Engquist, A successive shortest path algorithm for the assignment problem , Infor 20 (1982) 370–384.

L.R. Ford and D.R. Fulkerson, Flows in Networks ,(Princeton University Press, Princeton, 1962.)

M.L. Fredman and R.E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms , Journal of ACM 34 (1987) 596–615 Also in Proc. 25’th FOCS (1984) 338–346.

J. Gilsinn and C. Witzgall, A performance comparison of labeling algorithms for calculating shortest path trees , Tech. Rep. 772, Washington, D.C., 1973.

F. Glover and D. Karney, Implementation and computational comparisons of primal , dual , primal-dual codes for minimum cost network flow problems , Networks 4 (1977) 191–212.

F. Glover, R. Glover, and D. Klingman, Threshold assignment algorithm , Mathematical Programming Study 25 (1986) 12–37.

D. Goldfarb, Efficient dual simplex algorithms for the assignment problem , Mathematical Programming 37 (1985) 187–203.

D. Goldfarb, J. Hao, and S. Kai, Efficient Shortest Path Simplex Algorithms , Operations Research 38 (1990) 624–628.

M. Gondran and M. Minoux, Graphs and Algorithms ,(Wiley, New York, 1984.)

M.S. Hung, A polynomial simplex method for the assignment problem , Operations Research 31 (1983) 595–600.

M.S. Hung and W.O. Rom, Solving the assignment problem by relaxation , Operations Research 27 (1980) 969–982.

E. Johnson, On shortest paths and sorting , in Proc. 25’th conference of ACM, Boston, 1972, 529–539.

E.L. Johnson, Flows in networks , in Handbook of Operations Research, J.J. Moder amp ; S.E. Elmaghraby, ed., Von Nostrand, 1978.

R. Jonker and A. Volgenant, Improving the Hungarian assignment algorithm , Operations Research Letters 58 (1986) 171–176.

R. Jonker and A. Volgenant, A shortest path algorithm for dense and sparse linear assignment problems , Computing 38 (1987) 325–340.

P. Kleinschmidt, C. Lee, and H. Schannath, Transportation problems which can be solved by the use hirsch-paths for the dual problems , Mathematical Programming 37 (1987), 153–168.

H.W. Kuhn, The hungarian method for the assignment problem , Naval Research Logistics Quarterly 2 (1955) 83–97.

J. Munkres, Algorithms for the assignment and transportation problems , SIAM Journal 5 (1957) 32–38.

MathSciNet   MATH   Google Scholar  

W.M. Nawijn and B. Dorhout, On the expected number of assignments in reduced matrices for the linear assignment problem , Operations research Letters 8 (1989) 329–336.

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

E. Lawler, Shortest path and network algorithms , Annals of Discrete Mathematics 4 (1979) 251–265.

J.B. Orlin, On the simplex algorithm for networks and generalized networks , Mathematical Programming Study 24 (1985) 166–178.

J.B. Orlin and R.K. Ahuja, New scaling algorithms for the assignment and minimum cycle mean problems , Working Paper OR 178–88, M. I. T. 1988.

C. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms & Complexity ,(Prentice-Hall, Englewood Cliffs, 1982.)

K. Paparrizos, A non-dual signature method for the assignment problem and a generalization of the dual simplex method for the transportation problem , RAIRO Operations Research 22 (1988) 269–289.

K. Paparrizos, An infeasible (exterior point) simplex algorithm for assignment problems ,Mathematical Programming (to appear)

K. Paparrizos, A relaxation Column signature method for assignment problems , EJOR 50 (1991) 211–219.

K. Paparrizos, Generalization of a signature method to transportation problems , Technical Report, Democritus University of Thrace, 1990.

A. Pierce, Bibliography on algorithms for shortest path , shortest spanning tree and related circuit routing problems , Networks 5 (1975) 129–143.

R.T. Rockafellar, Network Flows and Monotropic Optimization ,(Wiley, New York, 1984.)

Roohy-Laleh, Improvements to the theoretical efficiency of the simplex method ,PhD thesis, University of Charleton, Ottawa, 1981. Dissertation Abstract International vol.43, August 1982 p.448B.

D.D. Sleator and R.E. Tarjan, A data structure for dynamic trees , Journal of Computer and System Sciences 26 (1983) 362–391.

V. Srinivasan and G.L. Thompson, Accelerated algorithms for labeling and relabeling of trees , with applications to distribution problems , Journal of ACM 19 (1972) 712–726.

V. Srinivasan and G.L. Thompson, Benefit-cost analysis for coding techniques for the primal transportation problem , Journal of ACM 20 (1973) 184–213.

V. Srinivasan and G.L. Thompson, Cost operator algorithms for the transportation problem , Mathematical Programming 12 (1977) 372–391.

R.E. Tarjan, Data Structures and Network Algorithms ,(SIAM, Philadelphia, 1983.)

T. Terlaky, A convergent criss-cross method , Mathematische Operationsfurchung and Statistics ser. Optimization 16 (1985), 683–690.

G.L. Thompson, A recursive method for the assignment problems , Annals of Discrete Mathematics 11 (1981) 319–343.

C. Witzgall, On labeling algorithms for determining shortest paths in networks , Tech. Rep. 9840, Washington, D.C., 1968.

N. Tomizawa, On some techniques useful for solution of transportation network problems , Networks 1 (1972) 173–194.

Download references

Author information

Authors and affiliations.

Department of Industrial Engineering, Bilkent University, Ankara, Turkey

Mustafa Akgül

You can also search for this author in PubMed   Google Scholar

Editor information

Editors and affiliations.

Department of Industrial Engineering, Bilkent University, 06533, Ankara, Turkey

Fachbereich Mathematik, Universität Kaiserslautern, Erwin-Schroedinger-Straße, W-6750, Kaiserslautern, Germany

Horst W. Hamacher

Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, 32611-2083, Gainesville, FL, USA

Süleyman Tüfekçi

Rights and permissions

Reprints and permissions

Copyright information

© 1992 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper.

Akgül, M. (1992). The Linear Assignment Problem. In: Akgül, M., Hamacher, H.W., Tüfekçi, S. (eds) Combinatorial Optimization. NATO ASI Series, vol 82. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-77489-8_5

Download citation

DOI : https://doi.org/10.1007/978-3-642-77489-8_5

Publisher Name : Springer, Berlin, Heidelberg

Print ISBN : 978-3-642-77491-1

Online ISBN : 978-3-642-77489-8

eBook Packages : Springer Book Archive

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

• Math Article

Linear Programming

In Mathematics, linear programming is a method of optimising operations with some constraints. The main objective of linear programming is to maximize or minimize the numerical value. It consists of linear functions which are subjected to the constraints in the form of linear equations or in the form of inequalities.  Linear programming is considered an important technique that is used to find the optimum resource utilisation. The term “linear programming” consists of two words as linear and programming. The word “linear” defines the relationship between multiple variables with degree one. The word “programming” defines the process of selecting the best solution from various alternatives.

Linear Programming is widely used in Mathematics and some other fields such as economics, business, telecommunication, and manufacturing fields. In this article, let us discuss the definition of linear programming, its components, and different methods to solve linear programming problems.

Table of Contents:

• Characteristics
• Linear programming Problems
• Simplex Method

Graphical Method

• Applications
• Practice Problems

What is Linear Programming?

Linear programming (LP)   or Linear Optimisation may be defined as the problem of maximizing or minimizing a linear function that is subjected to linear constraints. The constraints may be equalities or inequalities. The optimisation problems involve the calculation of profit and loss.   Linear programming problems  are an important class of optimisation problems, that helps to find the feasible region and optimise the solution in order to have the highest or lowest value of the function.

In other words, linear programming is considered as an optimization method to maximize or minimize the objective function of the given mathematical model with the set of some requirements which are represented in the linear relationship. The main aim of the linear programming problem is to find the optimal solution.

Linear programming is the method of considering different inequalities relevant to a situation and calculating the best value that is required to be obtained in those conditions.  Some of the assumptions taken while working with linear programming are:

• The number of constraints should be expressed in the quantitative terms
• The relationship between the constraints and the objective function should be linear
• The linear function (i.e., objective function) is to be optimised

Components of Linear Programming

The basic components of the LP are as follows:

• Decision Variables
• Constraints
• Objective Functions

Characteristics of Linear Programming

The following are the five characteristics of the linear programming problem:

Constraints – The limitations should be expressed in the mathematical form, regarding the resource.

Objective Function – In a problem, the objective function should be specified in a quantitative way.

Linearity – The relationship between two or more variables in the function must be linear. It means that the degree of the variable is one.

Finiteness –  There should be finite and infinite input and output numbers. In case, if the function has infinite factors, the optimal solution is not feasible. 

Non-negativity – The variable value should be positive or zero. It should not be a negative value.

Decision Variables – The decision variable will decide the output. It gives the ultimate solution of the problem. For any problem, the first step is to identify the decision variables.

Linear Programming Problems

The Linear Programming Problems (LPP) is a problem that is concerned with finding the optimal value of the given linear function. The optimal value can be either maximum value or minimum value. Here, the given linear function is considered an objective function. The objective function can contain several variables, which are subjected to the conditions and it has to satisfy the set of linear inequalities called linear constraints. The linear programming problems can be used to get the optimal solution for the following scenarios, such as manufacturing problems, diet problems, transportation problems, allocation problems and so on.

Methods to Solve Linear Programming Problems

The linear programming problem can be solved using different methods, such as the graphical method, simplex method, or by using tools such as R, open solver etc. Here, we will discuss the two most important techniques called the simplex method and graphical method in detail.

Linear Programming Simplex Method

The simplex method is one of the most popular methods to solve linear programming problems. It is an iterative process to get the feasible optimal solution. In this method, the value of the basic variable keeps transforming to obtain the maximum value for the objective function. The algorithm for linear programming simplex method is provided below:

Step 1 : Establish a given problem. (i.e.,) write the inequality constraints and objective function.

Step 2: Convert the given inequalities to equations by adding the slack variable to each inequality expression.

Step 3 : Create the initial simplex tableau. Write the objective function at the bottom row. Here, each inequality constraint appears in its own row. Now, we can represent the problem in the form of an augmented matrix, which is called the initial simplex tableau.

Step 4 : Identify the greatest negative entry in the bottom row, which helps to identify the pivot column. The greatest negative entry in the bottom row defines the largest coefficient in the objective function, which will help us to increase the value of the objective function as fastest as possible.

Step 5 : Compute the quotients. To calculate the quotient, we need to divide the entries in the far right column by the entries in the first column, excluding the bottom row. The smallest quotient identifies the row. The row identified in this step and the element identified in the step will be taken as the pivot element.

Step 6: Carry out pivoting to make all other entries in column is zero.

Step 7: If there are no negative entries in the bottom row, end the process. Otherwise, start from step 4.

Step 8: Finally, determine the solution associated with the final simplex tableau.

The graphical method is used to optimize the two-variable linear programming. If the problem has two decision variables, a graphical method is the best method to find the optimal solution. In this method, the set of inequalities are subjected to constraints. Then the inequalities are plotted in the XY plane. Once, all the inequalities are plotted in the XY graph, the intersecting region will help to decide the feasible region. The feasible region will provide the optimal solution as well as explains what all values our model can take.  Let us see an example here and understand the concept of linear programming in a better way.

Calculate the maximal and minimal value of z = 5x + 3y for the following constraints.

x + 2y ≤ 14

3x – y ≥ 0

x – y ≤ 2

The three inequalities indicate the constraints. The area of the plane that will be marked is the feasible region.

The optimisation equation (z) = 5x + 3y. You have to find the (x,y) corner points that give the largest and smallest values of z.

To begin with, first solve each inequality.

x + 2y ≤ 14 ⇒  y ≤ -(1/2)x + 7

3x – y ≥ 0 ⇒  y ≤ 3x

x – y ≤ 2 ⇒ y  ≥ x – 2

Here is the graph for the above equations.

Now pair the lines to form a system of linear equations to find the corner points.

y = -(½) x + 7

Solving the above equations, we get the corner points as (2, 6)

y = -1/2 x + 7

y = x – 2

Solving the above equations, we get the corner points as (6, 4)

Solving the above equations, we get the corner points as (-1, -3)

For linear systems, the maximum and minimum values of the optimisation equation lie on the corners of the feasibility region. Therefore, to find the optimum solution, you only need to plug these three points in z = 3x + 4y

z = 5(2) + 3(6) = 10 + 18 = 28

z = 5(6) + 3(4) = 30 + 12 = 42

z = 5(-1) + 3(-3) = -5 -9 = -14

Hence, the maximum of z = 42 lies at (6, 4) and the minimum of z = -14 lies at (-1, -3)

Linear Programming Applications

A real-time example would be considering the limitations of labours and materials and finding the best production levels for maximum profit in particular circumstances. It is part of a vital area of mathematics known as optimisation techniques. The applications of LP in some other fields are

• Engineering – It solves design and manufacturing problems as it is helpful for doing shape optimisation
• Efficient Manufacturing – To maximise profit, companies use linear expressions
• Energy Industry – It provides methods to optimise the electric power system.
• Transportation Optimisation – For cost and time efficiency.

Importance of Linear Programming

Linear programming is broadly applied in the field of optimisation for many reasons. Many functional problems in operations analysis can be represented as linear programming problems. Some special problems of linear programming are such as network flow queries and multi-commodity flow queries are deemed to be important to have produced much research on functional algorithms for their solution.

Linear Programming Video Lesson

Linear programming problem.

Linear Programming Practice Problems

Solve the following linear programming problems:

• A doctor wishes to mix two types of foods in such a way that the vitamin contents of the mixture contain at least 8 units of vitamin A and 10 units of vitamin C. Food ‘I’ contains 2 units/kg of vitamin A and 1 unit/kg of vitamin C. Food ‘II’ contains 1 unit/kg of vitamin A and 2 units/kg of vitamin C. It costs Rs 50 per kg to purchase Food ‘I’ and Rs 70 per kg to purchase Food ‘II’. Formulate this problem as a linear programming problem to minimise the cost of such a mixture
• One kind of cake requires 200g of flour and 25g of fat, and another kind of cake requires 100g of flour and 50g of fat.  Formulate this problem as a linear programming problem to find the maximum number of cakes that can be made from 5kg of flour and 1 kg of fat assuming that there is no shortage of the other ingredients used in making the cakes.

Frequently Asked Questions on Linear Programming

Linear programming is a process of optimising the problems which are subjected to certain constraints. It means that it is the process of maximising or minimizing the linear functions under linear inequality constraints. The problem of solving linear programs is considered as the easiest one.

Mention the different types of linear programming.

The different types of linear programming are: Solving linear programming by Simplex method Solving linear programming using R Solving linear programming by graphical method Solving linear programming with the use of an open solver.

What are the requirements of linear programming?

The five basic requirements of linear programming are: Objective function Constraints Linearity Non-negativity Finiteness

Mention the advantages of Linear programming

The advantages of linear programming are: Linear programming provides insights to the business problems It helps to solve multi-dimensional problems According to the condition change, LP helps in making the adjustments By calculating the cost and profit of various things, LP helps to take the best optimal solution

What is meant by linear programming problems?

The linear programming problems (LPP) helps to find the best optimal solution of a linear function (also, known as the objective function) which are placed under certain constraints (set of linear inequality constraints)

To learn all concepts in Maths in a more engaging way, register at BYJU’S. Also, watch interesting videos on various Maths topics by downloading BYJU’S– The Learning App.

Leave a Comment Cancel reply

Your Mobile number and Email id will not be published. Required fields are marked *

Request OTP on Voice Call

Post My Comment

Thank you so much for clearly explained notes. I benefited a lot from them

Thank you very much for this material.

Register with BYJU'S & Download Free PDFs

Register with byju's & watch live videos.

• 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 Staff Scheduling Problem using Linear Programming

Learn how to use Linear Programming to solve Staff Scheduling problems.

As Senior operation manager, your job is to optimize scarce resources, improve productivity, reduce cost and maximize profit. For example, scheduling workers’ shifts for the most effective utilization of manpower. We need to consider the various restrictions of the total working hours of each employee, the number of shifts, shift hours, and other constraints. Such a problem can be considered an optimization problem.

Staff or workforce scheduling is used in numerous use-cases like nurse staff scheduling in a hospital, air flight scheduling, staff scheduling in the hotel, and scheduling of drivers. Such schedules can be created based on various time periods like hours, days, weeks, and months. Various organizations use spreadsheets and software. Poorly managed schedule causes overlapping of employee allocation, no breaks between shifts. Ultimately it will cause poor employee performance. For effective workforce scheduling, we need to consider the number of constraints and formulate them in the right manner. Workforce scheduling will help in effective human resource utilization, balanced timing, balanced workload, reduce employee fatigue and give importance to individual preferences ( link ).

Linear programming is a mathematical model for optimizing the linear function. We can achieve the best results using linear programming for a given specific set of constraints. Linear programming is widely used in management and economic science problems such as production planning, network routing, resource scheduling, and resource allocation. Linear programming can also be helpful in scheduling human resources. Such type of problem is known as Staff Scheduling or Workforce Scheduling problems.

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

Staff Scheduling Problem

In this problem, a saloon owner wants to determine the schedule for staff members. The staff consists of the full-time shift of 9 hours and part-time shift of 3 hours.  The saloon’s opening hours are divided into 4 shifts of 3 hours each. In each shift, different levels of demands are there that need the different number of staff members in each shift.

The required number of nurses for each shift is mentioned in the below table:

There is at least 1 full-time employee we need in each shift. The full-time employee will get $150 for 9 hours shift and the part-time employee will get $45 per shift.

Modeling Linear Programming Using Python PuLP

PuLP is an open-source library in Python for solving linear programming problems. In order to solve linear programming problems using PuLP, we need to formulate the objective function. PuLP will optimize to maximize or minimize the objective function. PuLP modeling process has the following steps for solving LP problems:

• Initialize Model

Define Decision Variable

Define objective function, define the constraints.

• Solve Model 

Understand the problem

Decision Variables

x i = Number of full-time employees scheduled in shift i.

y i = number of part-time employees scheduled in shift i.

Objective Function:

minimize Z= 150( x 0 + x 1 + x 2 + x 3 ) + 45( y 0 + y 1 + y 2 + y 3 )

Constraints 1:

• Employee starting shift constraints

x 0 + y 0 ≥ 6

x 0 + x 1 + y 1 ≥ 8

x 1 + x 2 + y 2 ≥ 11

x 2 + x 3 + y 3 ≥ 6

Constraints 2:

• Minimum full-time employees during any shift/period

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.

In this step, we will define the decision variables. In our problem, we have three variables wood tables, chairs, and bookcases. 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 .

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.

In this code, we have summed up the two variables(full-time and part-time) list values in an additive fashion.

Here, we are adding two types of constraints: employee starting shift constraints and minimum full-time employees during any period. We have added the 4 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.

In this article, we have learned about Staff Scheduling problems, Problem Formulation, and implementation in the python PuLp library. We have solved the staff scheduling 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. In upcoming articles, we will write more on different optimization problems and its solution using Python. You can revise the basics of mathematical concepts in this article and learn about Linear Programming in this article .

• Solving Linear Programming using Python PuLP
• Solving Cargo Loading Problem using Integer Programming in Python

You May Also Like

Keras Tutorial for Beginners

Working with crosstab, pivot_tables, and melt functions in Pandas

Data Visualization using Seaborn

This week: the arXiv Accessibility Forum

Help | Advanced Search

Mathematics > Optimization and Control

Title: an equilibrium dynamic traffic assignment model with linear programming formulation.

Abstract: In this paper, we consider a dynamic equilibrium transportation problem. There is a fixed number of cars moving from origin to destination areas. Preferences for arrival times are expressed as a cost of arriving before or after the preferred time at the destination. Each driver aims to minimize the time spent during the trip, making the time spent a measure of cost. The chosen routes and departure times impact the network loading. The goal is to find an equilibrium distribution across departure times and routes. For a relatively simplified transportation model we show that an equilibrium traffic distribution can be found as a solution to a linear program. In earlier works linear programming formulations were only obtained for social optimum dynamic traffic assignment problems. We also discuss algorithmic approaches for solving the equilibrium problem using time-expanded networks.

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 .

Information

• Author Services

Initiatives

You are accessing a machine-readable page. In order to be human-readable, please install an RSS reader.

All articles published by MDPI are made immediately available worldwide under an open access license. No special permission is required to reuse all or part of the article published by MDPI, including figures and tables. For articles published under an open access Creative Common CC BY license, any part of the article may be reused without permission provided that the original article is clearly cited. For more information, please refer to https://www.mdpi.com/openaccess .

Feature papers represent the most advanced research with significant potential for high impact in the field. A Feature Paper should be a substantial original Article that involves several techniques or approaches, provides an outlook for future research directions and describes possible research applications.

Feature papers are submitted upon individual invitation or recommendation by the scientific editors and must receive positive feedback from the reviewers.

Editor’s Choice articles are based on recommendations by the scientific editors of MDPI journals from around the world. Editors select a small number of articles recently published in the journal that they believe will be particularly interesting to readers, or important in the respective research area. The aim is to provide a snapshot of some of the most exciting work published in the various research areas of the journal.

Original Submission Date Received: .

• Active Journals
• Find a Journal
• Proceedings Series
• For Authors
• For Reviewers
• For Editors
• For Librarians
• For Publishers
• For Societies
• For Conference Organizers
• Open Access Policy
• Institutional Open Access Program
• Special Issues Guidelines
• Editorial Process
• Research and Publication Ethics
• Article Processing Charges
• Testimonials
• Preprints.org
• SciProfiles
• Encyclopedia

Article Menu

• Subscribe SciFeed
• Recommended Articles
• Google Scholar
• on Google Scholar
• Table of Contents

Find support for a specific problem in the support section of our website.

Please let us know what you think of our products and services.

Visit our dedicated information section to learn more about MDPI.

JSmol Viewer

On the theoretical link between optimized geospatial conflation models for linear features.

1. Introduction

2. geospatial data conflation methods, 2.1. heuristic vs. optimized conflation methods, 2.2. existing optimized conflation models, 2.2.1. common notation, 2.2.2. the assignment problem (ap), 2.2.3. the fixed-charge matching (fc-matching) problems, 2.2.4. the unified bidirectional matching u-bimatching problem, 2.2.5. the edge connectivity based matching (ec-matching) problem, 2.2.6. the m:1 (1:n) element connectivity bi-matching problem (ec-bimatching), 2.2.7. the edge-node matching (en-matching) problem, 2.2.8. m:n matching methods, 3.1. a base milp model, 3.1.1. equivalence to fc-matching, 3.1.2. a m:1 (1:n) version of the base model, 3.2. link to the assignment problems, 3.3. link to the network flow models, 3.3.1. connection between fc-matching and base-matching, 3.3.2. connection between fc-bimatching and base-bimatching, 3.4. link to the unified bidirectional matching u-bimatching problem, 3.5. link to the edge connectivity based matching (ec-matching) problem, 3.6. link to the edge-node matching (en-matching) problem, 4. experiments, 4.1. experimental settings, 4.2. properties of the base models, 4.3. equivalences and relations between the fc-matching problems and the base-matching problems, 5. conclusions and future directions, author contributions, data availability statement, conflicts of interest.

• Ruiz, J.J.; Ariza, F.J.; Ureña, M.A.; Blázquez, E.B. Digital map conflation: A review of the process and a proposal for classification. Int. J. Geogr. Inf. Sci. 2011 , 25 , 1439–1466. [ Google Scholar ] [ CrossRef ]
• Xavier, E.M.A.; Ariza-López, F.J.; Ureña-Cámara, M.A. A survey of measures and methods for matching geospatial vector datasets. ACM Comput. Surv. 2016 , 49 , 1–34. [ Google Scholar ] [ CrossRef ]
• Saalfeld, A. A fast rubber-sheeting transformation using simplicial coordinates. Am. Cartogr. 1985 , 12 , 169–173. [ Google Scholar ] [ CrossRef ]
• Saalfeld, A. Conflation automated map compilation. Int. J. Geogr. Inf. Syst. 1988 , 2 , 217–228. [ Google Scholar ] [ CrossRef ]
• Brown, J.N.; Rao, A.L.; Baran, J. Automated GIS conflation: Coverage update problems and solutions. In Proceedings of the 1995 Geographic Information Systems for Transportation (GIS-T) Symposium, Washington, WA, USA, 2–5 April 1995. [ Google Scholar ]
• Masuyama, A. Methods for detecting apparent differences between spatial tessellations at different time points. Int. J. Geogr. Inf. Science 2006 , 20 , 633–648. [ Google Scholar ] [ CrossRef ]
• McKenzie, G.; Janowicz, K.; Adams, B. A weighted multi-attribute method for matching user-generated points of interest. Cartogr. Geogr. Inf. Sci. 2014 , 41 , 125–137. [ Google Scholar ] [ CrossRef ]
• Li, L.; Goodchild, M.F. Automatically and accurately matching objects in geospatial datasets. Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci. ISPRS Arch. 2010 , 38 , 98–103. [ Google Scholar ]
• Li, L.; Goodchild, M.F. An optimisation model for linear feature matching in geographical data conflation. Int. J. Image Data Fusion 2011 , 2 , 309–328. [ Google Scholar ] [ CrossRef ]
• Tong, X.; Liang, D.; Jin, Y. A linear road object matching method for conflation based on optimization and logistic regression. Int. J. Geogr. Inf. Sci. 2014 , 28 , 824–846. [ Google Scholar ] [ CrossRef ]
• Lei, T.L. Geospatial data conflation: A formal approach based on optimization and relational databases. Int. J. Geogr. Inf. Sci. 2020 , 34 , 2296–2334. [ Google Scholar ] [ CrossRef ]
• Wu, H.; Xu, S.; Huang, S.; Wang, J.; Yang, X.; Liu, C.; Zhang, Y. Optimal road matching by relaxation to min-cost network flow. Int. J. Appl. Earth Obs. Geoinf. 2022 , 114 , 103057. [ Google Scholar ] [ CrossRef ]
• Rosen, B.; Saalfeld, A. Match Criteria for Automatic Alignment. In Proceedings of the 7th International Symposium on Computer-Assisted Cartography, Washington, WA, USA, 11–14 March 1985; pp. 1–20. [ Google Scholar ]
• Hillier, F.S.; Lieberman, G.J. Introduction to Operations Research , 8th ed.; McGraw-Hill: New York, NY, USA, 2005; p. 1088. [ Google Scholar ]
• Lei, T.; Lei, Z. Optimal spatial data matching for conflation: A network flow-based approach. Trans. GIS 2019 , 23 , 1152–1176. [ Google Scholar ] [ CrossRef ]
• Lei, T.L.; Wang, R. Conflating linear features using turning function distance: A new orientation-sensitive similarity measure. Trans. GIS 2021 , 25 , 1249–1276. [ Google Scholar ] [ CrossRef ]
• Ai, T.; Cheng, X.; Liu, P.; Yang, M. A shape analysis and template matching of building features by the fourier transform method. Comput. Environ. Urban Syst. 2013 , 41 , 219–233. [ Google Scholar ] [ CrossRef ]
• Beeri, C.; Kanza, Y.; Safra, E.; Sagiv, Y. Object fusion in geographic information systems. Proc. Thirtieth Int. Conf. Very Large Data Bases 2004 , 30 , 816–827. [ Google Scholar ]
• Corral, A.; Manolopoulos, Y.; Theodoridis, Y.; Vassilakopoulos, M. Algorithms for processing k-closest-pair queries in spatial databases. Data Knowl. Eng. 2004 , 49 , 67–104. [ Google Scholar ] [ CrossRef ]
• Tong, X.; Shi, W.; Deng, S. A probability-based multi-measure feature matching method in map conflation. Int. J. Remote Sens. 2009 , 30 , 5453–5472. [ Google Scholar ] [ CrossRef ]
• Lei, T.L.; Lei, Z. Harmonizing full and partial matching in geospatial conflation: A unified optimization model. ISPRS Int. J. Geo-Inf. 2022 , 11 , 375. [ Google Scholar ] [ CrossRef ]
• Lei, T.L.; Lei, Z. Linear feature conflation: An optimization-based matching model with connectivity constraints. Trans. GIS 2023 , 27 , 1205–1227. [ Google Scholar ] [ CrossRef ]
• Lei, Z.; Lei, T.L. Towards topological geospatial conflation: An optimized node-arc conflation model for road networks. ISPRS Int. J. Geo-Inf. 2024 , 13 , 15. [ Google Scholar ] [ CrossRef ]
• Yang, B.; Zhang, Y.; Luan, X. A probabilistic relaxation approach for matching road networks. Int. J. Geogr. Inf. Sci. 2013 , 27 , 319–338. [ Google Scholar ] [ CrossRef ]
• Zuo, Z.; Yang, L.; An, X.; Zhen, W.; Qian, H.; Dai, S. A hierarchical matching method for vectorial road networks using delaunay triangulation. ISPRS Int. J. Geo-Inf. 2020 , 9 , 509. [ Google Scholar ] [ CrossRef ]
• Guo, Q.; Xu, X.; Wang, Y.; Liu, J. Combined matching approach of road networks under different scales considering constraints of cartographic generalization. IEEE Access 2020 , 8 , 944–956. [ Google Scholar ] [ CrossRef ]
• Wang, Y.; Yan, H.; Li, P.; Lu, X. A multiscale road matching method based on hierarchical road meshes. Earth Sci. Inform. 2024 , 17 , 1765–1778. [ Google Scholar ] [ CrossRef ]
• Ali, A.B.; Harvey, F.; Vauglin, F. Geometric Matching of Areas, Comparison Measures and Association Links. In Proceedings of the 8th International Symposium on Spatial Data Handling, Vancouver, BC, Canada, 11–15 July 1998; pp. 557–568. [ Google Scholar ]
• Fan, H.; Zipf, A.; Fu, Q.; Neis, P. Quality assessment for building footprints data on OpenStreetMap. Int. J. Geogr. Inf. Sci. 2014 , 28 , 700–719. [ Google Scholar ] [ CrossRef ]
• Song, W.; Keller, J.M.; Haithcoat, T.L.; Davis, C.H. Relaxation-based point feature matching for vector map conflation. Trans. GIS 2011 , 15 , 43–60. [ Google Scholar ] [ CrossRef ]
• Fu, Z.; Yang, Y.; Gao, X.; Zhao, X.; Lu, Y.; Chen, S. Road networks matching using multiple logistic regression. Geomat. Inf. Sci. Wuhan Univ. 2016 , 41 , 171–177. [ Google Scholar ] [ CrossRef ]
• Lei, T.L. Integrating GIS and location modeling: A relational approach. Trans. GIS 2021 , 25 , 1693–1715. [ Google Scholar ] [ CrossRef ]

Click here to enlarge figure

Share and Cite

Lei, Z.; Yuan, Z.; Lei, T.L. On the Theoretical Link between Optimized Geospatial Conflation Models for Linear Features. ISPRS Int. J. Geo-Inf. 2024 , 13 , 310. https://doi.org/10.3390/ijgi13090310

Lei Z, Yuan Z, Lei TL. On the Theoretical Link between Optimized Geospatial Conflation Models for Linear Features. ISPRS International Journal of Geo-Information . 2024; 13(9):310. https://doi.org/10.3390/ijgi13090310

Lei, Zhen, Zhangshun Yuan, and Ting L. Lei. 2024. "On the Theoretical Link between Optimized Geospatial Conflation Models for Linear Features" ISPRS International Journal of Geo-Information 13, no. 9: 310. https://doi.org/10.3390/ijgi13090310

Article Metrics

Article access statistics, further information, mdpi initiatives, follow mdpi.

Subscribe to receive issue release notifications and newsletters from MDPI journals