A story about the Traveling Salesman Problem

In Itamar Moses’ Completeness, the lead character wrestles with three things: 1) Love 2) Biology and 3) The Traveling Salesman Problem. I was drawn to this play because, in my past, I have wrestled with those same three things. Love led to my wife. Biology led to my children. But the Traveling Salesman Problem nearly got me killed by gangsters.

Here’s how it happened:

In 1992, I had despaired of being able to wait tables. I switched to temp work which I morphed into software consultancy by wildly exaggerating my technical expertise in the field of computer science. To be clear: I had a BA in theater arts. My computer skills were entirely self-taught— the result of me tinkering obsessively with my Apple IIe, and later, my Macintosh SE 30 (2 megs of RAM!). Sure, I had taught myself a smattering of programming languages and algorithmic principles, but I had never completed a single computer class.

Luckily for me, it was the dawn of the computer age, a lawless wild west. It was the kind of world where a major bank would hire a 24-year-old to write a system to manage millions of dollars of transactions. Because they had no idea what they were doing. And I could sound like I did.

So, by 1994 I had a thriving little business going. At that time, I had hooked up with a company that made mapping software. They brokered a contract between myself and a guy named… well, we’ll call him Louie. Louie ran a consultancy business that was in charge of helping bottled water and laundry companies determine optimal delivery routes for their trucks. Keep in mind that this is all years before the modern internet, GPS navigation, google maps, etc., In 1994 this was fairly new territory.

When Louie explained the parameters of the job, I thought it would be easy: route trucks. Calculate the best routes based on a series of observational data points his team had gathered about travel time, traffic, etc. Louie explained that the program wouldn’t need to tell the drivers how to get from point A to point B to point C. He just wanted to know the best routes.

"Cool," I thought, "because figuring out which roads to go on would be hard." Figuring out the shortest trip would be easy. It's just addition. There were only between 200 and 1800 stops per data set and I had access to 486 chipsets!

"This is a plan?"

Now, at the time, the way I would work was this:

A) Take the job.

B) Bill the client what I thought was a lot of money, but which I know now was actually laughably small.

C) Go to the library and/or bookstore and research up the relevant computer algorithms for the things I didn't know— there was a lot of stuff I didn’t know… optimal sorts, string processing soundex theory, etc.. The books would have a lot of math, which I also didn't know, but I would read the code and adapt it. At the time, the internet and web didn't exist, but Borders had over two dozen books, IN STOCK of these algorithm collections.

D) Code the software

So, step (A) went great. And they agreed I could have six months to write the software which was, obviously, AN ETERNITY. So, I took the deposit, and bummed around for four weeks doing very little. I thought about the problem a bit, but no good solution popped into my head. This was odd, as I could normally count on my brain to come up with at least the outline of a sensible approach.

Finally, I had to try something. So, I knocked up a quick proof of concept to generate all the possible routes and then pick the shortest one. This took about four hours to write, but when I ran it, it just … froze. I put in some debugging code and found that it was running, but that seemed to have a lot more calculation to do than I had thought. Hmmm…

Noooooooo problem. Obviously, it was time to go steal the logic of my program from some computer science graduate's book at Boarder’s Book Store. But when I browsed through the books, nothing leapt out at me. This was strange because it seemed like it ought to be an obvious and common algorithm. But I couldn't figure out how to find it. I skimmed Donald Knuth, nothing. I read the indexes of every book available looking for… something… anything that sounded plausible. No dice. Of course, what was the problem even called? How could I look it up?

A month goes by. I'm starting to get nervous. I take another month to code the front end of the application, but it still doesn't do anything like, you know, route trucks. Louie finally wants to see a demo. A reasonable request, but one I can't provide. So, I copy the code onto a floppy disk, rub that floppy disk with a strong magnet, and drop it in the mail to him. Louie calls. “The file’s corrupted. I couldn’t open it.”

“Really? That’s strange.” I say. “I’ll get another copy in the mail to you right away”

Now I'm really panicking. I have accounted for accurate distance calculations. I have researched and coded calculations that account for the minor curvature of the earth to distinguish between delivery times. BUT, nothing I code can execute in the 45 minutes allowed for the software to process all 1800 stops each and every morning for the water companies to deliver their goods efficiently.

Then, I find a reference in an index to something called the "Traveling Salesman Problem". And there's a graph on the second page showing multiple points with cities labelled with weights for travel time for a dot labelled "salesman.”

I’ve found it! “Hey!” I yell to my wife from the floor of the book store. “This sounds like MY problem…”

I buy the book ($50!) and go home to read the relevant chapter. To this day, I can still remember the first line.

The traveling salesman problem has never been solved.

Uh-oh

It's hard to describe the dropping sense of panic I had when I read that. I read the entire chapter. Yup. Never been solved. Can't be solved. There's a graph showing the NP-1 curve, which I finally understand. My code is due in one week. Louie is coming to Chicago to get it. I have SPENT his deposit, and have no other income to pay him back.

Now is a good time to mention that Louie was connected. Like gangster connected. During our time together he had taken me to a laundry convention in which he paid for everything, including the $18,000 booth fee, in cash. After that, he had me take him on a tour of the area. I drove while he pointed out the houses of retired mafia members and then snorted cocaine from the dashboard.

So I wasn’t looking forward to telling Louie that I didn’t have his software. Or his money.

What followed was a desperate four day period in which I, sleeping about 2 hours a night, managed to code something "good enough" to demo. As Elliott, the lead character in Completeness points out, the "good enough" solution is just that. Not perfect, but not bad.

So, the software was polished enough for sale but Louie seemed to be out of money.  He had a copy of the executables, but the code was put in escrow awaiting the remainder of my fee. Louie protested, claiming that my delay had cost him. Things between the contracting companies got heated. Louie then went around the lawyers to contact me directly and demand the code. I refused to give it to him without the rest of the payment. That’s when Louie called me at 2am and screamed into the phone, "You pathetic little fuck; give me my fucking code or I am coming there with an ice pick and a body bag you motherFUCKER and I and my friends will fucking waste you, scoop you up and dump you in a fucking dumpster."

Unfortunately for Louie, this was my second death threat that year (the other was from an actor who had a mental breakdown). My life in the theater had made me perfectly comfortable with people threatening to kill me.

And perhaps Louie would have. But after that 2am call, he disappeared. Really. Gone. The company that introduced us hired a private detective to try and find him with no result. The remainder of my fee and my "solution" to the traveling salesman problem are still in escrow, I believe.

And fifteen years later, Completeness is written. So, of course, I have to direct it. Because in the real world, the unsolvable problems can get you killed. But in the theater, the unsolvable problems can show you how to live.

Itamar Moses on COMPLETENESS

Here's the tidied up transcript of a phone interview I had with Itamar right after we held our first read-thru for Completeness.  --jw

Jeremy Wechsler: I know you had this really long development process because I remember you were getting ready for the workshop of Completeness when we met.

Itamar Moses:  When was that?

2009?

Yes, that’s right.  I was working on the play for a few years. The first real workshop was at South Coast Rep. at the Pacific Playwright Festival.  In May, 2010.

We spoke immediately after the workshop and we were talking about the exciting part of trying to parse statements from the artistic director.  “If we workshop it, when we produce it…?”

Right, right right!  It was originally a commission from the Manhattan Theatre Club. After that workshop, South Coast Rep was very interested but first we had to work out whether Manhattan Theater Club wanted to produce it, because as the commissioning institution they had the right of first refusal. For a while it wasn’t clear where it was going to be first, where it was going to go next.  But it all kind of worked out. 

When did you start writing it?

The commission that turned into Completeness I got from Manhattan Theater Club from as far back as, I’m going to say 2005, 2006?  The commission was from the Sloan Foundation, and they only commission plays about math and science.  I would not have taken one had it not been the case that I already had a science related idea. 

I had been thinking about the Traveling Salesman Problem already; I first learned about it in an electrical engineering course that I took in college.  I know… “You took an electrical engineering course?”

I took Electrical Engineering 101. It was one of those classes you had to take as a requirement to graduate. And people were like, “Why didn’t you take Geology 101?” (Which I did) or Astronomy 101, but Electrical Engineering 101 was a class called “The Digital Information Age.”  (The final project was to write your own web page in HTML; it was not a particularly challenging electrical engineering course.) The TSP came up as the reason why a long-enough random series of numbers and letters is impossible to crack in the context of how security works. If you run an algorithm that runs every possible combination, it seems like that should work, but in fact there are quickly so many combinations that it won’t work because it will take the computer fifty million years to try it. It stuck in my head. Maybe I liked the name, “Traveling Salesman Problem?”

I didn’t know the problem well enough to write something evocative about it but when I got offered the Sloan Commission, I thought, “Here’s my opportunity! Here’s my excuse to investigate this problem, see if there’s a play in it.”  As far back as 2006 there’s some prospectus for MTC claiming ‘I want to write about a guy who’s trapped on the Traveling Salesman Problem, not realizing that that problem is at work in other aspects of his life’, which is in some ways not far off from what the play became.

To keep it light I thought it should be a romantic comedy and should make the other subject as seemingly distant from computer science as possible: the messiest human stuff, getting together and breaking up. So that idea goes back as far as 2006.  I had a lot of seeds based on a lot of different relationships, but it never really cohered into a play. And I didn’t really hit on a structure that felt like it contained a complete play until years later when I was talking to you, 2009, and I thought, “Oh, this is the structure.” I started working it out to get it ready for that workshop in 2010.

There is such an intricacy to the structure of the end result. This love for theatrical structure is one of the things that had invited so many comparisons to Stoppard over the years.

Yeah, I’m aware of structure as a way to implement the meaning, but I like to be playful with it.

I think one of the fun things with this play is how the structure ties into both the metaphor of the problems with human relationships and eventually acts as a sort of dramatic element itself. It obviously reminded me of The Four of Us and the way it embraces theater itself as a space in which this event his happening.

The structure of Completeness­, on a dramaturgical level, the scene by scene—and I don’t want to give away the story—but the way the pairings work, the way the couples break up and get together, it’s actually not much more complicated than, Boy meet Girl, Boy loses Girl, will Boy get Girl back? [laughs] The intricacy of it has to do with the layering, like, how many things are going on at once? At any given moment a person could be saying something about romance that could apply to the science and also applies to theater. And vice-versa. So there’s this three level paralleling of everything that… is not as hard to achieve as it sounds. It only works if it follows from the storytelling. In working on a play like this I discovered that when figuring out what the next scene should be, or the next moment, what should happen next in the story should allow that layering to happen organically. What the person would legitimately say next in explaining their scientific idea or in trying to negotiate with their romantic partner, what they would actually say in the real world would be something that is layered and would have those echoes. And that’s often how I would know I was on the right track.

You talked about how you had these fragments of scenes from real life , do you keep a running notebook of dialogue snippets that you want to use?

Sometimes, usually not dialogue. There might be a sentence fragment or two that I might keep in a text document in my computer, sometimes it would just be general one, that’s like “random ideas” or sometimes it’ll be specific like “play about my family” and I’ll just throw things in there as they occur to me.  But—this is also something I should be careful about as I get older—I also have a steal trap memory for moments or dialogue, especially if something has an emotional impact at the time. I can recount entire conversations pretty accurately. What sticks in my brain, I end up using because the fact that it’s stuck in my brain means I’m compelled by it or it has some meaning or energy.

How did you come across the protein interaction part, unless you took Biochemistry 101?

I did not.  That was much harder.  But that was much harder for a more practical reason.  The Traveling Salesman Problem is a specific problem in computer science. I knew I wanted it to operate as a kind of central metaphor before I really began the play.  So what that means is: I don’t have to get a BA in computer science, I don’t have to read books on general computer science. All I have to do is make sure I understand the Traveling Salesman Problem and whatever scholarly things around that to make it work. But in trying to find a complimentary scientific focus for Molly, that was much more difficult because I couldn’t randomly select some other problem. She has to be working on something just as specific-

Right.

It would feel imbalanced. I couldn’t just randomly pick another scientific focus, I had to pick the right one.  So I had this one fixed variable, which is the traveling Salesman Problem and then this, like other unknown variable.. From the entire annals of science, I have to find the idea!

Easy!

I knew right away I could narrow it down. I knew I didn’t want it to be a really soft science. There was an early version where I thought maybe she’s a botanist, and my girlfriend was like “So the girl is doing some girl science?” And I was like, “You’re right, let’s not do that.” So I wanted it to be an equally hard science, but I wanted it to deal with real world stuff.  So I knew it was going to be chemistry or biology. Those involve math, especially chemistry. But they involve math as a byproduct or how real stuff interacts in the real world. And so I just started reading generally about biology and I came to a number of different focuses for Molly, none of which really clicked in for me.

Ultimately, I had to talk to molecular biologists.  The Sloan people were very helpful in that way. They put me in touch with the chair of molecular biology at Columbia and one of his colleagues and we went for a drink in the East Village and I just grilled him for two hours while taking notes, and that was the turning point. I could lay out to them specifically what the dilemma was. 

What I needed, first of all on a plot level, what could a molecular biologist grad student need help with from a computer scientist to get that first inciting incident going. We talked about that, and what is the cutting edge in the field. What are graduate students working on? As soon as this idea of protein interactions networks came up–as an early test you do to find what bonds with what­–I thought, “There it is.” It was one of those things where your right brain knows instantly “That’s it. That’s going to work.” Then it’s the very slow process of your left brain catching up. Why does that work? And how does that work?

So then I knew what to read about specifically. I didn’t have to learn about all of molecular biology. I could be like “ok, what is a yeast two hybrid screen? What is the end goal of all this work?” It was also useful just hear how molecular biologists talk about this work. There are certain lines in the play that are direct quotes from those two professors, like, we were talking about the eventual goal of mapping the entire protein interactome of humans and I said, “well, um, how much have we mapped?” He said, “Less and less every day.” That went right into the play. The joke that Elliot tells in the final scene, one of the professors told me as a way to illustrate their process. So it was useful to engage with them as people but also to pick their brains.

When you look at the pictures of the Traveling Salesman Problem and the pictures of the proteins, it’s amazing how similar they look.  Were you totally excited by the parallel?

Yes and no. I was super excited but I also have enough experience with this stuff to… if the audience was going to experience that parallel they were going to go to a very very deep level where no one was going to talk about or write about after seeing the play. But yes, I was excited by it because it made me feel like I was on sturdy ground. I had hit on a genuinely accurate analogy. There was a bedrock of sound ideas under the play. 

When we did the first read-thru last night, we were struck by this climactic moment that abruptly broadened the scope of their problems to a generational level. And it really brought… it unified the human scale into a larger context. The whole play has these mathematical problems that could almost model the real world but never entirely, and we see how this problem is getting mapped out to a cultural dilemma. I have been thinking a lot about my 20s. And how sucky they were. But also, how does it suck in a different way now? Your characters are rarely confused about what they’re feeling.  They’re pretty self-analytical and have have the ability to pick themselves apart without knowing any real motivating forces.

Right.

You write about this process not infrequently.  Do you think this is a generational thing?

I think its two different things. I think I am a kind of person that is able to intellectually understand something and maybe even articulate it, before my emotions have caught up. And so, that means of couple of things: one, that it often doesn’t help. You can trick yourself into thinking that you understand the problem, but until you understand it emotionally or viscerally, you don’t really understand it; you don’t know what you actually want. That’s not a generational thing. There’s a different vocabulary now, but there has always been that divide: on one side, the people who tend to intellectualize things and try to articulate them, and on the other side, people who feel something and then act.  Later, they can understand why they did it. I think there have always been those types of people.

In terms of the generational thing, I think, yeah… one of the critics in New York specifically dinged me for that line at the end. He felt the play ‘was really about Gen Y special pleading and they have some special problem but all I can say is join the club.’ To me that was a totally wrong interpretation of that moment. It wasn’t that we’re the only generation that has a hard time making sense of romance, its just we have a hard time making sense of it, in a way that’s specific to our generation. And the way you experienced that line in the reading and the way I intended it, was an opening and reaching out acknowledging all future generations are going to have a problem. That harkens to the first thing Elliot does for Molly is write a genetic algorithm where every generation learns some things, but it’s an optimization process: it acts for some goal it never reaches, And so Molly is just articulating the point that this generation is at on this curve, so its not to say, ‘well, this is really tough for us’, its saying, ‘we’re in uncharted territory’ and I think we are. Whether your approach to that is leading with your head or leading with your heart or trying to fuse the two, we’re in uncharted territory.

I always thought writing a romantic comedy would be super fun because you could pick out the previous experiences but make it turn out the way you want it to. Do you find it makes you more optimistic about love or more calculating because you have to construct the spots where it didn’t go awry?

It’s a chicken and egg question because my romantic life has calmed down and stabilized a great deal in my 30s as opposed to in my 20s. Whether I’m able to write about things that actually might seem like they might work out because I have experienced stuff that has worked better or writing about it has helped me get to that place, the answer is probably both and neither. I’m probably just tired also. I don’t know.  I definitely remember feeling the opposite in my 20s – I could write relationship scenes in my 20s about things not working, and that to write something that was working felt like I was faking it, making something up, because I genuinely didn’t believe in it. And now I feel like I get it more. Although its funny. The end of Completeness is kind of a litmus test.  It’s not clear what’s going to happen. I know what I intended and I feel about it. But I have people come up to me after the play and say how refreshing it is to see the opposite.

I think the play suggests this is their first experience of a genuine adult love affair, they had their first attempt where they could imagine a life, and we can see the fist two steps, but there’s lots left for them to work through. So – there have been two productions. When you see your plays multiple times before you cast them off to roam the wild, how different to the productions feel to you? Are there facets of the play that get pulled out in one version?

Yeah because there are always different connections in a play, a lot of which you intend and a lot of which just happen. And a different, set, different staging, different emphasis on pauses or a different actor can bring out all kinds of things.  Things like pace…  like with Four of Us there’s a fair amount of elasticity in those scenes.  There are all kinds of different ways to do it.  And different subtexts can come in, different moments can be solved because the physical space is worked differently. Something that was always a huge gimmie laugh in the last production, is suddenly not funny, because the actor is hilarious but in a different way.

In this case its one of the things the play is about: on the metaphorical level as theatre as an art form, about the relationship, and about how the relationship between a script and a live performance is the same between a computer program and molecules actually interacting in a Petri dish. A script can give you certain things and then the live event is unpredictable and certain other things can happen. Both those impulses are in me, to control everything, make it production proof, whatever that means, and do it exactly the same way, but that turns out to be a mistake because its only in not quite aiming for that that you create something that can work in all kinds of different contexts.

Do you find there is an audience that enjoys this play particularly?

Audiences in their 20s seem to really enjoy this play. Because it speaks to something that not a lot of plays speak to in quite this focused a way. Someone told me that after it was produced in New York all the second and third year acting students at Julliard became obsessed with it and started doing scenes from Completeness in their acting classes because it gave them an opportunity to play characters that thought and talked like they do.  So that’s one big sub group, but that’s not to say to that older audiences don’t enjoy the play.  There are two responses I’ve gotten from older audiences. One is ‘now I finally understand what my kid are going through, they’re creating all these relationship problems from themselves and now I finally know what they’re going through.’ Another one is ‘It’s always been this way. We had our own versions of exactly this’.  But getting that this is the next generation dealing with the same problem. And science geeks seem to appreciate it.

Yup.

Because the science in the play is accurate. And I don’t think they’re used to seeing that and also as being seen as people who sleep with one another. Which is true! Otherwise where would new scientists come from?