How to speed up integer nonlinear programming with 1446 variables in python Gekko?

user_14937012 0
Viewed 76

I'm solving an integer nonlinear programming problem with python gekko, where there're 1446 integer variable, 31 constraints of the linear combinations of there variables, and 1 nonlinear objective to maximize.

The program takes a long time and I'm wondering if it can speed up, as well as how to tune a better m.solver_options.

Here're the codes.(I only leave some comments about the variables because their computation relies on some outer data files.)

m = GEKKO()
m.options.SOLVER = 1  # APOPT is an MINLP solver
# optional solver settings with APOPT
m.solver_options = ['minlp_maximum_iterations 500',
                    'minlp_as_nlp 0',
                    'minlp_branch_method 1',
                    'minlp_integer_tol 0',
                    'nlp_maximum_iterations 50',
                    ]

# Constraint: sum of all weights <= 1
# e.g. weights = [0.04 * int_v1, 0.05 * int_v2, ..., 0.03 * int_v1446]
m.Equation(m.sum(weights) <= 1)

# Constraint: sum of weights on each cluster has an upper bound
# e.g. weights_per_cluster = {'1': [int_v2, int_v5, int_v8], '2': [int_v1, int_v4, int_v6], ..., '30': [int_v9, int_v12]}
for cluster in clusters:
    m.Equation(m.sum(weights_per_cluster[cluster]) <= 0.1)

mu_sig_raw = np.array(mu_sig_raw).transpose() # real value, shape (106, 1446)
mu = np.mean(mu_sig_raw, axis=0) # real value, shape (1446, 1)
sigma = np.cov(np.transpose(mu_sig_raw)) # real value, shape (1446, 1446)

k = len(mu)
# Objective: profit-rate mean-variance model
m.Maximize(
    (m.sum([mu[i] * weights[i] for i in range(k)]) - 0.03)
    /
    m.sqrt(m.sum([
            m.sum([sigma[i, j] * weights[i] * weights[j] for j in range(k)])
            for i in range(k)
    ]))
)

m.solve(disp=True)
gekko python
1 Answers

The APOPT solver can be slow with many degrees of freedom (# Variables >> # Equations) or many integer variables. One strategy is to initialize with the IPOPT solver and then switch to APOPT for an integer solution.

m.options.SOLVER=3 # IPOPT
m.solve()

m.options.SOLVER=1 # APOPT
m.solve()

Another thing that can help is to redefine the inequalities as variables and set an upper bound on that variable.

for cluster in clusters:
    m.Equation(m.sum(weights_per_cluster[cluster]) <= 0.1)

Transform to:

v = []
for cluster in clusters:
    v.append(m.Var(ub=0.1))
    m.Equation(m.sum(weights_per_cluster[cluster]) == v[-1])

You may also want to further adjust the solver options. The APOPT solver has a number of options that are available for tuning the solver performance. Some of the available options and default values are listed below:

  • minlp_maximum_iterations 10000 - maximum number of nlp solutions from the branch and bound method. A successful solution is returned if there is an integer solution upon reaching the maximum number of iterations. Otherwise, the solution is not considered to be successful, and an error message is returned with the failed solution.
  • minlp_max_iter_with_int_sol 500 - maximum number of nlp solutions when a candidate integer solution is found
  • minlp_as_nlp 1 - solve minlp problem as a continuous nlp problem, ignoring integer constraints
  • minlp_branch_method 3 - 1=depth first (find integer solution faster), 2=breadth first, 3=lowest objective leaf, 4=highest objective leaf
  • minlp_gap_tol 1.0e-2 - gap is the spread between the lowest candidate leaf (obj_r=non-integer solution) and the best integer solution (obj_i). When the gap is below the minlp_gap_tol, the best integer solution is returned. The gap is defined as gap=(obj_i-obj_r)/max((abs(obj_i)+abs(obj_r))/2,1).
  • minlp_integer_tol 1.0e-2 - amount that a candidate solution variable can deviate from an integer solution and still be considered an integer.
  • minlp_integer_max 2.0e9 - maximum value to be considered as an integer. Values over 2147483647 or below -2147483648 not stored correctly with an internal integer variable type because of the number of bits used to store an integer.
  • minlp_integer_leaves 1 - add additional integer leaves, 0=off, 1=integer leaves with inequality on branching, 2=integer leaves with equality constraint on branching.
  • minlp_print_level 1 - print level (0-10). Development version has additional advanced diagnostics.
  • nlp_maximum_iterations 500 - maximum number of iterations for each nlp sub-problem. Reducing the nlp maximum iterations can improve the solution speed because less computational time is spent on candidate solutions that may not converge
  • objective_convergence_tolerance 1.0e-6 - convergence tolerance for the objective function. Values lower than 1.0e-10 sometimes run into covergence problems because of numerical scaling and cannot achieve the requested accuracy.
  • constraint_convergence_tolerance 1.0e-6 - convergence tolerance for the constraints. A lower convergence tolerance typically adds only a couple additional iterations to the solution, but the solution also does not change significantly.

If an integer solution is found, the minlp_gap_tol may help improve the solution time if the integer solution has a small enough gap. Because the complete script is not posted, we can't test any proposed improvements. Please consider posting a complete script for future questions.

user_23669410
Related