How Linear Programming Began

Tuesday, May 27th, 2008

George Dantzig explains how linear programming began:

Seeing that economists did not have a method of solution, I next decided to try my own luck at finding an algorithm. I owe a great debt to Jerzy Neyman, the leading mathematical statistician of his day, who guided my graduate work at Berkeley. My thesis was on two famous unsolved problems in mathematical statistics which I mistakenly thought were a homework assignment and solved. One of the results, published jointly with Abraham Wald, was on the Neyman-Pearson Lemma. In today’s terminology, this part of my thesis was on the existence of Lagrange multipliers (or dual variables) for a semi-infinite linear program whose variables were bounded between zero and one and satisfied linear constraints expressed in the form of Lebesgue integrals. There was also a linear objective to be extremized.

Luckily the particular geometry used in my thesis was the one associated with the columns of the matrix instead of its rows. This column geometry gave me the insight which led me to believe that the simplex method would be a very efficient solution technique. I earlier had rejected the method when I viewed it in the row geometry because running around the outside edges seemed so unpromising.

I proposed the simplex method in the summer 1947. But it took nearly a year before my colleagues and I in the Pentagon realized just how powerful the method really was. In the meantime, I decided to consult with the great, Johnny von Neumann to see what he could suggest in the way of solution techniques. He was considered by many as the leading mathematician in the world. On October 3, 1947, 1 met him for the first time at the Institute Advanced Study at Princeton.

John von Neumann made a strong impression on everyone. People came to him for help with their problems because of his great insight. In the initial stages of the development of a new field like linear programming, atomic physics, computers, or whatever, his advice proved invaluable. After these fields were developed in greater depth, however, it became more difficult for him to make the same spectacular contributions. I guess everyone has a finite capacity, and Johnny was no exception.

I remember trying to describe to von Neumann (as I would to an ordinary mortal) the Air Force problem. I began with the formulation of the linear programming model in terms of activities and items, etc. He did something which I believe was uncharacteristic of him. “Get to the point,” he snapped at me impatiently. Having at times a somewhat low kindling point, I said to myself, “OK, if he wants a quickie, then that’s what he’ll get.” In under one minute I slapped on the blackboard a geometric and algebraic version of the problem. Von Neumann stood up and said, “Oh that!” Then, for the next hour and a half, he proceeded to give me a lecture on the mathematical theory of linear programs.

At one point, seeing me sitting there with my eyes popping and my mouth open (after all I had searched the literature and found nothing), von Neumann said:

I don’t want you to think I am pulling all this out of my sleeve on the spur of the moment like a magician. I have recently completed a book with Oscar Morgenstern on the theory of games. What I am doing is conjecturing that the two problems are equivalent. The theory that I am outlining is an analogue to the one we have developed for games.

Google, Chevron Build Mirrors in Desert to Beat Coal With Solar

Tuesday, May 27th, 2008

The headline is upbeat — Google, Chevron Build Mirrors in Desert to Beat Coal With Solar — but here’s an important bit of solar-thermal reality that intrudes:

Development slowed when Congress eliminated tax credits for alternative energy in the early 1990s. Laws put in place in 2005 give solar investors a 30 percent tax credit.

Lots of things start to look good with “subsidy goggles” on.

As gas goes up, driving goes down

Tuesday, May 27th, 2008

As gas goes up, driving goes down — which should surprise no one:

Compared with March a year earlier, Americans drove an estimated 4.3 percent less — that’s 11 billion fewer miles, the DOT’s Federal Highway Administration said Monday, calling it “the sharpest yearly drop for any month in FHWA history.” Records have been kept since 1942.
According to AAA, the national average price for a gallon of regular gas rose to a record $3.936. That compares with an average price per gallon of $3.23 last Memorial Day.

That’s a 22-percent increase in gas prices leading to a 4.3-percent decrease in miles driven — which might imply a slightly more than 4.3-percent decrease in gas consumption.

Sure enough, the price elasticity of gasoline demand is relatively inelastic, at 0.2. But we already knew that.

Cost of converting entire U.S. to electric cars? Zero.

Tuesday, May 27th, 2008

Philip Greenspun runs an interesting little thought experiment. Cost of converting entire U.S. to electric cars? Zero.

  • total oil consumption in the U.S.: 21 million barrels every day (CIA Factbook)
  • cost per barrel: $130
  • days in year: 365
  • total spent per year: $1 trillion
  • percentage of oil consumed by passenger cars: 40
  • total spent per year on oil for passenger cars: $400 billion
  • at 5% interest, how much we could we borrow and pay $400 billion every year in interest: $8 trillion
  • number of registered cars in the U.S.: 250 million (Wikipedia)
  • cost of a new electric car, if mass-produced: $20,000
  • value of a used car, if exported to Latin America or China: $5,000
  • cost to upgrade average existing American car to a brand-new electric car: $15,000
  • number that could be converted for $8 trillion: more than 500 million cars (i.e., twice as many as we have now)

Aztec Chinampas

Monday, May 26th, 2008

Wayne C. Gramlich, Patri Friedman, and Andrew Houser open their Practical Guide to Seasteading with a review of previous seasteading-like efforts, including the Aztec Chinampas rafts:

The floating gardens of the Aztecs of Central America, a nomadic tribe, they were driven onto the marshy shore of Lake Tenochtitlan, located in the great central valley of what is now Mexico. Roughly treated by their more powerful neighbors, denied any arable land, the Aztecs survived by exercising remarkable powers of invention. Since they had no land on which to grow crops, they determined to manufacture it from the materials at hand.

In what must have been a long process of trial and error, they learned how to build rafts of rushes and reeds, lashing the stalks together with tough roots. Then they dredged up soil from the shallow bottom of the lake, piling it on the rafts. Because the soil came from the lake bottom, it was rich in a variety of organic debris, decomposing material that released large amounts of nutrients. These rafts, called Chinampas, had abundant crops of vegetables, flowers, and even trees planted on them. The roots of these plants, pushing down towards a source of water, would grow though the floor of the raft and down into the water.

These rafts, which never sank, were sometimes joined together to form floating islands as much as two hundred feet long. Some Chinampas even had a hut for a resident gardener. On market days, the gardener might pole his raft close to a market place, picking and handing over vegetables or flowers as shoppers purchased them.

By force of arms, the Aztecs defeated and conquered the peoples who had once oppressed them. Despite the great size their empire finally assumed, they never abondoned the site on the lake. Their once crude village became a huge, magnificent city and the rafts, invented in a gamble to stave off poverty, proliferated to keep pace with the demands of the capital city of Central Mexico.

Upon arriving to the New World in search of gold, the sight of these islands astonished the conquering Spainards. Indeed, the spectacle of an entire grove of trees seemingly suspended on the water must have been perplexing, even frightening in those 16th century days of the Spanish conquest.

Needful Provision, Inc.

Monday, May 26th, 2008

David A. Nuttle is a former “GS-14 CIA Special Operations Officer” — which sounds impressive — who has gone on to perform humanitarian aid in dangerous places around the world.

He wrote the Volunteer Safety & Survival Reference as “a single, quick reference to the essential information needed to help volunteers survive natural and man-made disasters of all types”:

In the decades following initial publication, the earlier 1979 handbook was used by police and military personnel, Boy Scouts, Peace Corps volunteers, and volunteers for charities and NGOs (non-governmental organizations). From the many testimonials of these users, the safety and survival information herein provided helps to save lives. At the same time, this safety and survival guide acted to sustain volunteer operations in high threat areas.

Materials added to this handbook were designed to provide known safety and survival techniques for volunteers working in overseas areas with extensive armed conflict and related hazards. The need for a such information has been emphasized by increased numbers of volunteers being kidnapped and killed in countries like Iraq, Afghanistan, Sudan, and other nations with high rates of conflict. Moreover, most charities and NGOs seldom effectively train their volunteers in safety and/or survival techniques.

Airship Dreams

Monday, May 26th, 2008

The folks over at Dark Roasted Blend lead off their piece on Airship Dreams with the Air Ray “flying structure” — a concept airship that mimics the manta-ray:

Less sci-fi is the SkyFreighter from Millennium Airship, which is designed to haul 500 tons of cargo — including large machinery and equipment intact — at 100 mph for 6000 miles:

Of course, airships scream retro-future, and nothing is more retro-future than an atomic airship:

The best way to understand government

Monday, May 26th, 2008

The best way to understand government, Mencius Modlbug claims, is to assume everything you know about it is nonsense:

Growing up in the modern Western world, you learned that in all pre-modern, non-Western societies, everyone — even the smartest and most knowledgeable — put their faith in theories of government now known to be nonsensical. The divine right of kings. The apostolic succession of the Pope. The Marxist evolution of history. Etc.

Why did such nonsense prosper? It outcompeted its non-nonsensical competitors. When can nonsense outcompete truth? When political power is on its side. Call it power distortion.

And why, dear open-minded progressive, do you think your theory of government, which you did not invent yourself but received in the usual way, is anything but yet another artifact of power distortion, adapted to retain your rulers in their comfortable seats?

Probably because there is a categorical difference between modern liberal democracy and the assorted monarchies, empires, dictatorships, theocracies, etc, which practiced the black art of official mind control. The priests of Amun tolerated no dissent. They flayed the heretic, the back-talker, the smartmouth, and stretched his still-living flesh to crack and writhe in the hot African wind, till the hyena or the crocodile came along to finish him. But now they are all pushing up the asphodels, and Google hasn’t even thought about deleting my blog.

You think of freedom of thought as a universal antibiotic, a sure cure for power distortion. It certainly allows me to post my seditious blasphemies — for now.

But as a progressive, your beliefs are the beliefs of the great, the good and the fashionable. And as we’ve seen over the past few weeks, power can corrupt the mind in two ways: by coercion, or by seduction. The Whig, the liberal, the radical, the dissenter, the progressive, protests the former with great umbrage — especially when his ox is being gored. Over the past four centuries, he has ridden the latter to power. He is Boromir. He has worn the Ring and worked it. And it, of course, has worked him.

Today’s late Whiggery, gray and huge and soft, lounges louche on its throne, fastened tight to the great plinth of public opinion that it hacked from the rock of history with its own forked and twisted tongue. The mass mind, educated to perfection, is sure. It has two alternatives: the Boromir-thing, or Hitler. And who wants Hitler? Resistance is more than useless. It is ridiculous. The Whig cackles, and knocks back another magnum of Mumm’s.

And a few small rats wear out our incisors on the stone. Today we’ll learn the real principles of government, which have spent the last four centuries sunk under a Serbonian bog of meretricious liberalism.

Why bother to learn “the real principles” of government though?

The only defense I can offer is Vaclav Havel’s idea of “living in truth.” As a fellow cog in the global public supermind, you are bombarded constantly and from every direction with the progressive theory of government, with which all humans who are not ignorant, evil or both must agree by definition, and which makes about as much sense as the Holy Trinity. If you are ready to be the nail that sticks up and is hammered down, you can be a “conservative,” which ties up a few of the loose ends, and unties others. It also makes you a social pariah, unless most of your neighbors are named “Earl.”

From there, Mencius reiterates his thoughts on government, promoting what he cutely calls neocameralism — a term that made little sense to me until I read a bit about paleocameralism, which was the notion that the state should promote the collective prosperity in order to maximize its tax revenue, or, more accurately, its profit. It was also tied to some backward protectionist ideas, including the goal of autarky and immunity to trade wars.

Evernote: Software to help you remember everything, forever

Monday, May 26th, 2008

Farhad Manjoo writes about Evernote, which he describes as software to help you remember everything, forever:

If you ever have the pleasure of meeting the Silicon Valley entrepreneur Phil Libin, don’t be alarmed — or offended — when he asks you to pose for a photograph. And when you hand Libin your business card, expect him to take a picture of that, too. Libin might also snap shots of signs and placards around your office, billboards and movie posters he passes on the street, the labels of wine and sake bottles he encounters at restaurants, and untold other scraps that pass through his hands during the course of a day.

Libin is a big, friendly, mustachioed fellow, and though there’s a certain compulsion to the photographing thing, he isn’t actually crazy. He’s simply an ardent proselytizer of his product. Libin is the CEO of Evernote, a software company that’s building what has been called “a backup for your brain.”

All of Libin’s photographs — that shot of you, your office, the movie posters and the wine labels and the random notes — fly into his Evernote account. There, the company’s servers extract meaning from the image data, rendering Libin’s memories searchable.

When he wants to recall the cut of your jib, the name of the sake he ordered last week, the flight number for his recent trip to Vegas, or anything else, Libin can scan his Evernote account by date or keyword. If he searches on “salon writer,” for instance, he’ll come up with my business card, which includes those words. Because Libin can do this anywhere — from his computer or his mobile phone — the software has become, for him, a kind of Google for the real world.

Evernote is a forgetter’s dream, but the tool isn’t only for those of us gone mushy in the brain. In the same way that GPS forever changed our relationship to physical spaces, the permanent, constant archiving of both the monumental and the mundane in life will surely alter how each of us navigates the social realm. During a recent interview, I asked Libin whom he considers his target market. In the mode of a TV pitchman, he answered, “Everyone wants a better memory.” And yet this makes sense: Everyone forgets, and Evernote makes it so you never have to.

The quest for what Libin calls a “human memory extension” is at least a few decades old. In 1945, the engineer Vannevar Bush described a theoretical machine he called the “memex” (for “memory extender”), “a device in which an individual stores all his books, records, and communications, and which is mechanized so that it may be consulted with exceeding speed and flexibility.” More recently, Gordon Bell, one of the inventors of the Internet, has been obsessively archiving his life as part of a research project for Microsoft.

Evernote combines several recent tech innovations — digital photography, ubiquitous networking, cheap storage and powerful image processing — to make Gordon Bell’s archiving ways possible for ordinary people.

The service runs on a desktop program that works on both Macs and PCs, as well as a Web client for mobile phones (souped-up mobiles with good Web access work best).

The Sky Is Falling

Monday, May 26th, 2008

The Sky Is Falling, as it always has, but far more chunks may hit the earth than we realized:

Breakthrough ideas have a way of seeming obvious in retro­spect, and about a decade ago, a Columbia University geophysicist named Dallas Abbott had a breakthrough idea. She had been pondering the craters left by comets and asteroids that smashed into Earth. Geologists had counted them and concluded that space strikes are rare events and had occurred mainly during the era of primordial mists. But, Abbott realized, this deduction was based on the number of craters found on land—and because 70 percent of Earth’s surface is water, wouldn’t most space objects hit the sea? So she began searching for underwater craters caused by impacts rather than by other forces, such as volcanoes. What she has found is spine-chilling: evidence that several enormous asteroids or comets have slammed into our planet quite recently, in geologic terms. If Abbott is right, then you may be here today, reading this magazine, only because by sheer chance those objects struck the ocean rather than land.

Abbott believes that a space object about 300 meters in diameter hit the Gulf of Carpentaria, north of Australia, in 536 A.D. An object that size, striking at up to 50,000 miles per hour, could release as much energy as 1,000 nuclear bombs. Debris, dust, and gases thrown into the atmosphere by the impact would have blocked sunlight, temporarily cooling the planet—and indeed, contemporaneous accounts describe dim skies, cold summers, and poor harvests in 536 and 537. “A most dread portent took place,” the Byzantine historian Procopius wrote of 536; the sun “gave forth its light without brightness.” Frost reportedly covered China in the summertime. Still, the harm was mitigated by the ocean impact. When a space object strikes land, it kicks up more dust and debris, increasing the global-cooling effect; at the same time, the combination of shock waves and extreme heating at the point of impact generates nitric and nitrous acids, producing rain as corrosive as battery acid. If the Gulf of Carpentaria object were to strike Miami today, most of the city would be leveled, and the atmospheric effects could trigger crop failures around the world.

What’s more, the Gulf of Carpentaria object was a skipping stone compared with an object that Abbott thinks whammed into the Indian Ocean near Madagascar some 4,800 years ago, or about 2,800 B.C. Researchers generally assume that a space object a kilometer or more across would cause significant global harm: widespread destruction, severe acid rain, and dust storms that would darken the world’s skies for decades. The object that hit the Indian Ocean was three to five kilometers across, Abbott believes, and caused a tsunami in the Pacific 600 feet high—many times higher than the 2004 tsunami that struck Southeast Asia. Ancient texts such as Genesis and the Epic of Gilgamesh support her conjecture, describing an unspeakable planetary flood in roughly the same time period. If the Indian Ocean object were to hit the sea now, many of the world’s coastal cities could be flattened. If it were to hit land, much of a continent would be leveled; years of winter and mass starvation would ensue.

At the start of her research, which has sparked much debate among specialists, Abbott reasoned that if colossal asteroids or comets strike the sea with about the same frequency as they strike land, then given the number of known land craters, perhaps 100 large impact craters might lie beneath the oceans. In less than a decade of searching, she and a few colleagues have already found what appear to be 14 large underwater impact sites. That they’ve found so many so rapidly is hardly reassuring.

Other scientists are making equally unsettling discoveries. Only in the past few decades have astronomers begun to search the nearby skies for objects such as asteroids and comets (for convenience, let’s call them “space rocks”). What they are finding suggests that near-Earth space rocks are more numerous than was once thought, and that their orbits may not be as stable as has been assumed. There is also reason to think that space rocks may not even need to reach Earth’s surface to cause cataclysmic damage. Our solar system appears to be a far more dangerous place than was previously believed.
A generation ago, the standard assumption was that a dangerous object would strike Earth perhaps once in a million years. By the mid-1990s, researchers began to say that the threat was greater: perhaps a strike every 300,000 years. This winter, I asked William Ailor, an asteroid specialist at The Aerospace Corporation, a think tank for the Air Force, what he thought the risk was. Ailor’s answer: a one-in-10 chance per century of a dangerous space-object strike.

I can’t help but think of Lucifer’s Hammer and the challenge of bootstrapping society.

How to really change your kid’s behavior

Monday, May 26th, 2008

Alan E. Kazdin explains how to really change your kid’s behavior — because yelling doesn’t work, and neither does quietly explaining why what they’re doing is wrong:

You begin by deciding what you want the child to do, the positive opposite of whatever behavior you want to stop. The best way to get rid of unwanted behavior is to train a desirable one to replace it. So turn “I want him to stop having tantrums” into “I want him to stay calm and not to raise his voice when I say no to him.”

Then you tell the child exactly what you would like him to do. Don’t confuse improving his behavior with improving his moral understanding; just make clear what behavior you’re looking for and when it’s appropriate, and don’t muddy the waters by getting into why he should do it. “When you get mad at your sister, I want you to use words or come tell me about it or just get away from her. No matter what, I want you to keep your hands to yourself.”

Whenever you see the child do what you would like, or even do something that’s a step in the right direction, you not only pay attention to that behavior, but you praise it in specific, effusive terms. “You were angry at me, but you just used words. You didn’t hit or kick, and that’s great!” Add a smile or a touch — a hug, a kiss, a pat on the shoulder. Verbal praise grows more effective when augmented via another sense.

China: Why Western B-Schools Are Leaving

Sunday, May 25th, 2008

China: Why Western B-Schools Are Leaving:

All foreign schools have to collaborate with a Chinese university and contend with the local education authority and the Education Ministry, which exercise tight control over joint ventures. But the biggest problem is that relatively few Chinese have the requisite language skills to handle an all-English curriculum. And with the cost of these programs averaging $50,000, companies send only those with real potential. “I’ve done the math several different ways, and I always get the same result: It’s a really small market,” says Patrick Moreton, managing director of the program offered by Fudan University and the Olin School of Business of Washington University in St. Louis, one of the more successful ventures. The five top programs in Shanghai together have only 230 students enrolled.

HyperCard: What Could Have Been

Sunday, May 25th, 2008

Leander Kahney talks to Bill Atkinson, the programming genius behind MacPaint and much of the original Macintosh operating system, about HyperCard: What Could Have Been:

Atkinson, now a successful nature photographer, created a string of groundbreaking applications during a long career at Apple.

But he feels that one of his greatest achievements, the HyperCard multimedia programming system, failed to live up to its potential.

HyperCard is a programming environment that can create applications as diverse as utilities and games by linking “cards” arranged into “stacks.” Commands are executed through a natural-language scripting language called HyperTalk.

The software has been phenomenally successful and highly influential. But Atkinson feels that if only he’d realized separate cards and stacks could be linked on different people’s machines through the Net — instead of cards and stacks on a particular machine — he would have created the first Internet browser.

“I have realized over time that I missed the mark with HyperCard,” he said from his studio in Menlo Park, California. “I grew up in a box-centric culture at Apple. If I’d grown up in a network-centric culture, like Sun, HyperCard might have been the first Web browser. My blind spot at Apple prevented me from making HyperCard the first Web browser.”

HyperCard was conceived and created in the 1980s, almost a decade before the explosion of the Internet.

“I thought everyone connected was a pipe dream,” he said. “Boy, was I wrong. I missed that one.”

Atkinson recalled engineers at Apple drawing network schematics in the form of a bunch of boxes linked together. Sun engineers, however, first drew the network’s backbone and then hung boxes off of it. It’s a critical difference, and he feels it hindered him.

“If I thought more globally, I would have envisioned (HyperCard) in that way,” he said. “You don’t transfer someone’s website to your hard drive to look at it. You browse it piecemeal…. It’s much more powerful than a stack of cards on your hard drive.

“With a 100-year perspective, the real value of the personal computer is not spreadsheets, word processors or even desktop publishing,” he added. “It’s the Web.”

US Retail Gasoline Priced in Gold

Sunday, May 25th, 2008

As Nick Szabo has pointed out, if you look at US Retail Gasoline Priced in Gold, it hasn’t changed in price much at all.

How Are Humans Unique?

Saturday, May 24th, 2008

Michael Tomasello, co-director of the Max Planck Institute for Evolutionary Anthropology, explains how humans are unique:

[The human 2-year-olds] performed about the same as the apes on the tests that measured how well they understood the physical world of space, quantities and causality. The children performed better only on tests that measured social skills: social learning, communicating and reading the intentions of others.

But such social gifts make all the difference. Imagine a child born alone on a desert island and somehow magically kept alive. What would this child’s cognitive skills look like as an adult — with no one to teach her, no one to imitate, no pre-existing tools, no spoken or written language? She would certainly possess basic skills for dealing with the physical world, but they would not be particularly impressive. She would not invent for herself English, or Arabic numerals, or metal knives, or money. These are the products of collective cognition; they were created by human beings, in effect, putting their heads together.

When you look at apes and children in situations requiring them to put their heads together, a subtle but significant difference emerges. We have observed that children, but not chimpanzees, expect and even demand that others who have committed themselves to a joint activity stay involved and not shirk their duties. When children want to opt out of an activity, they recognize the existence of an obligation to help the group — they know that they must, in their own way, “take leave” to make amends. Humans structure their collaborative actions with joint goals and shared commitments.

Another subtle but crucial difference can be seen in communication. The great apes — chimpanzees, bonobos, gorillas and orangutans — communicate almost exclusively for the purpose of getting others to do what they want. Human infants, in addition, gesture and talk in order to share information with others — they want to be helpful. They also share their emotions and attitudes freely — as when an infant points to a passing bird for its mother and squeals with glee. This unprompted sharing of information and attitudes can be seen as a forerunner of adult gossip, which ensures that members of a group can pool their knowledge and know who is or is not behaving cooperatively. The free sharing of information also creates the possibility of pedagogy — in which adults impart information by telling and showing, and children trust and use this information with confidence. Our nearest primate relatives do not teach and learn in this manner.

Finally, human infants, but not chimpanzees, put their heads together in pretense. This seemingly useless play activity is in fact a first baby step toward the creation of distinctively human social institutions. In social institutions, participants typically endow someone or something with special powers and obligations; they create roles like president or teacher or wife. Presidents and teachers and wives operate with special powers and obligations because, and only because, we all believe and act as if they fill these roles and have these powers. Two young children pretending together that a stick is a horse have thus taken their first step on the road not just to Oz but also toward inhabiting human institutional reality.