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.2.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.2.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.2.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.2.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.2.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.2.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.2.0
=======================================
No start point provided -- Knitro computing one.
concurrent_evals: 0
datacheck: 0
hessian_no_f: 1
maxtime: 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.2.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 a multi-start feature for the NLPBB algorithm.
This feature can be enabled by setting the mip_multistart option to
KN_MIP_MULTISTART_ON.
We recommend to always set the mip_multistart option to
KN_MIP_MULTISTART_ON. Even if the problem is convex, setting the
mip_multistart option to KN_MIP_MULTISTART_ON should not
incur a signficant overhead. This will be the default behavior of the NLPBB
algorithm in future versions.
Termination criteria
The NLPBB algorithm can be stopped early based on the following criteria:
Elapsed time with options
maxtime.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.