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.
The Knitro MINLP code is designed for convex mixed-integer programming and is only a heuristic for non-convex problems. The MINLP code also handles mixed-integer linear programs (MILP), with specializations applied for this subclass of models.
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.0.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.0.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 primarily designed for convex models, and in this case the optimality gap measure can be trusted. It can also be applied to non-convex models, and often works well on these models. However, it may sometimes get stuck at integer feasible points that are not globally optimal solutions when the model is non-convex. 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).
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.0.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.0.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:
Knapasck cuts, option
mip_knapsackClique cuts, option
mip_cliqueMixed-integer rounding cuts, option
mip_mirGomory cuts, option
mip_gomoryZero-half cuts, option
mip_zerohalfLift-and-project cuts, option
mip_liftprojectFlow-cover cuts, option
mip_cut_flowcoverProbing cuts, option
mip_cut_probing
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.0.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.0.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.0.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.0.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.
Multi-start strategies
If the problem is convex, the NLPBB algorithm terminates with a provably optimal solution. If the problem is non-convex, the NLPBB algorithm doesn’t provide any guarantee regarding the optimality of the returned solution. That is, it may terminate with a non-optimal solution. To increase the chances of finding an optimal solution, Knitro provides two multi-start strategies for the NLPBB algorithm.
Note that the NLPBB algorithm is not an iterative algorithm like the interior point algorithm or the active-set algorithm. That’s why multi-start is not as straightforward as for these other methods.
Node multi-start
Node multi-start enables multi-start for all continuous subproblems solved by the NLPBB algorithm, in order to increase the chances of finding the global optimum for these subproblems.
Node multi-start can be enabled by setting the ms_enable option to
KN_MS_ENABLE_YES as for the continuous algorithms. Option
ms_maxsolves specifies how many start points to try in each continuous
subproblem.
Since most of the running time of the NLPBB algorithm is spent inside the subproblem solves, using node multi-start will likely multiply the running time of the algorithm by the number of start points. Thus, it might become very expensive and is only recommended for small problems (e.g., less than 32 variables).
Here is an example of the same model solved without multi-start and with node multi-start:
=======================================
Commercial License
Artelys Knitro 14.0.0
=======================================
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: Minimize
Objective type: linear
Number of variables: 8
bounded below only: 0
bounded above only: 0
bounded below and above: 7
fixed: 0
free: 1
Number of binary variables: 0
Number of integer variables: 7
Number of constraints: 28
linear equalities: 0
quadratic equalities: 0
gen. nonlinear equalities: 0
linear one-sided inequalities: 0
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: 220
Number of nonzeros in Hessian: 28
Knitro using Branch and Bound method with 8 threads.
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
1 0.792153 8.98537 0.338079 0.096
2 1.81603 6.80605 0.302838 0.105
3 6.82792 4.35574e-02 0.302838 0.120
4 6.29827 3.66802e-02 0.302838 0.135
5 5.60237 0.189952 0.177556 0.148
6 5.56369 7.25825e-02 3.05272e-02 0.155
7 5.58861 2.70482e-03 1.15452e-03 0.169
8 5.58990 8.77615e-06 4.11680e-06 0.181
9 5.58990 0.00000e+00 1.71120e-10 0.195
10 5.58990 0.00000e+00 8.55601e-11 0.208
11 5.58990 0.00000e+00 1.14219e-09 0.216
1 5.59170 168.179 0.193187 0.234
2 5.59171 168.179 0.193187 0.243
3 5.59171 168.179 0.193187 0.257
4 5.59171 168.179 0.193187 0.270
5 5.71839 168.179 168.179 0.295
6 6.44679 168.179 168.179 0.305
7 7.40628 168.179 168.179 0.322
8 10.1344 168.179 168.179 0.332
9 16.0890 168.179 168.179 0.339
10 29.5712 168.179 168.179 0.350
11 85.4312 168.179 168.179 0.365
12 159.469 168.179 168.179 0.381
13 306.668 168.179 168.179 0.394
14 278.315 168.179 168.179 0.409
15 278.540 168.179 17.4617 0.421
16 278.453 168.179 15.2425 0.432
17 278.378 168.179 0.994058 0.446
18 168.981 168.179 0.998814 0.457
19 103.287 168.179 0.999987 0.466
20 62.5597 168.179 0.999988 0.480
21 31.7630 168.179 0.999988 0.489
22 21.0812 168.179 0.999988 0.499
23 13.9296 168.179 0.999998 0.511
24 12.4336 168.179 1.00000 0.522
25 8.99448 168.179 1.00000 0.535
26 7.87001 168.179 1.00000 0.550
27 7.94507 168.179 1.00000 0.565
28 7.90012 168.179 1.00000 0.579
29 7.88889 168.179 1.00000 0.591
30 7.88636 168.179 1.00000 0.601
31 7.86577 168.179 1.00000 0.615
32 7.86577 168.179 1.00000 0.618
WARNING: Evaluations seem expensive and concurrent evaluations are disabled,
please consider reducing the number of threads for the branch-and-bound
using option 'mip_numthreads'.
Recommended value: 'mip_numthreads=1'
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 5.58990 0.619
21 22 11.0498 FP 8.02616 27.36% 2.853
30 25 8.23770 LEAF 8.03372 2.48% 4.783
83 0 8.23770 8.23770 0.00% 6.249
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 = 8.23769932942488e+00
Final bound value = 8.23769932942488e+00
Final optimality gap (abs / rel) = 0.00e+00 / 0.00e+00 (0.00%)
# of root cutting plane rounds = 0
# of restarts = 0
# of nodes processed = 83 (19.216s)
# of strong branching evaluations = 0 (0.000s)
# of function evaluations = 1082 (5.669s)
# of gradient evaluations = 1043 (4.884s)
# of hessian evaluations = 925 (9.742s)
# of hessian-vector evaluations = 0
# of subproblems processed = 67 (21.221s)
Total program time (secs) = 6.26060 (21.891 CPU time)
Time spent in evaluations (secs) = 20.29497
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 / 1.607s
Rounding heuristic = 1 / 0 / 1.071s
MPEC heuristic = 0 / 0 / 0.000s
===========================================================================
Knitro 14.0.0: Locally optimal or satisfactory solution.
objective 8.237699329424883; optimality gap 0
83 nodes; 67 subproblem solves
ms_enable=1
=======================================
Commercial License
Artelys Knitro 14.0.0
=======================================
concurrent_evals: 0
datacheck: 0
hessian_no_f: 1
ms_enable: 1
ms_maxsolves: 0
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: 8
bounded below only: 0
bounded above only: 0
bounded below and above: 7
fixed: 0
free: 1
Number of binary variables: 0
Number of integer variables: 7
Number of constraints: 28
linear equalities: 0
quadratic equalities: 0
gen. nonlinear equalities: 0
linear one-sided inequalities: 0
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: 220
Number of nonzeros in Hessian: 28
Knitro using Branch and Bound method with 8 threads.
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
14 5.90161 7.38964e-13 2.06990e-08 0.890
14 5.91153 5.32907e-15 1.25417e-09 0.891
11 5.58990 0.00000e+00 1.14219e-09 0.910
16 5.91153 1.13687e-13 1.25405e-09 1.032
17 5.58990 1.95399e-14 3.46402e-07 1.033
16 5.91153 1.13687e-13 1.01696e-09 1.056
23 5.58990 1.77636e-15 9.80327e-14 1.105
36 5.90161 1.13687e-13 2.83099e-10 1.235
10 210.837 168.179 1.00000 1.784
12 135.216 168.179 1.00000 1.865
12 415.486 168.179 1.00000 2.092
17 7.90742 168.179 1.00000 2.220
21 7.87058 168.179 1.00000 2.259
18 7.87530 168.179 1.00000 2.276
20 7.87809 168.179 1.00000 2.307
32 7.86577 168.179 1.00000 2.375
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 5.58990 2.376
1 2 12.8490 FP 5.58990 56.50% 11.666
24 23 7.71576 LEAF 7.39936 4.10% 36.634
30 21 7.65775 FCRD 7.65129 0.08% 43.944
31 20 7.65775 7.65771 0.00% 45.256
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 = 7.65775209273327e+00
Final bound value = 7.65770738085629e+00
Final optimality gap (abs / rel) = 4.47e-05 / 5.84e-06 (0.00%)
# of root cutting plane rounds = 0
# of restarts = 0
# of nodes processed = 31 (0.000s)
# of strong branching evaluations = 0 (0.000s)
# of function evaluations = 6386 (2.518s)
# of gradient evaluations = 5716 (0.021s)
# of hessian evaluations = 5407 (0.000s)
# of hessian-vector evaluations = 0
# of subproblems processed = 42 (0.000s)
Total program time (secs) = 45.28794 (299.672 CPU time)
Time spent in evaluations (secs) = 2.53901
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 / 9.276s
Rounding heuristic = 2 / 1 / 1.720s
MPEC heuristic = 0 / 0 / 0.000s
===========================================================================
Knitro 14.0.0: Locally optimal or satisfactory solution.
objective 7.657752092733272; optimality gap 4.47e-05
31 nodes; 42 subproblem solves
Without multi-start, Knitro finds a solution of value 8.23770. When node multi-start is enabled, Knitro finds a better solution of value 7.65775.
MIP multi-start
MIP multi-start solves multiple branch-and-bound trees at the same time. Each branch-and-bound tree is associated with a locally optimal solution of the root node relaxation, which is used as a starting point for all its subproblem solves.
Thus, no multi-start is used for the continuous subproblems and the time spent in a node is equivalent to the time spent in a node without any multi-start.
There is a single node pool that contains the nodes from all branch-and-bound trees. When a node needs to be processed, Knitro selects the best node among the open nodes from all the branch-and-bound trees. That means that, if all the open nodes of a branch-and-bound tree are not promising, they won’t be processed until the promising nodes from the other branch-and-bound trees have all been processed.
MIP multi-start can be enabled by setting the mip_multistart option to
KN_MIP_MULTISTART_ON. Option ms_maxsolves sets the number of
root relaxations computed. Option ms_num_to_save sets the maximum
number of branch-and-bound trees solved. In particular:
If
ms_num_to_saveis set toms_maxsolves, a branch-and-bound tree will be created for all distinct locally optimal solutions of the root node relaxation found.Setting
ms_num_to_saveto1is equivalent to running multi-start only at the root node.
Here is an example of the same model solved without multi-start and with MIP multi-start:
=======================================
Commercial License
Artelys Knitro 14.0.0
=======================================
WARNING: Problem appears to have nonlinear equalities and be non-convex.
The Knitro mixed integer solver is designed for convex problems.
For non-convex problems it is only a heuristic, and the reported
bounds and optimality claims cannot be verified.
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: Minimize
Objective type: linear
Number of variables: 70
bounded below only: 36
bounded above only: 0
bounded below and above: 30
fixed: 0
free: 4
Number of binary variables: 14
Number of integer variables: 0
Number of constraints: 54
linear equalities: 10
quadratic equalities: 1
gen. nonlinear equalities: 15
linear one-sided inequalities: 28
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: 236
Number of nonzeros in Hessian: 86
Knitro using Branch and Bound method with 8 threads.
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
1 762.075 8690.14 7.12905 0.140
2 716.803 940.943 10.9205 0.152
3 710.057 929.518 355.985 0.153
4 808.275 382.840 11.3933 0.154
5 815.227 237.563 212.286 0.155
6 868.886 199.264 2781.03 0.156
7 1045.11 22.5822 397.428 0.156
8 1034.01 79.0942 528.380 0.169
9 1126.19 46.2518 666.390 0.171
10 1157.69 34.2918 1470.29 0.172
11 1209.11 26.5823 1053.39 0.184
12 1247.91 23.9088 1065.22 0.185
13 1435.30 11.4975 1954.46 0.187
14 1455.88 10.9255 1972.82 0.187
15 1552.19 7.94707 2065.17 0.188
16 1686.53 4.35518 2246.45 0.188
17 1767.12 3.07367 2484.90 0.189
18 1858.66 1.82489 2897.28 0.190
19 1847.17 1.66627 2417.20 0.190
20 1742.37 7.70408 2476.99 0.191
21 1714.43 3.78487 2157.65 0.192
22 1692.13 3.35028 2328.07 0.192
23 1671.01 2.13963 2934.62 0.193
24 1564.38 7.47667 2930.89 0.193
25 1519.02 0.315048 202.054 0.194
26 1504.45 0.270638 61.9523 0.195
27 1490.91 0.257351 72.8773 0.197
28 1438.66 0.218479 112.948 0.198
29 1438.08 0.212729 115.045 0.199
30 1393.94 0.170486 312.398 0.199
31 1348.35 2.10058 3188.58 0.200
32 1346.11 1.13779 4595.48 0.201
33 1338.52 1.07373 12775.2 0.201
34 1328.82 0.246492 3203.61 0.202
35 1298.29 2.20813 14183.8 0.209
36 1263.15 0.751379 6157.16 0.215
37 1237.73 5.38537e-02 14274.0 0.217
38 1150.73 2.07861 410.353 0.220
39 1131.93 0.886189 155.179 0.228
40 1129.36 0.831367 151.062 0.231
41 1120.75 0.316962 58.1305 0.232
42 1120.43 0.313709 57.9545 0.233
43 1110.27 0.356108 2.66045 0.234
44 1110.15 0.355924 2.65852 0.235
45 1109.87 0.355345 2.65845 0.235
46 1109.54 0.354653 4.73973 0.236
47 1108.76 0.316740 14.8072 0.236
48 1108.11 0.284633 23.6060 0.237
49 1107.65 0.254085 29.7572 0.238
50 1112.18 0.170984 29.5068 0.238
51 1110.67 0.221518 32.7837 0.239
52 1110.02 0.323319 36.8530 0.240
53 1109.20 5.11038e-02 0.299417 0.248
54 1108.91 3.75899e-02 17.0687 0.249
55 1108.25 5.07001e-02 0.194298 0.251
56 1108.13 0.103257 11.7448 0.253
57 1108.00 1.71929e-02 0.326436 0.254
58 1107.88 1.75664e-02 11.9461 0.255
59 1107.70 4.77221e-02 22.7197 0.255
60 1107.49 1.05335e-02 8.70644 0.256
61 1107.34 4.19617e-02 0.452127 0.256
62 1107.29 5.66492e-02 0.452118 0.257
63 1107.17 8.21140e-02 0.442639 0.258
64 1106.96 6.42086e-02 12.4246 0.258
65 1106.64 0.207684 25.7894 0.259
66 1106.56 0.221879 31.0652 0.260
67 1106.52 5.79296e-02 1.90502 0.261
68 1106.42 8.00833e-02 1.90440 0.270
69 1106.27 0.152195 1.90355 0.271
70 1105.97 0.211405 1.90184 0.272
71 1105.58 0.398599 1.89955 0.273
72 1105.29 1.24215e-02 2.86115 0.274
73 1105.36 9.96892e-04 3.29637 0.274
74 1105.34 8.97123e-04 1.40151 0.275
75 1105.34 3.83776e-04 1.67779 0.276
76 1105.06 0.323889 2.16698 0.285
77 1104.81 1.42388 14.0948 0.286
78 1104.66 0.427723 0.402504 0.287
79 1104.53 1.37545 18.6064 0.288
80 1104.32 0.418011 9.45795 0.289
81 1103.95 1.57327 5.71481 0.290
82 1103.86 1.56574 5.72354 0.290
83 1103.63 0.177134 5.81843 0.291
84 1103.56 0.103369 2.45853 0.292
85 1103.51 0.116132 1.32386 0.292
86 1103.48 5.23829e-02 0.231549 0.293
87 1103.43 0.284447 12.7623 0.294
88 1103.37 5.02383e-02 1.27629 0.295
89 1103.25 0.460614 5.80068 0.298
90 1103.13 6.45415e-02 5.81409 0.298
91 1103.12 7.47480e-04 1.89073 0.299
92 1103.12 2.12925e-04 1.96037 0.300
93 1103.11 1.64705e-03 0.154942 0.300
94 1103.08 1.16691e-02 0.145253 0.301
95 1102.99 0.105039 0.792631 0.301
96 1102.59 2.24957 63.8373 0.302
97 1102.53 2.21529 62.9266 0.309
98 1102.41 1.73667 53.2301 0.312
99 1101.93 3.36052 65.6356 0.313
100 1101.86 1.98783 58.1003 0.314
101 1101.70 4.81609e-02 55.5624 0.315
102 1101.48 0.345457 65.8778 0.316
103 1101.17 6.64795e-03 26.6171 0.317
104 1101.05 4.63370e-03 26.6138 0.318
105 1100.98 3.72972e-03 21.1519 0.327
106 1100.99 2.79819e-03 2.45657 0.330
107 1100.95 0.102248 1.27947 0.331
108 1100.80 0.570040 7.35153 0.332
109 1100.64 1.24927 12.8011 0.333
110 1100.54 1.34217 2.62487 0.334
111 1100.36 0.179569 3.71435 0.335
112 1100.26 9.62631e-02 2.75589 0.336
113 1100.19 3.44364e-02 2.84549 0.336
114 1099.98 0.420706 6.46228 0.337
115 1099.96 0.377692 6.46230 0.338
116 1099.65 4.95313e-02 6.61775 0.339
117 1099.70 2.21946e-02 2.32145 0.344
118 1099.70 2.21923e-02 2.32154 0.346
119 1099.52 2.72784e-02 9.95707 0.347
120 1099.34 5.41746e-03 7.39818 0.349
121 1099.36 4.08365e-03 7.08499 0.349
122 1099.40 3.82351e-03 3.05808 0.350
123 1099.44 3.55762e-04 9.95159e-04 0.351
124 1099.44 7.63601e-06 7.03206e-06 0.352
125 1099.44 3.47466e-10 1.02782e-10 0.352
126 1099.44 3.55271e-15 2.23230e-08 0.353
1 1701.61 4.95012 28.8042 0.358
2 1434.18 20.3112 244.904 0.366
3 1315.82 216.395 3.98060 0.367
4 1321.76 111.185 144.273 0.368
5 1465.25 45.1684 18.5068 0.369
6 1538.19 15.9991 38.5363 0.369
7 1580.48 2.56941 1.29211 0.370
8 1618.60 2.03510 22.2456 0.371
9 1668.12 1.32032 39.3079 0.371
10 1797.54 0.698452 64.5918 0.372
11 2011.65 0.161962 86.5686 0.372
12 2123.69 0.120279 100.202 0.373
13 2161.75 0.109719 103.797 0.385
14 2166.70 0.108553 104.186 0.385
15 2169.20 0.107732 104.452 0.386
16 2083.04 0.207730 118.282 0.388
17 2095.82 9.02828e-02 119.059 0.389
18 2095.72 9.01110e-02 119.063 0.390
19 2074.66 1.03127 119.367 0.391
20 2074.62 0.101746 119.400 0.392
21 2074.64 0.102133 119.396 0.392
22 2075.28 0.105179 119.335 0.393
23 2176.61 6.40139e-02 124.295 0.394
24 2176.58 6.33761e-02 124.222 0.394
25 2179.14 7.22400e-02 124.306 0.397
26 2191.03 8.75877e-02 124.505 0.398
27 2339.73 5.69038e-02 127.773 0.399
28 2372.63 5.05409e-02 128.438 0.400
29 2392.07 4.71235e-02 128.962 0.400
30 2419.43 4.21108e-02 130.050 0.401
31 2435.31 3.87801e-02 130.798 0.401
32 2437.36 3.82973e-02 130.898 0.402
33 2446.44 3.60721e-02 131.329 0.408
34 2454.83 3.33226e-02 131.805 0.409
35 2464.59 3.60727e-02 131.800 0.412
36 2484.00 4.37577e-02 131.800 0.413
37 2494.44 4.65814e-02 131.800 0.414
38 2508.59 4.64594e-02 131.800 0.415
39 2513.99 4.65496e-02 131.802 0.416
40 2530.97 4.63924e-02 131.802 0.416
41 2551.16 4.62204e-02 131.802 0.417
42 2557.61 4.61419e-02 131.802 0.418
43 2634.70 4.43628e-02 131.802 0.427
44 2729.16 4.36033e-02 131.799 0.429
45 2728.57 4.37088e-02 131.800 0.431
46 2776.29 4.30616e-02 131.799 0.432
47 2781.10 4.24033e-02 131.800 0.433
48 2797.94 4.17209e-02 131.799 0.434
49 2801.53 4.13391e-02 131.800 0.435
50 2811.58 3.94150e-02 131.800 0.435
51 2820.34 3.86400e-02 131.800 0.436
52 2839.69 3.74567e-02 131.799 0.437
53 2849.32 3.68448e-02 131.800 0.437
54 2864.72 3.62938e-02 131.800 0.438
55 2896.26 3.44269e-02 131.800 0.438
56 2965.09 3.18188e-02 131.800 0.439
57 3094.55 2.74868e-02 131.800 0.446
58 3181.05 2.36684e-02 131.800 0.448
59 3396.05 2.49290e-02 131.800 0.449
60 3495.81 2.50025e-02 131.800 0.450
61 3476.68 2.50178e-02 131.806 0.450
62 3527.28 2.50198e-02 131.806 0.451
63 3533.10 2.50199e-02 131.806 0.451
64 3510.40 2.50244e-02 131.807 0.452
65 3486.21 2.50244e-02 131.807 0.453
66 3477.22 2.50255e-02 131.807 0.453
67 3336.74 2.50255e-02 131.807 0.454
68 3325.18 2.50255e-02 131.807 0.454
69 3230.29 2.50255e-02 131.807 0.462
70 3219.99 2.50255e-02 131.807 0.465
71 3169.79 2.50255e-02 131.807 0.466
72 3169.79 2.50255e-02 131.807 0.468
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 1099.44 0.469
7 8 1154.55 FP 1099.44 4.77% 0.639
14 15 971.806 FCRD 1099.44 -13.13% 0.728
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 = 9.71805831935477e+02
Final bound value = 1.09943627160339e+03
Final optimality gap (abs / rel) = -1.28e+02 / -1.31e-01 (-13.13%)
# of root cutting plane rounds = 0
# of restarts = 0
# of nodes processed = 14 (0.678s)
# of strong branching evaluations = 0 (0.000s)
# of function evaluations = 4806 (0.037s)
# of gradient evaluations = 2061 (0.013s)
# of hessian evaluations = 2062 (0.031s)
# of hessian-vector evaluations = 0
# of subproblems processed = 24 (0.992s)
Total program time (secs) = 0.74348 (1.016 CPU time)
Time spent in evaluations (secs) = 0.08101
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.143s
Rounding heuristic = 2 / 1 / 0.131s
MPEC heuristic = 1 / 0 / 0.044s
===========================================================================
Knitro 14.0.0: Locally optimal or satisfactory solution.
objective 971.8058319354769; optimality gap 0
14 nodes; 24 subproblem solves
mip_multistart=1
ms_maxsolves=16
=======================================
Commercial License
Artelys Knitro 14.0.0
=======================================
WARNING: Problem appears to have nonlinear equalities and be non-convex.
The Knitro mixed integer solver is designed for convex problems.
For non-convex problems it is only a heuristic, and the reported
bounds and optimality claims cannot be verified.
concurrent_evals: 0
datacheck: 0
hessian_no_f: 1
mip_multistart 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: Minimize
Objective type: linear
Number of variables: 70
bounded below only: 36
bounded above only: 0
bounded below and above: 30
fixed: 0
free: 4
Number of binary variables: 14
Number of integer variables: 0
Number of constraints: 54
linear equalities: 10
quadratic equalities: 1
gen. nonlinear equalities: 15
linear one-sided inequalities: 28
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: 236
Number of nonzeros in Hessian: 86
Knitro using Branch and Bound method with 8 threads.
Root nodes relaxation
---------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
3 929.263 2.13163e-14 2.35600e-06 0.074
1 1081.23 3.07310e-13 1.58151e-06 0.097
2 1007.93 3.55271e-15 1.13487e-07 0.129
5 1000.60 5.32907e-15 1.29674e-12 0.136
0 1141.15 1.38890e-04 6.38968e-07 0.141
4 1089.54 1.77636e-15 7.63833e-14 0.147
7 963.826 3.37508e-14 1.60024e-08 0.169
9 916.433 3.55271e-15 1.96806e-11 0.181
8 1048.01 2.48690e-14 6.40391e-06 0.195
11 1103.89 3.55271e-15 6.25278e-12 0.207
10 1079.53 4.97380e-14 3.68452e-06 0.213
12 1067.50 3.55271e-15 1.49569e-12 0.246
13 1009.07 5.32907e-15 8.35616e-08 0.259
6 3279.04 0.824824 89.0033 0.268
15 1034.36 5.32907e-15 2.64751e-09 0.272
14 972.822 2.84217e-14 2.81217e-06 0.277
# of points selected: 15
WARNING: Evaluations seem expensive and concurrent evaluations are disabled,
please consider reducing the number of threads for the branch-and-bound
using option 'mip_numthreads'.
Recommended value: 'mip_numthreads=4'
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
15 30 914.184 FCRD 906.524 0.84% 0.540
16 29 909.028 MPEC 906.524 0.28% 1.145
33 12 909.028 916.250 -0.79% 1.150
EXIT: Optimal solution found (assuming convexity).
Final Statistics for MIP
------------------------
Final objective value = 9.09027862649573e+02
Final bound value = 9.16249757013197e+02
Final optimality gap (abs / rel) = -7.22e+00 / -7.94e-03 (-0.79%)
# of root cutting plane rounds = 0
# of restarts = 0
# of nodes processed = 33 (0.449s)
# of strong branching evaluations = 0 (0.000s)
# of function evaluations = 13182 (0.089s)
# of gradient evaluations = 6142 (0.035s)
# of hessian evaluations = 6084 (0.075s)
# of hessian-vector evaluations = 0
# of subproblems processed = 73 (2.223s)
Total program time (secs) = 1.18863 (3.891 CPU time)
Time spent in evaluations (secs) = 0.19887
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 = 10 / 0 / 0.059s
Rounding heuristic = 15 / 10 / 0.420s
MPEC heuristic = 15 / 1 / 0.512s
===========================================================================
Knitro 14.0.0: Locally optimal or satisfactory solution.
objective 909.0278626495726; optimality gap 0
33 nodes; 73 subproblem solves
Without multi-start, Knitro finds a solution of value 971.806. When MIP multi-start is enabled, Knitro finds a better solution of value 909.028.
Termination criteria
The NLPBB algorithm can be stopped early based on the following criteria:
Elapsed time with options
mip_maxtime_realandmip_maxtime_cpu.Number of nodes processed with option
mip_maxnodes.Number of subproblem solves with option
mip_maxsolves.Optimality gap with options
mip_opt_gap_absandmip_opt_gap_rel.Stop as soon as a feasible solution is found with option
mip_terminate.
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.
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.