Solved

Error when solving non-linear model with AIMMS Outer Approximation Algorithm

  • 5 May 2023
  • 8 replies
  • 131 views

Badge +1

Model description

We have a non-linear mathematical model with the following set, variables, and parameters:

Set

t in [1,N_T]

 

 

Variables

x_t

y

 

Parameters

A

B

C_t

 

And the following objective function:

min{sum((x_t-A)/A) for all t}

Subject to:

x_t = x_{t-1} + B(Ay - x_{t-1}y - C_{t-1})

x_t >= 0

1<= y <= 2499999

With the initial value of the variable x_t being:

x_1 = 19,500

The values of the set are:

t = [1 2 3 4 5 6 7 8 9 10]

The values of the parameters are:

A = 21,500

B = 0.00095

C_t = [50,000 50,240 50,300 51,000 51,040 50,700 50,800 50,200 49,000 48,700]

Solving

The non-linearity in the problem lies in the following product in the constraint:

x_{t-1}y

We have implemented the model in AIMMS and tried the Outer Approximation algorithm for this problem, but get the following error message:

The generated mathematical program “OA_NLP” has type “QCP” which cannot be changed into “RMINLP”.

What might be causing this message?

 

Also, does anyone have suggestions on other ways to solve this model, for example ways to linearise it?

icon

Best answer by Marcel Hunting 15 May 2023, 14:58

View original

8 replies

Userlevel 5
Badge +4

Hi @kin006. It seems that your model does not contain any integer or binary variables. The AIMMS Outer Approximation Algorithm can only be used for nonlinear models containing integer or binary variables (MINLP, MIQCP, MIQP).

Your model seems to be a non-convex QCP. If you are using an academic license then you could use Gurobi or Octeract to solve the model. Note that to use Gurobi in AIMMS you need to apply for a Gurobi Solver license from Gurobi Optimization.

It is not possible to linearize x * y if x and y are continuous variables.

@Marcel Hunting is CPLEX not able to address non-convex QCP?

Userlevel 5
Badge +4

@Ramteen CPLEX can handle non-convex (MI)QP but it cannot handle non-convex (MI)QCP.

Badge +1

Thank you very much for your help @Marcel Hunting!

The model I described is a simplified version of the original model I want to solve. In the original model, I have if-else constraints, which I model by using binary variables. Then I would think the model can be solved by Outer Approximation Algorithm, Gurobi or CPLEX, but I also get products of three variables in the constraints: wyu and x_{t-1}yu), where the variable u is binary. I wrote a description of the model below, and I will be very grateful if anyone has any suggestions on solvers for this problem or other tricks for solving such a model.

 

Model description

Objective function:

min{sum((x_t-A)/A) for all t}

 

The values of the set are:

t=[1 2 3 4 5 6 7 8 9 10]

 

The initial value of the variable x_t is:

x_1=19,500

 

Constraints:

x_t=x_{t-1} B[(A + w(D/2) x{t-1})y]u - BC_{t-1}

 

(A + (D/2) x_{t-1})y ≥ X_{min}

(A - (D/2) x_{t-1})y ≤ X_{max}

1 ≤ y ≤ 2.499,999

 

A - (D/2) x_{t-1} ≤ uA_x

A + (D/2) x_{t-1} ≥ -uA_x

u binary

 

A_x=2,500,000

A+(D/2)-x_{t-1} ≤ (1-v)A_y

A-(D/2)-x_{t-1} ≥ -vA_y

v binary

w = 2v - 1

A_y=2,500,000 + D

Parameter values:

A = 21500

X_{min} = -2,500,000         ,            X_{max} = 2,500,000

B = 0.00095

C_= [50000 50240 50300 51000 51040 50700 50800 50200 49000 48700]

D = 400

Userlevel 5
Badge +4

Hi @kin006. Your model is a non-convex MINLP. It can be solved by the Outer Approximation Algorithm but it will only find a local optimum. The gobal solvers Octeract and BARON will find a global optimum. Please note that Octeract is available as part of the free AIMMS Academic License but BARON is not.

You can reformulate

x(t) = x(t-1) + B[(A + w(D/2) - x(t-1))y]u - BC(t-1)

as

x(t) = x(t-1) + B[z(t-1)]u - BC(t-1)

z(t) = (A + w(D/2) - x(t))y

and then you get a non-convex MIQCP which can be solved by Gurobi. Here z(t) is a new variable with range ‘free’. Please note that to solve a non-convex (MI)QCP you have to set the Gurobi option ‘Nonconvex strategy’ to ‘Translate’.

Badge +1

Thank you very much for replying to my questions, @Marcel Hunting!

I have implemented the model as you described, with the new variable z(t) with range ‘free’, and with the Gurobi option ‘Nonconvex strategy’ to ‘Translate’. However, I get an error message that the mathematical problem is not quadratic when I manually try to define it as a MIQCP.

The new variable z(t) is defined as a fragment of the definition of the variable x(t), but how does this change the problem from MINLP to MIQCP? I guess I am missing something here.

Again, I appreciate your help! :)

Userlevel 5
Badge +4

Hi @kin006. The reformulation that I proposed should be quadratic. I have no idea why AIMMS generates your model as a MINLP. To investigate this I would need to see your AIMMS model. Could you please add your AIMMS project here, preferably after adding it to a zip file, or send it to our support by email if your project contains sensitive information?

Badge +1

Thank you, @Marcel Hunting! I am going through my model and implementation in AIMMS to see if there are any bugs that I can fix that might be the reason why the model is not becoming quadratic. If I am still not able to solve the model, I will send it to the support email :)

Reply


Didn't find what you were looking for? Try searching on our documentation pages:

AIMMS Developer & PRO | AIMMS How-To | AIMMS SC Navigator