Binary Optimization for GEKKO

Question

I am trying to solve a quadratic binary optimization problem with Gekko with qobj, by defining a NxN symmetric matrix and an N-dimensional bias vector at random. However I observed computational times suspiciously low: 2e-2s for solving with N=20 and 0.05s to solve a 200 dimensional problem. Also i never get more than 3-4 iterations. Am i missing something here?

import numpy as np
N = 20
#create square symmetric matrix for the quadratic term
b = np.random.normal(0,1,(N,N))
Q = (b + b.T)/2
#bias vector for linear term
c=np.random.normal(0,1,N)
from gekko import GEKKO
m = GEKKO(remote=False)
z = m.Array(m.Var,N,integer=True,lb=0,ub=1,value=1)
m.qobj(c,A=Q,x=z,otype='min')
m.solve(disp=True)

Any suggestion is appreciated!

John Hedengren John Hedengren · Accepted Answer · 2021-03-29T18:29:14

Switch to APOPT solver for Mixed Integer solution.

m.options.SOLVER=1

Here is the complete script. MIQP problems are generally very fast. It slows down significantly if the problem is nonlinear (NLP) with mixed integer elements (MINLP).

import numpy as np
N = 200
#create square symmetric matrix for the quadratic term
b = np.random.normal(0,1,(N,N))
Q = (b + b.T)/2
#bias vector for linear term
c=np.random.normal(0,1,N)
from gekko import GEKKO
m = GEKKO(remote=False)
z = m.Array(m.Var,N,integer=True,lb=0,ub=1,value=1)
m.qobj(c,A=Q,x=z,otype='min')
m.options.SOLVER=1
m.solve(disp=True)
print(z)

[[0.0] [1.0] [1.0] [0.0] [1.0] [1.0] [1.0] [1.0] [1.0] [0.0] [1.0] [1.0]
 [1.0] [1.0] [1.0] [1.0] [1.0] [1.0] [1.0] [1.0] [0.0] [1.0] [1.0] [1.0]
 [1.0] [1.0] [1.0] [1.0] [0.0] [1.0] [0.0] [1.0] [1.0] [0.0] [0.0] [0.0]
 [0.0] [1.0] [1.0] [0.0] [0.0] [1.0] [1.0] [1.0] [1.0] [1.0] [0.0] [1.0]
 [1.0] [1.0] [0.0] [1.0] [1.0] [1.0] [1.0] [1.0] [1.0] [1.0] [1.0] [0.0]
 [0.0] [1.0] [0.0] [0.0] [0.0] [0.0] [1.0] [1.0] [0.0] [0.0] [0.0] [0.0]
 [1.0] [1.0] [0.0] [0.0] [1.0] [1.0] [0.0] [1.0] [1.0] [0.0] [1.0] [1.0]
 [0.0] [1.0] [0.0] [0.0] [1.0] [1.0] [1.0] [1.0] [1.0] [1.0] [1.0] [1.0]
 [0.0] [1.0] [1.0] [1.0] [1.0] [1.0] [1.0] [1.0] [1.0] [1.0] [1.0] [1.0]
 [1.0] [1.0] [1.0] [0.0] [0.0] [0.0] [1.0] [1.0] [1.0] [1.0] [1.0] [1.0]
 [0.0] [0.0] [1.0] [1.0] [0.0] [1.0] [0.0] [1.0] [0.0] [1.0] [1.0] [1.0]
 [0.0] [0.0] [0.0] [0.0] [1.0] [0.0] [0.0] [1.0] [1.0] [0.0] [0.0] [1.0]
 [1.0] [1.0] [0.0] [1.0] [0.0] [0.0] [1.0] [1.0] [1.0] [1.0] [0.0] [1.0]
 [0.0] [0.0] [0.0] [0.0] [0.0] [0.0] [1.0] [1.0] [1.0] [1.0] [1.0] [0.0]
 [0.0] [0.0] [1.0] [1.0] [1.0] [1.0] [0.0] [1.0] [0.0] [0.0] [1.0] [1.0]
 [0.0] [0.0] [0.0] [1.0] [1.0] [1.0] [0.0] [1.0] [0.0] [1.0] [0.0] [0.0]
 [0.0] [1.0] [1.0] [1.0] [0.0] [1.0] [1.0] [0.0]]

Binary Optimization for GEKKO

1 Answers