Optimization Practice Problems

[Violette Ransone]

Ithink that the shortest path problem is probably the problem that is solved most often. But if we move to problems where we need more complicated solvers, like Gurobi, Cplex, and Baron? What are the problems which are solved most often in industry (or people deploy the solution)?

By problems I mean something like vehicle-routing-problems, scheduling problems, etc. It would also be great to know why these types of problems are solved most often (easy to implement, easy to deploy, most money involved, ...).

About the reasons for why they are solved most often: Saving cost, maximizing profit, improve customer service, mitigate risks, ... essentially whatever is your objective function in that specific industry.

A good source for OR applications in practice is INFORMS Journal on Applied Analytics (formerly, Interfaces). Also, there are some good answers about good-cause OR applications in this question. I suggest that you search for an industry that you're interested in to find more about OR applications there.

Oil Refining. In the old days (through the '70s and into at least the early 80s), LPs to optimize oil refining, solved by some variant of the Simplex Method, were the most frequently solved optimization problems, and were responsible for a large portion of the total worldwide floating point computations.

Even in the 70s, there was some oil refining optimization done using Nonlinear Programming (or in some case, just Nonlinear Equation Solving). But I think such optimizations were more commonly performed by oil company researchers in Operations Research colloquiums, such as I attended at Stanford in the early 80s, than they were in practice at the oil companies which employed them.

Even though Logistics applications (ranging from simple Economic Order Quantity (EOQ), to the more complicated Multi-Indenture Multi-Echelon (MIME)) are asked to produce suggestions to practitioners very frequently, given that they are already formulated, their solutions are not quoted or cited; they are part of the management process. Nevertheless, the insight that one can get by understanding their formulation and assumptions can be a game changer.

I populated it with hunderds of thousands of entries and need some complex, stupid and unoptimized queries to make some tests and practice my optimization skills. Right now I tried to write some queries but they don't make much impact on the database.

I find it hard to come up with queries that are really bad :-) Here are some ideas. Hopefully, others will come up with more. I suggest you put your tables (empty or even with some sample rows) in , where we can try our queries. I don't know for instance, if I don't have any syntax errors in below queries.

A colleague of mine today committed a class called ThreadLocalFormat, which basically moved instances of Java Format classes into a thread local, since they are not thread safe and "relatively expensive" to create. I wrote a quick test and calculated that I could create 200,000 instances a second, asked him was he creating that many, to which he answered "nowhere near that many". He's a great programmer and everyone on the team is highly skilled so we have no problem understanding the resulting code, but it was clearly a case of optimizing where there is no real need. He backed the code out at my request. What do you think? Is this a case of "premature optimization" and how bad is it really?

What this means is that, in the absence of measured performance issues you shouldn't optimize because you think you will get a performance gain. There are obvious optimizations (like not doing string concatenation inside a tight loop) but anything that isn't a trivially clear optimization should be avoided until it can be measured.

There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified. It is often a mistake to make a priori judgements about what parts of a program are really critical, since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail. After working with such tools for seven years, I've become convinced that all compilers written from now on should be designed to provide all programmers with feedback indicating what parts of their programs are costing the most; indeed, this feedback should be supplied automatically unless it has been specifically turned off.

Not all early optimizations are evil, micro optimizations are evil if done at the wrong time in the development life cycle, as they can negatively affect architecture, can negatively affect initial productivity, can be irrelevant performance wise or even have a detrimental effect at the end of development due to different environment conditions.

If performance is of concern (and always should be) always think big. Performance is a bigger picture and not about things like: should I use int or long?. Go for Top Down when working with performance instead of Bottom Up.

In your case, it seems like a little programmer time was already spent, the code was not too complex (a guess from your comment that everyone on the team would be able to understand), and the code is a bit more future proof (being thread safe now, if I understood your description). Sounds like only a little evil. :)

I'm surprised that this question is 5 years old, and yet nobody has posted more of what Knuth had to say than a couple of sentences. The couple of paragraphs surrounding the famous quote explain it quite well. The paper that is being quoted is called "Structured Programming with go to Statements", and while it's nearly 40 years old, is about a controversy and a software movement that both no longer exist, and has examples in programming languages that many people have never heard of, a surprisingly large amount of what it said still applies.

The improvement in speed from Example 2 to Example 2a is only about 12%, and many people would pronounce that insignificant. The conventional wisdom shared by many of today's software engineers calls for ignoring efficiency in the small; but I believe this is simply an overreaction to the abuses they see being practiced by penny-wise-and-pound-foolish programmers, who can't debug or maintain their "optimized" programs. In established engineering disciplines a 12% improvement, easily obtained, is never considered marginal; and I believe the same viewpoint should prevail in software engineering. Of course I wouldn't bother making such optimizations on a one-shot job, but when it's a question of preparing quality programs, I don't want to restrict myself to tools that deny me such efficiencies.

Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified. It is often a mistake to make a priori judgments about what parts of a program are really critical, since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail.

My own programming style has of course changed during the last decade, according to the trends of the times (e.g., I'm not quite so tricky anymore, and I use fewer go to's), but the major change in my style has been due to this inner loop phenomenon. I now look with an extremely jaundiced eye at every operation in a critical inner loop, seeking to modify my program and data structure (as in the change from Example 1 to Example 2) so that some of the operations can be eliminated. The reasons for this approach are that: a) it doesn't take long, since the inner loop is short; b) the payoff is real; and c) I can then afford to be less efficient in the other parts of my programs, which therefore are more readable and more easily written and debugged.

I've often seen this quote used to justify obviously bad code or code that, while its performance has not been measured, could probably be made faster quite easily, without increasing code size or compromising its readability.

In general, I do think early micro-optimizations may be a bad idea. However, macro-optimizations (things like choosing an O(log N) algorithm instead of O(N^2)) are often worthwhile and should be done early, since it may be wasteful to write a O(N^2) algorithm and then throw it away completely in favor of a O(log N) approach.

Note the words may be: if the O(N^2) algorithm is simple and easy to write, you can throw it away later without much guilt if it turns out to be too slow. But if both algorithms are similarly complex, or if the expected workload is so large that you already know you'll need the faster one, then optimizing early is a sound engineering decision that will reduce your total workload in the long run.

Thus, in general, I think the right approach is to find out what your options are before you start writing code, and consciously choose the best algorithm for your situation. Most importantly, the phrase "premature optimization is the root of all evil" is no excuse for ignorance. Career developers should have a general idea of how much common operations cost; they should know, for example,

3a8082e126