Optimizing Real Time Decision Making
Why would a taxi company ever wait before dispatching cars to calling customers? The answer may surprise you: it is for decreasing customer waiting time.
Yes, you read it correctly: they wait before responding in order to decrease customer waiting time.
I'm not making this up. It is precisely what a customer of ours, a taxi company, is doing.
The answer looks quite counter intuitive, isn't it? Let's use a simple example to explain why it makes sense. It is a simplified view of what... [More]
Tags: analytics optimization 
Practical Guidelines for Solving Difficult Mixed Integer Programs
Update on Sept 30 2013: Ed Klotz has co authored a paper with Alexandra M. Newman on that very topic, worth a read. They also have a related paper on Practical guidelines for solving difficult linear programs
Update on Sept 6 2013: slides and replay for Ed Klotz presentation are available in our developerWorks community .
Ed Klotz will present on our next virtual user group webinar. Ed is the worldwide expert on how to tune CPLEX and reformulate models in order to get better... [More]

Un Peu de Math avec CPLEX
There is one thing I didn't disclose in my previous post (Un Peu de Math) on the Analytic Bridge Mathematical Competition : I used CPLEX to refine and validate various hypothesis. As usual, my first try wasn't very convincing, and I had to rely on better understanding of the problem to solve it efficiently.
Let me start with a statement of the optimization problem to be solved. A permutation x is a function such that x(i) is in the set {0,1,...,n1} for all i in that set.... [More]
Tags: mathematics modeling 
Un Peu de Math
The following was triggered by a mathematical problem proposed by Vincent Granville. The problem was to compute the maximum value q(n) of a function related to the well known metrics Spearman's footrule , or L1. This would then be used in a new stat isti cal corr elat io n based on ranked variables that would be very useful for Big Data applications. I'll refer readers to Granville's article for more details.
At first sight this seemed quite diffficult, and Granville launched a... [More]
Tags: analytics big_data mathematics 
More On Absolute Value
I needed to model an absolute value in a MIP model. I could have used one of the methods described in the very good review by Paul Rubin , but another method seemed better suited to my special case.
I am given a binary variable z and an integer variable x such that
0 <= x <= 2
z = abs(x1)
The rest of the model is such that we cannot assume we minimize z. This is therefore a non convex constraint.
The method I used works for any function of x . In order to model z =... [More]
Tags: modeling 
Technical Lessons Learned While Selling Optimization To Business Users
Update on Sept 6 2013: slides and replay for this presentation are available in our developerWorks community .
For those who missed my EUROINFORMS talk here is a replay in the context of our virtual user group series. It follow presentations on topics such as latest CPLEX release , or constraint programming .
The presentation focus is on how to make business people use optimization more. I'll review various issues discussed in this blog, and more, as well as potential ways to address... [More]

DWave vs CPLEX Comparison. Part 3: WMAX2SAT
How good is CPLEX for the last series of test problems used in this McGeoch&Wang paper ? Remember, it is this paper that compared a specialized hardware from the DWave company with three software solvers, including CPLEX. It generated lots of buzz because (a) DWave machine is claimed to be a quantum computer, and (b) because reported results show a dramatic speedup compared to CPLEX. The paper used three series of test problems for the comparison. We have revisited and improved CPLEX results dramatically... [More]

Proactive Analytics
Why blog again about optimization and analytics? Because the current way of having optimization be part of analytics is a bit misleading. Let me first say I assume that optimization is part of analytics here. Granted, a previous post of mine supported a different view, but the idea that mathematical optimization is part of the broader category of analytics is gaining momentum. For instance, the INFORMS society is pushing for it with its... [More]
Tags: optimization analytics 
Do We Need Accuracy In Solvers?
I just read this interesting blog post by Samik Raychaudhuri on solver accuracy. He wrote : " typical data accuracy does not go beyond the decimal point, and even if it does, seldom beyond 12 places of decimal. Why solve a problem accurately up to 10 places of decimal when the input data is not that accurate? " It reminded me of the 53 bits ought to be enough for anybody post by John D. Cook.
Paul Rubin commented on the first post that one of the problems that leads to... [More]

DWave vs CPLEX Comparison. Part 2: QUBO
Can we improve CPLEX performance for yet another test series used in McGeoch&Wang paper , namely the native QUBO instances? According to the paper, these instances were random instances constructed to match what the DWave hardware can solve directly. These are problems of the form
minimize sum ij Q ij x i x j
where all the variables x i are binary.
Such problems are called QUBO (Quadratic Unconstrained Binary Optimization ) problems. CPLEX release 12.3 didn't do very well according to the paper... [More]
Tags: optimization dwave qubo modeling 
Virtual User Group: CPLEX 12.5.1
Update on Sept 6 2013: slides and replay for Roland Wunderling's presentation are available in our developerWorks community .
Roland Wunderling will be presenting on CPLEX 12.5.1 in our next Virtual User Group.
Do not miss this unique opportunity to learn more about our latest CPLEX release. This release was made available to our commercial customers on June 12, 2013. Free academic version should follow shortly via our academic initiative . Besides the performance improvement I described here ,... [More]

DWave vs CPLEX Comparison. Part 1: QAP
Why am I discussing again the DWave quantum computer vs CPLEX comparison paper published by Cathy McGeoch and Carrie Wong ? Mainly because it looked like an interesting challenge to redo the CPLEX experiments to see if we could get better results.
Here are new results for the quadratic assignment problem test series. Our results for the other tests series in will be reported in subsequent posts. To cut a long story short, our results are better than those in the... [More]
Tags: modeling dwave optimization analytics 
CPLEX 12.5.1
We are about to have a new CPLEX release, namely IBM ILOG CPLEX Optimization Studio 12.5.1. We plan for electronic availability this week.
The main focus for this release was to improve performance across the board, and particularly for Mixed Integer Programming (MIP) and Mixed Integer Quadratic Programming (MIQP and MIQCP). We also improved numerical accuracy and fixed few bugs.
For MIP we get the following geometric average speed up compared to the 12.5 release of November 2012:
A 15% overall improvement on... [More]

Efficiency Can Get You In Trouble
This post was triggered by a recent tweet by Laura McLay. Laura was pointing to John D. Cook entry on how Efficiency could land you in jail . In that post John explains how a German postman was almost fired because he found better (read more efficient) ways to deliver mail. The story may be a bit more complex (read Chris Nahr's comment on John's post), but it seems plausible. Basically, the postman was punished because he was breaking some glass in order to gain efficiency.
In... [More]

Is Quantum Computing Useful For Optimization ?
A recent paper by Cathy McGeoch and her doctoral student Cong Wang triggered a lot of interest because it compares a specialized computing device built by the DWave company to software solvers including our own CPLEX. No surprise, the specialized hardware beats by far software on the problems it is designed to solve. That in itself would not justify the hype we're observing.
What triggered interest is that DWave computing device is claimed to be a quantum computer. This brings us to a quite interesting... [More]
Tags: dwave 