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].

 

Requirements

You can use RAPOSa on the following operating systems:

  • Ubuntu 18
  • CentOS 7
  • Windows 10, requires to have Visual C++ Redistributable for Visual Studio 2015 installed in the system (often preinstalled; if not, you can download them from here).


User options

The available options are:

  • help: print the help
  • maxtime: CPU time limit (default: 300 s)
  • maxtime_nonlinsolver: time limit for non linear solver (default: infinity, not supported for minos)
  • upperbound: initial upper bound (default: infinity)
  • maxiter: limit of iterations (default: 1e9)
  • varbound: new bound for all unbounded variables (default: 100) (unstable and under development)
  • tolrel: relative convergence tolerance (default: 0.001)
  • tolabs: absolute convergence tolerance (default: 0.001)
  • linsolver: the linear programming solver: "lpsolve", "gurobi" (1), "googleor-cbc", "googleor-clp" or "googleor-glop" are available (default: googleor-glop)
  • nonlinsolver: the non linear programming solver: "ipopt", "knitro" (2), "minos" (2) and "conopt" (2) are available (default: ipopt)
  • output: the output file in json format ('None' by default)
  • outlev: the output level: 0 -> only display solution (by default), 1 -> display real time reporting
  • repfreq: report frequency if outlev is set in 1 (default: 30 sec)

(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.

Not all options are compulsory. The correct way to pass the options is with "-" followed by the corresponding option and the corresponding value, as shown below:

raposa problem.nl -nonlinsolver knitro -output file.out -outlev 1 -repfreq 5 -maxtime 60

Another way to pass the options is through a file called "raposa.options" as shown below:

nonlinsolver knitro
output file.out
outlev 1
repfreq 5
maxtime 60

This file must be in the directory you are executing RAPOSa.




Example of use

You can download the files used in this section here.

Consider the following polynomial programming problem with box-constrained variables:

$$ \begin{array}{rl} \text{min} & x^2 + y^2 + x\\ \text{s.t}. & xy\geq 1\\ & 1\leq x \leq 10\\ & 1\leq y \leq 8\\ \end{array} $$

We are going to explain how to solve it through a .nl file. In this page, we explain how to create the .nl file using AMPL, Pyomo or JuMP.
 

How to formulate a polynomial programming problem in AMPL and solve it using RAPOSa in AMPL.

In AMPL, the problem would be written as follows:

var x >=1, <= 10;
var y >=0, <= 8;
minimize f: x^2 + y^2 + x^2;
subject to g: x*y >= 1;

If you want to solve this with raposa, you only need to add the following command:

option solver raposa;
solve;

If you want to run RAPOSa with a specific option, you have to add the following line before the "solve" command:

option raposa_options 'outlev=1 maxtime=60';

For more information about interacting with AMPL, you can see this link.
 

How to formulate a polynomial programming problem in AMPL and convert it to .nl format.

In AMPL, the problem would be written as follows:

var x >=1, <= 10;
var y >=0, <= 8;
minimize f: x^2 + y^2 + x^2;
subject to g: x*y >= 1;

If you save the above in a file called "problem.mod", you only need to run the following command:

ampl -ogproblem problem.mod

So, you will get the file "problem.nl" with the problem.

If in addition to the model file "problem.mod" you have a data file "problem.dat", you should run the following command:

ampl -ogproblem problem.mod problem.dat

If you want to save variables names in "problem.col" file (.nl format doesn't store the name of the variables) you need to create a file called "options.opt", with the following content:

option auxfiles c;

and then run the following command:

ampl -ogproblem problem.mod options.opt

or:

ampl -ogproblem problem.mod problem.dat options.opt

For more information on the generation of .nl files in AMPL you can see this link.
 

How to formulate a polynomial programming problem in Pyomo and convert it to .nl format

In Pyomo, the problem would be written as follows:

from pyomo.environ import *
m = ConcreteModel()
m.x = Var(bounds=(1,10))
m.y = Var(bounds=(0,8))
def obj(m):
	return (m.x*m.x + m.y*m.y + m.x)
def cons(m):
	return (m.x * m.y >= 1)
m.obj = Objective(rule=obj)
m.cons = Constraint(rule=cons)

and in order to write it in .nl format, it is necessary to add "write" command at the end, as shown below:

from pyomo.environ import *
m = ConcreteModel()
m.x = Var(bounds=(1,10))
m.y = Var(bounds=(0,8))
def obj(m):
	return (m.x*m.x + m.y*m.y + m.x)
def cons(m):
	return (m.x * m.y >= 1)
m.obj = Objective(rule=obj)
m.cons = Constraint(rule=cons)
m.write('problem.nl')

Thus, running the previous file in the python console, you obtain a .nl file which is called "problem.nl".

If you want to save variables names in "problem.col" file (.nl format doesn't store the name of the variables) you need to include the option "symbolic_solver_labels", as shown below:

from pyomo.environ import *
m = ConcreteModel()
m.x = Var(bounds=(1,10))
m.y = Var(bounds=(0,8))
def obj(m):
	return (m.x*m.x + m.y*m.y + m.x)
def cons(m):
	return (m.x * m.y >= 1)
m.obj = Objective(rule=obj)
m.cons = Constraint(rule=cons)
m.write('problem.nl',io_options='symbolic_solver_labels':True})

For more information on the generation of .nl files in Pyomo you can see this link.
 

How to formulate a polynomial programming problem in JuMP and convert it to .nl format.

In JuMP, the problem would be written as follows:

using JuMP, AmplNLWriter
m = Model(solver=AmplNLSolver("bonmin"))
@variable(m, 1 <= x <= 10 )
@variable(m, 1 <= y <= 8 )
@NLobjective(m, Min, x^2 + y^2 + x )
@NLconstraint(m, x*y >= 1.0 )

and in order to write it in .nl format, it is necessary to add several lines, as shown below:

using JuMP, AmplNLWriter
m = Model(solver=AmplNLSolver("bonmin"))
@variable(m, 1 <= x <= 10 )
@variable(m, 1 <= y <= 8 )
@NLobjective(m, Min, x^2 + y^2 + x )
@NLconstraint(m, x*y >= 1.0 )
JuMP.build(m)
m2 = m.internalModel.inner
AmplNLWriter.make_var_index!(m2)
AmplNLWriter.make_con_index!(m2)
f = open("./problem.nl","w")
AmplNLWriter.write_nl_file(f,m2)
close(f)

Thus, running the previous file in the julia console, you obtain a .nl file which is called "problem.nl".

If you want to save variables names in "problem.col" file (.nl format doesn't store the name of the variables) you need to create the "problem.col" file manually. In this case, the content would be as follows:

x
y

For more information on the generation of .nl files in JuMP you can see this link.
 

How to solve a problem in .nl format with RAPOSa

Solve a problem in .nl format with RAPOSa is easy. You only need to run the following command:

./raposa problem.nl

and RAPOSa will be executed with default options.

If you want to run it with specific options, for example a time limit of 30 seconds and gurobi as linear solver, you should run the following command:

./raposa problem.nl -maxtime 30 -linsolver gurobi

If you want to know all available options, you should run the following command:

./raposa -help

In this case, if you run the command

./raposa problem.nl -outlev 1 -output output.json

you will obtain the following output:

=====================================================================================================================
 RAPOSa v1.0.0 (2019.02.20)
 Copyright (C) 2019 ITMATI - Univ. de Santiago de Compostela (USC). All rights reserved.
 This software is free for non-commercial purposes.
 Full licence information can be found in the LICENSE.txt file.
 http://www.itmati.com/RAPOSa/index.html
=====================================================================================================================
 Linear solver: googleor-glop
 Nonlinear solver: ipopt
=====================================================================================================================
  Iteration       Time (s)       Lower Bound       Upper Bound       Relative Gap     Absolute Gap       Feas error
          1           0.00            2.0000            3.0000         0.33322226           1.0000       0.00000000
          3           0.01            3.0000            3.0000         0.00000000           0.0000       0.00000000

Global solution found after 3 iterations and 0.00871544 seconds.
Objective: 3

and the following "output.json" file:

{
        "Total time": 0.00894198,
        "Number of iterations": 3,
        "Upper bound": 3,
        "Lower bound": 3,
        "Absolute gap": 0,
        "Relative gap": 0,
        "Feasilibity error": 5.88503e-11,
        "Solution": {
                "x[0]" : 1,
                "x[1]" : 1
        }
}