timoberthold@fico.com

The 3 Phases of Optimization

Blog Post created by timoberthold@fico.com Advocate on Feb 12, 2018

My dishwasher tabs at home are promoted as a "three-phase system." They feature components to carry out three different tasks of cleaning dishes: softening the water (essential for the next two phases), dissolving grease (the main bit I, as a user, am interested in) and finally, some rinse aid (for a nice finish). While solving optimization problems is not a typical household chore, a Mixed-Integer Programming (MIP) solver, like FICO Xpress, can be viewed as a three-phase system.

 

The solution process consists of three distinct phases:

  1. Finding a first feasible solution: essential for the next two phases.
  2. Improving the solution quality: the main bit I, as a user, am interested in.
  3. Proving optimality: a nice finish.

 

In a recent research paper, together with our research collaboration partners from MODAL/ZIB, we show that the entire solving process can be improved by adapting the search strategy with respect to phase-specific aims using different control tunings. Since MIP is solved by a tree search algorithm, it comes as no surprise that the major tweaks were done for tree search controls. During the first phase, we used special branching and node-selection rules to quickly explore different regions of the search tree. The second phase used modified local search heuristics. During the third phase, we switched to pure depth-first-search, disabled all primal heuristics, and activated local cutting plane separation to aggressively prune the search tree.

 

phase.pngSolving phases of a MIP solution process. Point t1 marks the transition from

feasibility to improvement, t2 marks the transition from improvement to proof.

 

Additionally, we provided criteria to predict the transition between the individual phases. Just like a dishwasher, a MIP solver is a bit of a black box; sometimes it's hard to tell what's going on inside. In our case, the challenging bit was to predict the transition from the improvement phase to the proof phase. How do you know that the best solution found so far is optimal when you have not yet proven optimality? Well, you can't, but we found a good approximate criterion: we define the set of rank-1 nodes as the set of all nodes with a node estimate at least as good as the best-evaluated node at the same depth. The term rank-1 is motivated by ranking the nodes of a depth level of the search tree by an estimate of their expected solution quality, with the most promising nodes being ranked first. We trigger the transition to the last solving phase when the set of rank-1 nodes becomes empty, loosely speaking: when we start processing nodes of poor quality.

 

The combination of applying named phase transition criterion and the tuned controls for each phase led to an average increase in speed up of 14% on hard MIP instances. We also found that when you are only interested in one of the phases, like finding any feasible solution or finding good solutions without proving optimality, there is room for improvement by control tuning. You can look forward to an upcoming blog post on our performance tuner.

 

If you are interested in the math behind all of this, the article has been published in Optimization Methods and Software. A preprint is available here. The work is based on results from Gregor Hendel's Master thesis, which was supervised by me, Timo Berthold. For the experiments, we used the academic software SCIP.

 

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.

 

I hope you enjoyed the read. I have to go home now and do the dishes.

Outcomes