RAPOSa: A Global Solver for Polynomial Programming Problems

RAPOSa (Reformulation Algorithm for Polynomial Optimization - Santiago) is a global optimization solver, specifically designed for polynomial programming problems with box-constrained variables. Written entirely in C++, it is based on the Reformulation-Linearization Technique developed by Hanif D. Sherali and Cihan H. Tuncbilek [1] and subsequently improved by Hanif D. Sherali, Evrim Dalkiran and collaborators [2] [3] [4].
 

You choose the auxiliary solvers

RAPOSa leans on two subsolvers, one for the auxiliary linear subproblems and one local optimizer. They are used to generate lower and upper bounds, respectively. To date, RAPOSa can connect with the following subsolvers (some free and some commercial).

The best results are obtained with Gurobi and Knitro and the best results without a commercial subsolver are obtained with Glop and Ipopt.

(1) If you want to use gurobi, you must have a gurobi license and choose the gurobi version of RAPOSa in our download section (available soon).

(2) If you want to use knitro, CONOPT or MINOS, you must have the corresponding solver with its license.

 

Generate input files from AMPL or Pyomo

RAPOSa currently solves problems defined in AMPL, via a .nl input file obtained with an AMPL license (see examples section). However, if you are not into AMPL, you can always write your problem directly into a .nl file (see [5]) or use Pyomo or JuMP (both free) to generate a .nl file (see examples section). Support for other modeling languages like GAMS is expected to come in the future.

 

Sequential or parallel version, you choose

The branch-and-bound scheme in which the Reformulation Linearization Technique is based takes great advantage of current parallelization procedures. A parallel version of RAPOSa is also available (on demand). It can benefit on the number of cores you have access to and which can improve significantly the performance of the algorithm.

 

Features

  • Implementation of the basic RLT algorithm introduced in [1]
  • Implementation of efficient generation of bound factors via J-Sets
  • Warm start of LP solver at each node (just for Gurobi)
  • Warm generation of J-Sets at each node

 

Performance

RAPOSa has been benchmarked with general global optimization solvers for nonlinear programming problems like BARON and Couenne. The following comparison graphs represent the optimality gap obtained after a 10 minute computation on problems of different degrees borrowed from [2]. As can be seen, in quadratic problems BARON performs slightly better and there are not very big differences. However, in higher degrees the performance of RAPOSa is preferable to that of BARON and Couenne. This battery of problems can be downloaded in AMPL and .nl format at: AMPL / .nl. More details on these tests can be seen in [6].

ITMATI

ITMATI

ITMATI

 

Development Team

  • Julio González Díaz (Univ. de Santiago de Compostela)
  • Brais González Rodríguez (Univ. de Santiago de Compostela)
  • Ángel M. González Rueda (Univ. de Santiago de Compostela)
  • Joaquín Ossorio Castillo (ITMATI)
  • David Rodríguez Penas (Univ. de Santiago de Compostela)
  • Diego Rodríguez Martínez (ITMATI)

 

Bibliography

[1]: Sherali, H. D. and Tuncbilek, C. H., 1992. A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique. Journal of Global Optimization, 2(1), pp. 101-112.

[2]: Sherali, H. D., Dalkiran, E. and Liberti, L., 2012. Reduced RLT representations for nonconvex polynomial programming problems. Journal of Global Optimization, 52(3), pp. 447-469.

[3]: Sherali, H. D., Dalkiran, E. and Desai, J., 2012. Enhancing RLT-based relaxations for polynomial programming problems via a new class of v-semidefinite cuts. Computational Optimization and Applications, 52(2), pp. 483-506.

[4]: Dalkiran, E. and Sherali, H.D., 2013. Theoretical filtering of RLT bound-factor constraints for solving polynomial programming problems to global optimality. Journal of Global Optimization, 57(4), pp. 1147-1172.

[5]: Gay, D. M., 2005. Writing .nl files. Optimization and Uncertainty Estimation.

[6]: González Díaz, Julio, 2018. Computational advances in RLT algorithms: RAPOSa, a freely available implementation. International Symposium on Mathematical Programming, Bordeaux.