Tag Archives: simplex

The Assignment Problem

I just finished a script that generates instances of the assignment problem and solves them step by step. You can check it out here.

Assignment Problem Image

Suppose you are the owner of a company and need to delegate tasks to your employees. You’ve generated a table that tells how long (in minutes) you think it would take each person to accomplish each individual task (called Jobs). Your goal is to find an assignment of people to jobs that minimizes the total amount of time it will take to complete all jobs. The requirements are that each job must be completed by only one person, and each person can complete only one job.

We can think of the employees at the job as our supply and the tasks as the demand. In order for this problem to have a feasible solution, we must have enough people (supply) to complete the number of jobs (demand). Because of this, our examples will all include situations where there are exactly the same number of people as jobs.

To solve this problem, we must first generate an initial assignment and see how good this assignment is. There are several ways of generating an initial solution, but two that I wanted to focus on are the “NorthWest Corner Rule” and the “Minimum Matrix Method”.

  1. The Northwest Corner Rule considers the matrix and repeatedly assigns the top remaining row to the left-most remaining column. If we think of the cost matrix as a being like a map then “top” becomes similar to “north” and left-most becomes similar to “west”, hence the derivation of the name. In assignment problems, this will result in the main diagonal being selected.
  2. The Minimum Matrix Method is an iterative method that searches the matrix for the minimum cell in the matrix and assigns that person to the associated job and removes them from consideration and repeats itself until all people have been assigned to jobs.

Once we have formulated an initial feasible solution, we need to check it for optimality. To do this, we use the Network Simplex Method, where we build a basis based on this initial solution. When we consider this problem as a network flow problem, a basis for the problem is a spanning tree (one less than twice the number of nodes in the graph that does not have any cycles) of the network. Because the assignment solution only contains one edge for every two nodes in the graph, we need to add a number of edges to the basis that contains no flow (which makes the solution degenerate) to form this spanning tree.

Once a spanning tree is formulated, we can solve for the dual variables by arbitrarily setting one node’s dual value to zero and solving for the remaining dual variables under the requirement that all arcs in the basis (spanning tree) must satisfy the equation uk + vi = cki for each person k and job i.

When we have dual variables, we can check to see if this solution is optimal by checking to see if all the other constraints are violated. This means that for every person k and every job i, we must have uk + vi cki (notice that this is a more relaxed version of what we had when we were solving for the dual variables themselves).

If a constraint is found to be violated, then we need to add the associated edge to the basis and remove an edge on the cycle that is formulated as a result, which generates a new solution.

So check out The Assignment Problem Script and let me know what you think.

The Simplex Method

I just added a script which generates a random linear programming problem and executes the Simplex Method Method on it. 

The Simplex Method, originally discovered by George Dantzig, is one of the most important algorithms in computer science. It literally connects computer scientists to problems in mathematics, engineering, business, economics, transportation, and a host of problems that are faced by everyday people. For many of these problems, no one has yet discovered a pattern or a simpler means of solving it, other than the Simplex Method. Each of these problems has its own difficulties that distinguish it from other problems. While some such problems are important enough to receive their own studies to improve upon the efficiency of the simplex method (Network Flow problems come to mind), there are just too many problems for each one to receive such consideration. Thus we see the importance of the Simplex Method because it can solve these problems as long as they can be formulated as linear programming problems.

To understand the power of the Simplex Method, we need to understand a class of problems: linear programming problems. A linear programming problem is a problem where we seek to minimize/maximize a linear objective function (over finitely many variables) subject to a finite set of linear inequality constraints over these variables. A general example of a linear programming problem is “The Transportation Problem”.

The Transportation Problem Suppose you own a manufacturing company and its your job to ship your product from warehouse locations all across the United States to a number of customers. Each customer has ordered a certain quantity of the item, and each warehouse can supply up to a certain amount. Then we define the following variables:

m = the number of warehouses
n = the number of customers
ai = the total amount of item available at warehouse i
bj the total requirement of customer j
xi, j = the amount of item shipped from warehouse i to customer j.

In order for things to work properly, we need that the total amount in supply is equal to the the total amount ordered. If we assumed that we have 3 customers and 2 warehouses, then the following constraints help formulate this problem.

x1, 1 + x1, 2 + x1, 3 = a1
x2, 1 + x2, 2 + x2, 3 = a2
x1, 1 + x2, 1 = b1
x1, 2 + x2, 2 = b2
x1, 3 + x2, 3 = b3

You also know the cost of shipping one unit of the item from warehouse i to customer j and label it ci, j.

Then the objective function which we seek to minimze is c1, 1x1, 1 + c1, 2x1, 2 + c1, 3x1, 3 + c2, 1x2, 1 + c2, 2x2, 2 + c2, 3x2, 3.

And we also have that xi, j is nonnegative since we are shipping (and not receiving) goods.

Because we can state this problem as a linear programming problem, we can solve it using the simplex method. Although this problem was very simple to formulate, the ability to formulate a problem as a linear programming problem is seen as a great accomplishment because there exists so much literature on linear programming problems, and a method on how to solve them, (i.e. the Simplex method). For this reason, much work is often dedicated to finding good linear programming representations of problems.

Another set of problems of interest are integer programming problems. These problems add the additional requirement to linear programming problems that some or all of these variables can only take on a discrete set of values instead of a continuous realm. Integer programming problems are generally thought to be more difficult to solve than linear programming problems. What makes integer programming problems special is the fact that many problems that are known to be just as difficult as integer programming problems can be formulated as integer programming problems. Although the Simplex Method does not promise to always solve these problems to optimality, it offers a way to approach integer programming problems, and thus every problems that is known to be just as hard these problems which is at least a starting point.

New Years is a LEARNINGlover Thing!

Starting this web site has served as the perfect opportunity to unwind. In particular, two blogs I wrote recently have served different purposes. The first was “The Degrees of Consciousness of a Black Nerd“, where I spoke about many of the things I think about being who I am and relating the the (somewhat unique) set of people that I communicate with on a daily basis. The other was what I’ve been working on since mid December. Its the blog entry I wrote on Sudoku and the Sudoku program that I wrote last month using the Dancing Links Algorithm. Since originally writing that, I’ve updated the program with a lot of Sudoku problems, as well as two types of “hints”. One generates the “possibilities matrix” which basically just shows what is possible for each cell. The other scans the possibilities matrix and searches for isolated cells (cells where some number can only go in one row/column/subgrid). Both those additions were extremely fun and provided a nice opportunity to program in my spare time.

So I’ve been thinking about these two things and how much I enjoyed the two, but for different reasons. The Degrees of Consciousness of a Black Nerd brought much attention on facebook where the idea was both accepted and rejected and I was able to explain the ideas further and hear similar stories from others who had similar experiences. Sudoku, on the other hand hasn’t generated as much conversation. A few friends have told me that they liked the program, but I don’t know of too many people outside of myself using it. That’s OK. I didn’t really create the program for publication, moreso because I enjoy Sudoku and took it as a challenge to write a program to solve a puzzle.

That being said, I’ve been thinking about some other things that I would like to do – hopefully they’ll be more than just my opinion, but have some programming, operations research, or mathematical context to them as well. But here’s a list of things that I want to write about in the near future.

  • Connections between math and football (or sports in general). Anybody who knows me knows that I’m a huge sports fan. At other sites, I’ve posted stuff on QB rating systems and the flaws/inaccuracies in them. Part of me would like to look further into this stuff and either do a comparison, create a new rating system, or just try to understand (explain) different scouting metrics, particularly for QBs.
  • I wrote the Sudoku program, but that’s a well studied problem so it was easy to find research that helped me to understand other stuff. I also studied some problems in Ramsey Theory that can be represented by exact covering algorithms and it would be interesting to try to represent these as exact cover problems and to try to use the Dancing Links algorithm to solve these problems as well, maybe to find a comparative analysis to benchmarks.
  • One of the things I’ve picked up on lately is machine learning. While I’ve added flash cards on Bayesian Networks, I would like to add some programs on things like k-means clustering.
  • I added my sorting algorithms a few weeks ago, but would like to also add something on data structures (arrays, linked lists, trees, heaps, hash tables, etc). In undergrad this was called the class that weeded people out of computer science majors, so doing something on this type of stuff I think could be helpful to those who want to understand it better.
  • I have been in the process of writing a linear programming (Simplex) implementation for a while. I would like to get back to that to allow for a solver that can do at least simple algorithms.
  • I’ve written a few drafts that connect math to different areas that I’m interested in (music, sports, philosophy, religion, etc), but I need to find a better way to present the stuff because as they’re currently stated, this stuff can easily be misinterpreted.

The beautiful thing about this site is that I’m not constrained by any advisor or boss or deadlines. Its more of a how am I feeling right now kind of a thing and these are the things I’m feeling right now. So this list is kind of my “New Years Resolutions” for LEARNINGlover.com, and while I reserve the right to change my priorities any time I feel that something else deserves my attention more, these are the things I’m planning to spend time on in the next few weeks.