Things you learn in a Ph.D. that are not written in textbooks

Those are things I learned during the first phase of my experimentation over the course of my Ph.D (year 2 of 4) There is a story behind each of this statements; I may blog about some of them if there is interest in it and I find the time to write that. Please note that some of these elements are now common knowledge, it wasn’t the case in 2009:

  1. Symmetry significantly hurts MIP performance.
  2. Performance variability is a serious issue when solving MIPs
  3. Performance variability can be used as a tool to solve complex MIPs
  4. You can actually get good papers published about performance variability
  5. Always upgrade to the latest version of the solver you use
  6. It’s really hard to get CPLEX to remember how you named your variables in the .NET API
  7. Serialization >> XML
  8. When solving a supply chain design models through a MIP solver, one of two things happen:
    1. You get very quickly to a relatively small gap, then is stays struck around 1% gap until all RAM is consumed;
    2. Fails to find a good feasible solution and goes nowhere.

Benders sub-section:

  1. The classical, straight-out-of-the-textbook Benders decomposition does not work in practice.
  2. For Benders decomposition to work in practice, you often need to add a few constraints so as not to make the master problem unbounded.
  3. For Benders to work on large problems, you need to apply a lot of hacks, tricks and customization.
  4. The integer L-shaped algorithm has but one significant drawback when solving stochastic MIPs: if you’re not lucky you might actually have to wait a lot of time before finding a feasible solution to your problem.*
  5. You can speed up Benders quite a lot by providing good initial bounds;
  6. Chances are that if you already got a good solution and bounds, you will get better results by MIPping it directly than by using Benders.

Tabu search sub-section:

  1. The classical, straight-out-of-the-textbook Tabu Search does not work in practice.
  2. It’s really hard to prevent long cycles in a Tabu Search.
  3. A “real” Tabu is somewhat sensitive to parameter setting, and it does not work at all until it works very well.

To be honest, I learned * in 2011 but it just fit there too well to ignore it.

Comments

  1. I totally agree with you regarding the first three points in the Benders section, similar to what I found during my Master thesis for the application of the Lagrangean relaxation to tackle a NLMIP problem. I added some cuts to Sub problems to strengthen their performance and used different ways to find good Lagrangean multipliers other than the Pure Subgradient.

Speak Your Mind

*