Mixed-integer nonlinear programming

Knitro provides tools for solving optimization models (both linear and nonlinear) with binary or integer variables. The Knitro mixed-integer programming (MIP) code offers two algorithms for mixed-integer nonlinear programming (MINLP):

  • A nonlinear branch-and-bound (NLPBB) algorithm

  • A mixed-integer sequential quadratic programming (MISQP) algorithm

The desired algorithm can be selected using the mip_method option.

The MISQP algorithm is designed for problems with expensive function evaluations, and can handle non-relaxable integer variables. In the other cases, the NLPBB algorithm should be preferred.

Setting variables as binary/integer

AMPL example

Using MINLP features in AMPL is very simple: one only has to declare variables as integer in the AMPL model. In our toy example, from Getting started with AMPL let us modify the declaration of variable x as follows:

var x{j in 1..3} >= 0 integer;

and then run the example again. The Knitro log now mentions 3 integer variables, and displays additional statistics related to the MIP solve.

=======================================
          Commercial License
         Artelys Knitro 14.1.0
=======================================

concurrent_evals:        0
datacheck:               0
hessian_no_f:            1
The problem is identified as a MIQCQP.
Knitro changing mip_method from AUTO to 1.
Knitro changing mip_rootalg from AUTO to 1.
Knitro changing mip_lpalg from AUTO to 3.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 0.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_pseudoinit from AUTO to 1.

Problem Characteristics
-----------------------
Objective goal:  Minimize
Objective type:  quadratic
Number of variables:                                  3
    bounded below only:                               3
    bounded above only:                               0
    bounded below and above:                          0
    fixed:                                            0
    free:                                             0
Number of binary variables:                           0
Number of integer variables:                          3
Number of constraints:                                2
    linear equalities:                                1
    quadratic equalities:                             0
    gen. nonlinear equalities:                        0
    linear one-sided inequalities:                    0
    quadratic one-sided inequalities:                 1
    gen. nonlinear one-sided inequalities:            0
    linear two-sided inequalities:                    0
    quadratic two-sided inequalities:                 0
    gen. nonlinear two-sided inequalities:            0
Number of nonzeros in Jacobian:                       6
Number of nonzeros in Hessian:                        5

Knitro detected 0 GUB constraints
Knitro derived 0 knapsack covers after examining 0 constraints
       Nodes        Best solution      Bound       Gap
   Expl  |  Unexpl      value
      1       0      936.000 LEAF      936.000      0.00%

EXIT: Optimal solution found (assuming convexity).

Final Statistics for MIP
------------------------
Final objective value               =  9.36000000000000e+02
Final bound value                   =  9.36000000000000e+02
Final optimality gap (abs / rel)    =  0.00e+00 / 0.00e+00 (0.00%)
# of nodes processed                =  1
# of subproblems processed          =  1 (0.002s)
# of strong branching evaluations   =  0 (0.000s)
Total program time (secs)           =  0.00366 (0.004 CPU time)
Time spent in evaluations (secs)    =  0.00000

Cuts statistics (computed / added)
----------------------------------
Knapsack cuts                       =  0 / 0
Mixed-Integer Rounding cuts         =  0 / 0

Heuristics statistics (calls / sucesses / time)
-----------------------------------------------
Feasibility pump                    =  0 / 0 / 0.000
Rounding heuristic                  =  0 / 0 / 0.000
MPEC heuristic                      =  0 / 0 / 0.000

Knitro 14.1.0: Locally optimal or satisfactory solution.
objective 936; optimality gap 0
1 nodes; 1 subproblem solves

Note that this example is not particularly interesting since the two solutions we know for the continuous version of this problem are already integer “by chance”. As a consequence, the MINLP solve returns the same solution as the continuous solve. However, if for instance you change the first constraint to:

s.t. c1: 8*x[1] + 14*x[2] + 7*x[3] - 50 = 0;

instead of:

s.t. c1: 8*x[1] + 14*x[2] + 7*x[3] - 56 = 0;

you will observe that the integer solution differs from the continuous one.

MATLAB example

To use the MINLP features in MATLAB, one must use the function knitro_minlp (knitro_minlp), for models with nonlinear features or knitro_milp (knitro_milp) for mixed-integer linear programs. The function signature for knitro_minlp is very similar to knitro_nlp (and similarly for knitro_milp compared with knitro_lp), but with the additional xType array to specify which variables are integer or binary.

The array xType sets the variable types and must be the same length as x0 if it is used. Continuous, integer, and binary variables are set with 0, 1, and 2, respectively. Passing an empty array, [], is equivalent to an array of all zeros.

Modifying the toy example in MATLAB to use integer variables can be done as follows:

xType = [2;2;2];

%modify the solver call
x = knitro_minlp(obj, x0, xType, A, b, Aeq, beq, lb, ub, nlcon);

See Knitro / MATLAB reference for more details.

C example

As with AMPL, defining a MIP problem only requires declaring integer variables via the API function KN_set_var_types() (by default, variables are assumed to be continuous).

In order to turn our C toy example into a MINLP problem, it thus suffices to add

/* in the declarations */
int i;

/* mark all variables as integer */
for (i=0; i<n; i++) {
    error = KN_set_var_type (kc, i, KN_VARTYPE_INTEGER);
}

The Knitro log will look similar to what we observed in the AMPL example above. Again, this example is quite unusual in the sense that the continuous solution is already integer, which of course is not the case in general.

Object-oriented C++ example

A MIP problem is defined and solved via the object-oriented interface by adding additional problem information in the problem class.

In the following, we will define how to turn the toy example into a MINLP problem. The ProblemQCQP1 class has to be extended with new definitions:

setVarTypes({ {0, 1, 2}, {KN_VARTYPE_INTEGER, KN_VARTYPE_INTEGER, KN_VARTYPE_INTEGER} });

This is the sparse method of setting variable types. It sets variables 0, 1 and 2 to be integer. As there are only 3 variables, this can be done in a dense fashion:

setVarTypes({ {KN_VARTYPE_INTEGER, KN_VARTYPE_INTEGER, KN_VARTYPE_INTEGER} });

The Knitro log will look similar to what we observed in the AMPL example above. Again, this example is quite unusual in the sense that the continuous solution is already integer, which of course is not the case in general.

Nonlinear branch-and-bound algorithm

Overview

The NLPBB algorithm is a standard branch-and-bound algorithm for nonlinear optimization. This method involves solving a relaxed, continuous nonlinear optimization subproblem at every node of the branch-and-bounds tree. This method is generally the preferred method.

It is an exact algorithm for convex models, and in this case the optimality gap measure can be trusted.

It is also designed to work well on non-convex models. However, it may not return a globally optimal solutions in this case. In addition, the optimality gap measure may not be accurate since this measure is based on the assumption that the nonlinear optimization subproblems are always solved to global optimality (which may not be the case when the model is non-convex).

Multi-start

Since Knitro 14.1, it is neither necessary nor recommended to set multi-start options for mixed-integer problems anymore. Knitro adapts its behavior automatically and dynamically when it detects it needs to.

Termination criteria

The NLPBB algorithm can be stopped early based on the following criteria:

Callbacks

The NLPBB procedure provides a user callback utility that can be used in the callable library API to retrieve information during the branch-and-bound tree exploration.

This callback is not called at each node, but regularly during the search. Even if parallelism is enabled, this callback is thread safe: it will never be called more than once at the same time.

int  KNITRO_API KN_set_mip_node_callback (KN_context_ptr            kc,
                                          KN_user_callback * const  fnPtr,
                                          void             * const  userParams);

See the Callable library API reference section in the Reference Manual for details on setting this callback function and the prototype for this callback function.

Heuristics

In a raw implementation of an NLPBB algorithm, feasible solutions are only found at the end of the algorithm. This behavior is not desirable in practice. To overcome this, heuristics are called regularly during the search. The goal of heuristics is to find good feasible solutions. Knitro implements various heuristics in its NLPBB:

  • Rounding heuristics: Rounding heuristics round the fractional solution of the node subproblem relaxations and solve a new NLP subproblem with integer variables fixed. If a feasible solution to this NLP is found, then it is a feasible solution for the original MINLP. Corresponding option: mip_rounding.

  • An MPEC heuristic: The MPEC heuristic is available for problems with only binary variables and not when a problem has more general integer variables. This heuristic solves an NLP problem where the integrality constraints are handled through complementarity constraints. Corresponding option: mip_heuristic_mpec.

  • A feasibility pump heuristic: The feasibility pump heuristic alternatively solves two NLP subproblems. In this first one, integer variables are fixed at integer values. If this subproblem is infeasible, the second NLP looks for a feasible point (except for the integrality constraints) as close as possible to the integer infeasible point. The solution of this second NLP subproblem is then rounded to fix the values of the integer variables for the first NLP subproblem. Corresponding option: mip_heuristic_feaspump.

  • A local search heuristic: This heuristic iteratively performs small changes to an initial possibly infeasible point to find a feasible or improving solution. Corresponding option: mip_heuristic_localsearch.

  • Diving heuristics: Diving heuristics perform a partial depth-first search exploration of the branch-and-bound tree. Dedicated branching rules aimed at increasing the chances of finding a good feasible solution are used, instead of the regular branching rules aimed at minimizing the number of nodes explored. Corresponding option: mip_heuristic_diving.

  • Large neighborhood search heuristics: Large neighborhood search heuristics fix a large fraction of the binary and integer variables and then solve the resulting MINLP subproblem. Corresponding option: mip_heuristic_lns.

  • An MISQP heuristic: the MISQP heuristic runs the MISQP algorithm on the problem. Note that it is only relevant for a general MINLP, and not for an MIQCQP, since in this case, the subproblem is the same as the original problem. Corresponding option: mip_heuristic_misqp.

The general behavior of heuristics in Knitro can be controlled with the mip_heuristic_strategy option.

In the log, feasible solutions are displayed in the “Best solution value” column. The string next to the solution value indicates how the solution has been found. Additional statistics are available at the end of the log in the “Heuristics statistics” section.

=======================================
          Commercial License
         Artelys Knitro 14.1.0
=======================================

No start point provided -- Knitro computing one.

concurrent_evals:        0
datacheck:               0
hessian_no_f:            1
Knitro changing mip_method from AUTO to 1.
Knitro changing mip_rootalg from AUTO to 1.
Knitro changing mip_lpalg from AUTO to 3.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 0.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_pseudoinit from AUTO to 1.

Problem Characteristics
-----------------------
Objective goal:  Maximize
Objective type:  linear
Number of variables:                                568
    bounded below only:                             489
    bounded above only:                               0
    bounded below and above:                         79
    fixed:                                            0
    free:                                             0
Number of binary variables:                          72
Number of integer variables:                          0
Number of constraints:                              837
    linear equalities:                              388
    quadratic equalities:                             0
    gen. nonlinear equalities:                        0
    linear one-sided inequalities:                  421
    quadratic one-sided inequalities:                 0
    gen. nonlinear one-sided inequalities:           28
    linear two-sided inequalities:                    0
    quadratic two-sided inequalities:                 0
    gen. nonlinear two-sided inequalities:            0
Number of nonzeros in Jacobian:                    1892
Number of nonzeros in Hessian:                      108

Knitro using Branch and Bound method with 8 threads.

Root node relaxation
--------------------

 Iter      Objective      Feasibility        Optimality       Time
                             error              error        (secs)
 ----      ---------      -----------        ----------      ------
    1        1442.06          23.0795           7.55016       0.103
    2        1225.73          16.9986           5.82697       0.104
    3        1107.15          14.8133           3.93535       0.106
    4        875.113          9.44474           2.34635       0.107
    5        738.924          6.44912           4.39287       0.109
    6        393.470          2.64552           2.56055       0.110
    7        143.641         0.294228           3.20966       0.120
    8        197.342      9.07371e-02           1.00048       0.123
    9        248.700      3.62049e-02          0.282786       0.124
   10        316.813      2.37936e-02          0.137491       0.126
   11        336.444      8.58772e-03       4.87589e-02       0.127
   12        346.296      9.93823e-04       6.01516e-02       0.129
   13        349.494      4.07988e-04       8.04447e-02       0.132
   14        351.512      8.69325e-05       2.25036e-02       0.133
   15        352.257      2.30812e-05          0.332156       0.136
   16        352.308      1.03624e-05           2.37838       0.137
   17        352.310      1.04646e-05           4.99722       0.139
   18        352.310      8.07938e-07           1.72924       0.141
   19        352.310      1.52211e-07          0.112212       0.142
   20        352.310      6.66994e-10       2.54080e-02       0.150
   21        352.310      7.78636e-11       1.51057e-02       0.153
   22        352.310      1.77726e-12       1.59590e-08       0.155
   23        352.310      1.77726e-12       1.59590e-08       0.156
   24        352.310      1.77726e-12       1.59590e-08       0.159

Tree search
-----------

       Nodes        Best solution   Best bound      Gap       Time
   Expl  |  Unexpl      value         value                  (secs)
   ---------------  -------------   ----------      ---      ------
      1       2                        352.310                0.162
      3       4      256.097   FP      344.264     34.43%     0.334
     74      57      317.494 FCRD      328.320      3.41%     1.368
    145      46      325.555 FCRD      326.926      0.42%     1.498
    165      32      325.555           325.555     -0.00%     1.509

EXIT: Optimal solution found (assuming convexity).

HINT: The problem may be a non-convex mixed-integer problem.  Set
      mip_multistart=1 to enable a mixed-integer multistart heuristic,
      which may improve the chances of finding the global solution.

Final Statistics for MIP
------------------------
Final objective value               =  3.25554562174787e+02
Final bound value                   =  3.25554550653924e+02
Final optimality gap (abs / rel)    =  -1.15e-05 / -3.54e-08 (-0.00%)
# of root cutting plane rounds      =  0
# of restarts                       =  0
# of nodes processed                =  165 (4.342s)
# of strong branching evaluations   =  0 (0.000s)
# of function evaluations           =  3191 (0.038s)
# of gradient evaluations           =  3151 (0.041s)
# of hessian evaluations            =  2897 (0.113s)
# of hessian-vector evaluations     =  0
# of subproblems processed          =  129 (4.799s)
Total program time (secs)           =  1.56151 (5.031 CPU time)
Time spent in evaluations (secs)    =  0.19222

Cuts statistics (gen / add)
---------------------------
Knapsack cuts                       =  0 / 0
Mixed-integer rounding cuts         =  0 / 0
Flow-cover cuts                     =  0 / 0
Probing cuts                        =  0 / 0

Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump                    =  1 / 1 / 0.082s
Rounding heuristic                  =  14 / 13 / 0.152s
MPEC heuristic                      =  1 / 1 / 0.252s

===========================================================================

Knitro 14.1.0: Locally optimal or satisfactory solution.
objective 325.55456217478707; optimality gap -1.15e-05
165 nodes; 129 subproblem solves

In this example, a first feasible solution of value 256.097 is found by the feasibility pump heuristic (FP). Then, two better feasible solutions are found by rounding heuristics (FCRD), the latter being optimal.

Cuts

Cuts are valid constraints that are not in the original problem, but that the solver manages to infer. These constraints are valid for the original problem, but not necessarily for its relaxation. Thus, they might improve the value of the relaxation and lead to smaller branch-and-bound trees.

The solver looks for cuts during node processing after the relaxation has been solved. If it finds cuts violated by the solution of the relaxation, it adds them to the model and re-computes its relaxation.

Knitro includes several strategies to infer cuts that can be controlled with the corresponding options:

The general behavior of cuts in Knitro can be controlled with the mip_cut_strategy option.

The logs contain a dedicated section for the root node cutting plane algorithm that shows the cut loop at the root node. Additional statistics are available at the end of the log in the “Cuts statistics” section.

=======================================
          Commercial License
         Artelys Knitro 14.1.0
=======================================

No start point provided -- Knitro computing one.

concurrent_evals:        0
datacheck:               0
hessian_no_f:            1
The problem is identified as a convex MIQP.
Knitro changing mip_method from AUTO to 1.
Knitro changing mip_rootalg from AUTO to 1.
Knitro changing mip_lpalg from AUTO to 3.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 1.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 0.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_pseudoinit from AUTO to 1.

Problem Characteristics
-----------------------
Objective goal:  Minimize
Objective type:  quadratic
Number of variables:                                960
    bounded below only:                               0
    bounded above only:                               0
    bounded below and above:                        720
    fixed:                                            0
    free:                                           240
Number of binary variables:                         720
Number of integer variables:                          0
Number of constraints:                             5329
    linear equalities:                               24
    quadratic equalities:                             0
    gen. nonlinear equalities:                        0
    linear one-sided inequalities:                 5305
    quadratic one-sided inequalities:                 0
    gen. nonlinear one-sided inequalities:            0
    linear two-sided inequalities:                    0
    quadratic two-sided inequalities:                 0
    gen. nonlinear two-sided inequalities:            0
Number of nonzeros in Jacobian:                   11444
Number of nonzeros in Hessian:                      240

Knitro using Branch and Bound method with 8 threads.

Root node relaxation
--------------------

 Iter      Objective      Feasibility        Optimality       Time
                             error              error        (secs)
 ----      ---------      -----------        ----------      ------
    1        195790.          1044.38           43.2671       0.101
    2        195148.          1044.36           25.0342       0.109
    3        748387.          2635.41           25.0342       0.114
    4        658502.          53.7644           43.2671       0.120
    5        656226.         0.690997           43.2671       0.135
    6        652982.         0.497964           43.2671       0.142
    7        637536.         0.104836           43.2671       0.146
    8        634823.      6.18016e-02           43.2671       0.153
    9        630366.      2.21319e-03           28.2639       0.164
   10        627435.      2.50206e-05           5.80827       0.169
   11        621811.      2.16121e-05           3.48621       0.181
   12        589708.      1.63046e-06           1.92004       0.196
   13        576183.      1.68210e-07           1.05835       0.203
   14        574231.      1.02064e-07           1.00229       0.214
   15        570516.      1.22875e-08          0.274724       0.228
   16        569618.      7.81793e-08       5.35004e-02       0.235
   17        569370.      4.93326e-08       1.08262e-02       0.241
   18        569306.      1.54418e-08       2.51111e-03       0.246
   19        569299.      1.11281e-09       9.15305e-05       0.250
   20        569299.      5.38114e-10       6.99464e-05       0.264
   21        569299.      5.38114e-10       6.99464e-05       0.270

Root node cutting planes
------------------------

 Iter     Cuts      Best solution   Best bound      Gap       Time
                        value         value                  (secs)
 ----     ----      -------------   ----------      ---      ------
    0        0                         569299.                0.317
    0       88                         569299.                0.462
    0       88                         576564.                0.535
    1       88                         576564.                0.641
    1       88                         576719.                0.792
    1       88                         576719.                0.886
    2      100       581223.   FP      576719.      0.77%     0.971
    2      100       581223.           576719.      0.77%     1.026
    2      100       581223.           576719.      0.77%     1.059

Tree search
-----------

       Nodes        Best solution   Best bound      Gap       Time
   Expl  |  Unexpl      value         value                  (secs)
   ---------------  -------------   ----------      ---      ------
      1       2      581223.           576759.      0.77%     1.068
      1       2      579254.   FP      577007.      0.39%     1.346
    109     106      578234. FCRD      577982.      0.04%     7.661
    126     123      578177. FCRD      578136.      0.01%     7.940

EXIT: Optimal solution found.

Final Statistics for MIP
------------------------
Final objective value               =  5.78176639004716e+05
Final bound value                   =  5.78135906593907e+05
Final optimality gap (abs / rel)    =  4.07e+01 / 7.04e-05 (0.01%)
# of root cutting plane rounds      =  3
# of restarts                       =  0
# of nodes processed                =  126 (21.191s)
# of strong branching evaluations   =  0 (0.000s)
# of function evaluations           =  0 (0.000s)
# of gradient evaluations           =  0 (0.000s)
# of hessian evaluations            =  0 (0.000s)
# of hessian-vector evaluations     =  0
# of subproblems processed          =  214 (22.872s)
Total program time (secs)           =  8.10463 (28.094 CPU time)
Time spent in evaluations (secs)    =  0.00000

Cuts statistics (gen / add)
---------------------------
Knapsack cuts                       =  242 / 214
Mixed-integer rounding cuts         =  489 / 269
Gomory cuts                         =  0 / 0
Flow-cover cuts                     =  128 / 25
Probing cuts                        =  148 / 50

Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump                    =  2 / 2 / 0.504s
Rounding heuristic                  =  7 / 3 / 0.100s
MPEC heuristic                      =  2 / 1 / 1.170s

===========================================================================

Knitro 14.1.0: Locally optimal or satisfactory solution.
objective 578176.6390047162; optimality gap 40.7
126 nodes; 214 subproblem solves

In this example, three rounds of cutting planes at the root node improve the dual bound from 569299 to 576759.

Restart

Throughout the exploration of the tree, the solver gathers information about the problem. Having this information earlier could lead to better decisions that could make the branch-and-bound tree smaller. To overcome this, Knitro implements a restart mechanism. At some point, Knitro may decide to restart the exploration of the tree. The restart mechanism is enabled by default. It can be disabled with option mip_restart.

=======================================
          Commercial License
         Artelys Knitro 14.1.0
=======================================

No start point provided -- Knitro computing one.

concurrent_evals:        0
datacheck:               0
hessian_no_f:            1
mip_maxtime_real:        3600
Knitro changing mip_method from AUTO to 1.
Knitro changing mip_rootalg from AUTO to 1.
Knitro changing mip_lpalg from AUTO to 3.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 0.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_pseudoinit from AUTO to 1.

Problem Characteristics
-----------------------
Objective goal:  Minimize
Objective type:  linear
Number of variables:                               3010
    bounded below only:                              10
    bounded above only:                               0
    bounded below and above:                       3000
    fixed:                                            0
    free:                                             0
Number of binary variables:                        1500
Number of integer variables:                          0
Number of constraints:                             1821
    linear equalities:                               10
    quadratic equalities:                             0
    gen. nonlinear equalities:                        0
    linear one-sided inequalities:                 1801
    quadratic one-sided inequalities:                 0
    gen. nonlinear one-sided inequalities:           10
    linear two-sided inequalities:                    0
    quadratic two-sided inequalities:                 0
    gen. nonlinear two-sided inequalities:            0
Number of nonzeros in Jacobian:                   12010
Number of nonzeros in Hessian:                     3000

Knitro using Branch and Bound method with 8 threads.

Root node relaxation
--------------------

 Iter      Objective      Feasibility        Optimality       Time
                             error              error        (secs)
 ----      ---------      -----------        ----------      ------
    1        34061.5          34016.5           1.00000       0.056
    2        4618.89          4573.89           1.00000       0.063
    3        565.124          520.124           1.00000       0.069
    4        44.9919          3.37053       8.90075e-02       0.075
    5        44.9842          3.15208       7.05244e-02       0.082
    6        40.2277         0.692171       8.47165e-02       0.088
    7        34.1249         0.393888          0.105463       0.094
    8        23.1634         0.187067       8.88250e-02       0.101
    9        6.44146         0.331273       9.96163e-02       0.107
   10        4.84509          3.68111       3.75953e-02       0.113
   11        4.82270          3.18048       3.11531e-02       0.119
   12        4.72466          2.41894       1.52618e-02       0.126
   13        4.59011         0.655004       2.34789e-03       0.132
   14        4.49568         0.288989       1.26076e-03       0.138
   15        4.44470      5.40446e-02       2.86726e-04       0.145
   16        4.44300          5.89285       1.68812e-05       0.151
   17        4.44302          5.20723       6.88817e-04       0.157
   18        4.44314         0.574396       6.81981e-07       0.164
   19        4.44305         0.368235       7.90967e-07       0.170
   20        4.44301         0.112719       3.07706e-07       0.176
   21        4.44301      0.00000e+00       1.23866e-08       0.183
   22        4.44301      0.00000e+00       1.23866e-08       0.190
   23        4.44301      0.00000e+00       1.23866e-08       0.195
    1    0.00000e+00          7.52575       0.00000e+00       0.200
    2    0.00000e+00          7.52575       0.00000e+00       0.200
    3    0.00000e+00          7.52575       0.00000e+00       0.201
    4    0.00000e+00          7.52575       0.00000e+00       0.202

Tree search
-----------

       Nodes        Best solution   Best bound      Gap       Time
   Expl  |  Unexpl      value         value                  (secs)
   ---------------  -------------   ----------      ---      ------
      1       2                        4.44301                0.203
     15      16                        4.44301                3.286
    122     123                        4.44301               10.809
    283     284                        4.44794               19.249
    414     415      11.6508   FP      4.44794     61.82%    25.678
    449     450      11.6508           4.44822     61.82%    27.210
    601     602      11.6508           4.44845     61.82%    35.207
    770     771      11.6508           4.44846     61.82%    42.804
    930     931      11.6508           4.44894     61.81%    50.144
   1094    1095      11.6508           4.44894     61.81%    57.286
   1249    1250      11.6508           4.44894     61.81%    64.055
   1410    1411      11.6508           4.44894     61.81%    71.031
   1572    1573      11.6508           4.44894     61.81%    77.669
   1731    1732      11.6508           4.44894     61.81%    84.310
   1894    1895      11.6508           4.44894     61.81%    90.982
   2054    2055      11.6508           4.44894     61.81%    97.558
   2215    2216      11.6508           4.44894     61.81%   104.111
   2377    2378      11.6508           4.44894     61.81%   110.587
   2536    2537      11.6508           4.44894     61.81%   117.090
   2697    2698      11.6508           4.44894     61.81%   123.397
   2856    2857      11.6508           4.44894     61.81%   129.571
   3017    3018      11.6508           4.44894     61.81%   135.588
   3177    3178      11.6508           4.44894     61.81%   141.609
   3337    3338      11.6508           4.44894     61.81%   147.451
   3497    3498      11.6508           4.44894     61.81%   153.169
   3657    3658      11.6508           4.44894     61.81%   159.112
   3817    3818      11.6508           4.44894     61.81%   164.826
   3977    3978      11.6508           4.44894     61.81%   170.670
   4137    4138      11.6508           4.44894     61.81%   176.398
   4297    4298      11.6508           4.44894     61.81%   181.984
   4457    4458      11.6508           4.44894     61.81%   187.600
   4617    4618      11.6508           4.44894     61.81%   193.230
   4777    4778      11.6508           4.44894     61.81%   198.934
   4937    4938      11.6508           4.44894     61.81%   204.594
   5097    5098      11.6508           4.44894     61.81%   210.314
   5257    5258      11.6508           4.44894     61.81%   215.912
   5417    5418      11.6508           4.44894     61.81%   221.555
   5577    5578      11.6508           4.44894     61.81%   226.966
   5737    5738      11.6508           4.44894     61.81%   232.583
   5897    5898      11.6508           4.44894     61.81%   238.037
   6057    6059      11.6508           4.44894     61.81%   243.025
   6217    5899      11.6508           4.44894     61.81%   243.032
   6377    5739      11.6508           4.44894     61.81%   243.038
   6537    5579      11.6508           4.44894     61.81%   243.043
   6697    5419      11.6508           4.44894     61.81%   243.047
   6857    5259      11.6508           4.44894     61.81%   243.052
   7017    5099      11.6508           4.44894     61.81%   243.056
   7177    4939      11.6508           4.44894     61.81%   243.060
   7337    4779      11.6508           4.44894     61.81%   243.064
   7497    4619      11.6508           4.44894     61.81%   243.068
   7657    4459      11.6508           4.44894     61.81%   243.072
   7817    4299      11.6508           4.44894     61.81%   243.076
   7977    4139      11.6508           4.44894     61.81%   243.080
   8137    3979      11.6508           4.44894     61.81%   243.085
   8297    3819      11.6508           4.44894     61.81%   243.089
   8457    3659      11.6508           4.44894     61.81%   243.093
   8617    3499      11.6508           4.44894     61.81%   243.098
   8777    3339      11.6508           4.44894     61.81%   243.102
   8937    3179      11.6508           4.44894     61.81%   243.106
   9097    3019      11.6508           4.44894     61.81%   243.111
   9257    2859      11.6508           4.44894     61.81%   243.115
   9417    2699      11.6508           4.44894     61.81%   243.120
   9577    2539      11.6508           4.44894     61.81%   243.125
   9737    2379      11.6508           4.44894     61.81%   243.130
   9897    2219      11.6508           4.44894     61.81%   243.135
  10057    2059      11.6508           4.44894     61.81%   243.139
  10217    1899      11.6508           4.44894     61.81%   243.144
  10377    1739      11.6508           4.44894     61.81%   243.148
  10537    1579      11.6508           4.44894     61.81%   243.153
  10697    1419      11.6508           4.44894     61.81%   243.158
  10857    1259      11.6508           4.44894     61.81%   243.162
  11017    1099      11.6508           4.44894     61.81%   243.167
  11177     939      11.6508           4.44894     61.81%   243.171
  11337     779      11.6508           4.44894     61.81%   243.175
  11497     619      11.6508           4.44894     61.81%   243.179
  11657     459      11.6508           4.44894     61.81%   243.183
  11817     299      11.6508           4.44894     61.81%   243.187
  11977     139      11.6508           4.44894     61.81%   243.191
  12116       0      11.6508           4.44894     61.81%   243.406
  12116       2      11.6508           4.44894     61.81%   253.794
  12120       2      11.6508           4.44894     61.81%   262.165
  12124       4      11.6508           4.44894     61.81%   274.656
  12162      32      11.6508           4.44894     61.81%   283.179
  12194      36      11.6508           4.44894     61.81%   300.978
  12237      95      11.6508           4.44894     61.81%   315.590
  12312     174      11.6508           4.44894     61.81%   325.754
  12423     297      11.6508           4.44894     61.81%   335.146
  12528     400      11.6508           4.44894     61.81%   346.079
  12636     508      11.6508           4.44894     61.81%   356.752
  12745     623      11.6508           4.44894     61.81%   366.650
  12770     650      10.9481 MPEC      4.44894     59.36%   368.223
  12881     757      10.9481           4.44894     59.36%   376.200
  12928     802      5.85612 MPEC      4.44894     24.03%   381.034
  12998     884      5.85612           4.44894     24.03%   384.994
  13085     959      5.83273 MPEC      4.44894     23.72%   390.276
  13142    1026      5.83273           4.44894     23.72%   393.309
  13223    1099      5.21444 MPEC      4.44894     14.68%   397.820
  13268    1138      5.18298 MPEC      4.44894     14.16%   401.126
  13281    1151      5.18298           4.44894     14.16%   401.886
  13294    1164      4.73702 MPEC      4.44894      6.08%   402.669
  13406    1282      4.73702           4.44894      6.08%   409.177
  13544    1420      4.56283 MPEC      4.44894      2.50%   417.010
  13587    1461      4.56283           4.44894      2.50%   428.874
  13717    1593      4.55998 MPEC      4.45089      2.39%   436.419
  13762    1628      4.52585 MPEC      4.45234      1.62%   438.960
  13788    1632      4.52585           4.45234      1.62%   446.854
  13788    1640      4.52585           4.45234      1.62%   459.717
  13853    1727      4.47866 MPEC      4.45234      0.59%   468.984
  13939    1801      4.47866           4.45234      0.59%   477.167
  13974    1844      4.46637 MPEC      4.45283      0.30%   479.064
  14015    1887      4.46604 MPEC      4.45283      0.30%   481.175
  14068    1920      4.46604           4.45283      0.30%   484.296
  14088    1940      4.46395 MPEC      4.45283      0.25%   486.663
  14136    2010      4.46395           4.45283      0.25%   492.502
  14216    2080      4.46395           4.45283      0.25%   500.827
  14254    2112      4.45963 MPEC      4.45283      0.15%   505.449
  14285    2151      4.45963           4.45283      0.15%   508.571
  14313    2177      4.45769 MPEC      4.45283      0.11%   511.031
  14340    2204      4.45607 MPEC      4.45283      0.07%   513.312
  14385    2251      4.45607           4.45283      0.07%   516.411
  14493    2363      4.45607           4.45283      0.07%   523.320
  14512    2378      4.45565 MPEC      4.45283      0.06%   526.122
  14578    2452      4.45565           4.45286      0.06%   531.004
  14652    2510      4.45521 MPEC      4.45286      0.05%   538.755
  14652    2514      4.45521           4.45286      0.05%   539.560
  14748    2626      4.45521           4.45286      0.05%   546.339
  14836    2712      4.45513 MPEC      4.45286      0.05%   550.333
  14879    2745      4.45513           4.45286      0.05%   553.553
  14970    2842      4.45513           4.45286      0.05%   560.513
  14993    2867      4.45471 MPEC      4.45286      0.04%   561.555
  15080    2938      4.45471           4.45286      0.04%   567.541
  15141    3019      4.45420 MPEC      4.45286      0.03%   571.076
  15200    3074      4.45420           4.45286      0.03%   573.572
  15308    3180      4.45420           4.45286      0.03%   580.022
  15430    3292      4.45420           4.45286      0.03%   586.594
  15518    3370      4.45406 MPEC      4.45286      0.03%   592.839
  15523    3377      4.45406           4.45286      0.03%   593.548
  15644    3520      4.45406           4.45286      0.03%   599.171
  15738    3612      4.45406           4.45286      0.03%   605.883
  15806    3682      4.45401 MPEC      4.45286      0.03%   608.823
  15863    3715      4.45397 MPEC      4.45286      0.02%   611.671
  15867    3715      4.45397           4.45286      0.02%   612.634
  15948    3806      4.45377 MPEC      4.45286      0.02%   618.521
  15948    3808      4.45377           4.45286      0.02%   619.484
  16052    3912      4.45375 MPEC      4.45286      0.02%   625.094
  16062    3914      4.45375           4.45286      0.02%   625.939
  16170    4048      4.45375           4.45286      0.02%   631.833
  16200    4074      4.45360 MPEC      4.45286      0.02%   633.053
  16272    4130      4.45356 MPEC      4.45286      0.02%   636.959
  16289    4147      4.45356           4.45286      0.02%   638.045
  16375    4255      4.45343 MPEC      4.45286      0.01%   642.267
  16403    4281      4.45343           4.45286      0.01%   643.365
  16497    4361      4.45333 MPEC      4.45286      0.01%   648.716
  16517    4367      4.45333           4.45286      0.01%   649.950
  16584    4440      4.45326 MPEC      4.45286      0.01%   655.792

EXIT: Optimal solution found (assuming convexity).

HINT: The problem may be a non-convex mixed-integer problem.  Set
      mip_multistart=1 to enable a mixed-integer multistart heuristic,
      which may improve the chances of finding the global solution.

Final Statistics for MIP
------------------------
Final objective value               =  4.45325594185027e+00
Final bound value                   =  4.45285857261477e+00
Final optimality gap (abs / rel)    =  3.97e-04 / 8.92e-05 (0.01%)
# of root cutting plane rounds      =  1
# of restarts                       =  1
# of nodes processed                =  16584 (1683.251s)
# of strong branching evaluations   =  2355 (837.700s)
# of function evaluations           =  359358 (70.532s)
# of gradient evaluations           =  352044 (26.927s)
# of hessian evaluations            =  321563 (108.781s)
# of hessian-vector evaluations     =  0
# of subproblems processed          =  15415 (2582.962s)
Total program time (secs)           =  655.80438 (2604.388 CPU time)
Time spent in evaluations (secs)    =  206.24011

Cuts statistics (gen / add)
---------------------------
Knapsack cuts                       =  0 / 0
Mixed-integer rounding cuts         =  0 / 0
Flow-cover cuts                     =  0 / 0
Probing cuts                        =  0 / 0

Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump                    =  8 / 1 / 13.021s
Rounding heuristic                  =  2 / 0 / 6.890s
MPEC heuristic                      =  89 / 32 / 53.206s

===========================================================================

Knitro 14.1.0: Locally optimal or satisfactory solution.
objective 4.453255941850274; optimality gap 0.000397
16584 nodes; 15415 subproblem solves

In this example, Knitro performs a restart after about 12000 nodes. Before this restart, the value of the dual bound was stuck at 4.44894. Thanks to the information gathered before restarting, Knitro is able to improve the dual bound after the restart and close the optimality gap.

Branching priorities

It is also possible to specify branching priorities for the NLPBB algorithm. Priorities must be positive numbers (variables with non-positive values are ignored). Variables with higher priority values will be considered for branching before variables with lower priority values. When priorities for a subset of variables are equal, the branching rule is applied as a tiebreaker.

Branching priorities in AMPL

Branching priorities for integer variables can be specified in AMPL using the AMPL suffixes feature (see AMPL suffixes defined for Knitro) as shown below.

...
ampl: var x{j in 1..3} >= 0 integer;
...
ampl: suffix priority IN, integer, >=0, <=9999;
ampl: let x[1].priority := 5;
ampl: let x[2].priority := 1;
ampl: let x[3].priority := 10;

See the AMPL documentation for more information on the “.priority ” suffix.

Branching priorities in the callable library API

Branching priorities for integer variables can be specified through the callable library interface using the KN_set_set_mip_branching_priorities() functions shown below.

int  KNITRO_API KN_set_mip_branching_priorities
    (      KN_context_ptr  kc,
     const KNINT           nV,
     const KNINT * const   indexVars,
     const int   * const   xPriorities);
int  KNITRO_API KN_set_mip_branching_priorities_all
    (      KN_context_ptr  kc,
     const int   * const   xPriorities);
int  KNITRO_API KN_set_mip_branching_priority
    (      KN_context_ptr  kc,
     const KNINT           indexVar,
     const int             xPriority);

Values for continuous variables are ignored. Knitro makes a local copy of all inputs, so the application may free memory after the call. This routine must be called after calling KN_set_var_types() to mark integer variables.

Branching priorities in the object-oriented interface

Branching priorities for integer variables can be specified through the object-oriented interface using the function shown below.

void setVarMipBranchingPriorities(const KNSparseVector<int, int>& varMipBranchingPriorities);

The KNSparseVector<int, int> varMipBranchingPriorities is basically a pair of std::vector<int> where the first one represents the variables indexes, and the second corresponds to their user-defined branching priorities. Values for continuous variables are ignored.

MISQP algorithm

Overview

The MISQP algorithm is a largely heuristic method that attempts to extend the SQP method for continuous, nonlinear optimization to the case where there are integer variables. This method is primarily designed for small problems (e.g. less than 100 variables) where function evaluations may involve expensive black-box simulations and derivatives may not be available. This method is able to handle models where the integer variables cannot be relaxed. This means that the simulations or function evaluations can only occur when integer variables are at integer values (e.g. the integer variables may have no meaning at non-integral values). This method will typically converge in far fewer function evaluations compared with the other MINLP methods in Knitro and is primarily intended for small problems where these evaluations are the dominant cost. This method can be applied to either convex or non-convex models, but may converge to non-global integer, feasible points.

Multi-start

Since this algorithm runs similarly to the continuous SQP algorithm, you can apply the parallel multi-start feature (see Section Multi-Start) to the MISQP method to increase the chances of finding the global solution.

Special Treatment of Integer Variables

You can specify special treatment of integer variables using the mip_intvar_strategy user option in Knitro. In particularly, you can use this option to specify that all integer variables are relaxed, or that all binary variables should be converted to complementarity constraints (see Section Complementarity constraints for a description of complementarity constraints).

In addition you can specify special treatments of individual integer variables through the callable library interface function KN_set_mip_intvar_strategies()

int  KNITRO_API KN_set_mip_intvar_strategies
    (      KN_context_ptr  kc,
     const KNINT           nV,
     const KNINT * const   indexVars,
     const int   * const   xStrategies);
int  KNITRO_API KN_set_mip_intvar_strategies_all
    (      KN_context_ptr  kc,
     const int * const     xStrategies);
int  KNITRO_API KN_set_mip_intvar_strategy
    (      KN_context_ptr  kc,
     const KNINT           indexVar,
     const int             xStrategy);

Here indexVars specifies the index of the integer variable you want to apply the special treatment to, and xStrategies specifies how you want to handle that particular integer variable (e.g., no special treatment, relax, or convert to a complementarity constraint).

Special strategies for integer variables can be specified in the AMPL interface using the intvarstrategy AMPL suffix, and in the MATLAB interface using the extendedFeatures.xIntStrategy structure.

Additional examples

Examples for solving MINLP problems using the C, C++, C#, Java, Julia, MATLAB, Python and R interfaces are provided with the distribution in the knitromatlab and examples directories.