Mixedinteger 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 three algorithms for mixedinteger nonlinear programming (MINLP). The first is a nonlinear branchandbound method, the second implements the hybrid QuesadaGrossman method for convex MINLP, and the third implements a mixedinteger Sequential Quadratic Programming (MISQP) method that is able to handle nonrelaxable integer variables.
The Knitro MINLP code is designed for convex mixed integer programming and is only a heuristic for nonconvex problems. The MINLP code also handles mixed integer linear programs (MILP), with specializations applied for this subclass of models.
Overview
The table below presents a brief overview of the main features included in the three MINLP algorithms. For a more detailed description, check Algorithms/Methods.
Features 
BranchandBound 
QuesadaGrossmann 
Mixed Integer Sequential Quadratic Programming 

Nonconvex MINLP 
++ 
+ 
++ 
Convex MINLP 
++ 
++ 

Expensive evaluations 
++ 

Warmstart 
+ 
+ 
++ 
MIP heuristics 
Rounding / Feasibility pump / MPEC 
Rounding / Feasibility pump / MPEC 
 
MIP cutting planes 
Knapsack / Clique / Mixedinteger rounding / Zerohalf 
Knapsack / Clique / Mixedinteger rounding / Zerohalf 
 
LP solver 
 
IP/Direct or IP/CG or SLQP 
 
Nonconvex MINLP: performance on nonconvex MINLP
Convex MINLP: performance on convex MINLP
Expensive evaluations: performance on problems with expensive function evalutations
Warmstart: ability to warmstart
MIP heuristics: heuristic search approach available to find an initial integer feasible point
MIP cutting planes: cutting plane methods available
LP solver: solver available for the resolution of the linear subproblems
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 13.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 onesided inequalities: 0
quadratic onesided inequalities: 1
gen. nonlinear onesided inequalities: 0
linear twosided inequalities: 0
quadratic twosided inequalities: 0
gen. nonlinear twosided 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
MixedInteger 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 13.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 mixedinteger 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.
Objectoriented C++ example
A MIP problem is defined and solved via the objectoriented 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 is 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.
MINLP options
Many user options are provided for the MIP features to tune performance, including options for branching, node selection, rounding and heuristics for finding integer feasible points. User options specific to the MIP tools begin with mip_. It is recommended to experiment with several of these options as they often can make a significant difference in performance.
Name 
Meaning 

MIP branching rule 

Add clique cuts 

Limit on the number of cuts allowed in node subproblem 

MIP objective cutoff value 

When to perform cutting plane procedure 

MIP debugging level (0=none, 1=all) 

Add gomory cuts (0=none, 1=root) 

Branch on GUBs (0=no, 1=yes) 

MIP diving heuristic 

MIP feasibility pump heuristic 

MIP Large Neighborhood Search (LNS) heuristic 

MIP heuristic iteration limit 

MIP MISQP heuristic 

MIP MPEC heuristic 

MIP heuristic strategy 

MIP heuristic termination condition 

Add logical implications (0=no, 1=yes) 

Threshold for deciding integrality 

Treatment of integer variables 

Add knapsack cuts 

Add lift and project cuts 

LP subproblem algorithm 

Maximum nodes explored 

Maximum subproblem solves 

Maximum CPU time in seconds for MIP 

Maximum real in seconds time for MIP 

MIP method (0=auto, 1=BB, 2=HQG, 3=MISQP) 

Add mixed integer rounding cuts 

Enable MIP multistart 

Standard node relaxation algorithm 

Number of threads for MIP 

Absolute optimality gap stop tolerance 

Relative optimality gap stop tolerance 

MIP output interval 

MIP output level 

Enable MIP subproblem output 

Pseudocost initialization 

Are integer variables relaxable? 

Enable MIP restart 

Root node relaxation algorithm 

MIP rounding rule 

MIP node selection direction 

MIP node selection rule 

Strong branching candidate limit 

Strong branching tree level limit 

Strong branching iteration limit 

Termination condition for MIP 

Add zerohalf cuts 
Algorithms/Methods
The default MINLP method in Knitro is a standard implementation of branchandbound for nonlinear optimization. This method involves solving a relaxed, continuous nonlinear optimization subproblem at every node of the branchandbounds 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 nonconvex 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 in nonconvex. 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 nonconvex).
The hybrid QuesadaGrossman (HQG) method in Knitro is a variant of branchandbound for MINLP. It maintains one branchandbound tree but solves linear programming (LP) subproblems at most of the nodes, while only occasionally solving nonlinear optimization subproblems at integer feasible nodes. The solutions of the LP subproblems are used to generate outer approximations/cuts, which are continually added to the master problem. This method should generally only be applied to convex models since the outer approximations are only valid when the model is convex. This method will typically take many more nodes to solve compared with the standard branchandbound method, but the node subproblems are often easier to solve since most of them are LPs.
The third method (MISQP) 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 blackbox simulations and derivatives may not be available. In contrast to the other MINLP algorithms in Knitro, 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 nonintegral 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 nonconvex models, but may converge to nonglobal integer, feasible points. However, since this algorithm runs similarly to the continuous SQP algorithm, you can apply the parallel multistart feature (see Section MultiStart) to the MISQP method to increase the chances of finding the global solution.
Branching priorities
It is also possible to specify branching priorities in Knitro. Priorities must be positive numbers (variables with nonpositive 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 objectoriented interface
Branching priorities for integer variables can be specified through the objectoriented 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 userdefined branching priorities.
Values for continuous variables are ignored.
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.
MINLP callbacks
The Knitro MINLP procedure provides a user callback utility that can be used in the callable library API to perform some user task after each node is processed in the branchandbound tree. This callback function is set by calling the following function:
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.
Determining convexity/concavity
Knowing whether or not a function is convex may be useful in methods for
mixed integer programming as linearizations derived from convex functions
can be used as outer approximations of those constraints.
These outer approximations are useful
in computing lower bounds. The callable library API allows for the
user to specify whether or not the problem
functions (objective and constraints) are convex or concave via the functions:
KN_set_obj_property()
and KN_set_con_properties()
.
A function f is convex if for any two points x and y, we have
and concave if
By default functions are assumed to be nonconvex (i.e. neither convex, nor concave).
The objective function and any constraint functions that satisfy the
conditions above should be marked as convex or concave.
All linear functions are convex. Any nonlinear
equality constraint is nonconvex. Knitro will use function convexity/concavity
information to determine whether the optimization problem as a whole is convex or not.
If the problem is determined to be convex Knitro may be able to apply specializations
to improve performance. If you know your model is convex, you can also directly
tell Knitro this by setting the convex
option.
The MIP solvers in Knitro are designed for convex problems. For nonconvex problems, these solvers are only heuristics and may terminate at nonoptimal points. The continuous solvers in Knitro can handle either convex or nonconvex models. However, for nonconvex models, they may converge to local (rather than global) optimal solutions.
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.