14
$\begingroup$

I came across the preface of Optimization Theory for Large Systems (you can read it in Amazon). The author claims in the table (page v) that some of the methods such as Dantzig Wolfe decomposition, some column generations, etc. are not widely used today.

What do you think of this claim ? Is there a difference between the academic world and the industrial world in terms of use of those methods ? As someone who looks forward to work in the industry (ideally in a company that is developing solvers), what are the methods that I need to know ?

$\endgroup$
  • 2
    $\begingroup$ If we are talking LPs, then interior-point for large majority of big problems going to be fastest method as long as you can fit the problem on a computer. The best alternative is the dual simplex method. $\endgroup$ – ErlingMOSEK Oct 30 '19 at 5:47
  • 4
    $\begingroup$ AFAIK, in the industry in which the problems are mostly large scale, heuristics methods have been applied. The decomposition method is used in some industries such as airline scheduling. $\endgroup$ – A.Omidi Oct 30 '19 at 6:05
  • 3
    $\begingroup$ I think the first edition of the book is from 1970. Maybe the preface talks about the situation back then? $\endgroup$ – Robert Schwarz Oct 30 '19 at 7:44
  • $\begingroup$ After actually reading the preface, my comment is invalidated. I think the author only claims that col.gen. is not useful for pure LP problems. But it's still useful for MIP problems, within a branch-and-price framework. $\endgroup$ – Robert Schwarz Oct 30 '19 at 7:47
  • 1
    $\begingroup$ In my view, practical optimization is subject to a lot of sparsity in the matrices. Hence, you can have a look at pages.cs.wisc.edu/~swright/talks/sjw-toulouse.pdf $\endgroup$ – independentvariable Oct 30 '19 at 11:00
5
+50
$\begingroup$

The gap between industry and academia is huge.

My suggestion for a future professional would be to learn very good coding because without that skill people are very limited.

What I have seen in practice is that it's impossible to gauge how useful an algorithm/method is without trying it out first, so the most important skill is the skill to do try different things out quickly, a.k.a. coding.

What I tell my developers and optimisation specialists is to work smart, not hard - this means writing tools to automate anything that is time consuming and needs to be done more than once, because we need to try many different things to see what works. We have tools for generating symbolic decompositions automatically, distributing calculations over a cluster, scripting reformulations, testing, benchmarking, etc. Basically, if we can imagine it, it's either built, being built, or scheduled to be built.

Methods

For large-scale systems, modern methods focus on lowering memory requirements or distributing memory among many machines.

If the reason the problem is large is that it's very dense, and not because it has a trillion variables, then:

  • For NLPs, fast gradient methods are state of the art (e.g., the fast proximal gradient method).
  • For LPs, interior point is still the king if the system is very large.
  • For MI(N)LPs, people focus on distributing the calculations for traditional methods, e.g., generate the bender's decomposition and use many parallel workers to solve the subproblems.
  • Where branch-and-bound is applicable, using a hierarchical multiple manager-worker system to process nodes and create branch-and-bound subtrees in parallel like in PARASCIP or Octeract Engine.

If a system has so many variables that we can't fit it into memory, people are unlikely to use deterministic methods in practice, and will try stochastic stuff instead (e.g., evolutionary algorithms or PSO).

In general, the main differentiator nowadays is not theory, but figuring out how to implement it properly using parallel hardware. Unfortunately, this is not what academic research is designed to disseminate, which brings me to the "what I think of this claim" part of your question:

Industrial adoption

Software-wise, industrial software is light years ahead of any academic code in terms of performance, robustness, and reliability. CPLEX/GUROBI vs CBC is a great example of this.

Theory-wise, it's hard to tell. While a lot of amazing theoretical work has been done in academia over the past three decades, maybe 0.01% of it has found its way to actual application.

As a former academic, my conclusion was that the reason is the way the academic system is designed, which is why I left academia.

The academic reality

The central fallacy is that professors believe that PhD students can write professional-grade software. They can't. As a former PhD student myself, I realised this when I hired our first professional developer. There is simply no comparison between what people who write code for a living and the rest of us can do. My development work is mostly in the R&D, i.e., to prototype new features and to do algorithmic optimisations for performance. My code eventually goes to our developers who turn it into proper code. It's not that my code is bad, it's just not efficient for me to spend two months designing something properly. I do the things only I can do, and the developers do the things only they can do, and that is how it should be done nowadays.

Coding has advanced a lot since the 90's, so asking a theorist to write good code is not as straightforward as it was 30 years ago, but most professors still think that way, maybe because this was kind of true when they were students. There was less to know.

Because of the overwhelming growth in coding techniques and tools, asking students to write good (by today's standards) code is the equivalent of expecting an experimentalist to know as much as the theorists and the developers. It's simply too much for any one person.

This is a very practical issue because, at the end of the day, applied math is pointless unless implemented into software. This becomes trickier if we consider that it's very hard to properly compare the runtime behaviour of two algorithms unless both are professionally implemented. If there is a flaw in implementation, an algorithm can easily be 1,000,000 times slower than it could. If there is a bug because there is no testing framework in place, an algorithm can be 1,000,000 faster instead.

Developing software properly costs money, time, and requires hiring professional developers. Unfortunately, only a handful of universities world-wide are willing to make that investment.

The systemic issue is that academics are not rewarded by the system for producing good, tested, and reusable software. In fact they are actively discouraged because their h-index will not be as high (5 years of development for one good publication vs 4-5 theoretical papers a year).

The result

As a result, we have software to solve optimisation problems, but we still lack proper tools and libraries for developing new optimisation software quickly and correctly. This stagnates experimentation, is in the way of proper testing, and so on.

Everything anyone implements needs to be done pretty much from scratch. The COIN-OR project was an amazing idea that tried to address this, however the overwhelming majority of code in the projects is not reusable either because (i) it's unreadable so it can only be used as a black box (e.g., CBC/IPOPT), or (ii) it's unreadable and buggy, so it can't be used at all because no-one can read the code to fix it, or (iii) is really good but almost completely undocumented (e.g., CBC).

Don't get me wrong, some of the COIN-OR/open-source stuff is really good, it's simply rarely designed to be a true open source collaborative project, because it's driven by academics instead of coders. It's usually the code someone wrote and generously decided to share with others. The difference between OR code and other popular open source projects is actually staggering - there is a reason Tensorflow has 56,000 watchers on github and IPOPT only has 16.

| improve this answer | |
$\endgroup$
4
$\begingroup$

It is also my impression that decomposition methods are not widely used in a commercial context. In the industry, you often make an "effort vs. value" estimation to decide what methods to use. This will often not favor decomposition algorithms due to a relatively high effort and the risk of it not providing better results.

I would make the following considerations before deciding to implement a decomposition algorithm:

Value for end-user

The first question is to estimate what business value would we get out of it. Does the problem currently take unreasonable amount of time to solve or do we want to get better solutions within some timespan? Another aspect is how likely is it that the decomposition will give us these results, it can be fairly hard to predict if decomposition actually will work.

Effort to build

It is not straight forward to implement a robust decomposition algorithm. It requires quite a lot of code that would require testing and error handling

Effort to maintain

The code has to be maintained. Not only by the person who implemented it, but also by team members. This will require that multiple persons have a fairly deep understanding of the decomposition method and I would be fairly concerned around how fast we could identify a bug and fix it if an error occurred in a production system.

Effort to extend

In industry, models are living organisms that keep changing based on new business requirements. I would be concerned that the decomposition would either not work or lose its advantage if we had to incorporate some new constraints or objectives into the model.


In the end, it depends on the specific problem and there are definitely problems where decomposition works very well and if the potential upside is high, a first step would be to build a proof-of-concept to understand it better (e.g. try something like GCG for Dantzig-Wolfe, and GCG or CPLEX for Benders decomposition).

In terms of what methods to try instead, I refer to this previous answer: How could we simplify solving the large scale MIPs without using any advanced methods like decompositions?

| improve this answer | |
$\endgroup$
  • $\begingroup$ you are probably right, even though some applications require some decomposition stuff when exact solutions are needed; a note: GCG can do automatic Benders as well :) $\endgroup$ – Marco Lübbecke Dec 4 '19 at 18:08
  • $\begingroup$ Yes, there are definitely applications where it is worth the effort! ...and cool GCG does Benders too, updated my answer. $\endgroup$ – Michael Lindahl Dec 5 '19 at 7:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.