Documentation Center 
Solve binary integer programming problems
Solves binary integer programming problems of the form
f, b, and beq are vectors, A and Aeq are matrices, and the solution x is required to be a binary integer vector—that is, its entries can only take on the values 0 or 1.
x = bintprog(f)
x = bintprog(f,A,b)
x = bintprog(f,A,b,Aeq,beq)
x = bintprog(f,A,b,Aeq,beq,x0)
x = bintprog(f,A,b,Aeq,Beq,x0,options)
x = bintprog(problem)
[x,fval] = bintprog(...)
[x,fval,exitflag] = bintprog(...)
[x,fval,exitflag,output] = bintprog(...)
x = bintprog(f) solves the binary integer programming problem
x = bintprog(f,A,b) solves the binary integer programming problem
x = bintprog(f,A,b,Aeq,beq) solves the preceding problem with the additional equality constraint.
Aeq·x = beq.
x = bintprog(f,A,b,Aeq,beq,x0) sets the starting point for the algorithm to x0. If x0 is not in the feasible region, bintprog uses the default initial point.
x = bintprog(f,A,b,Aeq,Beq,x0,options) minimizes with the default optimization options replaced by values in options, which you can create using the function optimoptions.
x = bintprog(problem) finds the minimum for problem, where problem is a structure described in Input Arguments.
Create the problem structure by exporting a problem from Optimization app, as described in Exporting Your Work.
[x,fval] = bintprog(...) returns fval, the value of the objective function at x.
[x,fval,exitflag] = bintprog(...) returns exitflag that describes the exit condition of bintprog. See Output Arguments.
[x,fval,exitflag,output] = bintprog(...) returns a structure output that contains information about the optimization. See Output Arguments.
The following table lists the input arguments for bintprog. Function Arguments contains general descriptions of input arguments for optimization functions.
f  Vector containing the coefficients of the linear objective function.  
A  Matrix containing the coefficients of the linear inequality constraints A·x≤ b.  
b  Vector corresponding to the righthand side of the linear inequality constraints.  
Aeq  Matrix containing the coefficients of the linear equality constraints Aeq·x = beq.  
beq  Vector containing the constants of the linear equality constraints.  
x0  Initial point for the algorithm.  
options  Options for the algorithm.  
problem  f  Linear objective function vector f 
Aineq  Matrix for linear inequality constraints  
bineq  Vector for linear inequality constraints  
Aeq  Matrix for linear equality constraints  
beq  Vector for linear equality constraints  
x0  Initial point for x  
solver  'bintprog'  
options  Options created with optimoptions 
Function Arguments contains general descriptions of arguments returned by bintprog. This section provides specific details for the arguments exitflag, output, and iterative display.
exitflag  Integer identifying the reason the algorithm terminated. The following lists the values of exitflag and the corresponding reasons the algorithm terminated.  
1  Function converged to a solution x.  
0  Number of iterations exceeded options.MaxIter.  
2  The problem is infeasible.  
4  Number of searched nodes exceeded options.MaxNodes.  
5  Search time exceeded options.MaxTime.  
6  Number of iterations the LPsolver performed at a node to solve the LPrelaxation problem exceeded options.MaxRLP.  
output  Structure containing information about the optimization. The fields of the structure are  
iterations  Number of iterations taken  
nodes  Number of nodes searched  
time  Execution time of the algorithm  
algorithm  Optimization algorithm used  
branchStrategy  Strategy used to select branch variable—see Options  
nodeSearchStrategy  Strategy used to select next node in search tree—see Options  
message  Exit message  
Iterative display  bintprogspecific iterative display:  
Best lower bound on obj  Objective function value of LP relaxation problem that gives the best current lower bound on the final objective function value.  
Explored nodes  Cumulative number of explored nodes.  
Obj of best integer point  Objective function value of the best integer point found so far. This is an upper bound for the final objective function value.  
Obj of LP relaxation  Objective function value of the linear programming (LP) relaxation problem.  
Relative gap between bounds 
where
 
Unexplored nodes  Number of nodes that have been set up but not yet explored. 
Optimization options used by bintprog. Use optimoptions to set or change options. See Optimization Options Reference for detailed information.
BranchStrategy  Strategy the algorithm uses to select the branch variable in the search tree—see Branching. The choices are

Diagnostics  Display diagnostic information about the function. The choices are 'on' or the default, 'off'. 
Display  Level of display:

MaxIter  Maximum number of iterations allowed (a positive integer). The default is 100000*numberOfVariables 
MaxNodes  Maximum number of solutions, or nodes, the function searches (a positive integer). The default is 1000*numberOfVariables 
MaxRLPIter  Maximum number of iterations the LPsolver performs to solve the LPrelaxation problem at each node (a positive integer). The default is 100*numberOfVariables 
MaxTime  Maximum amount of CPU time in seconds the function runs (a positive scalar). The default is 7200. 
NodeDisplayInterval  Node display interval (a positive integer). Gives the number of nodes to search between reporting to the iterative display. The default is 20. 
NodeSearchStrategy  Strategy the algorithm uses to select the next node to search in the search tree—see Branching. The choices are:

TolFun  Termination tolerance on the function value (a positive scalar). The default is 1.0e3. 
TolXInteger  Tolerance within which the value of a variable is considered to be integral (a positive scalar). The default is 1.0e8. 
TolRLPFun  Termination tolerance on the function value of a linear programming relaxation problem (a positive scalar). The default is 1.0e6. 
To minimize the function
f(x) = –9x_{1} – 5x_{2} – 6x_{3} – 4x_{4},
subject to the constraints
where x_{1}, x_{2}, x_{3}, and x_{4} are binary integers, enter the following commands:
f = [9; 5; 6; 4]; A = [6 3 5 2; 0 0 1 1; 1 0 1 0; 0 1 0 1]; b = [9; 1; 0; 0]; x = bintprog(f,A,b) Optimization terminated. x = 1 1 0 0
[1] Wolsey, Laurence A., Integer Programming, John Wiley & Sons, 1998.
[2] Nemhauser, George L. and Laurence A. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, 1988.
[3] Hillier, Frederick S. and Lieberman Gerald J., Introduction to Operations Research, McGrawHill, 2001.