What is Combinatorial Optimization?
Optimization just means "finding the best", and the word `combinatorial' is just a six syllable way of saying that the problem involves discrete choices, unlike the older and better known kind of optimization which seeks to find numerical values.
The employment or assignment problem, matching people with jobs, is a what used to be called a pigeonhole problem. There are a number of discrete slots, or pigeonholes, which we might number 1, 2, 3, 4, 5, 6, ... and there are a number of objects, A, B, C, D, E, F, ... which have to be put in the most appropriate pigeonhole. We call assignment of objects to slots a feasible solution if assigns each object to a unique slot. Here are some feasible solutions:
1A, 2B, 3C, 4D, 5E, 6F, ... (simplistic initial solution, match in order listed)
1B, 2A, 3D, 4C, 5F, 6E, ... (start with initial solution, swap pairs)
If there are N slots and equally many objects, then there are N ways of assigning the first object, N-1 ways of assigning the second object and so on, so that the number of solutions is N! (which is pronounced "factorial N"). If there are 3 slots, there are 6 different feasible solutions: 1A, 2B, 3C 1A, 2C, 3B 1B, 2A, 3C 1B, 2C, 3A 1C, 2A, 3B 1C, 2B, 3A
But, if there are 6 slots and objects, there are 720 feasible solutions, if there are 12 slots and objects there are 479 Million different solutions, and if there are 24 different slots and objects the number of feasible solutions is 6.2045 times 10 to the 23rd power.
The technical term for this is Combinatorial Explosion -- the explosively rapid increase in the number of possibilities with the number of items to be assigned.
Suppose we are dealing with a small company that has 50 employees. If everyone was interchangeable with everone else, so you could really give any job to any person, then we would be actually dealing with the pigeonhole problem, and the number of possible ways of assigning people to jobs is 3.0414 times 10 the the power of 64. But, more realistically, suppose that each person is only suited to two jobs out of the 50. Then the number of different feasible solutions is about 2 to the 50th power, which is 1,125,899,906,842,624 or about one million billion.
When the search-space or solution-space of feasible solutions is very large, the chances that any real solution arrived at by management is actually a good solution becomes very small. The solution-space is too big to search in any effective way, so people just pick the best solution they happen to stumble across.
This creates what I call the job-mismatch problem: most people are in the wrong job because finding the right jobs for everybody is a combinatorial nightmare: too many choices.
To my way of thinking, the unemployment problems facing many nations today is just the tip of the job-mismatch iceberg. It is so hard to match up people to jobs that lots of people just don't get assigned to jobs at all.
I admit that there may be job shortages in very specific situations, but I'm convinced that on the whole, unemployment just a combinatorial problem, not a job shortage problem. If you insist that you are a coal miner and nothing but a coal miner, and you insist in living in the same town you have always lived in, and refuse to travel long distances to work, then there may indeed be a job shortage when the only pit in town closes. But in general, there's no job shortage.
Actually, the very idea of a job is a relic of earlier centuries. We can say instead that there are many tasks to be done and many people who are available to do them. The real combinatorial optimization problem is not matching people to jobs, but the ongoing problem of matching people to tasks. Having a set or sequence of tasks grouped together into a job, then finding a person to do that job is actually just a crude way of approaching the harder problem of finding people to do the specific tasks.
So there are at least two ways in which all this talk about unemployment is completely off-the-rails: first, it is not an economic problem involving job shortages, it is a combinatorial optimization problem. Second, it is not about jobs at all, it is about matching people up with specific tasks.
The point here is not just that everyone else has been addressing the wrong problem, but that nobody has dealt with the problem in the right way at all.
Jobs seem to depend on economics, since high unemployment and poor economic conditions coincide. Unemployment seems to result from poor economic conditions -- indeed, we often see companies in trouble laying off employees.
But I think we have the causal connection the wrong way around: I think economic conditions depend on how well we solve the job-mismatch problem. Companies do fail because of bad management, but if it was easy for people to find good jobs, those employees would have found other jobs long before the company got to the point of laying off workers. People hang around in dead end jobs or in companies doomed by bad management because they feel they have no choice: it is too hard to find another job.
Unfortunately, we haven't addressed the problem in the way software and systems engineers do -- instead we leave it to politicians, whose only qualification seems to be the ability to get elected to public office.
Any qualified software engineer faced with a problem in which certain items were not finding slots would immediately look at the more general problem of matching items to slots, and would be certain to investigate the combinatorial aspects of the problem.
Let me generalize a bit: we need to match people to tasks, but we also need to match people with co-workers. In fact, almost all social problems involve matching and optimization.
Underlying almost all the social ills of our society is the combinatorial explosion of possibilities and the lack of adequate techniques for reducing the size of the search space. Technology based on combinatorial optimization theory can provide ways around such problems. It turns out that the "assignment problem" or "bipartite matching problem" is quite approachable -- computationally intensive, but approachable. There are good algorithms for solving it.
One of the strong claims made by Soviet ideologists was that they had no unemployment because of the advantages of central planning. They were wrong. Essentially they thought that they could solve the assignment problem for a society of millions of people by having a central core of bureaucrats figure out who should do what, and they were wrong. But exactly why were they wrong?
It all comes down to the size of the problem. Assignment problems are roughly O(3) problems, meaning that the amount of work needed to solve them depends on the cube of the number of elements (that's for Gabor's algorithm). Matching a few thousand nodes can take 30 minutes or so on my aging 120 Mhz Pentium, but matching a few million nodes (a thousand times as many) would take not 1000 times as long but 1,000,000,000 times as long.
Even if they had all the job-suitability, or skills and aptitude data already prepared, just doing the calculations involved in matching 50 or 100 million people to jobs would have taken more computing power than existed on earth at the time at the time the Soviet Union dissolved.
Clever approximation algorithms could probably approximate a good solution using computing power that is available today, but that could only be true if the true problem had been properly addressed.
New: Social Technology through Diagrams
New: Social Techs novel online
New: Social Technology Blog
New: Social Technology Wiki
The main Social Technology page.
Find Compatibles , the key page, with the real solution to all other problems explained
Technological Fantasies , a page about future technology
Social Tech a page about Social Technology, technology for social purposes. I think I was the first person to use this phrase on the Internet, quite a long time ago.
Roughly corresponding to these web pages are the following blogs :
Social Technology the main blog, hosted on this site, with posts imported from the following blogger.com blogs, which still exist and are useable.
Find Compatibles devoted to matching people with friends, lovers, jobs, places to live and so on, but doing so in ways that will actually work, using good math, good algorithms, good analysis.
Technological Fantasies devoted to future stuff, new ideas, things that might be invented or might happen, such as what is listed above and below.
Sex-Politics-Religion is a blog about these important topics, which I have been told should never be mentioned in polite conversation. Alright that advice does seem a bit dated, but many people are still told not to bring up these subjects around the dinner table.
I believe I was the first person on the Internet to use the phrase Social Technology -- years before the Web existed.
Those were the good old days, when the number of people using the net exceeed the amount of content on it, so that it was easy to start a discussion about such an upopular topic. Now things are different. There are so many web pages that the chances of anyone finding this page are low, even with good search engines like Google. Oh, well.
By Social Technology I mean the technology for organizing and maintaining human society. The example I had most firmly in mind is the subject of Find Compatibles , what I consider to be the key page, the one with the real solution to all other problems explained.
As I explained on my early mailing lists and later webpages, I find that social technology has hardly improved at all over the years. We still use representative democracy, exactly the same as it was used in the 18th century. By contrast, horse and buggy transporation has been replaced by automobiles and airplanes, enormous changes.
In the picture below you will see some 18th century technology, such as the ox-plow in the middle of the picture. How things have changed since then in agricultural technology. But we still use chance encounters, engagements and marriages to organize our home life and the raising of children.
I claim that great advances in social technology are not only possible but inevitable. I have written three novels about this, one preposterously long, 5000 pages, another merely very very long, 1500 pages. The third is short enough at 340 pages to be published some day. Maybe. The topic is still not interesting to most people. I will excerpt small parts of these novels on the web sometime, maybe even post the raw text for the larger two.
This site includes many pages dating from 1997 to 2008 which are quite out of date. They are included here partly to show the development of these ideas and partly to cover things the newer pages do not. There will be broken links where these pages referenced external sites. I've tried to fix up or maiintain all internal links, but some will probably have been missed. One may wish to look at an earlier version of this page , rather longer, and at an overview of most parts of what can be called a bigger project.
Type in this address to e-mail me. The image is interesting. See Status of Social Technology
Copyright © 2007, 2008, 2009, Douglas Pardoe Wilson
I have used a series of e-mail address over the years, each of which eventually became out of date because of a change of Internet services or became almost useless because of spam. Eventually I stuck with a Yahoo address, but my inbox still fills up with spam and their spam filter still removes messages I wanted to see. So I have switched to a new e-mail service. Web spiders should not be able to find it, since it is hidden in a jpeg picture. I have also made it difficult to reach me. The picture is not a clickable link. To send me e-mail you must want to do so badly enough to type this address in. That is a nuisance, for which I do apologize, but I just don't want a lot of mail from people who do not care about what I have to say.