Skip to content

Quantum computing and operations research

Quantum computing is one of those weird ideas out there that will either change the world or go the way of  cold fusion, so I periodically think I need to learn more about the area. I am by no means an expert (or even knowledgeable) in the area.  My expertise comes from reading Scott Aaronson’s blog, which makes me as knowledgeable as about about a million other people out there.   Seeing a series of papers showing how quantum computing can factor numbers is interesting, until you realize that the number involved are still well in the range of what my eight year old can do in his head.  There are a lot better ways to spend my research time.

So, when a paper comes out involving using quantum computers to solve NP-hard problems (for a paper just presented at the ACM Conference on Computing Frontiers), I didn’t exactly leap at the opportunity to read it.  That was until I saw the senior author: Cathy McGoech (the other coauthor is doctoral student Cong Wang).  Cathy is the real deal.  I have met her a few times, but I don’t know her well personally.  But her research has had a big effect on me.  Cathy, together with David Johnson (of Johnson and Garey fame) began the DIMACS Challenges twenty years ago.  The goal in these challenges is to look at real-life algorithmic performance.  The two of them ran the first Challenge (on Network Flows and Matchings);  I ran the second Challenge, on cliques, coloring, and satisfiability.  Cathy was extremely influential in how I thought about the Challenge.  In particular, how can one distinguish between “fast coding” and “fast algorithms”?  And what do interesting computational questions look like?  I certainly never got to her level of sophistication when it comes to experimental design and evaluation, but her work made me better.

My research has moved off in my dillettante way to other things;  Cathy has continued to work very hard to put experimental algorithmics on a solid footing.  She even has a new book out on the topic (which I just ordered).

All this means: if Cathy is saying something about a computational evaluation, it is going to be worth listening to.

Short synopsis:  Cathy and her coauthor got access to a D-Wave Two platform, heuristically solved a number of instances of three NP-Hard problems (Quadratic Unconstrained Binary Optimization, Weighted Maximum Two-Satisfiability, and Quadratic Assignment),  and generally performed much faster than methods such as CPLEX.

The D-Wave platform has caused some controversy, since it is unclear what exactly happens in the system.  The “holy grail”, as I understand it (it is not Aaronson’s fault if I get this wrong!) is quantum entanglement.  This sort of “action at a distance” is key to much of the theory behind quantum computing.  Does D-Wave get this?  The paper covers this:

Finally there has been some debate as to whether D-Wave chips form a ‘truly’ quantum system; this has been demonstrated for smaller (8 and 16 qubit) systems … but
not, as yet, for the full hardware graph. Boixo et al. 
report that the hardware demonstrates quantum tunneling
(which would be inconsistent with classical annealing), and
find some evidence of qubit entanglement. A recent review
article in Science [ Science, 13 May 2011] concludes that the hardware is at least a little quantum mechanical.

I suppose the researchers ended up at least a little tenured for this work.

But how does it work?  Generally, pretty well:

In all three experiments the V5 hardware or its hybrid counterpart Blackbox found
solutions that tied or bettered the best solutions found by
software solvers. Performance was especially impressive on
instances that can be solved directly in hardware. On the
largest problem sizes tested, the V5 chip found optimal so-
lutions in less than half a second, while the best software
solver, CPLEX, needed 30 minutes to find all optimal solutions.

We have also carried out some tests to compare V6 to
the software solvers; very preliminary results suggest that
on QUBO instances with n = 503, the hardware can find
optimal solutions around 10,000 times faster than CPLEX.

Pretty impressive sounding, and certainly something worth paying attention to.

But still, it is important to understand some key aspects of this work:

1) The solutions found are “just” heuristic solutions.  There is no proof of optimality, nor can there be with the setup being used.  In essence, we are getting a very fast population search with what looks like simulated annealing.

2) The comparator is primarily CPLEX, a code designed for finding and proving optimal solutions.  I have refereed 3 papers in the last month alone that give heuristics that are orders of magnitude faster than CPLEX in finding good solutions.  Of course, CPLEX is generally infinitely faster in proving optimality (since it wins whenever it proves optimality).  Beating CPLEX by orders of magnitude on some problems in finding good solutions (particularly with short times) does not require fancy computing.

3) The problems chosen are not exactly in CPLEX’s sweet spot.  Consider maximum weighted 2-SAT, where the goal is to maximize the weight of satisfied clauses in a satisfiability problem, where each clause has exactly two variables.  The natural linear relaxation of this problem results in a solution with all variables taking on value .5, which gives no guidance to the branch-and-bound search.  Now CPLEX has a lot of stuff going on to get around these problems, but there are certainly NP-Hard problems for which CPLEX has better relaxations, and hence better performance.  And if you take any sort of problem and add complicating constraints (say, max weighted 2-sat with restrictions on the number of  TRUE values in various subsets of variables), I’ll put my money on CPLEX.

4) The D-Wave system is still a bit pricey:  at about $10,000,000, there are cheaper ways to get the sort of speedup that McGeoch and Wang found.

Cathy understands the comparator issue:

It would of course be interesting to see if highly tuned
implementations of, say, tabu search or simulated annealing
could compete with Blackbox or even QA on QUBO prob-
lems; some preliminary work on this question is underway.

Despite these qualms, Cathy has gotten me interested.

Google too, by the looks of it.

Be sure to check out Scott Aaronson’s take on this, as he resumes his role as “Chief D-Wave Skeptic”.

2013 05 16 Computing
Research Comments Off Permalink

Google Reader and Operations Research

I has been some months now since Google has announced the end of Google Reader.  I have gone through many of the stages of grief (getting stuck at “Anger” for a while) and am now entering acceptance.

Personally, I have no problem with Feedly or one of the other readers.  But there is another aspect of Google Reader that seems harder to replace.  On my blog, I have two sidebar entries:  a “From the OR blogs”, giving recent posts from the OR Blogroll, and a listing of the OR Blogroll itself.  I think both are pretty useful since they given automatic visibility to new (and existing!) blogs in OR.  I don’t think they get a ton of use, but they are nice to have.

Google Reader provided scripts for both the recent posts and the blogroll.  I need  a replacement that

  1. Allows easy addition/deletion of blogs
  2. Show recent posts from all the blogs
  3. Can also act as my personal reader

The last requirement precludes most of the wordpress scripts (I use wordpress on a local machine to handle this blog).  I do not want to keep, say, a feedly list of blogs along with a separate “ORBlogRoll” within wordpress.

Anyone found a Google Reader replacement that can do this?

2013 04 29 Administration - Announcements
Blogs and Web Comments (2) Permalink

The Golden Ticket

The Golden Ticket

I picked up Lance Fortnow’s new book The Golden Ticket: P, NP and the Search for the Impossible.  Lance is chair of the School of Computer Science at my alma mater Georgia Tech (I got my PhD there in Industrial Engineering) and the co-author of the excellent Computational Complexity blog.

The title of the book comes from the Willy Wonka story of finding a golden ticket that allows passage into a chocolate factory and a lifetime supply of candy.  But golden tickets are rare:  how can one find one?  Can finding golden tickets be done fast?  The difficulty of finding rare items in a sea of possibilities is at the heart of the P=NP issue.

After a brief introduction to the sort of problems that are in NP (problems whose solution can be checked quickly, with some being in P, problems whose solution can be found quickly), Lance moves on to an extended fantasy of what would happen if a proof of P=NP (in other words: problems whose solutions can be checked quickly can also have their solutions found quickly) were to be discovered.  An initial proof leads to inefficient (but polynomial) codes which are used to improve on themselves culminating in the “Urbana algorithm”  (I bet it would be the “Carnegie Algorithm”, but this is Lance’s story):

… 42 million lines of unintelligible code.  And it solved NP problems fast, very fast. [without becoming self-aware.  No Skynet in this book.]

Lance then explores the effect of the Urbana algorithm.    Some of his predictions seem a bit far-fetched.  I don’t think the difficulty in predicting snow storms a year in advance (as he suggests will happen) is an issue of algorithm speed, but rather limits on data availability and modeling limits, but, again, this is Lance’s fantasy so I really shouldn’t quibble.

One of Lance’s stories has a father and daughter going to a baseball game, and the father muses on the effect the Urbana algorithm has had on baseball:

First, of course, is the schedule of this particular game.  As late as 2004, a husband-and-wife team, Henry and Holly Stephenson, scheduled games for Major League Baseball.  They used a few simple rules, like the number of games played at home and away by each team, and some local quirks, like the Boston Red Sox like to host a daytime baseball game on Patriot’s Day in mid-April, as the runners in the Boston Marathon pass nearby [a story that takes on a whole different flavor now].  In 2005, Major League Baseball contracted with a Pittsburgh company, the Sports Scheduling Group, because its scheduling could better avoid teams playing each other in consecutive weeks.

Hey, that’s me!  I made it into Lance’s book!  Well, me and my colleagues at the Sports Scheduling Group.  Lance goes on to say a few more words about the effect of the Urbana algorithm on scheduling:

So the baseball czars want to schedule games in a way that everyone has the best possible weather and good teams play each other at the end of the season, not to mention more mundane cost savings like reducing the amount of travel for each team.  Handling all these issues and the multitude of possible schedules would have been impossible a mere fifteen years ago [the story is based in 2026], but the Urban algorithm spits out the best schedule in  a matter of minutes.

If I were to continue the story, I would include something Lance did not:  the Sports Scheduling Group would likely have gone out of business shortly after the release of the Urbana algorithm.  While part of our skill is understanding sports leagues, a big part of our competitive advantage is that we can solve sports scheduling problems pretty darn quickly, despite the fact they are all NP-complete (the hardest of the NP problems).  In short, while a proof of P=NP might be a golden ticket for some, our golden ticket is is the difficulty caused by P <> NP.  In Warren Buffet’s terms, computational complexity is our business’s moat, preventing others from following too easily.

So far, I love the book (and not just because of the shout-out!).  It is a book on a technical subject aimed at a general audience.  I’m only partway through (I am kinda stuck on showing the baseball story to those around me), but Lance’s mix of technical accuracy with evocative story telling works for me so far.

 

2013 04 27 Books
Sports Comments Off Permalink

Crowdsourcing the Travelling Salesman

Despite some worries, the field of operations research is not exactly sitting on a street corner with a begging bowl.  There are lots of people out there who are willing to pay us for what we do.  Perhaps not as often as they should, or as much as we deserve, but “operations research” is a legitimate career path.  You can get jobs in government, academia or industry; you can work as a consultant; you can write (and get paid for) software; you can even write popular books on the subject!

But if you create an operations-research inspired movie, you might find it a rather tough go to get enough fannies in the seats in order to pay the bills.  While we certainly are captivated by the idea of “what would happen if P=NP”, most of the world seems far more captivated with “I wonder how James Franco would do as Oz”.  So when a movie does explore an operations research theme, it needs to be creative in its funding.

Traveling Salesman is a movie that explores what would happen if a group of mathematicians did find a fast algorithm for the Traveling Salesman Problem.  Now, I know what I would do if I found such an algorithm:  I would dance a jig on my Dean’s desk, and immediately look for the cushiest academic job I could find.  It appears that the writers of this movie went off in a slightly different direction, involving government agents, ominous music, and sweat-soaked brows.  Well, I suppose that might happen too.

The producers of the film are trying to get broader distribution, and are counting on the wisdom of the crowds to fund that distribution.  There is an IndieGoGo campaign with a very modest goal of raising $3500.  With that, they will make the film available through such outlets as (from their campaign):

  • Buy and Rent from iTunes
  • Buy and Rent from Amazon VOD
  • Buy and Rent from Google PLAY
  • Buy and Rent from Distrify
  • Netflix and Hulu are under consideration
  • Other outlets are also in negotiation

Personally, I love it just for the tchotchkes (that movie poster will look great in my office).

Right now they are at $2675:  is there interest in the operations research community to put them over the top?

2013 03 11 Film Comments (2) Permalink

Doing work on Metaheuristics and Optimization/Constraint Programming?

I’m putting together a track at the upcoming 10th Metaheuristics International Conference. The conference will be held August 5-8, 2013 in Singapore. The conference website is http://www2.sis.smu.edu.sg/mic2013/

The topic of the Track is Metaheuristics and Optimization/Constraint Programming. There has been a lot of work recently on combining metaheuristics with exact methods. I think it is a very exciting area: faster optimization codes and speedier computers make it easier to use optimization or constraint programming as part of a metaheuristic approach to problems.

If you have some work that you would like to present at the conference, I encourage you to submit that work to the track. Submissions can be in the form of 10 page full papers or 3 page extended abstracts. All submissions are thoroughly reviewed. More information on submission is at the general Call for Papers: http://www2.sis.smu.edu.sg/mic2013/call_for_papers.htm

You will submit your paper through ConfTool at https://www.conftool.net/mic2013/ Note that you will have the opportunity to select the track “Special Session on Meta-Heuristics and Constraint Programming” (or similar: the track is not limited to CP).

The submission deadline is February 28. Please let me know if you have any questions.

2013 02 15 Conferences Comments (2) Permalink

Summer Internship at IBM Research, AI for Optimization Group

Just saw this announcement of a summer internship

A summer internship position is available for 2013 in the “AI for Optimization” group within the Business Analytics and Mathematical Sciences department at IBM Watson Research Center, Yorktown Heights, New York.  The internship will last for about 3 months and will be scheduled between March and October, 2013.

Candidates should be exceptional Masters or PhD students in Computer Science and related areas, and not have already received their PhD by the internship start date.  The successful candidate is expected to have strong interest and some experience in one or more of the following:

 +  Developing Novel Technologies based on AI and OR to advance the state of the art in combinatorial optimization (e.g., Heuristic Search, Mixed Integer Programming (MIP), Linear Programming (LP), Satisfiability (SAT))

 +  Robust Parallelization of search-based algorithms (e.g., using parallel Branch&Bound; information exchange) exploiting novel computing architectures such as BlueGene, multi-core end-user machines, large compute clusters, and the Cloud

 +  Advancing Simulation-Based Optimization approaches to solve real-world problems and/or to improve optimization methods themselves by, e.g., employing techniques from Machine Learning, Local Search, and Genetic Algorithms for automated algorithm selection and parameter tuning

 +  Applications of Optimization to Analytics, Production Modeling, Sustainability, Systems, and Databases

Interested candidates should send their CV as well as names and contact information of at least two references to all of the following:

Ashish Sabharwal [ashish.sabharwal@us.ibm.com]
Horst Samulowitz [samulowitz@us.ibm.com]
Meinolf Sellmann [meinolf@us.ibm.com]

I wish I didn’t already have my PhD!

2013 01 16 Jobs in OR
Research Comments Off Permalink

Easy and Hard Problems in Practice

David Eppstein of the blog 0xde has a list of his top 10 preprints in algorithms in 2012.  One particularly caught my eye:

Clustering is difficult only when it does not matter, Amit Daniely, Nati Linial, and Michael Saks,  arXiv:1205.4891. [...] this represents a move from worst-case complexity towards something more instance-based. The main idea here is that the only hard instances for clustering problems (under traditional worst-case algorithms) are ones in which the input is not actually clustered very well. Their definition of a “good clustering” seems very sensitive to outliers or noisy data, but perhaps that can be a subject for future work.

This paper really hit home for me.  I have taught data mining quite often to the MBAs at the Tepper School and clustering is one topic I cover (in fact, research on clustering got me interested in data mining in the first place).  I generally cover k-means clustering (easy to explain, nice graphics, pretty intuitive), and note that the clustering you end up with depends on the randomly-generated starting centroids.  This is somewhat bothersome until you play with the method for a while and see that, generally, k-means works pretty well and pretty consistently as long as the data actually has a good clustering (with the correct number of clusters).  It is only when the data doesn’t cluster well that k-means depends strongly on the starting clusters.  This makes the starting centroid issue much less important:  if it is important, then you shouldn’t be doing clustering anyway.

There are other operations research algorithms where I don’t think similar results occur.  In my work in practice with integer programming, most practical integer programs turn out to be difficult to solve.  There are at least a couple of reasons for this (in addition to the explanation “Trick is bad at solving integer programs”).  Most obviously, easy problems typically don’t get the full “operations research” treatment.  If the solution to a problem is obvious, it is less likely to require more advanced analytics (like integer programming and similar).

More subtly,  there is a problem-solving dynamic at work.  If an instance is easy to solve, then the decision maker will do something to make it harder.  Constraints will be tightened (“What if we require at least 3 weeks between consecutive visits instead of just two?”) or details will be added (“Can we add the lunch breaks?”) until the result becomes a challenge to solve.  I have not yet had a real-world situation where we exhausted the possibilities to add details to models or to further explore the possible sets of constraints.  Eventually, we get to something that we can’t solve in a reasonable amount of time and we back up to something we can (just) solve.  So we live on the boundary of what can be done.  Fortunately, that boundary gets pushed back every year.

I am sure there is a lot of practical work in operations research that does not have this property.  But I don’t think I will wake up one morning to see a preprint: “Integer programming is difficult only when it doesn’t matter”.

2013 01 02 Applications
integer programming
Research Comments (2) Permalink

Help Santa Plan His Tour (Twice!)

Just in time for the holidays, there is a very nice competition at Kaggle: The Traveling Santa Problem. The problem was devised by the ever-creative Bob Bosch, about whom I have written before. The problem is an interesting variant on the Traveling Salesman Problem. Given a set of points and distances between them, the TS(alesman)P is to find the shortest cycle through all the points.  The TS(alesman)P would not be a great competition problem:  you could save the effort and just send the prize to my soon-to-be-neighbor Bill Cook with his Concorde code.

The TS(anta)P asks for two disjoint cycles, with a goal of minimizing the longer of the two. Of course, there is a clear explanation of why Santa wants this:

Santa likes to see new terrain every year–don’t ask, it’s a reindeer thing–and doesn’t want his route to be predictable.

OK, maybe it not so clear. But what Santa wants, Santa gets.

There is just one instance to work with, and it is a monster with 150,000 points. It turns out that the points are not randomly scattered throughout the plane, nor do they seem to correspond to real cities. I won’t spoil it here, but there is a hint at the kaggle discussion boards.

There are prizes for the best solution by the end of the competition (January 18, 2013) and, most interestingly, at a random date to be chosen between December 23 and January 17.  The $3000 in prizes would certainly make a nice Christmas bonus (that is  7.5 Lego Death Stars!). You can check out the full rules, leaderboard, discussion, and more at the competition site.

I personally find this competition much more interesting than the data-mining type competitions like the General Electric sponsored Flight Quest (which is certainly not uninteresting). In Flight Quest, the goal is to predict landing times for planes. This is all fine and good, but as an operations researcher, I want to make some decisions to change those times to make the system work better.  Helping Santa avoid ennui might not be particularly realistic but it is much better than simply predicting when my Christmas toys arrive.

If we can get a good turnout for the Santa problem, perhaps we can see more optimization competitions, or better yet, competitions that combine data mining with optimization.

2012 12 15 Challenges Comments (1) Permalink

Which Average do you Want?

Now that I am spending a sentence as an academic administrator in a business school (the Tepper School at Carnegie Mellon University), I get first-hand knowledge of the amazing number of surveys, questionnaires, inquiries, and other information gathering methods organizations use to rank, rate, or otherwise evaluate our school. Some of these are “official”, involving accreditation (like AACSB for the business school and Middle States for the university). Others are organizations that provide information to students. Biggest of these, for us, is Business Week, where I am happy to see that our MBA program went up four positions from 15th to 11th in the recent ranking. Us administrators worry about this so faculty don’t have to.

Responding to all these requests takes a huge amount of time and effort. We have a full-time person whose job is to coordinate these surveys and to analyze the results of them. Larger schools might have three or four people doing this job. And some surveys turn out to be so time-intensive to answer that we decline to be part of them. Beyond Grey Pinstripes was an interesting ranking based on sustainability, but it was a pain to fill out, which seems to be one reason for its recent demise.

As we go through the surveys, I am continually struck by the vagueness in the questions, even for questions that seem to be asking for basic, quantitative information. Take the following commonly asked question: “What is the average class size in a required course?”. Pretty easy, right? No ambiguity, right?

Let’s take a school with 4 courses per semester, and two semesters of required courses. Seven courses are “normal”, classes run in 65 student sections, while one course is divided into 2 half-semester courses, each run in 20 student seminars (this is not the Tepper School but illustrates the issue). Here are some ways to calculate the average size:

A) A student takes 9 courses: 7 at 65 and 2 at 20 for an average of 55.
B) If you weight over time, it is really 8 semester-courses: 7 at 65 and 1 at 20 for an average of 59.4
C) There are about 200 students, so the school offers 21 sections of 65 student classes and 20 sections of size 20 for an average of 43.

Which is the right one? It depends on what you are going to use the answer for. If you want to know the average student experience, then perhaps calculation B is the right one. An administrator might be much more concerned about calculation C, and that is what you get if you look at the course lists of the school and take the average over that list. If you look at a student’s transcript and just run down the size for each course, you get A.

We know enough about other schools that we can say pretty clearly that different schools will answer this in different ways and I have seen all three calculations being used on the same survey by different schools. But the surveying organization will then happily collect the information, put it in a nice table, and students will sort and make decisions based on these numbers, even though the definition of “average” will vary from school to school.

This is reminiscent of a standard result in queueing theory that says that the system view of a queue need not equal a customer’s view. To take an extreme example, consider a store that is open for 8 hours. For seven of those hours, not a single customer appears. But a bus comes by and drops off 96 people who promptly stand in line for service. Suppose it takes 1 hour to clear the line. On average, the queue length was 48 during that hour. So, from a system point of view, the average (over time) queue length was (0(7)+48(1))/8=6. Not too bad! But if you ask the customers “How many people were in line when you arrived?”, the average is 48 (or 47 if they don’t count themselves). Quite a difference! What is the average queue length? Are you the store or a customer?

Not surprisingly, if we can get tripped up on a simple question like “What’s your average class size?”, filling out the questionnaires can get extremely time consuming as we figure out all the different possible interpretations of the questions. And, given the importance of these rankings, it is frustrating that the results are not as comparable as they might seem.

2012 12 14 Academic Administration
Statistics Comments (1) Permalink

Registries To Avoid Publication Bias

I have been thinking about the issue of how a field knows what they know.  In a previous post, I wrote about how the field of social psychology is working through the implications of fraudulent research, and is closely examining the cozy interactions between journals, reviewers, and famous researchers.   And any empirical field based on statistical analysis has got to live with the fact that if there 1000 results in the field, some number (50 perhaps, if p=.05 is a normal cutoff and lots of results are just under that value) are going to be wrong just because the statistical test created a false positive.  Of course, replication can help determine what is real and what is not, but how often do you see a paper “Confirming Prof. X’s result”?  Definitely not a smooth path to tenure.

This is worse if malevolent forces are at work.  Suppose a pharmaceutical company has bet the firm on drug X, and they want to show that drug X works.  And suppose drug X doesn’t work.  No problem!  Simply find 20 researchers, sign them to a non-disclosure, and ask them to see if drug X works.  Chances are one or more researchers will come back with a statistically significant result (in fact, there is about a 65% chance that one or more will, given a p=.05).  Publish the result, and voila!  The company is saved!  Hurray for statistics and capitalism!

Fortunately, I am not the first to see this issue:  way back in 1997, the US Congress passed a bill requiring the registration of clinical trials, before the trials get underway.

The first U.S. Federal law to require trial registration was the Food and Drug Administration Modernization Act of 1997 (FDAMA) (PDF).

Section 113 of FDAMA required that the National Institutes of Health (NIH) create a public information resource on certain clinical trials regulated by the Food and Drug Administration (FDA). Specifically, FDAMA 113 required that the registry include information about federally or privately funded clinical trials conducted under investigational new drug applications (INDs) to test the effectiveness of experimental drugs for patients with serious or life-threatening diseases or conditions.

This led to the creation of clinicaltrials.gov (where I am getting this history and the quotes) in 2000.  This was followed by major journals requiring registration before papers could be considered for publication:

In 2005 the International Committee of Medical Journal Editors (ICMJE) began to require trial registration as a condition of publication.

The site now lists more than 130,000 trials from around the world.  It seems this is a great way to avoid some (but by no means all!) fraud and errors.

I think it would be useful to have such systems in operations research.  When I ran a DIMACS Challenge twenty years ago, I had hoped to keep up with results on graph coloring so we had a better idea of “what we know”:  then and now there are graph coloring values in the published literature that cannot be correct (since, for instance, they contradict published clique values:  something must be wrong!).  I even wrote about a system more than two years ago but I have been unable to find enough time to take the system seriously.  I do continue to track results in sports scheduling, but we as a field need more such systems.

 

2012 12 03 Challenges
Computing Comments (1) Permalink