timoberthold@fico.com

The Path to Repeatable Solutions: Deterministic Algorithms in FICO Xpress

Blog Post created by timoberthold@fico.com Advocate on Apr 3, 2018

Reliability and reproducibility are key goals when developing the FICO Xpress solver engines; but what does that mean exactly? First, the same input to an algorithm should always lead to the same output. In addition to that, runtimes should be repeatable. Ultimately, the algorithm should always take the exact same path to the final results. This is what computer scientists call a deterministic algorithm, it makes results reproducible. That is handy, and even necessary in many different contexts:

 

  • Want to show a live demonstration to your bosses? Your software better be deterministic!
  • Want to fix a bug that one of your customers reported? Your software better be deterministic!
  • Want to report your research results in a scientific journal that peer-reviews software? Your software better be deterministic!
  • The results of your work might have legal consequences,for example, when you optimize the assignment of students to universities? Your software really, really better be deterministic!

 

I could go on, but for those reasons and many more, any commercial MIP (Mixed Integer Programming) solver that I am aware of, and even many academic solvers, are deterministic, to a certain point. That is, they are deterministic as long as they run in the same computational environment, i.e., on the same machine. Even if the input is completely identical, a different operating system, more or fewer CPU cores, or different cache sizes can destroy deterministic behavior.

 

While this probably doesn't matter for your live demonstration (as it will be on the same laptop as the test run), it is almost guaranteed to break performance in the journal peer review. For customer support, it comes down to being required to hold a farm of different machines, light ones, heavy ones, with (at least) three different operating systems to maintain. This can be a nightmare for both the developers and the IT admins.

 

concept gears.png

Reliability is a crucial aspect of optimization software.

 

This is where we at FICO Xpress outperform other solvers. To the best of my knowledge, Xpress is the only MIP solver whose solution path is identical under Windows, Linux and Mac. Our performance is also independent of the cache size. There is a dependence concerning different numbers of CPUs, but it can be overcome. The important ingredient here is that our MIP parallelization (see my earlier blog post about Parallelization of the FICO Xpress-Optimizer) does not depend on the number of actually available threads, but on the number of tasks that we hold in the queue to be scheduled in parallel. Such a task can consist of solving a node of the branch-and-bound tree or running a certain primal heuristic. Tasks do not have a one-to-one association to computing threads; therefore, they can be interrupted and be continued in a different thread in a later point in time. The idea is to always have more tasks available than there are threads.

 

The maximum number of parallel tasks can be determined via the user control MAXMIPTASKS. An important consequence of breaking the task-thread-association is that a run on a machine with X threads can always be reproduced on a machine with Y threads, no matter whether X is smaller or larger than Y. You just need to adjust the MAXMIPTASKS control in the Y-run to the value that is reported in the log file of the X-run. For example, on my 40-threaded Windows development server, the corresponding log line reads:

 

   Starting tree search.

   Deterministic mode with up to 40 running threads and up to 128 tasks.

 

So, if I want to redo a run on my 8-threaded Mac laptop, or inside my 4-threaded Linux virtual machine, I simply set MAXMIPTASKS=128, then I am good to go.

 

Albert Einstein is credited with saying: "Insanity is doing the same thing over and over again and expecting a different outcome." It's good to know that my favorite MIP solver is sane, and, moreover, offers me different ways of doing the same thing with the same outcome. This gives me the freedom to choose the way that comforts me most and is the best for the job at hand.

 

You can develop, model, and deploy FICO Xpress Optimization software for free by downloading our Community License. Learn more about FICO Xpress Optimization, ask questions, and hear from experts in the Optimization Community.

Outcomes