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.
Vector containing the coefficients of the linear objective function.
Matrix containing the coefficients of the linear inequality constraints A·x≤ b.
Vector corresponding to the right-hand side of the linear inequality constraints.
Matrix containing the coefficients of the linear equality constraints Aeq·x = beq.
Vector containing the constants of the linear equality constraints.
Initial point for the algorithm.
Options for the algorithm.
|Linear objective function vector f|
|Matrix for linear inequality constraints|
|Vector for linear inequality constraints|
|Matrix for linear equality constraints|
|Vector for linear equality constraints|
|Initial point for x|
|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.
Integer identifying the reason the algorithm terminated. The following lists the values of exitflag and the corresponding reasons the algorithm terminated.
Function converged to a solution x.
Number of iterations exceeded options.MaxIter.
The problem is infeasible.
Number of searched nodes exceeded options.MaxNodes.
Search time exceeded options.MaxTime.
Number of iterations the LP-solver performed at a node to solve the LP-relaxation problem exceeded options.MaxRLP.
Structure containing information about the optimization. The fields of the structure are
Number of iterations taken
Number of nodes searched
Execution time of the algorithm
Optimization algorithm used
Strategy used to select branch variable—see Options
Strategy used to select next node in search tree—see Options
bintprog-specific 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.
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
Number of nodes that have been set up but not yet explored.
Strategy the algorithm uses to select the branch variable in the search tree—see Branching. The choices are
Display diagnostic information about the function. The choices are 'on' or the default, 'off'.
Level of display:
Maximum number of iterations allowed (a positive integer). The default is 100000*numberOfVariables
Maximum number of solutions, or nodes, the function searches (a positive integer). The default is 1000*numberOfVariables
Maximum number of iterations the LP-solver performs to solve the LP-relaxation problem at each node (a positive integer). The default is 100*numberOfVariables
Maximum amount of CPU time in seconds the function runs (a positive scalar). The default is 7200.
Node display interval (a positive integer). Gives the number of nodes to search between reporting to the iterative display. The default is 20.
Strategy the algorithm uses to select the next node to search in the search tree—see Branching. The choices are:
Termination tolerance on the function value (a positive scalar). The default is 1.0e-3.
Tolerance within which the value of a variable is considered to be integral (a positive scalar). The default is 1.0e-8.
Termination tolerance on the function value of a linear programming relaxation problem (a positive scalar). The default is 1.0e-6.
To minimize the function
f(x) = –9x1 – 5x2 – 6x3 – 4x4,
subject to the constraints
where x1, x2, x3, and x4 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
intlinprog solves more problems than bintprog, and has better performance. To update your existing bintprog code to use intlinprog, make the following changes:
Set intcon to 1:numVars, where numVars is the number of variables in your problem.
Set lb to zeros(numVars,1).
Set ub to ones(numVars,1).
Update any relevant options. Use optimoptions to create options for intlinprog.
Change your call to bintprog as follows:
[x,fval,exitflag,output] = bintprog(f,A,b,Aeq,Beq,x0,options) % Change your call to: [x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,Beq,lb,ub,options)
bintprog uses a linear programming (LP)-based branch-and-bound algorithm to solve binary integer programming problems. The algorithm searches for an optimal solution to the binary integer programming problem by solving a series of LP-relaxation problems, in which the binary integer requirement on the variables is replaced by the weaker constraint 0 ≤ x ≤ 1. The algorithm
Searches for a binary integer feasible solution
Updates the best binary integer feasible point found so far as the search tree grows
Verifies that no better integer feasible solution is possible by solving a series of linear programming problems
For more information, see bintprog Algorithm
 Wolsey, Laurence A., Integer Programming, John Wiley & Sons, 1998.
 Nemhauser, George L. and Laurence A. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, 1988.
 Hillier, Frederick S. and Lieberman Gerald J., Introduction to Operations Research, McGraw-Hill, 2001.