Solving the Unsolvable - conquering large scale optimization problems

Document created by neillcrossley@fico.com Advocate on Aug 7, 2017Last modified by neillcrossley@fico.com Advocate on Sep 8, 2017
Version 10Show Document
  • View in full screen mode

Solving large, complex optimization problems can be a daunting task.

Conquering them effectively, however, can be the difference between success and failure in today's highly competitive marketplace.

As problems grow in size and scope, it becomes increasingly difficult to get answers in a timely manner. Recent improvements in optimization solver engine performance have not been sufficient to deal with the challenge of these increasingly complex problems. In many cases, optimization problems are too large to fit into memory, require too much time to compute or are simply too hard to solve.

 

For these reasons, simply boosting the computational horsepower is often not enough. As one of the ways to address the scalability issue, next generation solver engines must look for ways to decompose problems into smaller, more manageable components. Doing so will allow even the most complex problems to be solved so that key tactical, strategic, and operational decisions can still be made with confidence. Organizations that solve problems efficiently at all levels of complexity have a unique competitive advantage. To this end FICO Xpress Optimization has a number of capabilities that make large-scale optimization problems more manageable and help turn the unsolvable into solvable.

 

The key element in making this happen is Decomposition.

Decomposition is simply the process of breaking large optimization problems into smaller, more manageable sub-problems and solving them either sequentially or in parallel.

 

There are two well-known methods to decomposition:

  • Benders, a row generation approach
  • Dantzig-Wolfe, a column generation approach
Mosel Decomposition.PNG

The solvers and modeling tools on FICO Xpress Optimization support the implementation of decomposition approaches in various ways, illustrated right. Most importantly, the unique features of the Xpress Mosel modeling language make it a particularly suitable platform for the development of decomposition.

 

Schemes of decomposition and concurrent solving that can be implemented with Xpress Mosel include:

  • Simple parallel runs (different data instances; different algorithm configurations)
  • Decomposition approaches (Benders; Dantzig-Wolfe)
  • Column generation (loop over top node; branch-and-price)
  • Cut generation (cut-and-branch; branch-and-cut)

 

Xpress Mosel is a high-level modeling language combined with standard functionality of programming languages allowing for the implementation of models and solution algorithms in a single environment. Through its open, modular architecture, extensions to the language can be made without any need for modifications to the core system. The platform independent compiled models (BIM) are portable across all platforms supported by Xpress Optimization and protect your intellectual property on deployment. Various library interfaces are available for embedding models into applications (c, Java, C#, VB). Model development and analysis is supported by the integrated development environment Xpress Workbench and set of tools (debugger, profiler).

 

More Information:

Attachments

    Outcomes