RAPOSa: A Global Solver for Polynomial Programming Problems

RAPOSa logo


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.

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

 

Run directly from AMPL or from nl files

RAPOSa currently solves problems directly from AMPL and via a .nl input file obtained with AMPL, Pyomo or JuMP. See the examples section for more information.

 

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 RAPOSa performs slightly better than BARON and Couenne. Moreover, in degree 4 problems the performance of RAPOSa is much better. Finally, in degree 6, the performance of RAPOSa is better than the performance of BARON and similar to the performance of 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] and [7].

ITMATI

ITMATI

ITMATI

 

Development Team

  • Gabriel Álvarez Castro (ITMATI)
  • 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 A Coruña)
  • Joaquín Ossorio Castillo (ITMATI)
  • Beatriz Pateiro López (Univ. de Santiago de Compostela)
  • 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.

[7]: González Rodríguez, Brais, 2019. RAPOSa, a freely available solver for polynomial optimization problems. International Conference on Continuous Optimization, Berlin.