Optimal Blending of Cocaine

There’s an accompanying cocaine blending optimization spreadsheet for those who’d like to follow along with todays post.

Even though I’m back in Atlanta, I think I’m going to keep this thing going. It’s been a wild past three days, and I’ve gotta unload this story before I forget it.

I rolled back into Atlanta last week with my head held high. Actually, I kept everything pretty high for about the whole next week. A lot of the other guys in the house are straight up boozy, like Jimmy Buffet listening, polo-shirt-loafer-kakhi-short wearing frat boys. I don’t know why I got the 80s Wall Street gene instead, but I’ve never been into drinking. And weed is the worst! Probably because I’m type A, and weed and type A have never mixed. But a little Henry VIII, now give me a line of that and I’m golden.

Don’t get me wrong. I know I’ve gotta quit this junk eventually. And I know it’s incredibly 80s, but hell, I’m a huge fan of Holy Ghost! so I figure I’m in pretty good company.

I tell you all this to set the scene for the night I roll back into town. Graham and I head back to the club. Dude just got dumped by his girlfriend of all of two weeks because she couldn’t get over his weird looking Pectus Excavatum. I don’t blame her. Dude’s funny-looking. So me and Graham are at the club, and I’ve been doing lines off the back of a toilet all night long, so I’m feeling a combination of awesome and kinda grossed out from the number of pubes that I may have snorted as collateral damage. Well, sure nuff, my stash runs dry. so I ring Andre who’s hooked me up since Freshman year.

Andre’s ridiculous. Straight up stereotype. He rolls up in his Escalade out in back of the club on Means Street. Color pearl. Rims so big they look like flying saucers. He slides me two grams from out the driver’s side window, and I reach for the wad of cash in my back pocket.

Oh shit, I think to myself. Nothing but lint. I search all my pockets. Nothing. My wallet is gone. At this point, I’m freaking out.

“You get me to come all the way out to the club, and you don’t even have cash?” he asked.

I told him to wait, and I tried to go back in the club. No ID. The bouncer’s a complete dick about it. I tell him I was just inside, but he’s not having it. I tell him I must have dropped my wallet in the bathroom. Well, he just mutters something about looking for it later and shoos me on my way.

I walk back to Andre’s truck, and he’s giving me an impatient stare from behind the sunglasses he’s wearing even though it’s after midnight. I explain to him that I’m wiped for the night and try to hand him back his product, but he’s not having it.

“Hell no. I ain’t taking that back,” he says.

“But I can’t pay for it,” I pleaded.

“Then you’re going to work for it,” he said.

Andre smiled and put a phone to his ear. He let it ring and when someone answered, he rolled up the Escalade window and spoke to whoever was on the other end of the line for a few minutes.

When he hung up, he rolled the window back down.

“Get in the truck,” he said.

“Uhhh,” I said. I couldn’t think of what to say, but the idea of getting in an Escalade with my coke dealer sounded like a truly bad idea.

Suddenly Andre raised a piece of metal that glinted in the faint light coming from the mothy lamps scattered down Means Street. I could make out the barrel of a pistol.

“I said, get in the truck.”

What was I supposed to do? I just nodded and opened the door behind him.

“What does this look like? A taxi?” Andre barked at me, “Get in the passenger side.”

I just nodded and went around to the other side. My stomach had sunk so low I could feel it in my toes. And I was coked out of my head already, so my heart was humming like a helicopter.

We drove in silence for half an hour. Andre jumped on the interstate and headed south toward Hartsfield. He got off in Hapeville and did a bunch of turns that in the dark confused the hell out of me. After about ten minutes we pulled up to a gravel driveway and drove down the bumpy road for what seemed like a mile. At the end was nothing but a dimly lit trailer.

“Oh shit,” I thought to myself. A trailer in the middle of nowhere. I’m so dead. I’m so screwed. I was kicking myself and launching Hail Mary prayers toward heaven between each panicked thought.

“Go inside,” was all Andre said.

“You’re not coming?” I asked.

Andre smiled, “Nope. This is all you.” Andre motioned with the gun for me to get out of his car. I opened the passenger door and stepped down onto the gravel drive.

For a moment, I entertained the thought of running. But I knew in my state I’d just trip through the woods until someone caught up with me. No, Andre had said that I was going to “work for it.” That didn’t sound like I was going to die.

I walked to the old Airstream and opened the door. The light inside was dim, coming from a single battery-powered Coleman lantern, and the interior was cleaned out except for a single old wooden kitchen table. At the table sat a man.

I don’t know what I was expecting, but it wasn’t this guy. Maybe someone bigger, someone more scary. Some kind of Bond villain or something. Instead, the man sitting in front of me was old. Like sixty. He had a gray beard cropped close and a well-trimmed haircut. He reminded me of Jonathan Goldsmith from the Dos Equis commercials oddly enough.I swear this is what he looked like

Without saying anything the man motioned for me to grab the seat across from him.

I grabbed an old chrome and vinyl diner chair and took a seat. It was muggy in the trailer and a few moths buzzed about the dim lantern light. I couldn’t tell if my flop sweat was from panic or humidity.

“Mr. Sheffield, I presume?” the man asked in an oddly crisp, bass voice.

“Correct,” I replied.

“Andre tells me that you are unable to pay for the services we provide,” he said.

“I, I lost my wallet, but I,” the panic rose in me a little as I tried to explain myself. The man rose a hand.

“Please, I’m not here for an explanation, and I mean you no harm. I just have some questions for you,” he added.

“OK,” I say.

He folded his hands in front of him on the table.

“Andre tells me you’re a Georgia Tech student. Said you’ve been going there a few years,” the man said, “True?”

“Yes sir,” I said, “I just finished my junior year.”

“Major?” he asked.

“Well,” I swallowed, “I’m dual math and CS.”

The man nodded, “That’s good. GPA?”

“3.93,” I said.

“Out of 4 or 5?” he asked.

“Georgia Tech goes to 4.”

The man nodded, “Good, good.”

He leaned back into his chair and smiled.

“I’d like to apologize for Andre’s aggressive tactics, but you must understand that recruiting in my line of work is complicated when I have a need for someone besides a foot soldier.”

“Recruiting?” I asked.

The man smiled, “I’m sorry. I haven’t properly introduced myself.”

He held out a hand for me to shake.

“My name is Victor, and let’s just say I operate the organization that Andre’s a part of.”

“OK,” I said. I was feeling a little relieved. This guy didn’t seem to want to hurt me, and we seemed to be talking business although I wasn’t sure what about.

“So how can I help you?” I ventured to ask.

The man smiled his shit-eating grin again.

“Oh, if you’re any good, then there are all sorts of ways you can help me. Consider this your interview, and in exchange for your assistance, I’ll let you keep those two grams of my product. For free.”

I thought about it a moment, “Sounds fine.”

“Then let’s get to it,” said Victor. He reached down to the floor and lifted a briefcase to the table. Opening it, he placed a gun on the table, and again I felt nervous. On top of the gun he set a stack of papers. Finally, he withdrew a laptop from the case and placed it in front of me.

“So I’m going to be honest with you,” said Victor, “I run all sorts of products through the U.S. and Canada. Coke only makes up 12% of my revenue, but it’s extremely high margin.”

This guy was starting to sound oddly professional.

“Now, I’ve got a competitor in the Northwest who’s releasing his own product into the market at eight thousand dollars a kilo to the street,” he said as he brushed his parted hair back.

“That’s how much it costs me to blend,” he added, “If I release my stuff at that price, I’d be making nothing. And I’m not interested in a price war per se, but I know if I can get my price down a little below that with my current specs, I could beat them on both quality and price.”

“I understand,” I nodded, “So you need to get your costs down?”

The man nodded, “I’ve been cutting my coke a certain way for going on a decade now. It’s worked great, but it’s a bit costlier than I need I think. I’d like you to help me find a way to cut it for cheaper.”

The situation was looking brighter. This was indeed something I might be able to help with.

“What do people generally cut coke with?” I asked.

Victor smiled, “It fascinates me that someone as intelligent as you would put something up their nose without knowing the ingredients.”

I shrugged, “Well, I figured at least most of it was coke, and when you’re doing lines off the back of a toilet, what came blended in the coke is the least of your worries.”

“That’s true,” said Victor. He slid a sheet of paper over to me. It was a spreadsheet with a list of ingredients and specifications. Here’s a picture of what it looked like.

Cocaine additive specs

“OK, so I’m seeing coke, meth, some pain killers, Ritalin, some sweeteners, and some other stuff,” I said.

“A bunch of white powders we can choose from,” said the man, nodding.

“And these columns to the right of the price. Can you explain these?” I asked.

“Those columns are how much one gram of the substance affects a kilogram blend compared to a standard solid kilogram of coke.”

He pointed to the sheet, “So, for instance, while coke naturally gives 1% of the buzz in a kilogram per gram, meth gives twice that, and Ritalin gives half a percent.”

“While stuff like talcum powder doesn’t give any buzz,” I said, “but a gram of it ups bitterness and texture by 2% from pure coke.”

“Exactly,” he nodded, “By texture, we mean size of the particles in the blend. Bitterness and sweetness can both be smelled and tasted as the senses are related. They basically cancel each other out. Comedown is a big deal because headaches and other adverse effects discourage repeat buyers. And addictiveness is naturally a big part of what we do. Free marketing. Behavioral targeting if you like.”

The man smiled a toothy smile at this last bit.

I grabbed a ballpoint pen that Victor had laid on the table and began to take notes.

“So the objective then is just to mix this up to make the cheapest kilogram?” I asked.

Victor nodded, “While staying inside the specs that have worked in the past.”

“Can you rattle those specs off for me?”

“They’re pretty simple,” said Victor, “Buzz can be no less than 80% of pure but no more than 110% because then people start to realize it’s got meth in it. Bitterness and sweetness counteract, but combined, I prefer not to go more than 10% in each direction, total. As for comedown, I don’t want anything more than 130% of pure while keeping addictiveness to a minimum of 90% of pure.”

“No maximum for addictiveness?” I ask looking up from my paper.

“Absolutely not,” he said.

I continued to jot down my notes.

I had an objective, prices, specs, bounds, everything I needed.

“Will you use some kind of simulation to solve this?” asked Victor.

I looked up, “What do you mean?”

“Well, when I was getting my MBA, I took a class where we used Monte Carlo simulation, and it seemed to me that trying various values for the ingredients in the mix might work,” he said.

“Ah, so I think what you’re getting at is more of a search approach, right?” I asked, “As in, searching over possible values until you hit on something good?”

“Exactly,” said Victor.

I smiled, “We could do that, but a better way would be to use a linear programming approach.”

“What’s that?” he asked.

“Linear programming isn’t programming at all. It’s something they invented during World War II to optimize enemy losses. Basically, instead of searching over different values for the mixture, if we structure the problem as a linear program, we can use something called the ‘simplex algorithm’ to give us a mathematically guaranteed optimal answer really quickly.”

“What does it take to express something as a linear program?” he asked.

“Well, you have a goal, which is just a linear function of your decisions. In this case the decisions are how many grams of each white powder to use in the blend, and the goal is to minimize the sum product of each weight times its price per gram.”

“Our total cost,” he said.

“Exactly,” I nodded, “But we need to do this minimization in light of some constraints. A constraint is just an inequality where both sides are linear functions with respect to the decisions.”

“Huh?” Victor looked confused.

“So we can say something like, the sum of all our powder amounts times their buzz level must be less than or equal to one hundred and ten percent. On one side, we have a linear function since each decision is simply multiplied by its buzz factor and added together. On the other side of the constraint, we have a constant, which is of course, linear with respect to the decisions.” (I’ve attached a picture in this post for how you achieve this simply using a sumproduct in Excel)

“So you just couldn’t do something like take the square of the amount of coke you’re using for some reason?” asked Victor.

“Exactly. No multiplying the decisions together,” I said, “Which is fine, because all our constraints are linear. We’ve got contraints for buzz, smell, texture, comedown, and addictiveness. We also have to add a constraint forcing the quantities to add up to one kilogram and constraints forcing that each quantity be between 0 and 100 grams.”

“Why do you need those last ones?” asked Victor.

“Well, if you didn’t have them, then the optimal solution might be to play with negative numbers. Like using a negative amount of meth just to take some buzz off and get a rebate back on some of my costs. We want a solution that can exist in the real world, so negative numbers won’t do at all.”

“Makes sense.”

“You have Microsoft Excel on there?” I asked, pointing to Victor’s laptop.

He nodded yes and slid the laptop over to me.

I opened a new spreadsheet and began mocking up the entire problem.

First I put in a section for the costs and specs and another section below it for where the spreadsheet could place the amount of each substance it wanted to use. I flanked those cells on either side with their limits of 0 and 100 grams.

Then I wrote the cost function at the top of the sheet. It was a simple sum product between cost and quantity. Below all that I added a third section with the quality bounds and calculations I’d gotten from Victor.

Going over to the Data tab in Excel I opened up Solver and told it where to find my objective and decision variables. I added in all of my constraints into the system as linear equalities. From the drop-down box I selected Simplex-LP and hit the solve button.
Suddenly, the objective function changed.

“Just shy of sixty nine hundred bucks,” I said smiling and pushed the laptop over to Victor so he could look at it.

“Fascinating,” he said, “only two thirds coke, and look at the B-12 usage. High Benzedrine with only a little bit of meth.”

Victor shrugged.

“It’s worth a try,” he said.

“You have an MBA?” I asked.

He smiled, “Another time.”

Half an hour later, Andre was driving me back to the club. I sat silently in the passenger seat, half worried, half exhilarated. Another time? What had he meant?

I’ve uploaded a mock-up of my blending problem spreadsheet for those who want to play with how I solved it.
Anyway, I’m happy to be back in A-town…where we blend our drugs with science!

Big Data-ish Tip

Mathematical programming has been around for a long time, so the toolset available is pretty mature. MS Excel Solver only handles problems up to a couple hundred variables which is really small, so what do you do when you’ve got a big optimization problem?

Well, let’s take it in steps. First, if you’re already in Excel, I’d check out Open Solver. It’s great for mid-size problems. It plugs into Excel, works just like the built-in solver, and uses Coin-OR‘s branch and cut implementation (Cbc) on the backend. And it’s free. Yay, free.

Now, if you want to build in an optimization model into something larger, Excel is not the home for you. Moving to the command line, we can stay in free-land by modeling in GLPK, but honestly, the solver that comes with GLPK kinda blows on large problems. Consider instead modeling with the MathProg/GMPL language that’s part of GLPK but dumping out a file for solution using Cbc (this is possible…I done it!). Beware though, if you don’t formulate your problem right, the conversion from GMPL to some kind of matrix representation is gonna be slow.

OK, so those are the free options. Moving from there, if you’re an enterprise it’s a no-brainer that you want to use OPL/CPLEX. It’s the cutting edge for large-scale optimization. But enjoy buying and licensing this thing. You can’t pick up a copy at Walmart. It’s going to require talking to some salesy type people.

If you’re more of a tech/web company, might I recommend Gurobi? Fast as balls, works on large problems, better licensing, more support for cloudy things. And while I’m at it, I’ll give a plug to AIMMS too, which is a modeling environment that you can hit Cbc, CPLEX, Gurobi, and many other solvers from.  AIMMS let’s a simpleton create GUIs on top of optimization models, which is awesome.

  • Pingback: Introduction to Machine Learning: Logistic Regression for Predicting Bad Trips | Analytics Made Skeezy

  • Pingback: [repost ]Introduction to Machine Learning: Logistic Regression for Predicting Bad Trips » New IT Farmer

  • http://nav33n.tumblr.com Naveen Venkataraman

    Awesome intro to LP. Is there a way to use R to do this?

    • John

      Check out the discussion here for various R packages:

      If you want to stay no-cost, I’d look for packages that interface with CLP and other COIN-OR stuff versus GNU lp-solve. GNU lpsolve is slow in my experience.

      Sadly, I don’t see a way to hook into CBC. Note also that you don’t want to have to provide a model to a solver in MPS format (like some of those R options require). That’s a matrix format that can be difficult to slog through.

      What you need is something more like PuPL (https://projects.coin-or.org/PuLP) which is bad ass but it’s Python, not R.

      Good luck!

    • john4man

      Ugh, I feel like the hooks for LP in R are pretty terrible. In everything I’ve seen you have to give R the entire problem in matrix form. (Maybe someone else reading this has seen otherwise?)

      See here: http://cran.r-project.org/web/views/Optimization.html

      Python has Pulp which is nice.

  • day

    Nicely done. The Kilogram reference got me confused (withdrawal symptoms perhaps) – isn’t the analysis for 100g product.

    • john4man

      Yep, I got my wires crossed. I’ll fix this. Thanks!

  • http://www.websitedoctor.com/ Alastair McDermott

    Super intro to LP, love the example. Out of interest, what other analogies did you consider using?

    • john4man

      In the book I’m writing for Wiley (coming out the this Fall) I work through a bunch of orange juice blending problems (http://www.businessweek.com/articles/2013-01-31/coke-engineers-its-orange-juice-with-an-algorithm) and do a more thorough job of explaining simplex etc.

      So that’s one analogy that I’m actually going to use!

      • http://www.websitedoctor.com/ Alastair McDermott

        There’s very much a book in this current narrative, love it. It’s a great intro for a non data scientist like me (I’m learning more about what’s possible, rather than implementation details).

  • leanne

    Does anyone know why GLPK cannot handle large problems

    • john4man

      I think it’s implementation of branch and cut is pretty “textbook,” so it hasn’t benefitted from the last couple decades of interesting academic research in the space.

  • John Berryman

    Hey John, met you on Twitter earlier today (@JnBrymn). Great stuff. I started at the beginning and made it here tonight. I’d forgotten what LP was, though I doubt I’ll forget again.

    One curiosity, though. Let’s say I have two competing objectives by which I want to optimize the coke mix – for instance price and addictivity. Let’s further say that these quantities are not comparable; so, for instance, I can’t optimize .75*price+.25*addictivity. Rather, I am interested in seeing all the sensible options – all the non-dominated, (aka http://en.wikipedia.org/wiki/Pareto_efficient). Is there any LP-ish algorithm for this modified problem? Effectively we would be doing something like finding all the points on the “best” side of the constraint hull.

    • john4man

      Great question. You’re right that usually people do linear combinations of multiple objectives. To find non-dominated points I suspect you could write a script that searches the space by optimizing either price or addictiveness while setting the other as a constraint with some value. By switching which one is the constraint and by searching the constraint value, you could assemble a frontier.