Accelerating the pace of engineering and science

# Documentation Center

• Trial Software

# bintprog

Solve binary integer programming problems

## Equation

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.

## Syntax

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(...)

## Description

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.

## Input 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 right-hand 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

## Output Arguments

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 LP-solver performed at a node to solve the LP-relaxation 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 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. 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 b is the objective function value of the best integer point.a is the best lower bound on the objective function value. Unexplored nodes Number of nodes that have been set up but not yet explored.

## Options

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'mininfeas' — Choose the variable with the minimum integer infeasibility (the variable whose value is closest to 0 or 1, but not equal to 0 or 1).'maxinfeas' — Choose the variable with the maximum integer infeasibility (the variable whose value is closest to 0.5 (default)). Diagnostics Display diagnostic information about the function. The choices are 'on' or the default, 'off'. Display Level of display:'off' or 'none' displays no output.'iter' displays output at each iteration, and gives the default exit message.'iter-detailed' displays output at each iteration, and gives the technical exit message.'final' (default) displays just the final output, and gives the default exit message.'final-detailed' displays just the final output, and gives the technical exit message. 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 LP-solver performs to solve the LP-relaxation 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:'df' — Depth-first search strategy. At each node in the search tree, if there is a child node one level down in the tree that has not already been explored, the algorithm chooses one such child to search. Otherwise, the algorithm moves to the node one level up in the tree and chooses a child node one level down from that node. 'bn' — Best-node search strategy, which chooses the node with lowest bound on the objective function (the default). TolFun Termination tolerance on the function value (a positive scalar). The default is 1.0e-3. TolXInteger Tolerance within which the value of a variable is considered to be integral (a positive scalar). The default is 1.0e-8. TolRLPFun Termination tolerance on the function value of a linear programming relaxation problem (a positive scalar). The default is 1.0e-6.

## Examples

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```

expand all

### Tips

• 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)
[x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,Beq,lb,ub,options)```

### Algorithms

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