timoberthold@fico.com

To go where no Optimizer has gone before

Blog Post created by timoberthold@fico.com on Oct 3, 2017

Mixed-Integer programming (MIP) solvers like FICO Xpress address the most challenging optimization problems. About every seven years a new test library of MIP instances is released, the MIPLIB (see our blog post Call for MIPLIB 2017 Submissions). Besides a benchmarking set, MIPLIB always contains unsolved "challenge" instances which the scientific community tries to tackle for the years after a MIPLIB release. Sometimes, it is new algorithms that are the key to solving an instance, e.g., in December 2016, Xpress 8.1 could solve the previously unsolved instance pigeon-19 in less than a second by the use of special cutting plane techniques.

 

Sometimes, however, it is sheer computation power that makes the difference. Together with our cooperation partners at the Research Campus MODAL in Berlin, we developed a ground-breaking, massively parallel version of Xpress, called ParaXpress. ParaXpress is an academic expert code which can perform awesome feats with a bit of hand-crafting for each individual run. For considerations on parallelizing a MIP solver, see our blog posts on Parallelization of the FICO Xpress-Optimizer and on The Two Faces of Parallelism. ParaXpress runs FICO Xpress on supercomputers with tens of thousands of CPU cores, harnessing the computational power of hundreds of CPU years within a few hours.

 

ws17.jpgParticipants of the 2nd German-Japanese workshop on Mathematical Optimization and Data Analysis

 

At the 2nd German-Japanese workshop on Mathematical Optimization and Data Analysis at ZIB, Prof. Dr. Yuji Shinano  from MODAL, the master brain behind the ParaXpress development proudly presented the latest achievements: Two previously unsolved instances from MIPLIB2010, gmut-75-50 and gmut-77-40, could be solved for the first time ever by ParaXpress. Those are the first MIPLIB challenge instances solved in 2017.

 

To achieve this feat, we used the ISM supercomputer (located in Tokyo) and the HLRN-III supercomputer (located in Berlin), both members of the TOP500 list. We used up to 24576 CPU cores in parallel. Finding and proving the optimal solution took about eight hours per instance (this rolls out to 115000 CPU hours, that's 13 CPU years), exploring about twenty billion branch-and-bound nodes.

 

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