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 three algorithms for mixed-integer nonlinear programming (MINLP). The first is a nonlinear branch and bound method, the second implements the hybrid Quesada-Grossman method for convex MINLP, and the third implements a mixed-integer Sequential Quadratic Programming (MISQP) method that is able to handle non-relaxable 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) of moderate size.

Note

The Knitro MIP tools do not currently handle special ordered sets (SOS’s) or semi-continuous variables.

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, 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 10.0.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_rounding from AUTO to 3.
Knitro changing mip_heuristic from AUTO to 1.
Knitro changing mip_pseudoinit from AUTO to 1.

Problem Characteristics
-----------------------
Objective goal:  Minimize
Number of variables:                     3
    bounded below:                       3
    bounded above:                       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
    nonlinear equalities:                0
    linear inequalities:                 0
    nonlinear inequalities:              1
    range:                               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
Knitro solving root node relaxation

   Node    Left    Iinf     Objective         Best relaxatn  Best incumbent
  ------  ------  ------  --------------     --------------  --------------
*      1       0       0    9.360000e+02       9.360000e+02    9.360000e+02

EXIT: Optimal solution found.

Final Statistics for MIP
------------------------
Final objective value               =   9.36000000000000e+02
Final integrality gap (abs / rel)   =  0.00e+00 /   0.00e+00 ( 0.00%)
# of nodes processed                =        1
# of subproblems solved             =        2
Total program time (secs)           =       0.00829 (     0.007 CPU time)
Time spent in evaluations (secs)    =       0.00018

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

Knitro 10.0.0: Locally optimal or satisfactory solution.
objective 936; integrality gap 0
1 nodes; 2 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 knitromatlab_mip, rather than knitromatlab. The function signature is very similar to knitromatlab, but three additional argument arrays are used. The most elaborate form is:

[x,fval,exitflag,output,lambda,grad,hessian] =
        knitromatlab_mip(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,...
            xType,objFnType,cineqFnType,extendedFeatures,options,KnitroOptions)

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.

The scalar objFnType sets the objective function type. Uncertain, convex, and nonconvex are set with 0, 1, and 2, respectively. Passing an empty array, [], is equivalent to passing zero.

The array cineqFnType sets the inequality constraint function types and its length must be the same as the number of inequality constraints. Linear constraints are known to be convex, and nonlinear equality constraints are known to be nonconvex, so they are not included in the array. Uncertain, convex, and nonconvex inequality constraints are set with 0, 1, and 2, respectively. Passing an empty array, [], is equivalent to passing an array of all zeros.

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

xType = [2;2;2];
objFnType = 1;
cineqFnType = 1;

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

C example

A MIP problem is defined and solved via the callable library interface using the API functions KTR_mip_init_problem() and KTR_mip_solve().

The signature of KTR_mip_init_problem() is the following.

int  KNITRO_API KTR_mip_init_problem (
        KTR_context_ptr kc,
        const int             n,
        const int             objGoal,
        const int             objType,
        const int             objFnType,
        const int    * const  xType,
        const double * const  xLoBnds,
        const double * const  xUpBnds,
        const int             m,
        const int    * const  cType,
        const int    * const  cFnType,
        const double * const  cLoBnds,
        const double * const  cUpBnds,
        const int             nnzJ,
        const int    * const  jacIndexVars,
        const int    * const  jacIndexCons,
        const int             nnzH,
        const int    * const  hessIndexRows,
        const int    * const  hessIndexCols,
        const double * const  xInitial,
        const double * const  lambdaInitial);

The only differences with KTR_init_problem() are

const int             objFnType,
const int    * const  xType,
...
const int    * const  cFnType,

where objFnType sets the objective function type (convex, nonconvex or uncertain), xType sets the variable type (binary, integer or continuous) and cFnType sets the constraint function type (same choices as for the objective function).

The signature of KTR_mip_solve() is exactly the same as for KTR_solve().

In order to turn our C toy example into a MINLP problem, it thus suffices to replace the call to KTR_init_problem() with

/* in the declarations */
int objFnType = KTR_FNTYPE_NONCONVEX;
int *xType;
int *cFnType;

/* allocate and fill in the arrays */
xType = (int *) malloc (n * sizeof(int));
cFnType = (int *) malloc (m * sizeof(int));
xType[0] = KTR_VARTYPE_INTEGER;
xType[1] = KTR_VARTYPE_INTEGER;
xType[2] = KTR_VARTYPE_INTEGER;
cFnType[0] = KTR_FNTYPE_CONVEX;
cFnType[1] = KTR_FNTYPE_NONCONVEX;

/* call to KTR_mip_init_problem */
nStatus = KTR_mip_init_problem (
        kc, n, objGoal, objType,
        objFnType, xType,
        xLoBnds, xUpBnds,
        m, cType, cFnType, cLoBnds, cUpBnds,
        nnzJ, jacIndexVars, jacIndexCons,
        nnzH, NULL, NULL, xInitial, NULL);

/* free memory */
free(xType);
free(cFnType);

and the call to KTR_solve() by a call to KTR_mip_solve() with the same arguments. 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 ProblemExample class has to be extended with new definitions.

In the function setObjectiveProperties(), the function KTRProblem::setObjFnType(int fnType) is used to define the objective function type:

setObjFnType(KNITRO::KTREnums::FunctionType::Convex);

In the function setConstraintProperties(), the constraint function types are defined with the function KTRProblem::setConFnTypes(int id, int fnType):

setConFnTypes(0, KNITRO::KTREnums::FunctionType::Convex);
setConFnTypes(1, KNITRO::KTREnums::FunctionType::Nonconvex);

In the function setVariableProperties(), the variable types are defined with the function KTRProblem::setVarFntypes(int fnTypes):

setVarFnTypes(KNITRO::KTREnums::VariableType::Integer);

Without specifying a variable index, the function sets variable types for all variables to integer.

This example uses the KTRProblem class to simplify implementing KTRIProblem. If using KTRIProblem only, the functions KTRIProblem::getObjFnType, KTRIProblem::getConFnType, and KTRIProblem::getVarFnType should be implemented to return the appropriate values.

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_branchrule MIP branching rule
mip_debug MIP debugging level (0=none, 1=all)
mip_gub_branch Branch on GUBs (0=no, 1=yes)
mip_heuristic MIP heuristic search
mip_heuristic_maxit MIP heuristic iteration limit
mip_heuristic_terminate MIP heuristic termination condition
mip_implications Add logical implications (0=no, 1=yes)
mip_integer_tol Threshold for deciding integrality
mip_integral_gap_abs Absolute integrality gap stop tolerance
mip_integral_gap_rel Relative integrality gap stop tolerance
mip_intvar_strategy Treatment of integer variables
mip_knapsack Add knapsack cuts (0=no, 1=ineqs, 2=ineqs+eqs)
mip_lpalg LP subproblem algorithm
mip_maxnodes Maximum nodes explored
mip_maxsolves Maximum subproblem solves
mip_maxtime_cpu Maximum CPU time in seconds for MIP
mip_maxtime_real Maximum real in seconds time for MIP
mip_method MIP method (0=auto, 1=BB, 2=HQG, 3=MISQP)
mip_nodealg Standard node relaxation algorithm
mip_outinterval MIP output interval
mip_outlevel MIP output level
mip_outsub Enable MIP subproblem output
mip_pseudoinit Pseudo-cost initialization
mip_relaxable Are integer variables relaxable?
mip_rootalg Root node relaxation algorithm
mip_rounding MIP rounding rule
mip_selectrule MIP node selection rule
mip_strong_candlim Strong branching candidate limit
mip_strong_level Strong branching tree level limit
mip_strong_maxit Strong branching iteration limit
mip_terminate Termination condition for MIP

Algorithms/Methods

The default MINLP method in Knitro is a standard implementation of branch-and-bound 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 integrality 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 in nonconvex. In addition, the integrality gap meaure 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 Quesada-Grossman (HQG) method in Knitro is a variant of branch-and-bound for MINLP. It maintains one branch-and-bound 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 branch-and-bound 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 black-box 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 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. However, since this algorithm runs similarly to the continuous SQP algorithm, you can apply the parallel multi-start 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 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 function shown below.

int KTR_mip_set_branching_priorities (      KTR_context_ptr kc,
                                      const int * const     xPriorities);

The array xPriorities has length “n”, where n is the number of variables. 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 KTR_mip_init_problem() and before calling KTR_mip_solve().

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 KTRSolver::mipSetBranchingPriorities(const std::vector<int>& xPriorities);

The std::vector<int> xPriorities has length “n”, where n is the number of variables. Values for continuous variables are ignored. This method must be called after calling the KTRSolver constructor and before calling KTRSolver::solve().

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

int  KNITRO_API KTR_mip_set_intvar_strategy
    (      KTR_context_ptr kc,
     const int             xIndex,
     const int             xStrategy);

Here xIndex specifies the index of the integer variable you want to apply the special treatment to, and xStrategy 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 branch-and-bound tree. This callback function is set by calling the following function:

int  KNITRO_API KTR_set_mip_node_callback (KTR_context_ptr       kc,
                                           KTR_callback * const  fnPtr);

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

Determining convexity

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 for the mixed integer programming API allows for the user to specify whether or not the problem functions (objective and constraints) are convex or not. If unknown, they can be marked as such.

A function f is convex if for any two points x and y, we have

f(\alpha x + (1-\alpha)y) \le \alpha f(x)+(1-\alpha)f(y), \;
  \mbox{for all} \; \alpha \in [0, 1].

In identifying the objective or constraints as convex, we are assuming a problem form where the objective is being minimized and the constraints are all formulated as “less than or equal to” constraints. If we are maximizing or looking at “greater than or equal to” constraints, then the objective or constraint should be labeled as convex if its negation is convex.

More specifically, the objective function f(x) should be marked as convex if when minimizing f(x) satisfies the above convexity condition, or if when maximizing -f(x) satisfies it. A constraint c_i(x) should be labeled as convex if:

  • c^L is infinite, c^U is finite and c_i(x) satisfies the convexity condition; or
  • c^L is finite, c^U is infinite and -c_i(x) satisfies the convexity condition; or
  • c_i(x) is linear.

All linear functions are convex. Any nonlinear equality constraint is nonconvex.

The MIP solvers in Knitro are designed for convex problems (problems where the objective and all the constraints are convex). If one or more functions are nonconvex, these solvers are only heuristics and may terminate at non-optimal 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 MATLAB, C, C++, Java, C#, Python and R interfaces are provided with the distribution in the knitromatlab and examples directories.