What types of optimization problems does UG solve?

UG, as a stand-alone solver using SCIP as the underlying base solver, is called FiberSCIP and ParaSCIP can solve mixed-integer linear and nonlinear programs. For solving MINLP it applies an LP based spatial branch-and-cut algorithm, that is guaranteed to solve bounded MINLPs within a given numerical tolerance in a finite amount of time.

The SCIP applications

• STP (Steiner Tree Problem) and its applications, also known as SCIP-Jack, and
• MISDPs (mixed integer semidefinite programs) provided by SCIP-SDP,

are parallelized by UG. They can be solved as stand-alone UG applications.

Any branch-and-bound based solver for a specific problem, which is realized by SCIP plugins, can easily parallelized by adding a small lines of glue code.

(see, An Easy Way to Build Parallel State-of-the-art Combinatorial Optimization Problem Solvers: A Computational Study on Solving Steiner Tree Problems and Mixed Integer Semidefinite Programs by using ug[SCIP-*,*]-Libraries)

In the UG framework, the underlying base solver is abstracted. By adding the UG wrapper code etc. for a specific optimization problem, a massively parallel solver for the problem can be built. Ongoing projects are the following:

• Quadratic Assignment Problem (QAP): DNN relaxation with Newton Bracket method based branch-and-bound solver is parallelized (see, Solving Challenging Large Scale QAPs).
• Traveling Salesman Problem (TSP): Concorde TSP solver has been parallelized by UG.
• MIP: Another MIP solver, in which multi-threaded FICO Xpress solver is used as underlying base solver (see, ParaXpress: an experimental extension of the FICO Xpress-Optimizer to solve hard MIPs on supercomputers).

Also, UG version 1.0 can be used to parallelize non-branch-and-bound based solvers: A Shortest Vector Problem (SVP : see SVP Challenge) solver has been parallelized by UG.